版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、第一章1. 怎樣理解“算法+數(shù)據(jù)結(jié)構(gòu)=程序”這個(gè)公式?舉例說明。算法是語句序列解決特定問題的固有程序片段。數(shù)據(jù)結(jié)構(gòu)是確定數(shù)據(jù)間的關(guān)系。從具 體問題抽象出一個(gè)合適的數(shù)學(xué)模型、然后設(shè)計(jì)一個(gè)解決此數(shù)學(xué)模型的算法,最后編寫出程 序。尋求數(shù)學(xué)模型的是指就是數(shù)據(jù)結(jié)構(gòu)要完成的工作。參看書p1前兩段的描述。2. 數(shù)據(jù)結(jié)構(gòu)的概念,它包含哪三方面的內(nèi)容?數(shù)據(jù)結(jié)構(gòu):是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間 餓關(guān)系和操作的學(xué)科。參看書p3包含三方面的內(nèi)容:1、數(shù)據(jù)之間的邏輯關(guān)系 2、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式3、在數(shù)據(jù)上定義的運(yùn)算的集合。3. 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)的基本概念。舉例說明數(shù)據(jù)元素和
2、數(shù)據(jù)項(xiàng)的聯(lián)系與區(qū)別。數(shù)據(jù):描述客觀事物的數(shù)字、字符以及所有能直接輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處 理的符號(hào)的集合。數(shù)據(jù)元素:數(shù)據(jù)的基本單位,在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮或處理。數(shù)據(jù)項(xiàng):數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位,是數(shù)據(jù)元的一個(gè)具體值,是數(shù) 據(jù)記錄中最基本的、不可分的有名數(shù)據(jù)單位。例 1 : class Aint c123;int i;;class BA a;B b ;b.a是數(shù)據(jù)項(xiàng),B是數(shù)據(jù)元素例2: 本書的數(shù)目信息為一個(gè)數(shù)據(jù)元素,而數(shù)目信息中每一項(xiàng)(如書名、作者名等)為一 個(gè)數(shù)據(jù)項(xiàng)4. 從邏輯結(jié)構(gòu)來看,數(shù)據(jù)結(jié)構(gòu)有哪四種基本結(jié)構(gòu),各自的特點(diǎn)是什么?1、集合(數(shù)據(jù)元素之間同屬于一
3、個(gè)集合,再無其他關(guān)系)2、線性結(jié)構(gòu)(數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系)3、樹形結(jié)構(gòu)(數(shù)據(jù)元素之間一對(duì)多的關(guān)系)4、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)(數(shù)據(jù)元素之間多對(duì)多的關(guān)系)5. 從物理結(jié)構(gòu)來看,數(shù)據(jù)結(jié)構(gòu)有哪兩種基本結(jié)構(gòu),各自的特點(diǎn)是什么?1、順序存儲(chǔ)結(jié)構(gòu)特點(diǎn):借助元素在存儲(chǔ)器中的相應(yīng)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特定:借助元素在存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。6. 算法的5個(gè)特征,4個(gè)評(píng)價(jià)標(biāo)準(zhǔn)是什么? 特征:有窮性、確定性、可行性、輸入、輸出。評(píng)價(jià)標(biāo)準(zhǔn):正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求。7. 描述時(shí)間復(fù)雜度。(1)x=0; y=0; z=0;for (i=1; i<
4、;=n; i+) x+;for( j=1; jv=n; j+) y+;for( k=0; k<=(2*n); k+ )z+;程序片段中語句x=0、x+、y+、z+的時(shí)間復(fù)雜度和整段程序的時(shí)間復(fù)雜度。0(1)0(n)0(22)0(23)0(23)第二章線性表1. 描述線性結(jié)構(gòu)的特點(diǎn)。2. 判斷對(duì)錯(cuò),并解釋說明。線性表中的數(shù)據(jù)元素可以是各種各樣的,但同一線性表中的元素一定具有相同(1) 特性。線性表采用順序存儲(chǔ)表示時(shí),必須占用一片連續(xù)的存儲(chǔ)單元。線性表采用鏈?zhǔn)酱鎯?chǔ)表示時(shí),不能占用一片連續(xù)的存儲(chǔ)單元。101,每個(gè)元素的長(zhǎng)度為3,計(jì)算出第6個(gè)元(2)(3)3. 順序表的第一個(gè)元素的存儲(chǔ)地址是 素
5、的存儲(chǔ)地址是多少?L0C ( a6) =LOC(a1)+5*L=101+5*3=1164. 長(zhǎng)度為n的順序表中,在第i個(gè)元素前插入一個(gè)新元素時(shí),需要移動(dòng)多少個(gè)元素? 插入算法的平均移動(dòng)次數(shù)是多少,時(shí)間復(fù)雜度是什么?參看書P2425,需要移動(dòng)n-i+1個(gè)兀素,平均移動(dòng)次數(shù)為 n/2,時(shí)間復(fù)雜度是0(n)5. 長(zhǎng)度為n的順序表中,將第i個(gè)元素刪除時(shí),需要移動(dòng)多少個(gè)元素?刪除算法的 平均移動(dòng)次數(shù)是多少,時(shí)間復(fù)雜度是什么?參看書P2425,需要移動(dòng)n-i個(gè)元素,平均移動(dòng)次數(shù)為(n-1)/2 ,時(shí)間復(fù)雜度是0(n)6. 線性鏈表的存儲(chǔ)特點(diǎn)是?單鏈表中的結(jié)點(diǎn)由哪兩部分構(gòu)成,畫圖說明。7. 在一個(gè)單鏈表中,
6、q所指結(jié)點(diǎn)是P所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn),若在q與P之間插入一個(gè)s所指的結(jié)點(diǎn),寫出執(zhí)行的兩條語句(提示:先鏈接、后斷開)。s->next=p; q->next=s;或者 s->next=q->next; q->next=s;8. 在單鏈表中,w所指結(jié)點(diǎn)是s所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)刪除s結(jié)點(diǎn),寫出執(zhí)行的兩條語句。w->n ext=s->n ext;free(s)9. 畫圖說明單循環(huán)鏈表為空的狀態(tài),并寫出循環(huán)鏈表判斷是否為空的語句。參看書P35圖2.12 ( b) 判空語句 H->next=H10. 雙向鏈表中,要在指針 q指向的結(jié)點(diǎn)后插入新結(jié)點(diǎn)t,寫出執(zhí)
7、行的四條語句。t->p rior=q ; t->n ext=q->n ext ; q->n ext=t ; t->n ext->p rior=s11. 雙向鏈表中,要?jiǎng)h除指針q的后繼結(jié)點(diǎn),寫出執(zhí)行的兩條語句。T=q->next ; q->next=t->next ; free(t);或者 t=q->next;q->next-q->next->next;free(t)第三章棧和隊(duì)列1. 判斷對(duì)錯(cuò)(1)棧和隊(duì)列是操作受限的線性表。(2)棧的插入操作只需要在表尾端進(jìn)行,隊(duì)列的插入操作只需要在表頭進(jìn)行。FRONT相關(guān)。(3)
8、棧的操作只和棧頂指針 TOP相關(guān),隊(duì)列的操作只和隊(duì)頭指針2. 棧的特點(diǎn)是?隊(duì)列的特點(diǎn)是?(先進(jìn)先出、先進(jìn)后出中選擇) 棧的特點(diǎn)是先進(jìn)后出(FILO)隊(duì)列的特點(diǎn)是先進(jìn)先出(FIFO)3. 用文字描述算法。(參照我寫的(1)的算法描述完成)(1)順序存儲(chǔ)的棧插入操作 算法描述:(2)順序棧的刪除操作 算法描述:第一步,判斷棧是否為空,如果棧空,不能進(jìn)行刪除操作;第二步,棧不空的時(shí)候,棧頂指針TOP減1,向下移動(dòng)一位;第三步,將要?jiǎng)h除的棧頂元素用新變量保存;(3)鏈?zhǔn)酱鎯?chǔ)的隊(duì)列的插入操作 算法描述:第一步,禾U用指針創(chuàng)建新結(jié)點(diǎn),新節(jié)點(diǎn)的數(shù)據(jù)域值為要入隊(duì)列的元素,新結(jié)點(diǎn)的指 針域復(fù)制為NULL ;第二
9、步,將鏈隊(duì)列的尾節(jié)點(diǎn)鏈接上新結(jié)點(diǎn);第三步,修改鏈隊(duì)列的尾指針的指向,讓它指向新結(jié)點(diǎn);(4)鏈棧的刪除操作 算法描述:第一步,禾U用指針創(chuàng)建新結(jié)點(diǎn),新節(jié)點(diǎn)的數(shù)據(jù)域值為要入棧的元素,新結(jié)點(diǎn)的指針 域復(fù)制為NULL ;第二步,新結(jié)點(diǎn)的指針域指向鏈棧的頭結(jié)點(diǎn);第三步,修改鏈棧的頭指針TOP的指向,讓它指向新結(jié)點(diǎn);4.假設(shè)棧為S,寫出判斷語句typ edef struct sqstackint datamax;int top;sqstack ;s->t op= =0 s->t op = =maxsqstack *s ;(1)順序棧為空的條件判斷語句(2)順序棧為滿的條件判斷語句5. 假設(shè)隊(duì)列
10、為Q,寫出判斷語句typ edef struct SqQueueint dataMAX;int front;Front和隊(duì)尾指針 Rear*/Q->rear= =Q->fro nt(Q->rea r+1)%MAX= =Q->fro ntint rear; /*定義隊(duì)頭指針;SqQueue *Q(1) 循環(huán)隊(duì)列為空的條件判斷語句(2) 循環(huán)隊(duì)列為滿的條件判斷語句6. 總結(jié)說明,線性表的順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的區(qū)別? 參看書P27第一段第六章樹和二叉樹1. 一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g),它含有雙親結(jié)點(diǎn)(4)個(gè),單分支結(jié)點(diǎn)(2)個(gè),葉子結(jié)點(diǎn)(3)個(gè)。e
11、只有左孩子f,二叉樹根為a; a有左孩子b,右孩子e; b有左孩子c,右孩子d; f只有右孩子g2. 判斷對(duì)錯(cuò)K' , K''的長(zhǎng)度(1) 在樹中,如果從結(jié)點(diǎn) K出發(fā),存在兩條分別到達(dá) 相等的路徑,則結(jié)點(diǎn) K' , K''互為兄弟。,還可能是堂兄結(jié)點(diǎn), 由完全二(2) 完全二叉樹的某結(jié)點(diǎn)若無左孩子,則必是葉結(jié)點(diǎn)。叉樹的性質(zhì)決定(3) 一棵完全二叉樹按層次遍歷的序列為ABCDEFGH I,則在 后序遍歷中結(jié)點(diǎn)B的直接后繼是F。由于是完全二叉樹,所以樹中第一層是A,第二層從左向右是 B和C,第三層是D、E、F、G,第四層從左向右是 H和I。畫出二叉樹
12、,進(jìn)行后序遍歷,后序遍歷序列 為 HIDEBFGCA。二叉樹的后序遍歷序列中,任意一個(gè)結(jié)點(diǎn)均處在其子樹結(jié)點(diǎn)的后(4)面。后序遍歷算法決定的,左、右、根(5)由二叉樹結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵二叉樹。(6)結(jié)構(gòu)。(7)個(gè)結(jié)點(diǎn)都有不唯一,因?yàn)橹挥性谥行虮闅v中才能劃分左右子樹樹存儲(chǔ)時(shí)采用雙親表示法時(shí),求某個(gè)結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)一棵有n ( n1)個(gè)結(jié)點(diǎn)的d叉樹,右用多重鏈表表示,樹中每 d個(gè)鏈域,則在樹的nd個(gè)鏈域中,有n ( d-1) +1個(gè)是空鏈域,只有n-1個(gè)是非空鏈域。根據(jù)樹的特性:一對(duì)多,每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)雙親結(jié)點(diǎn),除了根結(jié)點(diǎn)外。因此,n個(gè)結(jié)點(diǎn)的樹中有n-1個(gè)結(jié)點(diǎn)都
13、有且僅有一個(gè)雙親,這個(gè)關(guān)系表示在鏈?zhǔn)酱鎯?chǔ)里就一定 會(huì)占用它雙親的一個(gè)指針域,所以樹中一定有n-1個(gè)非空指針域,多叉樹也適用。(8)在一棵二叉樹的二叉鏈表中,空指針域數(shù)等于非空指針域數(shù)加2。解:二叉鏈表中有n個(gè)結(jié)點(diǎn)時(shí),一定存在2n個(gè)指針域,n+1個(gè)空鏈域,則非空鏈域?yàn)閚-1個(gè),所以,空鏈域=非空鏈域+2(9)樹的后根遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的中序遍歷。P138筆記(10)樹利用孩子兄弟表示法轉(zhuǎn)換后的二叉樹中根結(jié)點(diǎn)一定不存在右子樹。 看書P137頁最后一句話,參看書,參3. 二叉樹根結(jié)點(diǎn)的層次為1,所有含有(4 )°要想得出最小高度,必須是完全二叉樹才能保證, 結(jié)點(diǎn)的完全二叉樹的高
14、度是?參看二叉樹性質(zhì)4. 設(shè)一棵二叉樹結(jié)點(diǎn)的先根序列為則二叉樹中葉子結(jié)點(diǎn)是(E F H )。參看書P154例題5. 樹的存儲(chǔ)結(jié)構(gòu)有幾種?分別是?二叉樹的存儲(chǔ)結(jié)構(gòu)有幾種,分別是? 樹的存儲(chǔ)結(jié)構(gòu)有三種:雙親表示法、孩子表示法、孩子兄弟表示法二叉樹的存儲(chǔ)結(jié)構(gòu)有兩:順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)(又叫二叉鏈表的表示法) 在一棵二叉樹的二叉鏈表中,空指針域數(shù)等于非空指針域數(shù)加(2)06. 若二叉樹有7個(gè)度為2的結(jié)點(diǎn),試問有?個(gè)終端結(jié)點(diǎn)。由二叉樹的性質(zhì)3得出,n0=n2+1,所以度為1的終端結(jié)點(diǎn)有7+1=8個(gè)7. 一棵有124個(gè)葉結(jié)點(diǎn)的完全二叉樹,最多有?個(gè)結(jié)點(diǎn)。首先,由二叉樹的性質(zhì) 3得出,度為2的結(jié)點(diǎn)個(gè)數(shù)為124
15、-1=123個(gè); 又根據(jù)二叉樹的定義可以得出這樣的結(jié)論:完全二叉樹的前n-1層8. 一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn),其中葉子結(jié)點(diǎn)的個(gè)數(shù)是?500解:設(shè)分支總數(shù)變量為b,則n=b+1 ,得出分支數(shù)為1000°分支數(shù)是偶數(shù),所以不 存在度為1的結(jié)點(diǎn),只有度為2的結(jié)點(diǎn)和葉子結(jié)點(diǎn)。根據(jù)性質(zhì)3, n0=n2+1,所以1001 =n0+n2= 2*n0+1 o n0=500。9. w=4,5,6,7,8,如何構(gòu)建哈夫曼樹?第9章查找查找表的概念?這是四種經(jīng)典數(shù)據(jù)結(jié)構(gòu)中的哪一種?靜態(tài)查找和動(dòng)態(tài)查找有什么聯(lián)系和區(qū)別?查找表中的關(guān)鍵字是數(shù)據(jù)元素還是數(shù)據(jù)項(xiàng),有什么特點(diǎn)?ASL表示什么?寫出計(jì)算的公式,
16、并解釋公式中每個(gè)變量的含義。描述順序查找的算法思想(用漢字描述,不是代碼) 描述折半查找的算法思想。給定由以下元素組成的關(guān)鍵字序列(55, 46, 89, 13, 24, 67, 23, 15),將他15個(gè)結(jié)點(diǎn)的二叉樹中,最小高度是因此這個(gè)題目考核的是有 即可得出15個(gè)4,ABDECFGH ,中根序列為 DEBAFCHG ,1.2.3.4.5.6.7.們存儲(chǔ)在數(shù)組的第1位至第8位,現(xiàn)在要查找關(guān)鍵字為15和100的元素。描述查找過程。8. 畫出包含8個(gè)元素的查找表對(duì)應(yīng)的折半判定樹。樹的深度為?9. 根據(jù)給定的序列(21,54,43,76,87,65,32),生成一棵二叉排序樹,并分析該二叉排序 樹的平均查找長(zhǎng)度 ASL;同時(shí)根據(jù)該序列,生成一棵平衡二叉樹 ,并分析該平衡二叉樹 的平均查找長(zhǎng)度ASL 0第10章排序1.比較分析9種排序方法的時(shí)間復(fù)雜度和穩(wěn)定性。排序方法平均時(shí)間最壞情況輔助空間穩(wěn)定性
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度美容美發(fā)服務(wù)個(gè)人代理合同4篇
- 二零二五年度企業(yè)債權(quán)轉(zhuǎn)讓與債務(wù)轉(zhuǎn)移合同
- 2025年度大型建筑鋼材項(xiàng)目集中采購合同
- 2024年銷售人員業(yè)績(jī)合同2篇
- 2025年度個(gè)人二手房買賣協(xié)議書范本:二手房交易法律咨詢合同
- 2025年度內(nèi)部員工股權(quán)激勵(lì)計(jì)劃變更與股權(quán)轉(zhuǎn)讓合同
- 二零二五年度奶粉行業(yè)市場(chǎng)分析報(bào)告定制合同
- 二零二五年度培訓(xùn)中心教師教學(xué)資源共享聘用合同
- 2025年度私人旅行規(guī)劃服務(wù)合同2篇
- 2025版抹灰班組安全生產(chǎn)責(zé)任制考核合同4篇
- 基因突變和基因重組(第1課時(shí))高一下學(xué)期生物人教版(2019)必修2
- 內(nèi)科學(xué)(醫(yī)學(xué)高級(jí)):風(fēng)濕性疾病試題及答案(強(qiáng)化練習(xí))
- 音樂劇好看智慧樹知到期末考試答案2024年
- 辦公設(shè)備(電腦、一體機(jī)、投影機(jī)等)采購 投標(biāo)方案(技術(shù)方案)
- 查干淖爾一號(hào)井環(huán)評(píng)
- 案卷評(píng)查培訓(xùn)課件模板
- 2024年江蘇省樣卷五年級(jí)數(shù)學(xué)上冊(cè)期末試卷及答案
- 人教版初中英語七八九全部單詞(打印版)
- 波浪理論要點(diǎn)圖解完美版
- 金融交易數(shù)據(jù)分析與風(fēng)險(xiǎn)評(píng)估項(xiàng)目環(huán)境敏感性分析
- 牛頓環(huán)與劈尖實(shí)驗(yàn)論文
評(píng)論
0/150
提交評(píng)論