數(shù)據(jù)結(jié)構(gòu)原理與分析--01343--18日下-復(fù)習(xí)資料

1、數(shù)據(jù)結(jié)構(gòu)原理與分析-01343-18日下-復(fù)習(xí)資料一、填空1. 線性表是具有 n個(gè)什么的有限序列數(shù) 據(jù)元素 。2. 鄰接表的存儲(chǔ)結(jié)構(gòu)以下圖的深度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的先序遍歷。3. 在一棵二叉樹(shù)的二叉鏈表中，空指針域 數(shù)等于非空指針域數(shù)加24. 某二叉樹(shù)的前序和后序序列正好相反，那么該二叉樹(shù)一定是什么二叉樹(shù)高度等于其結(jié)點(diǎn)數(shù)。5. 對(duì)于棧操作數(shù)據(jù)的原那么是后進(jìn)先出 6. 結(jié)點(diǎn)前序?yàn)閤yz的不同二叉樹(shù)，所具有 的不同形態(tài)為5 。7. 設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表 示，假設(shè)只設(shè)頭指針，那么入隊(duì)操作的時(shí)間復(fù) 雜度為On。8. 在一棵高度為h假定樹(shù)根結(jié)點(diǎn)的層號(hào)為0的完全二叉樹(shù)中，所含結(jié)點(diǎn)個(gè)數(shù)不小于2

2、h 。9. 具有n個(gè)頂點(diǎn)的有向無(wú)環(huán)圖最多可包含有向邊的條數(shù)是nn-1/2 。10. 因此在初始為空的隊(duì)列中插入元素a,b,c,d 以后，緊接著作了兩次刪除操作， 此時(shí)的隊(duì)尾元素是 d .11. 假設(shè)二叉樹(shù)中度為 2的結(jié)點(diǎn)有15個(gè)，度 為1的結(jié)點(diǎn)有10個(gè)，那么葉結(jié)點(diǎn)的個(gè)數(shù)16。12. 對(duì)于一棵滿二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h,那么n=2h + 1-1 。13. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，所有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于n+114. 用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)， 通常用來(lái)實(shí)現(xiàn)算法的輔助結(jié)構(gòu)是棧。15. 堆的形狀是一棵完全二叉樹(shù)。16. 假設(shè)在一棵非空樹(shù)中，某結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)包括A自身，

3、B是A的雙親結(jié)點(diǎn)， 那么B的度為4 。17. 任何一個(gè)無(wú)向連通圖的最小生成樹(shù) 有 一棵或多棵18. 在非空二叉樹(shù)的中序遍歷序列中，二叉樹(shù)的根結(jié)點(diǎn)的左邊應(yīng)該只有左子樹(shù)上的所有結(jié)點(diǎn)。19. 排序方法中，從未排序序列中依次取出 元素與已排序序列中的元素進(jìn)行比擬，將 其放入已排序序列的正確位置上的方法， 稱(chēng)為插入排序。20. 對(duì)于一棵滿二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h,那么n=2h + 1-1 。21. 具有n個(gè)頂點(diǎn)的有向圖最多可包含的有向邊的條數(shù)是nn-1。22. 某二叉樹(shù)的前序和后序序列正好相同，那么該二叉樹(shù)一定是什么樣的二叉樹(shù)空或只有一個(gè)結(jié)點(diǎn)。23. 棧和隊(duì)列的主要區(qū)別在于插入刪除運(yùn)算的限定

4、不一樣。24. 串是任意有限個(gè)字符構(gòu)成的序列25. 對(duì)有14個(gè)數(shù)據(jù)元素的有序表 R14進(jìn)行折半搜索，搜索到 R3的關(guān)鍵碼等于給 定值，此時(shí)元素比擬順序依次為R6,R2 , R4 , R3。26. 深度為h且有多少個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿二叉樹(shù)2h+1-1。27. 在含n個(gè)頂點(diǎn)e條邊的無(wú)向圖的鄰接矩 陣中，零元素的個(gè)數(shù)為n2-2e 。28. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和與所有頂點(diǎn)出度之和的倍數(shù)為1。29. 鄰接表的存儲(chǔ)結(jié)構(gòu)以下圖的廣度優(yōu)先遍 歷類(lèi)似于二叉樹(shù)的按層遍歷。30. 設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，那么此類(lèi)二叉樹(shù)中所包含的結(jié) 點(diǎn)數(shù)至少為2h-1。31. 假設(shè)一棵二叉樹(shù)具有

5、10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，那么度為 0的結(jié)點(diǎn)個(gè)數(shù) 是1132. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，所有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于n+133. 假設(shè)一棵二叉樹(shù)有11個(gè)度為2的結(jié)點(diǎn)，那么該二叉樹(shù)的葉結(jié)點(diǎn)的個(gè)數(shù)是12。34. 對(duì)有n個(gè)記錄的表按記錄鍵值有序建 立二叉查找樹(shù)，在這種情況下，其平均查 找長(zhǎng)度的量級(jí)為On35. 設(shè)森林F中有三棵樹(shù)，第一、第二和第 三棵的結(jié)點(diǎn)個(gè)數(shù)分別為 m1,m2和m3,那么森 林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)上的右子樹(shù)上結(jié)點(diǎn)個(gè)數(shù)是m2+m3。36. 對(duì)有18個(gè)元素的有序表作二分折半 查找，那么查找A3的比擬序列的下標(biāo)為9、4、2、 3。37. 假設(shè)要在O 1 的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩

6、個(gè)循環(huán)鏈表頭尾相接，那么應(yīng)對(duì)兩個(gè)循環(huán)鏈 表各設(shè)置一個(gè)指針，分別指向各自的尾結(jié)點(diǎn)。38. 深度為h的滿二叉樹(shù)所具有的結(jié)點(diǎn)個(gè)數(shù)是2h+1-1 。39. 設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，那么此類(lèi)二叉樹(shù)中所包含的結(jié) 點(diǎn)數(shù)至少為2h-1 40. 如果T2是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的先根序列就是T2中結(jié)點(diǎn)的先根序列。41. 有n個(gè)葉子的哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為2n-1 。42. 設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表 示，假設(shè)只設(shè)頭指針，那么入隊(duì)操作的時(shí)間復(fù) 雜度為On。43. 假設(shè)二叉樹(shù)中度為2的結(jié)點(diǎn)有15個(gè)，度 為1的結(jié)點(diǎn)有10個(gè)，那么葉子結(jié)點(diǎn)的個(gè)數(shù) 為16。44. 假設(shè)某完全二叉

7、樹(shù)的深度為h,那么該完全二叉樹(shù)中具有的結(jié)點(diǎn)數(shù)至少是2h 1。45. 叉樹(shù)的前序和后序序列正好相反，那么該二叉樹(shù)一定是什么二叉樹(shù)度等于其結(jié)點(diǎn)數(shù)。46. 初始序列已經(jīng)按鍵值有序時(shí)，用直接插入算法進(jìn)行排序，需要比擬的次數(shù)為n-1。47. 接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，為實(shí)現(xiàn)算法通常采用的輔助結(jié)構(gòu)是隊(duì)列。48. 用冒泡排序法對(duì)序列18,16,14,12,10,8 從小到大進(jìn)行排序，需要進(jìn)行的比擬次數(shù)是15。49. 有n個(gè)頂點(diǎn)的圖采用鄰接矩陣表示，那么該矩陣的大小為n*n 。50. 6個(gè)頂點(diǎn)的無(wú)向圖成為一個(gè)連通圖至少 應(yīng)有邊的條數(shù)是5。51. 單鏈表中，增加頭結(jié)點(diǎn)的目的是為了方便運(yùn)算的實(shí)現(xiàn)。52. 在線

8、索二叉樹(shù)中，結(jié)點(diǎn)*t沒(méi)有左子樹(shù)的充要條件是t->ltag=1。53. 按照二叉樹(shù)的定義,具有3個(gè)結(jié)點(diǎn)的二 叉樹(shù)有多少種5。54. 對(duì)待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子序列施 加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。這樣的排序方法是快 速排序55. 二分查找法要求查找表中各元素的鍵值必須是遞增或遞減。56. 線性表的長(zhǎng)度是指表中的元素個(gè)數(shù)57. 將長(zhǎng)度為m的單鏈表連接在長(zhǎng)度為n的單鏈表之后的算法的時(shí)間復(fù)雜度為On。58 .有一個(gè)有序表為1 , 3 ,9 ,12,32 , 41,45, 62, 75, 77, 82, 95, 100，當(dāng)二分查找值為82

9、的結(jié)點(diǎn)時(shí)，查找成功的比擬次 數(shù)是4。.59. 假設(shè)在一棵非空樹(shù)中，某結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)包括A自身，B是A的雙親結(jié)點(diǎn)， 那么B的度為4。60. 深度為h的滿二叉樹(shù)具有的結(jié)點(diǎn)個(gè)數(shù)為2h+1-1 。61. 用二叉鏈表存儲(chǔ)樹(shù)，那么根結(jié)點(diǎn)的右指針 是空。62. 個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于 所有邊數(shù)1倍。63. 單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的什么位置鏈頭。64. 線性表的長(zhǎng)度是指表中的元素個(gè)數(shù)65. 某二叉樹(shù)的前序和后序序列正好相同，那么該二叉樹(shù)一定是什么樣的二叉樹(shù)空或只有一個(gè)結(jié)點(diǎn)。66. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，所有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于n+1 。67. 一個(gè)具有n個(gè)頂點(diǎn)e條邊的無(wú)向圖

10、中， 采用鄰接表表示，那么所有頂點(diǎn)的鄰接表的 結(jié)點(diǎn)總數(shù)為2e 。68. 鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿的情況。69. 對(duì)于鍵值序列72,73,71,23,94,16,5,68,76,103用篩選法建堆，開(kāi)始結(jié)點(diǎn)的鍵值必須為94。70. 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù) 和后續(xù)結(jié)點(diǎn)數(shù)可以有任意多個(gè)。71. 對(duì)有n個(gè)記錄的有序表采用二分查找， 其平均查找長(zhǎng)度的量級(jí)為 Olog2n。72. 在一棵高度為h假定樹(shù)根結(jié)點(diǎn)的層號(hào) 為0的完全二叉樹(shù)中，所含結(jié)點(diǎn)個(gè)數(shù)不小 于2h。73. 假設(shè)一棵二叉樹(shù)有10個(gè)葉結(jié)點(diǎn)，那么該二 叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)為9。74. 設(shè)有一個(gè)順序棧 S,元

11、素S1, S2, S3, S4, S5, S6依次進(jìn)棧，如果 6個(gè)元素的出 棧順序?yàn)?S2, S3, S4, S6, S5, S1,那么順 序棧的容量至少應(yīng)為 3。75. 對(duì)于一棵二叉樹(shù)，設(shè)葉子結(jié)點(diǎn)數(shù)為n0,次數(shù)為2的結(jié)點(diǎn)數(shù)為n2,那么n0和n2的關(guān) 系是 n0= n2 + 1。76. 假設(shè)一棵二叉樹(shù)有12個(gè)葉結(jié)點(diǎn)，那么該二 叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)為11。77. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)結(jié)構(gòu)和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。78. 深度為h且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng) 為滿二叉樹(shù)。設(shè)根結(jié)點(diǎn)處在第1層。79. 圖的深度優(yōu)先搜索方法類(lèi)似于二叉樹(shù) 的先序遍歷。80. 哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。81. 在

12、線索二叉樹(shù)中，線索是指向結(jié)點(diǎn)在某 遍歷次序下的前驅(qū)或后繼結(jié)點(diǎn)的指針。82. ?？梢宰鳛閷?shí)現(xiàn)遞歸函數(shù)調(diào)用的一種 數(shù)據(jù)結(jié)構(gòu)。83. 一般樹(shù)的存儲(chǔ)結(jié)構(gòu)有雙親表示法、 孩子 兄弟表示法和孩子鏈表表示法。84. 將數(shù)據(jù)元素2,4,6,8,10,12,14,16,18,20依次存于一個(gè)一維數(shù)組中，然后采用折半查找元素12,被比擬過(guò)的數(shù)組元素的下標(biāo)依次為5, 7,6 。85. 圖的深度優(yōu)先遍歷序列不是唯一的。86. 假設(shè)二叉樹(shù)的一個(gè)葉子結(jié)點(diǎn)是某子樹(shù)的 中根遍歷序列中的第一個(gè)結(jié)點(diǎn)，那么它必是 該子樹(shù)的后跟遍歷中的第一個(gè)結(jié)點(diǎn)。87. 圖的遍歷是指從圖中某一頂點(diǎn)出發(fā)訪問(wèn)圖中全部頂點(diǎn)且使每一頂點(diǎn)僅被_ 訪問(wèn)一次。8

13、8. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊的數(shù)目的2倍。89. 由一棵二叉樹(shù)的后序序列和中序序列可唯一確定這棵二叉樹(shù)。90. 在有序表12,24,36,48,60,72,84 中二分查找關(guān)鍵字 72時(shí)所需進(jìn)行的關(guān)鍵字 比擬次數(shù)為2。91. 設(shè)根結(jié)點(diǎn)的層數(shù)為0,定義樹(shù)的高度為樹(shù)中層數(shù)最大的結(jié)點(diǎn)的層數(shù)加 1,那么高度 為k的二叉樹(shù)具有的結(jié)點(diǎn)數(shù)目，最少為 k, 最多為2k-1。92. 在直接插入排序、直接選擇排序、分劃 交換排序、堆排序中穩(wěn)定的排序方法有直 接插入排序。93. 具有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的葉子 結(jié)點(diǎn)數(shù)為50。94. 普里姆Prim算法適用于邊稠密圖。95. 在有n個(gè)葉子結(jié)點(diǎn)的哈

14、夫曼樹(shù)中，其結(jié) 點(diǎn)總數(shù)為2n-1。96. 將一棵樹(shù)轉(zhuǎn)換成一棵二叉樹(shù)后，二叉樹(shù)根結(jié)點(diǎn)沒(méi)有右子樹(shù)。97. 矩陣采用壓縮存儲(chǔ)是為了節(jié)省空間98. 假設(shè)連通網(wǎng)絡(luò)上各邊的權(quán)值均不相同，那么該圖的最小生成樹(shù)有1棵。99. 設(shè)無(wú)向圖G的頂點(diǎn)數(shù)為n,那么要使 G連 通最少有n-1條邊。100 .棧和隊(duì)列的共同特點(diǎn)是插入和刪除均在端點(diǎn)處進(jìn)行。101 .克魯斯卡爾Kruskar算法適用于邊稀疏圖。102. 假設(shè)連通圖的頂點(diǎn)個(gè)數(shù)為n,那么該圖的生成樹(shù)的邊數(shù)為 n-1。103. 圖的存儲(chǔ)結(jié)構(gòu)最常用的有鄰接矩陣和鄰接表。104. 由一棵二叉樹(shù)的前序序列和中序序列 可唯一確定這棵二叉樹(shù)。105. 隊(duì)列中允許進(jìn)行插入的一端

15、稱(chēng)為隊(duì)尾。106. 拓?fù)渑判蜉敵龅捻旤c(diǎn)數(shù)小于有向圖的 頂點(diǎn)數(shù)，那么該圖一定存在環(huán)。107. 在有序表15,23,24,45,48,62,85 中二分查找關(guān)鍵詞23時(shí)所需進(jìn)行的關(guān)鍵詞比擬次數(shù)為2。108 .樹(shù)中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加-1 。109. 在一個(gè)具有n個(gè)頂點(diǎn)的完全無(wú)向圖的 邊數(shù)為nn-1/2。110. 用分劃交換排序方法對(duì)包含有n個(gè)關(guān)鍵的序列進(jìn)行排序，最壞情況下執(zhí)行的時(shí)間雜度為On2111. 一棵高度為h假定樹(shù)根結(jié)點(diǎn)的層號(hào)為0的完全二叉樹(shù)中，所含結(jié)點(diǎn)個(gè)數(shù)不小于2h。112. 假設(shè)長(zhǎng)度為n的非空線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除表的第i個(gè)數(shù)據(jù)元素，首先需要移動(dòng)表中數(shù)據(jù)元素的個(gè)數(shù)是n-i

16、。113. 在非空二叉樹(shù)的中序遍歷序列中，二 叉樹(shù)的根結(jié)點(diǎn)的左邊應(yīng)該只有左子樹(shù)上 的所有結(jié)點(diǎn)。114. 假設(shè)一棵二叉樹(shù)具有 45個(gè)度為2的結(jié) 點(diǎn)，6個(gè)度為1的結(jié)點(diǎn)，那么度為0的結(jié)點(diǎn) 個(gè)數(shù)是46 。115. 在一個(gè)有向圖中，所有頂點(diǎn)的入度之 和等于所有邊數(shù)4倍。116. 設(shè)輸入序列為A,B,C,D,借助一個(gè)棧不可以得到的輸出序列是D,A,B,C 。117. 一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的起始地 址為100,那么該數(shù)組的首地址是70。118. 設(shè)abcdef以所給的次序進(jìn)棧，假設(shè)在進(jìn)棧操作時(shí)，允許退棧操作，那么下面得不到的 序列為cbdef 。119. 一般情況下，

17、將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置堆棧 。120 .假設(shè)長(zhǎng)度為n的非空線性表采用順序存 儲(chǔ)結(jié)構(gòu)，刪除表的第i個(gè)數(shù)據(jù)元素，i的合法值應(yīng)該121.是C. 1 < i < n 。122 .假設(shè)某線性表中最常用的操作是取第i個(gè)元素和刪除最后一個(gè)元素，那么采用什么 存儲(chǔ)方123.式最節(jié)省時(shí)間順序表。124 .一組記錄的關(guān)鍵字為 45, 80, 55, 40,42, 85，那么利用堆排序的方法建立的初始 堆為85, 80, 55, 40, 42, 45。125. 設(shè)有6000個(gè)無(wú)序的元素，希望用最快 的速度挑選出其中前 5個(gè)最大的元素，最好選用堆排序法。126. 排序方法中，從未排序序列

18、中挑選元 素，將其放入已排序序列的一端的方法， 稱(chēng)為選擇排序。127. 帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是head->next=NULL。128. 在一個(gè)單鏈表中，假設(shè)刪除 *p結(jié)點(diǎn)的 后繼結(jié)點(diǎn)，那么執(zhí)行p->n ext=p->n ext- >n ext 。129. 在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中，所 有結(jié)點(diǎn)的空子樹(shù)個(gè)數(shù)等于n+1130. 有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目，稱(chēng)為頂點(diǎn)v的入度。131. 假設(shè)頻繁地對(duì)線性表進(jìn)行插入和刪除操 作，該線性表應(yīng)該采用的存儲(chǔ)結(jié)構(gòu)是鏈 式。132. 設(shè)一個(gè)棧的輸入序列是1，2，3，4,5, 那么以下序列中，是棧的合法輸出序列的

19、是3 2 1 5 4。133. 有數(shù)據(jù)53，30，37，12 ,45, 24, 96，從空二叉樹(shù)開(kāi)始逐個(gè)插入數(shù)據(jù)來(lái)形成二叉 查找樹(shù)，假設(shè)希望高度最小，那么應(yīng)選擇下面 輸入序列是37,24,12,30,53,45,96。134 .二叉樹(shù)的第I層上最多含有結(jié)點(diǎn)數(shù)為2I 。135. 稀疏矩陣一般采用的壓縮存儲(chǔ)方法為三元組表。136. 某二叉樹(shù)的前序和后序序列正好相同，那么該二叉樹(shù)一定是什么樣的二叉樹(shù)空或只有一個(gè)結(jié)點(diǎn)。137. 假設(shè)長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié) 構(gòu)，在表的第i個(gè)位置插入一個(gè)數(shù)據(jù)元素， 需要移動(dòng)表中元素的個(gè)數(shù)是 n-i+1 。138. 設(shè)有數(shù)組Ai,j，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的

20、值為1至U 8，j的值為 1到10，數(shù)組從內(nèi)存首地址BA開(kāi)始順序存放，當(dāng)用以列為主存放時(shí)，元素A5，8的存儲(chǔ)首地址為BA+180。139. 二維數(shù)組 A56的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先順序存儲(chǔ)在起始地址 為3000的連續(xù)的內(nèi)存單元中，那么元素A45的存儲(chǔ)地址為3145 。140. 一個(gè)具有n個(gè)頂點(diǎn)的圖采用鄰接矩陣 表示，那么該矩陣的大小為n*n 。141. 假設(shè)字符串“ 1234567"采用鏈?zhǔn)酱鎯?chǔ)， 假設(shè)每個(gè)字符占用 1個(gè)字節(jié)，每個(gè)指針占 用2個(gè)字節(jié)，那么該字符串的存儲(chǔ)密度為33.3 %。142. 假設(shè)在一棵非空樹(shù)中，某結(jié)點(diǎn) A有3個(gè) 兄弟結(jié)點(diǎn)包括 A自身，B是A的雙親結(jié) 點(diǎn)

21、，那么B的度為3 。143. 設(shè)有三個(gè)元素 X，Y，Z順序進(jìn)棧進(jìn) 的過(guò)程中允許出棧，以下得不到的出棧排 列是ZXY。144. 樹(shù)形結(jié)構(gòu)的特點(diǎn)是：一個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼。145. 使具有30個(gè)頂點(diǎn)的無(wú)向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是29。146. 使具有9個(gè)頂點(diǎn)的無(wú)向圖成為一個(gè)連 通圖至少應(yīng)有邊的條數(shù)是8。147. 在順序表n足夠大中進(jìn)行順序查找，其查找不成功的平均長(zhǎng)度是n+1 148. 設(shè)樹(shù)T的度為4，其中度為1，2，3 和4的結(jié)點(diǎn)個(gè)數(shù)分別為 4，2，1，1那么T 中的葉子數(shù)為8。149. 棧的插入和刪除操作進(jìn)行的位置在棧頂。150. 假設(shè)一棵二叉樹(shù)具有 20個(gè)度為2的結(jié) 點(diǎn)，6個(gè)度為

22、1的結(jié)點(diǎn)，那么度為 0的結(jié)點(diǎn) 個(gè)數(shù)是21。151. 一棵線索二叉樹(shù)的線索個(gè)數(shù)比鏈接個(gè) 數(shù)多2個(gè)。152. 在循環(huán) 鏈表中，從任何一結(jié)點(diǎn)出發(fā)都 能訪問(wèn)到表中的所有結(jié)點(diǎn)。153. 在n個(gè)結(jié)點(diǎn)的順序表中插入一個(gè)結(jié)點(diǎn) 需平均移動(dòng)n/2個(gè)結(jié)點(diǎn)。154. 循環(huán)隊(duì)列的引入，目的是為了克服假 溢出 。155. 假設(shè)連通網(wǎng)絡(luò)上各邊的權(quán)值均不相同，那么該圖的最小生成樹(shù)有1棵。156. 二叉樹(shù)的遍歷方式有三種：先序遍歷、中序遍歷、后序遍歷。157. 假設(shè)一棵二叉樹(shù)有15個(gè)葉結(jié)點(diǎn)，那么該二 叉樹(shù)中度為2的結(jié)的點(diǎn)個(gè)數(shù)為14。158. 設(shè)某二叉樹(shù)的后序遍歷序列為ABKCBPM那么可知該二叉樹(shù)的根為M。159. 數(shù)據(jù)結(jié)構(gòu)的

23、三個(gè)方面：數(shù)據(jù)的邏輯結(jié) 構(gòu)、物理結(jié)構(gòu)、運(yùn)算。160. 每個(gè)結(jié)點(diǎn)只有一個(gè)鏈接域的鏈表叫做 單鏈表。161. 組成串的數(shù)據(jù)元素只能是字符。162. 具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)采用鏈接結(jié)構(gòu) 存儲(chǔ)，鏈表中存放 NULL指針域的個(gè)數(shù)為n+1。163. 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之 和等于所有邊數(shù)2倍。164設(shè)二叉樹(shù)根結(jié)點(diǎn)的層次為0, 棵高度為h的滿二叉樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)是2h+1-1。165. 將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按 層編號(hào)，那么對(duì)編號(hào)為 25的結(jié)點(diǎn)X,該結(jié)點(diǎn) 有左孩子，無(wú)右孩子 。166. 樹(shù)或樹(shù)形的定義是什么？答：一 個(gè)樹(shù)或樹(shù)形就是一個(gè)有限非空的結(jié)點(diǎn) 集合T,其中有一個(gè)特別標(biāo)出的稱(chēng)為該樹(shù) 之根r

24、oot T的結(jié)點(diǎn)；其余除根外 T點(diǎn)劃分成m 丁個(gè)不相交集合1'' m,而且這些集合的每一個(gè)又都是樹(shù)。167在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) 數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以有任意多個(gè)。16 8.什么是樹(shù)的路徑長(zhǎng)度？答：樹(shù)的路徑 長(zhǎng)度是指從根結(jié)點(diǎn)到樹(shù)中每個(gè)葉結(jié)點(diǎn)的路 徑長(zhǎng)度之和。二、選擇1. 假設(shè)某線性表中最常用的操作是取第i個(gè)元素和刪除最后一個(gè)元素，那么采用什么存儲(chǔ)方式最節(jié)省時(shí)間A。A.順序表B.單鏈表C.雙鏈表D.單循環(huán)鏈表2. 在下述的排序方法中，不屬于內(nèi)排序方 法的是C。A. 插入排序法B.選擇排序法C.拓?fù)渑判?法D.歸并排序法3. 以下四個(gè)關(guān)鍵詞序列中，不是堆的序列 為C。A. 0

25、5,23,16,68,94,72,71,73B. 05,16,23,68,94,72,71,73C. 05,23,16,73,94,72,71,68D. 05,23,16,68,73,71,72,944. 以下排序算法中，某一趟結(jié)束后未必能選出一個(gè)元素放其最終位置上的是D 。A. 堆排序B.冒泡排序C.快速排序D. 直接插入排序5. 用孩子兄弟鏈表表示一棵樹(shù)，假設(shè)要找到 結(jié)點(diǎn)x的第5個(gè)孩子，只要先找到 x的第 一個(gè)孩子，然后D。A.從孩子域指針連續(xù)掃描5個(gè)結(jié)點(diǎn)即可B.從孩子域指針連續(xù)掃描4個(gè)結(jié)點(diǎn)即可C. 從兄弟域指針連續(xù)掃描5個(gè)結(jié)點(diǎn)即可D.從兄弟域指針連續(xù)掃描4個(gè)結(jié)點(diǎn)即可6. 鏈棧和順序棧相比

26、，有一個(gè)較明顯的優(yōu)點(diǎn)是A。A.通常不會(huì)出現(xiàn)棧滿的情況B.通常不會(huì)出現(xiàn)?？盏那闆rC插入操作更加方便D.刪除操作更加方便7. 任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在其先根、中根、后根遍歷序列中的相對(duì)位置C。A.肯定發(fā)生變化B.有時(shí)發(fā)生變化 C.肯定不發(fā)生變化D.無(wú)法確定8. 排序方法中，從未排序序列中挑選元素， 將其放入已排序序列的一端的方法，稱(chēng)為D。A.希爾排序B.冒泡排序C.插入排序D. 選擇排序9. 堆是一種什么排序B。A.插入B.選擇C.交換D.歸并10. 以下排序方法中不穩(wěn)定的排序是C。A.直接插入排序B.冒泡排序C.堆排序 D.歸并排序11. 一個(gè)無(wú)向連通圖的生成樹(shù)是含有該連通圖的全部頂點(diǎn)的A。A.

27、極小連通子圖B.極大連通子圖 C.極 小子圖D.極大子圖12. 如下陳述中正確的選項(xiàng)是 A 。A. 串是一種特殊的線性表 B.串的長(zhǎng)度必須 大于零B. 串中元素只能是字母 D.空串就是空白串13. 快速排序不利于發(fā)揮其長(zhǎng)處的情況是C。A 待排序數(shù)據(jù)量太大B待排序數(shù)據(jù) 相同值過(guò)多C待排序數(shù)據(jù)已根本有序D待排序數(shù)據(jù)值差過(guò)大14. 性表中采用折半查找法查找元素，該線性表必須滿足C。A 元素按值有序B 采用順序存儲(chǔ)結(jié)構(gòu)C 元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)D 元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)15. r在排序前已按元素鍵值遞增順序排列，那么比擬次數(shù)較少的排序方法是A。A.直接插入排序B.快速排序C.歸并排

28、序D.選擇排序16. 一個(gè)遞歸的定義可以用遞歸過(guò)程求解，也可以用非遞歸過(guò)程求解，但單從運(yùn)行時(shí) 間來(lái)看，通常遞歸過(guò)程比非遞歸過(guò)程BA.較快B.較慢 C .相同D.不確定17. 如果待排序序列中兩個(gè)數(shù)據(jù)元素具有 相同的值，在排序后它們的位置發(fā)生顛倒， 那么稱(chēng)該排序是不穩(wěn)定的。不穩(wěn)定的排序方法是D。A.起泡排序 B .歸并排序C.直 接插入法排序D .簡(jiǎn)單項(xiàng)選擇擇排序18. 將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層編號(hào)，那么對(duì)編號(hào)為25的結(jié)點(diǎn)X,該結(jié)點(diǎn)B。 A.無(wú)左、右孩子B.有左孩子，無(wú)右孩子C. 有右孩子，無(wú)左孩子D.有左、右孩子19. 假設(shè)某鏈表最常用的操作是在最后一個(gè) 結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最

29、后一個(gè)結(jié)點(diǎn)，那么采用那種存儲(chǔ)方式最節(jié)省時(shí)間C。A.單鏈表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙 循環(huán)鏈表D.單循環(huán)鏈表20. 以下排序算法中，第一趟排序完畢后, 其最大或最小元素一定在其最終位置上的 算法是D。A.歸并排序B.直接插入排序C.快速 排序D.冒泡排序21. 樹(shù)形結(jié)構(gòu)最適合用來(lái)描述 C o A有 序的數(shù)據(jù)元素B無(wú)序的數(shù)據(jù)元素C數(shù)據(jù)元素之間具有層次關(guān)系的數(shù)據(jù)D數(shù)據(jù)元素之間沒(méi)有關(guān)系的數(shù)據(jù)22. 設(shè)有7000個(gè)無(wú)序的元素,希望用最快的速度挑選出其中前5個(gè)最大的元素,最好選用方法是C。A.冒泡排序B.快速排序C.堆排序D.基數(shù)排序23.鏈表不具有的特點(diǎn)是(A)。A.可隨機(jī)訪問(wèn)任一元素B.插入刪除不需要

30、移動(dòng)元素C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性表長(zhǎng)度成正比24. 假設(shè)待排序?qū)ο笮蛄性谂判蚯耙寻雌渑?序碼遞增順序排序，那么比擬次數(shù)最少的方 法排序是A oA.直接插入排序B .快速排序C.歸并排序D .直接選擇排序25. 以下關(guān)鍵字序列中是堆的序列為D。A. 16,72,31,23,94,53 B.94,23,31,72,16,53B. 16,53,23,94,31,72D.16,23,53,31,94,7226. 以下四個(gè)關(guān)鍵字序列中，那個(gè)序列不是 堆C oA. 05,23,16,68,94,72,71,73 B.05,16,23,68,94,72,71,73C. 05,23,16,7

31、3,94,72,71,68 D.05,23,16,68,73,71,72,9427. 下面4個(gè)序列中，滿足堆的定義是 DoA. 13,27,49,76,76,38,85,97 B.C. 13,76,49,76,27,38,85,97 D.28. 采用線性探查法處理沖突所構(gòu)成的散 列表上進(jìn)行查找，可能要探測(cè)到多個(gè)位置， 在查找成功情況下，所探測(cè)的這些位置上 的鍵值D。A. 一定都是同義詞B. 一定都不是同義詞C.都相同D.不一定都是同義詞29. 性表中采用折半查找法查找元素，該線性表必須滿足C。A 元素按值有序B 采用順序存儲(chǔ)結(jié)構(gòu)C 元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)D 元素按值有序，且采用鏈?zhǔn)酱?/p>

32、儲(chǔ)結(jié)構(gòu)1. 對(duì)于一個(gè)隊(duì)列，如果輸入項(xiàng)序列由答：1,2,3,4 o2. 將表達(dá)式a+b *c+d - e+g*h答：后綴表達(dá)式為：ab+c*d+eg+h*-3. 對(duì)于一個(gè)棧，給出輸入序列A, B,三、簡(jiǎn)答1,2,3,4所組成，試給出全部可能的輸出序列。改寫(xiě)成后綴表達(dá)式。C,試給出全部可能的輸出序列。答：解：輸出序列為：ABC CBA,ACB,BAC,BCA4. 將算術(shù)表達(dá)式 a+b* c+d/e 轉(zhuǎn)為后綴表達(dá)式。答：B . abcde/+*+5. 由權(quán)值為12, 6, 5, 9 ,10的五個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，請(qǐng)問(wèn)該樹(shù)的帶權(quán)路徑長(zhǎng)度是多少? 答：權(quán)值為95 。6. 由二叉樹(shù)的前序和后序遍歷

33、序列能否唯一確定一棵二叉樹(shù)。假設(shè)不能請(qǐng)舉出反例。 答：不能唯一確定一棵二叉樹(shù)。如以下圖。廠、1122337.求出以下圖所示有向圖的鄰接矩陣。答：有向圖的鄰接矩陣為:012340廠027OO1 J1OO0OOOOOO2OOOO05OO3OOOOOO0OO43OOOO40J8.有n個(gè)頂點(diǎn)的無(wú)向連通圖至少有多少條邊？有n個(gè)頂點(diǎn)的有向連通圖至少有多少條邊？答：有n個(gè)頂點(diǎn)的無(wú)向連通圖至少有 n-1條邊，有n個(gè)頂點(diǎn)的有向連通圖至少有n條邊。9 下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問(wèn)， 哪些排序方法是穩(wěn)定的？答：起泡排序，直接插入排序，歸并排序是穩(wěn)

34、定的。10. 為什么說(shuō)樹(shù)是一種非線性結(jié)構(gòu)？樹(shù)中的每個(gè)結(jié)點(diǎn)除了根結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)有一個(gè)直接前驅(qū)，但有多個(gè)直接后繼，所以說(shuō)樹(shù)是一種非線性結(jié)構(gòu)。11. 一棵二叉樹(shù)的前序和中序序列，求該二叉樹(shù)的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J中序序列：C, B, A, F, E, D, I, H, J, G答：后序序列為： C, B, F, E, I, J, H, G, D, A12 試述順序存儲(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ù)元素，而鏈表只需要改

35、變一些指針的鏈接, 鏈表比數(shù)組易于實(shí)現(xiàn)數(shù)據(jù)的插入和刪除操作。2) 內(nèi)存空間的占用情況：因鏈表多了一個(gè)指針域，故較浪費(fèi)空間，因此，在空間占用方面，數(shù)組優(yōu)于鏈表。3) 數(shù)據(jù)的存取操作：訪問(wèn)鏈表中的結(jié)點(diǎn)必須從表頭開(kāi)始，是順序的存取方式，而數(shù)組元素的訪問(wèn)是通過(guò)數(shù)組下標(biāo)來(lái)實(shí) 現(xiàn)的，是隨機(jī)存取方式，因此，在數(shù)據(jù)存取方面，數(shù)組優(yōu)于鏈表。4) 數(shù)據(jù)的合并與別離：鏈表優(yōu)于數(shù)組，因?yàn)橹恍枰淖冎羔樀闹赶?3. 將表達(dá)式(a+b)-c*(d+e)-f)*(g+h)改寫(xiě)成后綴表達(dá)式。答：后綴表達(dá)式為：ab+cde+*-f-gh+*14. 將算術(shù)表達(dá)式 a*(b+c)-d 轉(zhuǎn)為后綴表達(dá)式。答：abc+*d-15. 求出

36、以下圖所示有向圖的鄰接表。答：有向圖的鄰接表為:V0V1AV2V3AMead12352° 341A34A116. 試找出中序序列和后序序列相同的所有二叉樹(shù)。答：空樹(shù)或缺右子樹(shù)的單支樹(shù)。17. 用鄰接矩陣存儲(chǔ)一個(gè)包含1000個(gè)頂點(diǎn)和1000條邊的圖，那么該圖的鄰接矩陣中有多少元素？有多少非零元素?答：該圖的鄰接矩陣中有 1000*1000個(gè)元素。該圖的鄰接矩陣中有2000個(gè)非零元素。18. 畫(huà)出以下圖中二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)示意圖。答：二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)示意圖為:15A14ABCD/+E*-?！?丨3丨 rrA0A2A619. 寫(xiě)出中綴表達(dá)式 A-(B+C/D)*E的后綴形式。 答：中

37、綴表達(dá)式 A-(B+C/D)*E的后綴形式是：20. 為什么用二叉樹(shù)表示一般樹(shù)？答：樹(shù)的最直觀表示是為樹(shù)中結(jié)點(diǎn)設(shè)置指向子結(jié)點(diǎn)的指針域，對(duì)k叉樹(shù)而言，每個(gè)結(jié)點(diǎn)除data域外，還有k個(gè)鏈接域。這樣，對(duì)一個(gè)有n個(gè)結(jié)點(diǎn)的k叉樹(shù)來(lái)說(shuō)，共有n*k個(gè)指針域，其中n-1個(gè)不空，另外n(k-1)+1個(gè)指針域?yàn)榭?，因此?空鏈接域的比例約為(k-1 ) /k ，于是導(dǎo)致大量的空間浪費(fèi)。然而，如果采用二叉樹(shù)表示一棵n個(gè)結(jié)點(diǎn)的樹(shù)，那么樹(shù)中共有2n個(gè)鏈接域，其中未用到的有n+1個(gè)，占所有指針域的比例約為1/2，空間浪費(fèi)少很多。另外，因?yàn)槿魏螛?shù)型結(jié)構(gòu)都可以轉(zhuǎn)換成二叉樹(shù)，因此，通常用二叉樹(shù)表示樹(shù)型結(jié)構(gòu)。21請(qǐng)指出一組權(quán)值(

38、7, 5, 2, 4)對(duì)應(yīng)的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度。答：哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是35。22. 試找出前序序列和中序序列相同的所有二叉樹(shù)。解答：空樹(shù)或缺左子樹(shù)的單支樹(shù)。23. 完全二叉樹(shù)用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)最適宜，為什么？答：完全二叉樹(shù)用一維數(shù)組實(shí)現(xiàn)最適宜。因?yàn)橥耆鏄?shù)保存在一維數(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)也不容易。24. 求出以下圖所示無(wú)向圖的鄰接矩陣。01230111精

39、選10 0 110 0 1答：無(wú)向圖的鄰接矩陣為:25. 請(qǐng)構(gòu)造權(quán)值為 5 , 13, 21, 7, 18, 30, 41 的哈夫曼樹(shù)。 答：哈夫曼樹(shù)為：26. 我們已經(jīng)知道，樹(shù)的先根序列與其對(duì)應(yīng)的二叉樹(shù)的先根序列相同，樹(shù)的后根序列與其對(duì)應(yīng)的二叉樹(shù)的中根序列相 同。那么利用樹(shù)的先根遍歷次序與后根遍歷次序，能否唯一確定一棵樹(shù)？請(qǐng)說(shuō)明理由。答：能。因?yàn)闃?shù)的先根序列與其對(duì)應(yīng)的二叉樹(shù)的先根序列相同，樹(shù)的后根序列與其對(duì)應(yīng)的二叉樹(shù)的中根序列相同，而 二叉樹(shù)的先根序列與二叉樹(shù)的中根序列能唯一確定一棵二叉樹(shù)，所以利用樹(shù)的先根遍歷次序與后根遍歷次序，能唯一 確定一棵樹(shù)。27. 請(qǐng)給出如以下圖所示的權(quán)圖的鄰接矩陣

40、。0123 428.OOOOOOOOOOOOOOOOOO1OOOOOO5004求該二叉樹(shù)的后序序列。中序序列：c, b, d, e, a, g, i , h, j , f 前序序列：a, b, c, d, e, f, g, h, i , j 答：該二叉樹(shù)的后序序列為：c,e,d,b,i,j,h,g,f,a29.對(duì)半查找是否適合于以鏈接結(jié)構(gòu)組織的表？ 答：對(duì)半查找不適合于以鏈接結(jié)構(gòu)組織的表。30.請(qǐng)指出中序遍歷二叉查找樹(shù)的結(jié)點(diǎn)可以得到什么樣的結(jié)點(diǎn)序列。 答：中序遍歷二叉查找樹(shù)的結(jié)點(diǎn)就可以得到從小到大排序的結(jié)點(diǎn)序列。 31把以下圖中的森林轉(zhuǎn)化為一棵二叉樹(shù)。解答：森林轉(zhuǎn)化成的二叉樹(shù)如以下圖。78精選

41、32. 指出一般樹(shù)的存儲(chǔ)結(jié)構(gòu)有哪幾種?答：樹(shù)的存儲(chǔ)結(jié)構(gòu)有雙親表示法、孩子鏈表表示法和孩子兄弟表示法33. 試找出前序序列和后序序列相同的所有二叉樹(shù)。答：空樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)。34. 線性表有兩種存儲(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ù)雜度為35. 求出以下圖所示無(wú)向圖的鄰接表。答：無(wú)向圖的鄰接表為:V0V1V2V33A2AHead36. 一個(gè)圖如下所示，假設(shè)從頂點(diǎn)0出發(fā)

42、求出其廣度優(yōu)先搜索序列。解答：廣度優(yōu)先搜索序列：0123456737. 一組記錄的關(guān)鍵字為 (52, 56, 26, 12, 69, 85, 33, 48, 70)，給出快速排序的過(guò)程。解答：解：52, 56, 26, 12, 69, 85, 33, 48, 70第一趟排序33, 48, 26, 12, 52, 85, 69, 56, 70第二趟排序26, 12, 33, 4.52, 69, 56, 70, 85第三趟排序12,26,33, 48,_52,_56,70, 69, 85第四趟排序12,26,33, 4L52衛(wèi)6,血 69,85第五趟排序12,26,33, 452衛(wèi)6,屯 69,8

43、5 38. 下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問(wèn), 哪些排序方法是穩(wěn)定的？起泡排序，直接插入排序，歸并排序是穩(wěn)定的。39. 一棵二叉樹(shù)的前序和中序序列，求該二叉樹(shù)的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, F, E, D, I, H, J, G 答：后序序列為:C, B, F, E, I, J, H, G, D, A40. 把以下圖中的二叉樹(shù)轉(zhuǎn)化成森林。答案:41. 給定表(43,36,56,6,64,32,8,41),按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹(shù)，并求其平

44、均查找長(zhǎng)度。解答：根據(jù)給定表(43,36,56,6,64,32,8,41)，構(gòu)造的二叉查找樹(shù)如以下圖；其平均查找長(zhǎng)度為：23/8。42. 將以下圖中的二叉樹(shù)，轉(zhuǎn)換成相應(yīng)的森林。答：森林轉(zhuǎn)化成的二叉樹(shù)如以下圖。DCBGEAHFIJK按后根遍歷所得到的結(jié)點(diǎn)序列為DCEGBFHKJI，畫(huà)出該43. 知二叉樹(shù)按中根遍歷所得到的結(jié)點(diǎn)序列為 樹(shù)形結(jié)構(gòu)，并按中根遍歷序列進(jìn)行線索化答：44. 對(duì)于以下圖所示的二叉樹(shù)，試分別寫(xiě)出先根遍歷、中根遍歷該樹(shù)所得到的先根序列、中根序列。EICFJBGDKHLA答：先根遍歷的結(jié)點(diǎn)序列：ABCEIFJDGHK，中遍歷的結(jié)點(diǎn)序列:46.把以下圖中的二叉樹(shù)轉(zhuǎn)化成森林。1，給出快

45、速排序的過(guò)程。47. 一組記錄的關(guān)鍵字為 (52, 56, 26, 12, 69, 85, 33, 48, 70)解答：解：52, 56, 26, 12, 69, 85, 33, 48, 70第一趟排序33, 48, 26, 12, 52, 85, 69, 56, 70第二趟排序 26, 12, 33, 4玄52, 69, 56, 70, 85第三趟排序 12, 26, 33, 452衛(wèi)6,屯 69, 85 第四趟排序 12, 26, 33, 4卻2衛(wèi)6,衛(wèi)69,85 第五趟排序 12, 26, 33, 48, 52, 56, 70, 69, 8548.設(shè)記錄的關(guān)鍵字集合 key=51,28,

46、38,86,70,90,7,30,40,251)時(shí)，各趟排序結(jié)束后的結(jié)果。 解答：各趟排序結(jié)束后的結(jié)果。初始狀態(tài)：51 28388670 90 7304025第一趟排序(d=5):5173040259028388670第二趟排序(d=3):2873040258651389070第三趟排序(d=1):7252830384051708690，試寫(xiě)出對(duì)key進(jìn)行漸減增量排序增量d = 5 , 3,49.有一棵二叉樹(shù)如以下圖所示，分別指出其前序、中序遍歷的結(jié)點(diǎn)序列。答：它的前序序列為：ABCDEFGHIJ它的中序序列為：CDBAFGEIH。50.8個(gè)記錄，對(duì)應(yīng)的關(guān)鍵詞為：25,84,21,47,15,

47、27,68,35,20寫(xiě)出快速排序的第一趟排序過(guò)程圖示。答：初始鍵值序列25 84 21 47 15 27 68 35 20第一次交換25 84 21 47 15 27 68 35 20門(mén)=2 門(mén)=9第二次交換25 20 21 47 15 27 68 35 84i J f j掃描交叉25 20 21 15 47 27 68 35 84j f iRn與 R 互換25 20 21 15 47 27 68 35 84Rm fj.f分劃表 15 20 21 25 47 27 68 35 8451.給定表(40,9,56,6,39,73,8,23),按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹(shù)。答：二叉排序

48、樹(shù)如下。CBAEDF試畫(huà)出該二叉樹(shù)。答：二叉查找樹(shù)如下，平均查找長(zhǎng)度為),按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹(shù)，并求其平均查找長(zhǎng)度。3。53. 根據(jù)以下圖給出的二叉樹(shù)，求出先序、中序遍歷的結(jié)點(diǎn)序列。答：先序遍歷為：abdcef，并給出堆(D)第3次交換8'.3241：(50) (56)(79 蠢中序遍歷為：dbaefc54. 一組記錄的關(guān)鍵字為(50, 79, 8, 56, 32, 41, 85),給出利用重建堆方法建立的初始堆(堆頂最大)排序的過(guò)程。答：1) 建立的初始堆為：85 , 79, 50, 56, 32, 41, 82 )堆排序的過(guò)程如下：(g)第6次交換55. 答：把

49、以下森林轉(zhuǎn)化為56.數(shù)據(jù)序列為12,5,9,20,6,31,24，對(duì)該數(shù)據(jù)序列進(jìn)行排序，試寫(xiě)出冒泡排序每趟的結(jié)果。答：初始鍵值序列第一趟排序5第二趟排序5第三趟排序5第四趟排序512 5 9 20 6 31 249 12 6 20 24 319 6 12 20 24 319 6 12 20 24 316 9 12 20 24 3157.給定表40,36,55,6,64,77,9,41),按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹(shù)，并求其平均查找長(zhǎng)度。答：森林轉(zhuǎn)化成的二叉樹(shù)如以下圖。答：構(gòu)造的二叉查找樹(shù)如以下圖，其平均查找長(zhǎng)度為11/4。58. 對(duì)于以下圖所示的二叉樹(shù)，試分別寫(xiě)出先根遍歷、中根遍歷

50、和后根遍歷該樹(shù)所得到的先根序列、中根序列和后根序 列。解答：先根遍歷的結(jié)點(diǎn)序列：ABCEIFJDGHKL中遍歷的結(jié)點(diǎn)序列：EICFJBGDKHLA后根遍歷的結(jié)點(diǎn)序列：IEJFCGKLHDBA59. 數(shù)據(jù)序列為12,5,9,20,6,31,24，對(duì)該數(shù)據(jù)序列進(jìn)行排序，試寫(xiě)出歸并排序每趟的結(jié)果。解答：初始鍵值序列 12 5 9 20 6 31 24第一趟排序5 12 9 20 6 31 24第二趟排序59 1220 6 2431第三趟排序56912 20 2431()中，用二分法查找關(guān)鍵詞 36,進(jìn)行多少次比擬后查找成功?60. 序表(5, 12, 17, 19, 23, 25, 30, 36,

51、45, 49, 58) 寫(xiě)出查找過(guò)程。解答：經(jīng)過(guò)4次比擬查找成功。查找過(guò)程如下：5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58i=11m=61 j=115, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58 t f I i=7m=9j=11(B)第2次與45進(jìn)行比擬(A)第1次與25進(jìn)行比擬5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 585, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58i=7 j=8tm=7(C)第3次與30進(jìn)行比擬i=8I i j=8m=8(D)

52、第4次與36進(jìn)行比擬61. 一組記錄的關(guān)鍵字為 (52, 56, 26, 12, 69, 85, 33, 48, 70)解答：52, 56, 26, 12, 69, 85, 33, 48, 70，給出快速排序的過(guò)程。第一趟排序33,48,26, 12, 52, 85,險(xiǎn) 56,70第二趟排序26,12,33, 4玄52, 69,56, 70,85第三趟排序12,26,33, 4L52臣6,70. 69,85第四趟排序 12, 26, 33, 48526,衛(wèi) 69,85第五趟排序12, 26, 33, 48, 52, 56, 70, 69, 8562. 某二叉樹(shù)的后序序列為：ABCDEFG中序序列為：ACBGEDf給出它的前序序列。解：它的前序序列為： GCABFED63. 根據(jù)以下圖給出的二叉樹(shù)，求出中序和后序遍歷的結(jié)點(diǎn)序列。ce解答0643解答4536566432406