數(shù)據(jù)結(jié)構(gòu)復(fù)習題及答案(12級)-資料下載頁
2025-06-22 14:40本頁面
【正文】 ：(1)數(shù)組A的體積(即存儲量)；(2)數(shù)組的最后一個元素A??的起地址；(3)按行優(yōu)先存放時，元素A1,4的起地址；(4)按列優(yōu)先存放時，元素A4,7的起地址。(1)6*8*6=288(2)1000+47*6=1282(3)1000+(8+4)*8=1096(4)1000+(6*7+4)*8=13689. 分別畫出含三個結(jié)點的無序樹與二叉樹的所有不同形態(tài)。答：無序樹形態(tài)如下：二叉樹形態(tài)如下：10. 分別寫出圖1中所示二叉樹的先序遍歷、中序遍歷、后序遍歷的結(jié)點訪問序列。答：先序遍歷序列:ABDEHICFJG 中序遍歷序列:DBHEIAFJCG 后序遍歷序列:DHIEBJFGCA11. 試找出分別滿足下列條件的所有二叉樹。 (1) 先序序列與中序序列相同。 (2) 后序序列與中序序列相同。 (3) 先序序列與后序序列相同。答：(1) 先序序列和中序序列相同：空樹或缺左子樹的單支樹； (2) 后序序列和中序序列相同：空樹或缺右子樹的單支樹； (3) 先序序列和后序序列相同：空樹或只有根結(jié)點的二叉樹。12. 已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，試畫出這棵二叉樹。答：這棵二叉樹為:13. 分別寫出圖2中所示二叉樹的先序遍歷、中序遍歷、后序遍歷的結(jié)點訪問序列。答：先序遍歷序列:ABDGCEHF 中序遍歷序列:DGBAEHCF 后序遍歷序列:GDBHEFCA14. 給定權(quán)值(7,18,3,32,5,26,12,8)，構(gòu)造的哈夫曼樹。答：哈夫曼樹為:15. 假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7,19,2,6,32,3,21,10，試為這8個設(shè)計哈夫曼編碼。答：哈夫曼樹為:在上述哈夫曼樹的每個左分支上標以0，右分支上標以1，并設(shè)這8個字母分別為A、B、C、D、E、F、G和H，則它們的哈夫曼樹為分別為:A：0000 B：10 C：00110 D：0010 E：01 F：00111 G：11 H：000116. 畫出無向圖G1的鄰接矩陣和鄰接表示意圖，并寫出每個頂點的度。答：（1）鄰接矩陣:（2）鄰接鏈表：（3）每個頂點的度：頂點 度 V1 3 V2 3 V3 2 V4 3 V5 3 17. 畫出有向圖G2的鄰接矩陣、鄰接表和逆鄰接表示意圖，并寫出每個頂點的入度和出度。答：（1）鄰接鏈表：（2）逆鄰接鏈表：（3） 頂點 入度 出度 V1 3 0 V2 2 2 V3 1 2 V4 1 3 V5 2 1 V6 2 318. 對應(yīng)圖G3，寫出從v1出必的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列各三個。答：深度優(yōu)先查找遍歷序列：V1 V2 V3 V4 V5。 V1 V3 V5 V4 V2。 V1 V4 V3 V5 V2廣度優(yōu)先查找遍歷序列：V1 V2 V3 V4 V5。 V1 V3 V2 V4 V5。 V1 V4 V3 V2 V519. 何謂二叉排序樹?答：一棵二叉排序樹(又稱二叉查找樹)或者是一棵空樹，或者是一棵同時滿足下列條件的二叉樹： (1)若它的左子樹不空，則左子樹上所有結(jié)點的鍵值均小于它根結(jié)點鍵值。 (2)若它的右子樹不空，則右子樹上所有結(jié)點的鍵值均大于它根結(jié)點鍵值。 (3)它的左、右子樹也分別為二叉排序樹。20. 順序查找時間為O(n)，二分查找時間為O(log2n)，散列查找時間為O(1)，為什么有高效率的查找方法而不放棄低效率的方法?答：衡量算法的標準有很多，時間復(fù)雜度只是其中之一。盡管有些算法時間性能很好，但是其他方面可能就存在著不足。比如散列查找的時間性能很優(yōu)越，但是需要關(guān)注如何合理地構(gòu)造散列函數(shù)問題，而且總存在著沖突等現(xiàn)象，為了解決沖突，還得采用其他方法。 二分查找也是有代價的，因為事先必須對整個查找區(qū)間進行排序，而排序也是費時的，所以常應(yīng)用于頻繁查找的場合。對于順序查找，盡管效率不高，但卻比較簡單，常用于查找范圍較小或偶而進行查找的情況。21. 簡述多重散列法解決沖突的基本思想。答：此法要求設(shè)立多個散列函數(shù)Hi，i=1，…，k。當給定值K與閉散列表中的某個鍵值是相對于某個散列函數(shù)Hi的同義詞因而發(fā)生沖突時，繼續(xù)計算該給定值K在下一個散列函數(shù)Hi+1下的散列地址，直到不再產(chǎn)生沖突為止。22. 簡述公共溢出區(qū)法解決沖突的基本思想。答：散列表由兩個一維數(shù)組組成。一個稱為基本表，另一個稱為溢出表。插入首先在基本表上進行；假如發(fā)生沖突，則將信息存人溢出表。23. 在結(jié)點個數(shù)為n(n1)的各棵樹中，高度最小的樹的高度是多少?它有多少個葉結(jié)點?多少個分支結(jié)點?高度最大的樹的高度是多少?它有多少個葉結(jié)點?多少個分支結(jié)點?答：結(jié)點個數(shù)為n時，高度最小的樹的高度為1，有兩層，它有n1個葉結(jié)點，1個分支結(jié)點；高度最大的樹的高度為nl，有n層，它有1個葉結(jié)點，n1個分支結(jié)點。24. 什么是內(nèi)部排序?什么是排序方法的穩(wěn)定性?答：假定給定含有n個記錄的文件(r1，r2，…，rn)，其相應(yīng)的關(guān)鍵字為(k1，k2，…，kn)，則排序就是確定文件的一個序列r1，r2，…，rn，使得k1≤k2≤…≤kn，從而使得文件中n個記錄按其對應(yīng)關(guān)鍵字有序排列。如果整個排序過程在內(nèi)存中進行，則排序叫內(nèi)部排序。假設(shè)在待排序的文件中存在兩個或兩個以上的記錄具有相同的關(guān)鍵字，若采用某種排序方法后，使得這些具有相同關(guān)鍵字的記錄在排序前后相對次序依然保持不變，則認為該排序方法是穩(wěn)定的，否則就認為排序方法是不穩(wěn)定的。五、分析題。(每小題4分，共8分)1. 分析下面語句段執(zhí)行的時間復(fù)雜度。 (1) for(i＝1；i＝n；i++) for(j＝1；j＝n；j++) s++； (2) for(i＝1；i＝n；i++) for(j＝i；j＝n；j++)s++；(3) for(i＝1；i＝n；i++) for(j＝1；j＝i；j++) s++；(4) i＝1； k＝0；while(i＝n1){k+＝10*i；i++；}(5) for (i＝1；i＝n；i++) for (j＝1；j＝i ；j++) for (k＝1；k＝j(luò)；k++) x=x+1；(1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n1) (5) Ο(n3)2. 寫出下列程序段的運行結(jié)果(棧中的元素類型是char)：main( ){ SeqStack s，*p。；char x，y；p=amp。s。Init_Queue(p)。x= ‘c’； y= ‘k’；push (p，x)； push (p，’a’)；push (p，y)。x=pop (p)。push (p，’t’)。 push (p，x)；x=pop (p)；push (p，’s’)。while (!Empty_SeqStack(p)) { y=pop (p)； printf(“％c”，y)；}printf(“％c＼n”，x)； }答：stack3. 寫出下列程序段的運行結(jié)果(隊列中的元素類型是char)：main( ){ SeQueue a, *q。char x，y；q=amp。a； x=’e’； y=’c’。Init_Queue(q)。In_Queue(q，’h’)。 In_Queue(q, ’r’)。 In_Queue(q, y)。x=Out_Queue (q)；In_Queue(q，x)；x= Out_Queue (q)。In_Queue(q，’a’ )；while (!Empty_SeqStack(q)) { y= Out_Queue(q)； printf(“%c”，y)；}printf(“%C\n”，x)；}答：char
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1