數(shù)據(jù)結(jié)構(gòu)自考題講解

1、14. 下面程序段的時(shí)間復(fù)雜度是 O（mn） 。 for （int i=1;i=n;i+） for （int j=1;jnext=NULL） 。 43在一個(gè)單鏈表中，若刪除 （*p） 結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行 （p-next=p-next-next） 。 49. 若頻繁地對(duì)線性表進(jìn)行插入和刪除操作，該線性表應(yīng)該采用的存儲(chǔ)結(jié)構(gòu)是（鏈?zhǔn)剑?。 53若要在 O（1） 的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對(duì)兩個(gè)循環(huán)鏈表各設(shè)置一個(gè)指針，分 別指向 （ 各自的尾結(jié)點(diǎn) ） 。 77. 若長(zhǎng)度為 n 的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在表的第 i 個(gè)位置插入一個(gè)數(shù)據(jù)元素，需要移動(dòng)表中元素的 個(gè)數(shù)是（ n-i+1

2、 ）。 95. 若要在 O（1）的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對(duì)兩個(gè)循環(huán)鏈表各設(shè)置一個(gè)指針，分 別指向 （ 各自的尾結(jié)點(diǎn) ） 。 102. 將長(zhǎng)度為 m的單鏈表連接在長(zhǎng)度為 n 的單鏈表之后的算法的時(shí)間復(fù)雜度為 （ O（n） ） 。 107. 單鏈表中，增加頭結(jié)點(diǎn)的目的是為了（方便運(yùn)算的實(shí)現(xiàn)） 。 121. 在順序表（ n 足夠大）中進(jìn)行順序查找，其查找不成功的平均長(zhǎng)度是（ n+1 ）。 4. 在 循環(huán) 鏈表中，從任何一結(jié)點(diǎn)出發(fā)都能訪問(wèn)到表中的所有結(jié)點(diǎn)。 44. 每個(gè)結(jié)點(diǎn)只有 一個(gè) 鏈接域的鏈表叫做單鏈表。 333333333333333333333333333333333333

3、33333333333333 11線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問(wèn)：如果有n 個(gè)線性表同時(shí)并存，并且在處理過(guò) 程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化， 線性表的總數(shù)也會(huì)自動(dòng)地改變。 在此情況下， 應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？ 為什么？ 答：選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它可動(dòng)態(tài)申請(qǐng)內(nèi)存空間，不受表長(zhǎng)度（即表中元素個(gè)數(shù)）的影響，插入、刪除時(shí)間 復(fù)雜度為 O（1）。 12試述順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的區(qū)別及各自的優(yōu)缺點(diǎn)。 答：數(shù)組占用連續(xù)的內(nèi)存空間，鏈表不要求結(jié)點(diǎn)的空間連續(xù)。 1）插入與刪除操作： 由于數(shù)組在插入與刪除數(shù)據(jù)時(shí)需移動(dòng)大量的數(shù)據(jù)元素，而鏈表只需要改變一些指 針的鏈接，因此，鏈表比數(shù)組易于實(shí)現(xiàn)數(shù)據(jù)的插入和刪除操作

4、。 2）內(nèi)存空間的占用情況：因鏈表多了一個(gè)指針域，故較浪費(fèi)空間，因此，在空間占用方面，數(shù)組優(yōu)于 鏈表。 3）數(shù)據(jù)的存取操作：訪問(wèn)鏈表中的結(jié)點(diǎn)必須從表頭開始，是順序的存取方式，而數(shù)組元素的訪問(wèn)是通 過(guò)數(shù)組下標(biāo)來(lái)實(shí)現(xiàn)的，是隨機(jī)存取方式，因此，在數(shù)據(jù)存取方面，數(shù)組優(yōu)于鏈表。 數(shù)據(jù)的合并與分離：鏈表優(yōu)于數(shù)組，因?yàn)橹恍枰淖冎羔樀闹赶?44444444444444444444444444444444444444444444444444444444 四 1. 寫出計(jì)算單鏈表 head（ head 為單鏈表的表頭）中數(shù)據(jù)域 data 值為 m的結(jié)點(diǎn)個(gè)數(shù)的算法。 int count （Node *head）

5、1 / 18 / 計(jì)算單鏈表 head 中數(shù)據(jù)域 data 值為 m 的結(jié)點(diǎn)個(gè)數(shù) Node *p=head-next; int n=0; while (p!=NULL) if (p-data=m) n+； p=p-next; return n; / count 2. 已知非空單鏈表 head，試設(shè)計(jì)一個(gè)算法，交換 p 所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)在鏈表中的位置。 解答： int revers(listnode *head, listnode *p) /* 交換 p 所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)在鏈表中的位置 */ if (p-next=NULL) return 0 ; listnode *q=head; wh

6、ile (q-next!=p) q=q-next; r=p-next ； q-next=r; p-next =r-next ; r-next=p; return 1; / revers 3. 線性表用帶頭結(jié)點(diǎn)的單向鏈表示，試寫出刪除表中所有 data 域?yàn)榱愕脑氐乃惴ā?解答： 解： int DeleteItem(Node * head) Node *p=head; / 聲明指針 p，并令其指向鏈表頭結(jié)點(diǎn) while (p-next!=NULL) if(p-nex-data=0) p-next=p-next-next. else p=p-next; / 指針下移 4試設(shè)計(jì)一算法，計(jì)算帶頭結(jié)點(diǎn)

7、的單鏈表head(head 指向表頭 ) 的結(jié)點(diǎn)個(gè)數(shù)。 解答： int Length( ) / 計(jì)算帶表頭結(jié)點(diǎn)的單鏈表 head 的長(zhǎng)度 Node *p=head-next; int count=0; while (p!=NULL) p=p-next; count +; return count; 5 判斷單鏈表 head(head 指向表頭 ) 是否是遞增的。 解答：【編者注： 鏈表無(wú)頭結(jié)點(diǎn)】 int order(Node *head) Node *p=head; while(p-next!=NULL) if(p-datanext-data) p=p-next; else break; if

8、(p-next=NULL) return 1; else return 0; 6. 設(shè)計(jì)一個(gè)算法，在一個(gè)單鏈表 head 中找出值最小的元素。 解答：【編者注： 鏈表無(wú)頭結(jié)點(diǎn)】 2 / 18 int Min(Node * head ) / 在單鏈表 head 中找出值最小的元素 Node *p=head; int min=p-data; while (p-next!=NULL) if(p-next-datanext-data; p=p-next; return min; 7 設(shè)有兩個(gè)單鏈表 L 和 L1, 其結(jié)點(diǎn)結(jié)構(gòu)為 (data,next), 試編寫算法判斷鏈表 L1 中的各元素是否都是單鏈

9、表 L 中的元素。 解答： int SubLnk(Node *L, Node *L1) Node *p1=L1; while(p1!=NULL) Node *p=L; while(p!=NULL) if (p=NULL) return 0; / 【編者注： L1 中元素未在 L 中】 else p1=p1-next; return 1; 9. 設(shè)有一個(gè)正整數(shù)序列組成帶頭結(jié)點(diǎn)的單鏈表head，試編寫算法確定在序列中比正整數(shù)x 大的數(shù)有幾個(gè)。 (8 分) 解答： int count (Node * head ，int x ) 在帶頭結(jié)點(diǎn)的單鏈表 head 中，確定序列中比正整數(shù) x 大的數(shù)有幾個(gè)

10、Node *p=head-next; int count=0; while (p!=NULL) if (p-datax) count +; p=p-next; return count; 算法 count 結(jié)束 33333333333333333333333333333333333333333333333333333333333333333 5. 對(duì)于棧操作數(shù)據(jù)的原則是（后進(jìn)先出 ）。 13對(duì)于棧操作數(shù)據(jù)的原則是（后進(jìn)先出） 14. 設(shè)輸入序列為 A,B,C,D, 借助一個(gè)棧不可以得到的輸出序列是 （D,A,B,C ） 。 19. 因此在初始為空的隊(duì)列中插入元素 a,b,c,d 以后，緊接著作

11、了兩次刪除操作，此時(shí)的隊(duì)尾元素是 （d ）. 20. 一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置（堆棧） 。 25. 設(shè) abcdef 以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作 , 則下面得不到的序列為（ cabdef ）。 37. 因此在初始為空的隊(duì)列中插入元素 a,b,c,d 以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)尾元素是 （d ） 。 41棧和隊(duì)列的主要區(qū)別在于（插入刪除運(yùn)算的限定不一樣） 48. 鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是 （通常不會(huì)出現(xiàn)棧滿的情況 ） 。 50. 設(shè)一個(gè)棧的輸入序列是 1 ， 2， 3，4，5, 則下列序列中，是棧的合法輸出序列的是（ 3

12、2 1 5 4 ）。 72. 單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的什么位置（鏈頭）。 101. 鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是 （ 通常不會(huì)出現(xiàn)棧滿的情況 ） 。 110. 設(shè)長(zhǎng)度為 n 的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度為（O（n） ） 。 3 / 18 113. 設(shè)有三個(gè)元素 X，Y，Z 順序進(jìn)棧（進(jìn)的過(guò)程中允許出棧） ，下列得不到的出棧排列是 （ZXY ） 123. 棧的插入和刪除操作進(jìn)行的位置在（棧頂） 。 125. 鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是（ 通常不會(huì)出現(xiàn)棧滿的情況 ）。 22222222222222222222222222222222

13、22222222222 26 循環(huán)隊(duì)列的引入，目的是為了克服 假溢出 。 49. 隊(duì)列中允許進(jìn)行插入的一端稱為隊(duì)尾。 29. 棧和隊(duì)列的共同特點(diǎn)是插入和刪除均在端點(diǎn)處進(jìn)行。 34隊(duì)列中允許進(jìn)行插入的一端稱為隊(duì)尾。 39. 一個(gè)棧的輸入序列是： 1， 2， 3 則不可能的棧輸出序列是 3 1 2 。 40. 設(shè)有一個(gè)順序棧 S，元素 S1，S2，S3，S4，S5，S6 依次進(jìn)棧，如果 6個(gè)元素的出棧順序?yàn)?S2，S3，S4， S6，S5， S1，則順序棧的容量至少應(yīng)為3 。 3333333333333333333333333333333333 1. 對(duì)于一個(gè)隊(duì)列，如果輸入項(xiàng)序列由 1,2,3,4

14、 所組成，試給出全部可能的輸出序列 答： 1,2,3,4 。 4將算術(shù)表達(dá)式 a+b* （ c+d/e ）轉(zhuǎn)為后綴表達(dá)式。 答： B abcde/+*+ 13. 將表達(dá)式 （a+b）-c*（d+e）-f）*（g+h） 改寫成后綴表達(dá)式。 答：后綴表達(dá)式為： ab+cde+*-f-gh+* 14將算術(shù)表達(dá)式 a*（b+c）-d 轉(zhuǎn)為后綴表達(dá)式。 答： abc+*d- 19. 寫出中綴表達(dá)式 A-（B+C/D）*E 的后綴形式。 答：中綴表達(dá)式 A-（B+C/D）*E 的后綴形式是： ABCD/+E*- 33333333333333333333333333333333333333333333333

15、333333333333 16. 一維數(shù)組 A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用 6 個(gè)字節(jié)，第 6 個(gè)元素的起始地址為 100，則該數(shù)組的 首地址是（ 70）。 59. 稀疏矩陣一般采用的壓縮存儲(chǔ)方法為 （ 三元組表 ） ?！揪幷咦ⅲ?三元組表和十字鏈表】 81. 設(shè)有數(shù)組 Ai,j ，數(shù)組的每個(gè)元素長(zhǎng)度為 3 字節(jié)， i 的值為 1 到 8 ， j 的值為 1 到 10，數(shù)組從內(nèi)存 首地址 BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A5 ，8 的存儲(chǔ)首地址為 （ BA+180 ） 。 126. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了（節(jié)省存儲(chǔ)空間） 。 91. 二維數(shù)組 A56 的每個(gè)元素占 5 個(gè)單元

16、，將其按行優(yōu)先順序存儲(chǔ)在起始地址為3000 的連續(xù)的內(nèi)存單 元中，則元素 A45 的存儲(chǔ)地址為（ 3145）。 四 五 串串串串串串串串串串串串 2串是（任意有限個(gè)字符構(gòu)成的序列） 。 12串是（任意有限個(gè)字符構(gòu)成的序列）。 70. 串是（任意有限個(gè)字符構(gòu)成的序列） 。 104. 若字符串“ 1234567”采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)字符占用1 個(gè)字節(jié)，每個(gè)指針占用 2 個(gè)字節(jié)，則該字 符串的存儲(chǔ)密度為（ 33.3 ）。 4 / 18 四 五 樹樹樹樹樹樹樹樹樹 1. 具有 n 個(gè)結(jié)點(diǎn)的二叉樹采用鏈接結(jié)構(gòu)存儲(chǔ)，鏈表中存放NULL指針域的個(gè)數(shù)為（ n+1）。 3在一棵二叉樹的二叉鏈表中，空指針域數(shù)等

17、于非空指針域數(shù)加（2 ）。 4某二叉樹的前序和后序序列正好相反，則該二叉樹一定是什么二叉樹（ 高度等于其結(jié)點(diǎn)數(shù) ）。 7. 在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該 （ 只有左子樹上的所有結(jié)點(diǎn) ） 。 9. 若一棵二叉樹具有 45個(gè)度為 2的結(jié)點(diǎn)， 6個(gè)度為 1的結(jié)點(diǎn)，則度為 0的結(jié)點(diǎn)個(gè)數(shù)是（ 46 ）。 10. 某二叉樹的前序和后序序列正好相同，則該二叉樹一定是什么樣的二叉樹 （ 空或只有一個(gè)結(jié)點(diǎn) ） 。 15. 結(jié)點(diǎn)前序?yàn)?xyz 的不同二叉樹，所具有的不同形態(tài)為 （5 ） 。 17在一棵高度為 h（假定樹根結(jié)點(diǎn)的層號(hào)為 0） 的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于 （2h ）

18、。 21. 對(duì)于一棵滿二叉樹， m個(gè)樹葉， n個(gè)結(jié)點(diǎn)，深度為 h, 則（n=2h1-1 ） 。 27在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（2 ）。 30. 如果 T2 是由有序樹 T轉(zhuǎn)換而來(lái)的二叉樹，那么 T中結(jié)點(diǎn)的先根序列就是 T2 中結(jié)點(diǎn)的（先根序列） 。 31. 對(duì)于一棵滿二叉樹， m個(gè)樹葉， n個(gè)結(jié)點(diǎn)，深度為 h, 則（n=2h1-1 ） 。 38. 深度為 h 且有多少個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹 （2 h+1-1 ） 。 39某二叉樹的前序和后序序列正好相反，則該二叉樹一定是的二叉樹為（高度等于其結(jié)點(diǎn)數(shù) ） ?！揪幷咦ⅲ?只有一個(gè)葉子結(jié)點(diǎn)】 42. 設(shè)高度為 h 的

19、二叉樹上只有度為 0 和度為 2 的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為 （2h-1 ） ?！揪幷咦ⅲ?根結(jié)點(diǎn)高度為 1 】 44. 在一棵具有 n 個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于（n+1 ） 45. 若一棵二叉樹有 11 個(gè)度為 2 的結(jié)點(diǎn)，則該二叉樹的葉結(jié)點(diǎn)的個(gè)數(shù)是（ 12 ）。 51. 設(shè)森林 F中有三棵樹，第一、第二和第三棵的結(jié)點(diǎn)個(gè)數(shù)分別為m1,m2和 m3,則森林 F對(duì)應(yīng)的二叉樹根結(jié) 點(diǎn)上的右子樹上結(jié)點(diǎn)個(gè)數(shù)是 （ m2+m3 ） 。 54. 二叉樹的第 I 層上最多含有結(jié)點(diǎn)數(shù)為（ 2I ）?！揪幷咦ⅲ?根結(jié)點(diǎn)高度為 0】 55. 設(shè)高度為 h 的二叉樹上只有度為 0

20、和度為 2 的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（ 2h-1 ）。 56. 如果 T2是由有序樹 T 轉(zhuǎn)換而來(lái)的二叉樹，那么 T 中結(jié)點(diǎn)的先根序列就是 T2中結(jié)點(diǎn)的（先根序列 ）。 58. 有 n 個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（ 2n-1 ）。 60. 若二叉樹中度為 2 的結(jié)點(diǎn)有 15 個(gè)，度為 1 的結(jié)點(diǎn)有 10 個(gè)，則葉子結(jié)點(diǎn)的個(gè)數(shù)為（ 16 ）。 61. 若某完全二叉樹的深度為 h，則該完全二叉樹中具有的結(jié)點(diǎn)數(shù)至少是 （2h1 ） ?！揪幷咦ⅲ?根結(jié)點(diǎn)高度 為 1 】 62. 任何一棵二叉樹的葉結(jié)點(diǎn)在其先根、中根、后根遍歷序列中的相對(duì)位置 （肯定不發(fā)生變化 ） 。 74. 對(duì)于一

21、棵滿二叉樹， m個(gè)樹葉， n個(gè)結(jié)點(diǎn)，深度為 h, 則（n=2h1-1） 【編者注： 根結(jié)點(diǎn)高度為 0】 75. 某二叉樹的前序和后序序列正好相同，則該二叉樹一定是什么樣的二叉樹 （ 空或只有一個(gè)結(jié)點(diǎn) ） 。 76. 在一棵具有 n 個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于（n+1 ）。 78. 樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（ -1 ）。 79. 設(shè)二叉樹根結(jié)點(diǎn)的層次為 0，一棵高度為 h 的滿二叉樹中的結(jié)點(diǎn)個(gè)數(shù)是 （2 h+1-1 ） 。 80. 將一棵有 50 個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，則對(duì)編號(hào)為 25 的結(jié)點(diǎn) x，該結(jié)點(diǎn) （ 有左孩子，無(wú)右孩子 ） 。 83設(shè)森林 F 中有三棵樹，

22、第一、第二和第三棵的結(jié)點(diǎn)個(gè)數(shù)分別為m1,m2和 m3, 則森林 F 對(duì)應(yīng)的二叉樹根 結(jié)點(diǎn)上的右子樹上結(jié)點(diǎn)個(gè)數(shù)是 （m2+m3 ） 。 87. 用孩子兄弟鏈表表示一棵樹， 若要找到結(jié)點(diǎn) x 的第 5 個(gè)孩子， 只要先找到 x的第一個(gè)孩子， 然后（ 從兄 弟域指針連續(xù)掃描 4 個(gè)結(jié)點(diǎn)即可 ） 。 90. 深度為 h 的滿二叉樹具有的結(jié)點(diǎn)個(gè)數(shù)為（ 2h+1-1）?！揪幷咦ⅲ?根結(jié)點(diǎn)高度為 0】 96在一棵高度為 h（假定樹根結(jié)點(diǎn)的層號(hào)為 0）的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于 （2h ） 。 98. 有 n 個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（ 2n-1 ）。 106. 若在一棵非空樹中，某結(jié)點(diǎn) A有3個(gè)

23、兄弟結(jié)點(diǎn)（包括 A自身），B是 A的雙親結(jié)點(diǎn)，則 B的度為（ 3）。 108. 深度為 h 的滿二叉樹所具有的結(jié)點(diǎn)個(gè)數(shù)是（ 2h+1-1 ）。 109按照二叉樹的定義 , 具有 3 個(gè)結(jié)點(diǎn)的二叉樹有多少種 （5 ） 。 111樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（ -1 ）。 112. 樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（ -1 ） 117. 樹形結(jié)構(gòu)的特點(diǎn)是：一個(gè)結(jié)點(diǎn)可以有 （ 多個(gè)直接后繼 ） 。 119. 按照二叉樹的定義 , 具有 3 個(gè)結(jié)點(diǎn)的二叉樹具有的種類為 （5 ） 。 127. 結(jié)點(diǎn)前序?yàn)?xyz 的不同二叉樹，所具有的不同形態(tài)為 （5 ） 。 128. 若一棵二叉樹具有 20個(gè)度為

24、 2的結(jié)點(diǎn)， 6個(gè)度為 1的結(jié)點(diǎn)，則度為 0的結(jié)點(diǎn)個(gè)數(shù)是（ 21 ）。 5 / 18 129. 一棵線索二叉樹的線索個(gè)數(shù)比鏈接個(gè)數(shù)多（ 2 ）個(gè)。 124. 某二叉樹的前序和后序序列正好相同，則該二叉樹一定是的二叉樹為（ 空或只有一個(gè)結(jié)點(diǎn) ） 。 【編者注： 公式為 】 122. 設(shè)樹T的度為 4，其中度為 1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為 4，2，1，1 則T中的葉子數(shù)為 （ 8 ） m n0 1 （i 1）ni i1 22222222222222222222222222222222222222222222222222222222 1. 若一棵二叉樹有 10個(gè)葉結(jié)點(diǎn)，則該二叉樹中度為 2 的結(jié)

25、點(diǎn)個(gè)數(shù)為 9。 3.對(duì)于一棵二叉樹，設(shè)葉子結(jié)點(diǎn)數(shù)為 n0,次數(shù)為 2的結(jié)點(diǎn)數(shù)為 n2,則 n0和n2的關(guān)系是 n0= n21。 6. 深度為 h 且有 2h-1 個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。 （ 設(shè)根結(jié)點(diǎn)處在第 1 層） 。 8. 哈夫曼樹是帶權(quán)路徑長(zhǎng)度最小 的二叉樹。 9. 二叉樹的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 10. 哈夫曼樹是 帶權(quán)路徑長(zhǎng)度最小 的二叉樹。 11. 一般樹的存儲(chǔ)結(jié)構(gòu)有雙親表示法、孩子兄弟表示法和孩子鏈表表示法。 18. 由一棵二叉樹的后序序列和中序序列可唯一確定這棵二叉樹 。 20. 若二叉樹的一個(gè)葉子結(jié)點(diǎn)是某子樹的中根遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹的后

26、根遍歷中的 第一 個(gè)結(jié)點(diǎn)。 22. 具有 100 個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為 50 。 25. 將一棵樹轉(zhuǎn)換成一棵二叉樹后，二叉樹根結(jié)點(diǎn)沒(méi)有右子樹。 30. 二叉樹的遍歷方式有三種：先序遍歷、中序遍歷、后序遍歷。 33. 若一棵二叉樹有 15 個(gè)葉結(jié)點(diǎn)，則該二叉樹中度為 2 的結(jié)的點(diǎn)個(gè)數(shù)為 14 。 37. 則高度為 k 的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為 k，最多為 2k-1 ?！揪幷咦ⅲ?根結(jié)點(diǎn)高度為 1】 41. 對(duì)于一棵二叉樹，設(shè)葉子結(jié)點(diǎn)數(shù)為 n0, 次數(shù)為 2的結(jié)點(diǎn)數(shù)為 n2,則 n0和 n2的關(guān)系是 n0= n2 1 42. 設(shè)某二叉樹的后序遍歷序列為 ABKCBP，M 則可知該

27、二叉樹的根為 M 。 48. 由一棵二叉樹的后序序列和中序序列 可唯一確定這棵二叉樹。 3333333333333333333333333333333333333333333333333333 2. 已知一棵二叉樹的中序和前序序列如下，求該二叉樹的后序序列。 中序序列： c，b，d，e，a，g，i ， h，j ，f 前序序列： a，b，c，d，e，f，g，h，i ，j 答：該二叉樹的后序序列為： c,e,d,b,i,j,h,g,f,a 3. 為什么說(shuō)樹是一種非線性結(jié)構(gòu)？ 答：樹中的每個(gè)結(jié)點(diǎn)除了根結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)有一個(gè)直接前驅(qū)，但有多個(gè)直接后繼，所以說(shuō)樹是一種 非線性結(jié)構(gòu)。 5. 找出所有這

28、樣的二叉樹形，其結(jié)點(diǎn)在先根次序遍歷和中根次序遍歷下的排列是一樣的。 答： 為空樹，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹。 10. 完全二叉樹用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)最合適，為什么？ 答：完全二叉樹用一維數(shù)組實(shí)現(xiàn)最合適。因?yàn)橥耆鏄浔４嬖谝痪S數(shù)組中時(shí)，數(shù)組內(nèi)沒(méi)有空洞，不存在 空間浪費(fèi)問(wèn)題；另外，順序存儲(chǔ)方式下，父子結(jié)點(diǎn)之間的關(guān)系可用公式描述，即已知父（或子）結(jié)點(diǎn)尋找 子（或父）結(jié)點(diǎn)只需計(jì)算一個(gè)公式，訪問(wèn)結(jié)點(diǎn)方便。但采用鏈表存儲(chǔ)時(shí)就存在空間浪費(fèi)問(wèn)題，因?yàn)槊總€(gè)結(jié) 點(diǎn)要另外保存兩個(gè)鏈接域，并且尋找結(jié)點(diǎn)也不容易。 20 為什么用二叉樹表示一般樹？ 答：樹的最直觀表示是為樹中結(jié)點(diǎn)設(shè)置指向子結(jié)點(diǎn)的指針域，對(duì) k

29、叉樹而言，每個(gè)結(jié)點(diǎn)除 data 域外，還有 k個(gè)鏈接域。這樣，對(duì)一個(gè)有 n個(gè)結(jié)點(diǎn)的 k叉樹來(lái)說(shuō)，共有n*k個(gè)指針域，其中n-1個(gè)不空，另外 n（k-1）+1 個(gè)指針域?yàn)榭?，因此，空鏈接域的比例約為（k-1 ）/k ，于是導(dǎo)致大量的空間浪費(fèi)。然而，如果采用二叉 樹表示一棵 n 個(gè)結(jié)點(diǎn)的樹，則樹中共有 2n 個(gè)鏈接域，其中未用到的有 n+1 個(gè)，占所有指針域的比例約為 1/2 ，空間浪費(fèi)少很多。 另外，因?yàn)槿魏螛湫徒Y(jié)構(gòu)都可以轉(zhuǎn)換成二叉樹，因此，通常用二叉樹表示樹型結(jié)構(gòu)。 22試找出前序序列和中序序列相同的所有二叉樹。 解答：空樹或缺左子樹的單支樹。 23完全二叉樹用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)最合適，為什么？

30、 答：完全二叉樹用一維數(shù)組實(shí)現(xiàn)最合適。因?yàn)橥耆鏄浔４嬖谝痪S數(shù)組中時(shí)，數(shù)組內(nèi)沒(méi)有空洞，不存在 空間浪費(fèi)問(wèn)題；另外，順序存儲(chǔ)方式下，父子結(jié)點(diǎn)之間的關(guān)系可用公式描述，即已知父（或子）結(jié)點(diǎn)尋找 子（或父）結(jié)點(diǎn)只需計(jì)算一個(gè)公式，訪問(wèn)結(jié)點(diǎn)方便。但采用鏈表存儲(chǔ)時(shí)就存在空間浪費(fèi)問(wèn)題，因?yàn)槊總€(gè)結(jié) 6 / 18點(diǎn)要另外保存兩個(gè)鏈接域，并且尋找結(jié)點(diǎn)也不容易。 26我們已經(jīng)知道，樹的先根序列與其對(duì)應(yīng)的二叉樹的先根序列相同，樹的后根序列與其對(duì)應(yīng)的二叉樹的 中根序列相同。那么利用樹的先根遍歷次序與后根遍歷次序，能否唯一確定一棵樹？請(qǐng)說(shuō)明理由。 答：能。因?yàn)闃涞南雀蛄信c其對(duì)應(yīng)的二叉樹的先根序列相同，樹的后根序列與其對(duì)

31、應(yīng)的二叉樹的中根序 列相同，而二叉樹的先根序列與二叉樹的中根序列能唯一確定一棵二叉樹，所以利用樹的先根遍歷次序與 后根遍歷次序，能唯一確定一棵樹。 28已知一棵二叉樹的中序和前序序列如下，求該二叉樹的后序序列。 中序序列： c，b，d，e，a，g，i ， h，j ，f 前序序列： a，b，c，d，e，f，g，h，i ，j 答：該二叉樹的后序序列為： c,e,d,b,i,j,h,g,f,a 39已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。 前序序列： A, B, C, D, E, F, G, H, I, J 中序序列： C, B, A, F, E, D, I, H, J, G 答：后序

32、序列為： C, B, F, E, I, J, H, G, D, A 4444444444444444444444444444444444444444444444444 12 分) 四 8. 設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法交換二叉樹中每個(gè)結(jié)點(diǎn)的左子女和右子女。 解答： void exchange(BinTreeNode * t) if (t!=NULL) BinTreeNode * temp; if(t-lchild!=NULL)|(t-rchild!=NULL) temp= t-lchild; t-lchild= t-rchild; t-rchild= temp; exchan

33、ge(t-lchild); exchange(t-rchild); 10. 設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法計(jì)算二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)。 (12 分) 解答： void countleaf(BinTreeNode * t,int ( 2 分) countleaf(t-lchild,count); countleaf(t-rchild ,count); 11. 設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，試寫一算法求該二叉樹上度為 2 的結(jié)點(diǎn)個(gè)數(shù)。 (12 分) 解答： void count2(bitreptr t， int count) if (t!=NULL) if (t-lchild

34、 != NULL) count2(t-lchild,count) ； count2(t-rchild,count) ； / count2 12. 設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，試寫一算法求該二叉樹中最大值(元)。(12 分) 解答： void maxnode(bitreptr t， int max) if(t!=NULL) (2 分) if(t- datamax) max=t-data;(4 分) max= maxnode(t-lchild,max)；( 2 分) max= maxnode(t-rchild,max) ；(2 分) 7 / 18 return max; （ 2 分） / m

35、axnode 5555555555555555555555555555555555555555555555555555555555555555 五 6. 由二叉樹的前序和后序遍歷序列能否唯一確定一棵二叉樹。若不能請(qǐng)舉出反例 答：不能唯一確定一棵二叉樹。如下圖。 18. 畫出下圖中二叉樹的順序存儲(chǔ)結(jié)構(gòu)示意圖 答：二叉樹的順序存儲(chǔ)結(jié)構(gòu)示意圖為： 1 3 7 15 A0 A2 A6 A14 25. 對(duì)于下圖所示的二叉樹，試分別寫出先根遍歷、中根遍歷和后根遍歷該樹所得到的先根序列、中根序 列和后根序列 8 / 18 A B C D G E F H 解答：先根遍歷的結(jié)點(diǎn)序列： ABCEIFJDGHKL

36、中遍歷的結(jié)點(diǎn)序列： EICFJBGDKHLA 后根遍歷的結(jié)點(diǎn)序列： IEJFCGKLHDBA 32. 答：把下列森林轉(zhuǎn)化為一棵二叉樹。 答： 森林轉(zhuǎn)化成的二叉樹如下圖 33. 試找出前序序列和后序序列相同的所有二叉樹。 答：空樹或只有根結(jié)點(diǎn)的二叉樹。 40把下圖中的二叉樹轉(zhuǎn)化成森林。 答案： 9 / 18 42將下圖中的二叉樹，轉(zhuǎn)換成相應(yīng)的森林 A C B F E D J H G I L K N M A B D 答：森林轉(zhuǎn)化成的二叉樹如下圖 43. 知 二 叉 樹 按 中 根 遍 歷 所得 到 的 結(jié) 點(diǎn) 序 列 為 DCBGEAHFIJK， 按 后 根 遍 歷 所 得 到 的結(jié) 點(diǎn) 序 列

37、為 DCEGBFHKJI，A畫出該樹形結(jié)構(gòu)，并按中根遍歷序列進(jìn)行線索化。 答： 44. 對(duì)于下圖所示的二叉樹，試分別寫出先根遍歷、中根遍歷該樹所得到的先根序列、中根序列 答：先根遍歷的結(jié)點(diǎn)序列： ABCEIFJDGHK，L 中遍歷的結(jié)點(diǎn)序列： EICFJBGDKHLA 46把下圖中的二叉樹轉(zhuǎn)化成森林。 10 / 18 49. 有一棵二叉樹如下圖所示，分別指出其前序、中序遍歷的結(jié)點(diǎn)序列 答：它的前序序列為： ABCDEFGHIJ它, 的中序序列為： CDBAFGEIH。J 52. 有二叉樹先序序列為： ABCDEF中, 序序列為： CBAEDF試, 畫出該二叉樹。 答：二叉樹如下圖。 53根據(jù)下

38、圖給出的二叉樹，求出中序和后序遍歷的結(jié)點(diǎn)序列 答：先序遍歷為： abdcef 中序遍歷為： dbaefc 后序遍歷為： dbfeca 55555555555555555555555555 圖圖圖圖圖圖圖圖圖圖圖圖 1 ）倍?！揪幷吒牧舜鸢浮?11. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有邊數(shù)（ 11 / 18 18. 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ 2 ）倍。 23. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常用來(lái)實(shí)現(xiàn)算法的輔助結(jié)構(gòu)是（ 棧 ） 。 32. 具有 n 個(gè)頂點(diǎn)的有向圖最多可包含的有向邊的條數(shù)是 （n（n-1） ） 。 34. 任何一個(gè)無(wú)向連通圖的最小生成樹 （

39、有一棵或多棵 ） 。 47. 有向圖中，以頂點(diǎn) v 為終點(diǎn)的邊的數(shù)目，稱為頂點(diǎn) v 的（入度）。 66 在一個(gè)有向圖中，所有頂點(diǎn)的出度之和等于所有邊數(shù)的倍數(shù)是（ 1 ）。 67. 有 n 個(gè)頂點(diǎn)的圖采用鄰接矩陣表示，則該矩陣的大小為（ n*n ）。 68.6 個(gè)頂點(diǎn)的無(wú)向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（ 5 ）。 71. 無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ 2）倍?！揪幷吒牧舜鸢浮?82. 在一個(gè)具有 n 個(gè)頂點(diǎn)的完全無(wú)向圖的邊數(shù)為 （n（n-1）/2 ） 。 85. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以有（ 任意多個(gè) ） 。 2e ) 2e ) 92. 一個(gè)具有 n

40、 個(gè)頂點(diǎn) e 條邊的無(wú)向圖中，采用鄰接表表示，則所有頂點(diǎn)的鄰接表的結(jié)點(diǎn)總數(shù)為（ 93. 一個(gè)具有 n 個(gè)頂點(diǎn)的圖采用鄰接矩陣表示，則該矩陣的大小為（n*n ）。 94. 一個(gè)具有 n 個(gè)頂點(diǎn) e 條邊的無(wú)向圖中，采用鄰接表表示，則所有頂點(diǎn)的鄰接表的結(jié)點(diǎn)總數(shù)為（ 114. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常采用的輔助存儲(chǔ)結(jié)構(gòu)是（ 棧）。 116. 在含 n 個(gè)頂點(diǎn) e 條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（n 2-2e ）。 118. 使具有 30 個(gè)頂點(diǎn)的無(wú)向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（29）。 120. 使具有 9 個(gè)頂點(diǎn)的無(wú)向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（ 8 ）。

41、5. 普里姆 （Prim） 算法適用于邊稠密圖。 7. 圖的深度優(yōu)先搜索方法類似于二叉樹的先序遍歷 訪問(wèn)一次 13. 圖的深度優(yōu)先遍歷序列不是唯一的。 16. 圖的遍歷是指從圖中某一頂點(diǎn)出發(fā)訪問(wèn)圖中全部頂點(diǎn)且使每一頂點(diǎn)僅被 17. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊的數(shù)目的 2 倍 。 23. 普里姆 （Prim） 算法適用于邊稠密圖。 27. 若連通網(wǎng)絡(luò)上各邊的權(quán)值均不相同，則該圖的最小生成樹有1 棵 31. 若連通圖的頂點(diǎn)個(gè)數(shù)為 n，則該圖的生成樹的邊數(shù)為 n-1 。 32. 圖的存儲(chǔ)結(jié)構(gòu)最常用的有鄰接矩陣和鄰接表。 35. 拓?fù)渑判蜉敵龅捻旤c(diǎn)數(shù)小于有向圖的頂點(diǎn)數(shù)，則該圖一定存在環(huán)。

42、 38. 若連通網(wǎng)絡(luò)上各邊的權(quán)值均不相同，則該圖的最小生成樹有1 棵 47圖的存儲(chǔ)結(jié)構(gòu)最常用的有鄰接表和鄰接矩陣。 45. 設(shè)無(wú)向圖 G的頂點(diǎn)數(shù)為 n，則要使 G連通最少有 n-1 條邊。 8. 有n 個(gè)頂點(diǎn)的無(wú)向連通圖至少有多少條邊？有 n個(gè)頂點(diǎn)的有向連通圖至少有多少條邊？ 答：有 n個(gè)頂點(diǎn)的無(wú)向連通圖至少有 n-1 條邊，有 n個(gè)頂點(diǎn)的有向連通圖至少有 n 條邊 四 5555555555555555555555555555555555555555555555 五 7. 求出下圖所示有向圖的鄰接矩陣。 答：有向圖的鄰接矩陣為： 0 1 2 3 4 0 0 2 7 1 12 / 18 1 0

43、2 0 5 3 0 4 3 4 0 16求出下圖所示無(wú)向圖的鄰接表 答：無(wú)向圖的鄰接表為： Head 17. 用鄰接矩陣存儲(chǔ)一個(gè)包含 1000 個(gè)頂點(diǎn)和 1000 條邊的圖，則該圖的鄰接矩陣中有多少元素？有多少非零 元素？ 答：該圖的鄰接矩陣中有 1000*1000 個(gè)元素。該圖的鄰接矩陣中有 2000 個(gè)非零元素 27請(qǐng)給出如下圖所示的權(quán)圖的鄰接矩陣。 0 出發(fā)求出其廣度優(yōu)先搜索序列 答：解： 解答： 廣度優(yōu)先搜索序列： 0 1 2 3 4 0 1 0 2 7 1 2 0 3 0 5 4 0 3 4 0 36. 已知一個(gè)圖如下所示，若從頂點(diǎn) 排序排序排序排序排序排序排序排序 8. 排序方法中

44、， 從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較， 將其放入已排序序列的正 確位置上的方法，稱為 ( 插入排序 ) 。 29一組記錄的關(guān)鍵字為 45, 80, 55, 40, 42, 85，則利用堆排序的方法建立的初始堆為( 85, 80, 55, 40, 42, 45 )。 33設(shè)有 6000 個(gè)無(wú)序的元素 ,希望用最快的速度挑選出其中前 5個(gè)最大的元素 ,最好選用 (堆排序 )法。 35. 排序方法中，從未排序序列中挑選元素，將其放入已排序序列的一端的方法，稱為(選擇排序 ) 。 57. 用分劃交換排序方法對(duì)包含有 n 個(gè)關(guān)鍵的序列進(jìn)行排序，最壞情況下執(zhí)行的時(shí)間雜度為(O(n 2

45、) 。 14 / 18 63. 初始序列已經(jīng)按鍵值有序時(shí)，用直接插入算法進(jìn)行排序，需要比較的次數(shù)為 ( n-1) 。 65 用冒泡排序法對(duì)序列 18,16,14,12,10,8 從小到大進(jìn)行排序，需要進(jìn)行的比較次數(shù)是 (15 ) 。 73. 一組記錄的關(guān)鍵字為 45, 80, 55, 40, 42, 85 ，則利用堆排序的方法建立的初始堆為( 85, 80, 55, 40, 42, 45 )。 84. 對(duì)于鍵值序列 72,73,71,23,94,16,5,68,76,103 用篩選法建堆，開始結(jié)點(diǎn)的鍵值必須為 (94 ) 。 97. 若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，則采用比較

46、次數(shù)最少的方法是(直接插入排 序)。 100. 在對(duì) n 個(gè)元素進(jìn)行冒泡排序的過(guò)程中，最好情況下的時(shí)間復(fù)雜性為(n) )。 103. 若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，則采用 (直接插入排序) 方法比較次數(shù)最少。 105. 用分劃交換排序方法對(duì)包含有 n 個(gè)關(guān)鍵的序列進(jìn)行排序，最壞情況下執(zhí)行的時(shí)間雜度為(O(n 2) ) 。 21. 在直接插入排序、直接選擇排序、分劃交換排序、堆排序中穩(wěn)定的排序方法有直接插入排序。 3333333333333333333333333333333333333333333333333333333333333333 9下面列舉的是常用的排序方法：直接

47、插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排 序。試問(wèn)，哪些排序方法是穩(wěn)定的？ 答：起泡排序 , 直接插入排序，歸并排序是穩(wěn)定的。 21已知數(shù)據(jù)序列為 12,5,9,20,6,31,24 ，對(duì)該數(shù)據(jù)序列進(jìn)行排序，試寫出冒泡排序每趟的結(jié)果。 答： 初始鍵值序列 12 5 9 20 6 31 24 第一趟排序 5 9 12 6 20 24 31 第二趟排序 5 9 6 12 20 24 31 第三趟排序 5 6 9 12 20 24 31 【編者改了答案】 第四趟排序 5 6 9 12 20 24 31 31已知數(shù)據(jù)序列為 12,5,9,20,6,31,24 ，對(duì)該數(shù)據(jù)序列進(jìn)行排序，

48、試寫出歸并排序每趟的結(jié)果。 解答： 初始鍵值序列 12 5 9 20 6 31 24 第一趟排序 512 920 6 3124 第二趟排序 59 1220 6 2431 第三趟排序 56 912 20 2431() 37. 一組記錄的關(guān)鍵字為(52, 56, 26,12, 69, 85, 33, 48, 70)，給出快速排序的過(guò)程。 解答： 【編者： 本書對(duì)快速排序與其它書不一樣】 解：52, 56, 26, 12, 69, 85, 33, 48, 70錯(cuò)誤 第一趟排序 33, 48, 26, 12, 52, 85, 69, 56, 70 第二趟排序 26, 12, 33, 48, 52, 6

49、9, 56, 70, 85 第三趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85 第四趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85 第五趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85 38下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并 排序。試問(wèn)，哪些排序方法是穩(wěn)定的？ ，試寫出對(duì) key 進(jìn)行漸減增量排序(增量 起泡排序 , 直接插入排序，歸并排序是穩(wěn)定的。 48. 設(shè)記錄的關(guān)鍵字集合 key=51,28,38,86,70,90,7,30,40,25 d = 5

50、 ， 3， 1)時(shí)，各趟排序結(jié)束后的結(jié)果。 解答：各趟排序結(jié)束后的結(jié)果。 初始狀態(tài)： 51 28 38 86 70 90 730 4025 第一趟排序 (d=5): 51 7 3040 2590 2838 8670 第二趟排序 (d=3): 28 7 3040 2586 5138 9070 第三趟排序 (d=1): 7 25 2830 3840 5170 8690 四 5555555555555555555555555555555555555555555555555555555 五 15 / 18 34. 一組記錄的關(guān)鍵字為（ 50，79，8，56，32，41，85），給出利用重建堆方法建立的

51、初始堆（堆頂最大） 并給出堆排序的過(guò)程。 答：1） 建立的初始堆為 : 85 ，79，50， c）第 2 次交換 a）初始建堆 d）第 3 次交換 e）第 4 次交換 50 56 79 85 （f）第 5 次交換 g）第 6 次交換 2 ）堆排序的過(guò)程如下： 47. 一組記錄的關(guān)鍵字為 （52, 56, 26, 12, 69, 85, 33, 48, 70），給出快速排序的過(guò)程。 解答： 【編者： 本書對(duì)快速排序與其它書不一樣】 解：52, 56, 26, 12, 69, 85, 33, 48, 70錯(cuò)誤 第一趟排序 33, 48, 26, 12, 52, 85, 69, 56, 70 第二趟

52、排序 26, 12, 33, 48, 52, 69, 56, 70, 85 第三趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85 第四趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85 第五趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85 50. 已知 8 個(gè)記錄，對(duì)應(yīng)的關(guān)鍵詞為： 25,84,21,47,15,27,68,35,20寫出快速排序的第一趟排序過(guò)程圖示。 答：初始鍵值序列 25 84 21 47 15 27 68 35 20 第一次交換 25 84 21 47 15 27 68 35 20 i=2j

53、=9 第二次交換 25 20 21 47 15 27 68 35 84 16 / 18 掃描交叉 25 20 21 15 47 27 68 35 84 j i Rm與 Rj 互換 25 20 21 15 47 27 68 35 84 R 分劃表 m j 15 20 21 25 47 27 68 35 84 888888888888888888888888888888 查找查找查找查找查找出查找 24. 堆的形狀是一棵 ( 完全二叉樹 ) 。 36. 對(duì)有 14 個(gè)數(shù)據(jù)元素的有序表 R14 進(jìn)行折半搜索， 搜索到 R3 的關(guān)鍵碼等于給定值， 此時(shí)元素比較順 序依次為( R6 ，R2 ，R4 ，R3 )?！揪幷咦ⅲ合聵?biāo)從 0 開始】 46. 對(duì)有 n 個(gè)記錄的表按記錄鍵值有序建立二叉查找樹，在這種情況下，其平均查找