數(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.鄰接表的存儲結(jié)構(gòu)下圖的深度優(yōu)先遍歷類似于二叉樹的(先序遍歷)。3.在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（2）。4.某二叉樹的前序和后序序列正好相反，則該二叉樹一定是什么二叉樹(高度等于其結(jié)點(diǎn)數(shù))。5.對于棧操作數(shù)據(jù)的原則是（后進(jìn)先出 ）。6.結(jié)點(diǎn)前序?yàn)閤yz的不同二叉樹，所具有的不同形態(tài)為(5 )。7.設(shè)長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度為(O(n) )。8.在一棵高度為h(假定樹根結(jié)點(diǎn)的層號為0)的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不

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

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

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

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

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

7、叉樹的深度為h，則該完全二叉樹中具有的結(jié)點(diǎn)數(shù)至少是(2h1)。45.叉樹的前序和后序序列正好相反，則該二叉樹一定是什么二叉樹(度等于其結(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.用冒泡排序法對序列18,16,14,12,10,8從小到大進(jìn)行排序，需要進(jìn)行的比較次數(shù)是(15)。49.有n個(gè)頂點(diǎn)的圖采用鄰接矩陣表示，則該矩陣的大小為（n*n）。50.6個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（5）。51.單鏈表中，增加頭結(jié)點(diǎn)的目的是為了（方便運(yùn)算的實(shí)現(xiàn)）。52

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

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

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

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

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

13、序列可唯一確定這棵二叉樹 。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ù)最大的結(jié)點(diǎn)的層數(shù)加1，則高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為k，最多為2k-1。92.在直接插入排序、直接選擇排序、分劃交換排序、堆排序中穩(wěn)定的排序方法有直接插入排序。93.具有100個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為50。94.普里姆(Prim)算法適用于邊稠密圖。95.在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中,其結(jié)點(diǎn)總數(shù)為2n-1。96.將一棵樹轉(zhuǎn)換成一棵二叉樹后，二叉樹根結(jié)點(diǎn)沒有右子樹。97.矩陣采用壓縮存儲是為了

14、節(jié)省空間98.若連通網(wǎng)絡(luò)上各邊的權(quán)值均不相同，則該圖的最小生成樹有1棵。99.設(shè)無向圖G的頂點(diǎn)數(shù)為n，則要使G連通最少有n-1條邊。100.棧和隊(duì)列的共同特點(diǎn)是插入和刪除均在端點(diǎn)處進(jìn)行。101.克魯斯卡爾(Kruskar)算法適用于邊稀疏圖。102.若連通圖的頂點(diǎn)個(gè)數(shù)為n，則該圖的生成樹的邊數(shù)為n-1。103.圖的存儲結(jié)構(gòu)最常用的有鄰接矩陣和鄰接表。104.由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。105.隊(duì)列中允許進(jìn)行插入的一端稱為隊(duì)尾。106.拓?fù)渑判蜉敵龅捻旤c(diǎn)數(shù)小于有向圖的頂點(diǎn)數(shù)，則該圖一定存在環(huán)。107.在有序表(15,23,24,45,48,62,85)中二分查找關(guān)鍵詞2

15、3時(shí)所需進(jìn)行的關(guān)鍵詞比較次數(shù)為2。108.樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（-1）。109.在一個(gè)具有n個(gè)頂點(diǎn)的完全無向圖的邊數(shù)為 (n(n-1)/2)。110.用分劃交換排序方法對包含有n個(gè)關(guān)鍵的序列進(jìn)行排序，最壞情況下執(zhí)行的時(shí)間雜度為(O(n2)111.一棵高度為h(假定樹根結(jié)點(diǎn)的層號為0)的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于(2h)。112.若長度為n的非空線性表采用順序存儲結(jié)構(gòu)，刪除表的第i個(gè)數(shù)據(jù)元素，首先需要移動表中數(shù)據(jù)元素的個(gè)數(shù)是（n-i）。113.在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該(只有左子樹上的所有結(jié)點(diǎn))。114.若一棵二叉樹具有45個(gè)度為2的結(jié)點(diǎn)，6個(gè)度為1

16、的結(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采用順序存儲結(jié)構(gòu)，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的起始地址為100，則該數(shù)組的首地址是（70）。118.設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作,則下面得不到的序列為（cbdef）。119.一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置（堆棧）。120.若長度為n的非空線性表采用順序存儲結(jié)構(gòu)，刪除表的第i個(gè)數(shù)據(jù)元素，i的合法值應(yīng)該121.是（C. 1in）。1

17、22.若某線性表中最常用的操作是取第i個(gè)元素和刪除最后一個(gè)元素，則采用什么存儲方123.式最節(jié)省時(shí)間（順序表）。124.一組記錄的關(guān)鍵字為45, 80, 55, 40, 42, 85，則利用堆排序的方法建立的初始堆為（85, 80, 55, 40, 42, 45）。125.設(shè)有6000個(gè)無序的元素,希望用最快的速度挑選出其中前5個(gè)最大的元素,最好選用(堆排序)法。126.排序方法中，從未排序序列中挑選元素，將其放入已排序序列的一端的方法，稱為(選擇排序)。127.帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是(head->next=NULL)。128.在一個(gè)單鏈表中，若刪除(*p)結(jié)點(diǎn)的后繼結(jié)

18、點(diǎn)，則執(zhí)行(p->next=p->next->next)。129.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于（n+1）130.有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目，稱為頂點(diǎn)v的（入度）。131.若頻繁地對線性表進(jìn)行插入和刪除操作，該線性表應(yīng)該采用的存儲結(jié)構(gòu)是（鏈?zhǔn)剑?32.設(shè)一個(gè)棧的輸入序列是 1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（3 2 1 5 4）。133.有數(shù)據(jù)53，30，37，12，45，24，96，從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉查找樹，若希望高度最小，則應(yīng)選擇下面輸入序列是（37,24,12,30,53,45,96）。134.二

19、叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（2I）。135.稀疏矩陣一般采用的壓縮存儲方法為(三元組表)。136.某二叉樹的前序和后序序列正好相同，則該二叉樹一定是什么樣的二叉樹(空或只有一個(gè)結(jié)點(diǎn))。137.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在表的第i個(gè)位置插入一個(gè)數(shù)據(jù)元素，需要移動表中元素的個(gè)數(shù)是（n-i+1）。138.設(shè)有數(shù)組Ai,j，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A5，8的存儲首地址為(BA+180)。139.二維數(shù)組A56的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先順序存儲在起始地址為3000的連續(xù)的內(nèi)存單元中

20、，則元素A45的存儲地址為（3145）。140.一個(gè)具有n個(gè)頂點(diǎn)的圖采用鄰接矩陣表示，則該矩陣的大小為（n*n）。141.若字符串“1234567”采用鏈?zhǔn)酱鎯Γ僭O(shè)每個(gè)字符占用1個(gè)字節(jié)，每個(gè)指針占用2個(gè)字節(jié)，則該字符串的存儲密度為（33.3）。142.若在一棵非空樹中，某結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)（包括A自身），B是A的雙親結(jié)點(diǎn)，則B的度為（3）。143.設(shè)有三個(gè)元素X，Y，Z順序進(jìn)棧（進(jìn)的過程中允許出棧），下列得不到的出棧排列是(ZXY)。144.樹形結(jié)構(gòu)的特點(diǎn)是：一個(gè)結(jié)點(diǎn)可以有 (多個(gè)直接后繼)。145.使具有30個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（29）。146.使具有9個(gè)頂點(diǎn)的

21、無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是（8）。147.在順序表（n足夠大）中進(jìn)行順序查找，其查找不成功的平均長度是（n+1 ）。148.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（8）。149.棧的插入和刪除操作進(jìn)行的位置在（棧頂）。150.若一棵二叉樹具有20個(gè)度為2的結(jié)點(diǎn)，6個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（21）。151.一棵線索二叉樹的線索個(gè)數(shù)比鏈接個(gè)數(shù)多（2）個(gè)。152.在循環(huán) 鏈表中，從任何一結(jié)點(diǎn)出發(fā)都能訪問到表中的所有結(jié)點(diǎn)。153.在n個(gè)結(jié)點(diǎn)的順序表中插入一個(gè)結(jié)點(diǎn)需平均移動 n/2 個(gè)結(jié)點(diǎn)。 154.循環(huán)隊(duì)列的引入，目的是為了克服假

22、溢出 。155.若連通網(wǎng)絡(luò)上各邊的權(quán)值均不相同，則該圖的最小生成樹有1棵 。156.二叉樹的遍歷方式有三種：先序遍歷、中序遍歷、后序遍歷。157.若一棵二叉樹有15個(gè)葉結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)的點(diǎn)個(gè)數(shù)為14。158.設(shè)某二叉樹的后序遍歷序列為ABKCBPM，則可知該二叉樹的根為M 。159.數(shù)據(jù)結(jié)構(gòu)的三個(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)的二叉樹采用鏈接結(jié)構(gòu)存儲，鏈表中存放NULL指針域的個(gè)數(shù)為（n+1）。163.在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（2）倍。164設(shè)二叉樹

23、根結(jié)點(diǎn)的層次為0，一棵高度為h 的滿二叉樹中的結(jié)點(diǎn)個(gè)數(shù)是(2h+1-1)。165.將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹按層編號，則對編號為25的結(jié)點(diǎn)x，該結(jié)點(diǎn)(有左孩子，無右孩子)。166.樹（或樹形）的定義是什么？答：一個(gè)樹（或樹形）就是一個(gè)有限非空的結(jié)點(diǎn)集合T，其中有一個(gè)特別標(biāo)出的稱為該樹之根root（T）的結(jié)點(diǎn)；其余（除根外）的結(jié)點(diǎn)劃分成個(gè)不相交集合,而且這些集合的每一個(gè)又都是樹。167 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以有(任意多個(gè) )。168.什么是樹的路徑長度？答：樹的路徑長度是指從根結(jié)點(diǎn)到樹中每個(gè)葉結(jié)點(diǎn)的路徑長度之和。二、選擇1.若某線性表中最常用的操作是取第i個(gè)元素和

24、刪除最后一個(gè)元素，則采用什么存儲方式最節(jié)省時(shí)間（A）。A. 順序表 B. 單鏈表C. 雙鏈表D. 單循環(huán)鏈表2.在下述的排序方法中，不屬于內(nèi)排序方法的是（C）。A.插入排序法 B.選擇排序法C.拓?fù)渑判蚍―.歸并排序法3.下列四個(gè)關(guān)鍵詞序列中,不是堆的序列為(C)。A.05,23,16,68,94,72,71,73 B.05,16,23,68,94,72,71,73 C.05,23,16,73,94,72,71,68 D.05,23,16,68,73,71,72,94 4.下列排序算法中,某一趟結(jié)束后未必能選出一個(gè)元素放其最終位置上的是( D )。A. 堆排序 B. 冒泡排序C. 快速排序D.

25、 直接插入排序5.用孩子兄弟鏈表表示一棵樹，若要找到結(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.鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是(A)。A.通常不會出現(xiàn)棧滿的情況 B. 通常不會出現(xiàn)棧空的情況C插入操作更加方便 D.刪除操作更加方便7.任何一棵二叉樹的葉結(jié)點(diǎn)在其先根、中根、后根遍歷序列中的相對位置(C)。A. 肯定發(fā)生變化 B. 有時(shí)發(fā)生變化 C. 肯定不發(fā)生變化D. 無法確定 8.排序方法中，從未排序序列中挑選元素，將其放入已

26、排序序列的一端的方法，稱為(D)。A.希爾排序 B. 冒泡排序 C. 插入排序D. 選擇排序9.堆是一種什么排序（B）。A.插入 B. 選擇 C. 交換D. 歸并10.下列排序方法中不穩(wěn)定的排序是 (C)。A.直接插入排序 B. 冒泡排序 C. 堆排序 D. 歸并排序11.一個(gè)無向連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的 (A)。A.極小連通子圖 B. 極大連通子圖C. 極小子圖 D. 極大子圖12.如下陳述中正確的是(A )。A.串是一種特殊的線性表B.串的長度必須大于零B.串中元素只能是字母D.空串就是空白串13.快速排序不利于發(fā)揮其長處的情況是（C）。A 待排序數(shù)據(jù)量太大 B 待排序數(shù)據(jù)

27、相同值過多 C 待排序數(shù)據(jù)已基本有序D 待排序數(shù)據(jù)值差過大14.性表中采用折半查找法查找元素，該線性表必須滿足（C）。A 元素按值有序 B 采用順序存儲結(jié)構(gòu) C 元素按值有序，且采用順序存儲結(jié)構(gòu) D 元素按值有序，且采用鏈?zhǔn)酱鎯Y(jié)構(gòu)15.r在排序前已按元素鍵值遞增順序排列，則比較次數(shù)較少的排序方法是(A) 。A.直接插入排序 B.快速排序 C.歸并排序D.選擇排序16.一個(gè)遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運(yùn)行時(shí)間來看，通常遞歸過程比非遞歸過程（B）A較快B較慢 C相同D.不確定17.如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱該排序是不

28、穩(wěn)定的。不穩(wěn)定的排序方法是（D）。A起泡排序 B歸并排序C直接插入法排序 D簡單選擇排序18.將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹按層編號，則對編號為25的結(jié)點(diǎn)x，該結(jié)點(diǎn)(B)。A.無左、右孩子 B. 有左孩子，無右孩子C.有右孩子，無左孩子 D.有左、右孩子19.若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用那種存儲方式最節(jié)省時(shí)間(C)。A. 單鏈表 B. 雙鏈表C. 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D. 單循環(huán)鏈表20.下列排序算法中,第一趟排序完畢后,其最大或最小元素一定在其最終位置上的算法是( D )。A. 歸并排序 B. 直接插入排序 C. 快速排序 D. 冒泡排序

29、21.樹形結(jié)構(gòu)最適合用來描述（C）。A 有序的數(shù)據(jù)元素B 無序的數(shù)據(jù)元素C 數(shù)據(jù)元素之間具有層次關(guān)系的數(shù)據(jù)D 數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù)22.設(shè)有7000個(gè)無序的元素,希望用最快的速度挑選出其中前5個(gè)最大的元素,最好選用方法是(C)。A.冒泡排序B.快速排序C. 堆排序 D.基數(shù)排序23.鏈表不具有的特點(diǎn)是(A)。A.可隨機(jī)訪問任一元素 B.插入刪除不需要移動元素C.不必事先估計(jì)存儲空間 D.所需空間與線性表長度成正比24.若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，則比較次數(shù)最少的方法排序是（A）。A直接插入排序 B快速排序C歸并排序 D直接選擇排序25.下列關(guān)鍵字序列中是堆的序列為(

30、D)。A.16,72,31,23,94,53 B. 94,23,31,72,16,53 B.16,53,23,94,31,72D. 16,23,53,31,94,7226.下列四個(gè)關(guān)鍵字序列中,那個(gè)序列不是堆(C)。A. 05,23,16,68,94,72,71,73 B. 05,16,23,68,94,72,71,73 C. 05,23,16,73,94,72,71,68 D. 05,23,16,68,73,71,72,94 27.下面4個(gè)序列中，滿足堆的定義是（D）。A. 13,27,49,76,76,38,85,97 B. 76,38,27,49,76,85,13,97C. 13,76,

31、49,76,27,38,85,97 D. 13,27,38,76,49,85,76,9728.采用線性探查法處理沖突所構(gòu)成的散列表上進(jìn)行查找，可能要探測到多個(gè)位置，在查找成功情況下，所探測的這些位置上的鍵值（D）。A. 一定都是同義詞B. 一定都不是同義詞 C. 都相同 D. 不一定都是同義詞29.性表中采用折半查找法查找元素，該線性表必須滿足（C）。A 元素按值有序 B 采用順序存儲結(jié)構(gòu) C 元素按值有序，且采用順序存儲結(jié)構(gòu) D 元素按值有序，且采用鏈?zhǔn)酱鎯Y(jié)構(gòu) 三、簡答1.對于一個(gè)隊(duì)列，如果輸入項(xiàng)序列由1,2,3,4所組成，試給出全部可能的輸出序列。答：1,2,3,4。2. 將表達(dá)式 (a

32、+b) *c+d - (e+g)*h 改寫成后綴表達(dá)式。答： 后綴表達(dá)式為：ab+c*d+eg+h*- 3.對于一個(gè)棧，給出輸入序列A，B，C，試給出全部可能的輸出序列。答：解：輸出序列為：ABC，CBA,ACB,BAC,BCA。4將算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式。答： Babcde/+*+ 5.由權(quán)值為12，6，5，9 ,10的五個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，請問該樹的帶權(quán)路徑長度是多少？答：權(quán)值為 95 。6. 由二叉樹的前序和后序遍歷序列能否唯一確定一棵二叉樹。若不能請舉出反例。答：不能唯一確定一棵二叉樹。如下圖。1231237.求出下圖所示有向圖的鄰接矩陣。V0V4V3V

33、2V1213457答：有向圖的鄰接矩陣為： 0 2 7 1 0 0 5 0 3 4 0 0 1 2 3 4012348.有個(gè)頂點(diǎn)的無向連通圖至少有多少條邊？有個(gè)頂點(diǎn)的有向連通圖至少有多少條邊？答：有個(gè)頂點(diǎn)的無向連通圖至少有n-1條邊，有個(gè)頂點(diǎn)的有向連通圖至少有n條邊。9下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩(wěn)定的？答：起泡排序, 直接插入排序，歸并排序是穩(wěn)定的。10.為什么說樹是一種非線性結(jié)構(gòu)？樹中的每個(gè)結(jié)點(diǎn)除了根結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)有一個(gè)直接前驅(qū)，但有多個(gè)直接后繼，所以說樹是一種非線性結(jié)構(gòu)。11已知一棵二叉樹的前序和

34、中序序列，求該二叉樹的后序序列。前序序列：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試述順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別及各自的優(yōu)缺點(diǎn)。答：數(shù)組占用連續(xù)的內(nèi)存空間，鏈表不要求結(jié)點(diǎn)的空間連續(xù)。1）插入與刪除操作：由于數(shù)組在插入與刪除數(shù)據(jù)時(shí)需移動大量的數(shù)據(jù)元素，而鏈表只需要改變一些指針的鏈接，因此，鏈表比數(shù)組易于實(shí)現(xiàn)數(shù)據(jù)的插入和刪除操作。 2）內(nèi)存空間的占用情況：因鏈表多了一個(gè)指針域，故較浪費(fèi)空間，因此，在空間占用方面，數(shù)組優(yōu)于鏈表。 3）數(shù)據(jù)的存取操

35、作：訪問鏈表中的結(jié)點(diǎn)必須從表頭開始，是順序的存取方式，而數(shù)組元素的訪問是通過數(shù)組下標(biāo)來實(shí)現(xiàn)的，是隨機(jī)存取方式，因此，在數(shù)據(jù)存取方面，數(shù)組優(yōu)于鏈表。4） 數(shù)據(jù)的合并與分離：鏈表優(yōu)于數(shù)組，因?yàn)橹恍枰淖冎羔樀闹赶?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-15.求出下圖所示有向圖的鄰接表。V0V4V3V2V1213457答：有向圖的鄰接表為：V0V1V2V3V4122741353403Head16試找出中序序列和后序序列相同的所有二叉樹。答：空樹

36、或缺右子樹的單支樹。17.用鄰接矩陣存儲一個(gè)包含1000個(gè)頂點(diǎn)和1000條邊的圖，則該圖的鄰接矩陣中有多少元素？有多少非零元素？答：該圖的鄰接矩陣中有1000*1000個(gè)元素。該圖的鄰接矩陣中有2000個(gè)非零元素。18.畫出下圖中二叉樹的順序存儲結(jié)構(gòu)示意圖。13715答：二叉樹的順序存儲結(jié)構(gòu)示意圖為：13715 A0 A2 A6 A1419.寫出中綴表達(dá)式A-(B+C/D)*E的后綴形式。答：中綴表達(dá)式A-(B+C/D)*E的后綴形式是：ABCD/+E*-。20 為什么用二叉樹表示一般樹？ 答：樹的最直觀表示是為樹中結(jié)點(diǎn)設(shè)置指向子結(jié)點(diǎn)的指針域，對k叉樹而言，每個(gè)結(jié)點(diǎn)除data域外，還有k個(gè)鏈接

37、域。這樣，對一個(gè)有n個(gè)結(jié)點(diǎn)的k叉樹來說，共有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)。 21請指出一組權(quán)值（7，5，2，4）對應(yīng)的哈夫曼樹的帶權(quán)路徑長度。答：哈夫曼樹的帶權(quán)路徑長度是35。22試找出前序序列和中序序列相同的所有二叉樹。解答：空樹或缺左子樹的單支樹。23完全二叉樹用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)最

38、合適，為什么？答：完全二叉樹用一維數(shù)組實(shí)現(xiàn)最合適。因?yàn)橥耆鏄浔４嬖谝痪S數(shù)組中時(shí)，數(shù)組內(nèi)沒有空洞，不存在空間浪費(fèi)問題；另外，順序存儲方式下，父子結(jié)點(diǎn)之間的關(guān)系可用公式描述，即已知父（或子）結(jié)點(diǎn)尋找子（或父）結(jié)點(diǎn)只需計(jì)算一個(gè)公式，訪問結(jié)點(diǎn)方便。但采用鏈表存儲時(shí)就存在空間浪費(fèi)問題，因?yàn)槊總€(gè)結(jié)點(diǎn)要另外保存兩個(gè)鏈接域，并且尋找結(jié)點(diǎn)也不容易。24.求出下圖所示無向圖的鄰接矩陣。V0V1V2V301230 1 1 11 0 0 11 0 0 11 1 1 00 1 2 3答：無向圖的鄰接矩陣為： 539132541805513571221183025.請構(gòu)造權(quán)值為 5，13，21，7，18，30，41

39、的哈夫曼樹。答：哈夫曼樹為： 26我們已經(jīng)知道，樹的先根序列與其對應(yīng)的二叉樹的先根序列相同，樹的后根序列與其對應(yīng)的二叉樹的中根序列相同。那么利用樹的先根遍歷次序與后根遍歷次序，能否唯一確定一棵樹？請說明理由。答：能。因?yàn)闃涞南雀蛄信c其對應(yīng)的二叉樹的先根序列相同，樹的后根序列與其對應(yīng)的二叉樹的中根序列相同，而二叉樹的先根序列與二叉樹的中根序列能唯一確定一棵二叉樹，所以利用樹的先根遍歷次序與后根遍歷次序，能唯一確定一棵樹。 27請給出如下圖所示的權(quán)圖的鄰接矩陣。V0V4V3V2V1213457答：解：0 2 7 1 0 0 5 0 3 4 0 0 1 2 3 40123428已知一棵二叉樹的中序

40、和前序序列如下，求該二叉樹的后序序列。中序序列：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,a29 對半查找是否適合于以鏈接結(jié)構(gòu)組織的表？答：對半查找不適合于以鏈接結(jié)構(gòu)組織的表。30. 請指出中序遍歷二叉查找樹的結(jié)點(diǎn)可以得到什么樣的結(jié)點(diǎn)序列。答：中序遍歷二叉查找樹的結(jié)點(diǎn)就可以得到從小到大排序的結(jié)點(diǎn)序列。31把下圖中的森林轉(zhuǎn)化為一棵二叉樹。12684735解答： 森林轉(zhuǎn)化成的二叉樹如下圖。1268473532.指出一般樹的存儲結(jié)構(gòu)有哪幾種？答：樹的存儲結(jié)構(gòu)有雙親表示法、孩子鏈表表示法和孩子兄弟

41、表示法 33. 試找出前序序列和后序序列相同的所有二叉樹。答：空樹或只有根結(jié)點(diǎn)的二叉樹。34.線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：如果有 n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)？ 為什么？答：選鏈?zhǔn)酱鎯Y(jié)構(gòu)。它可動態(tài)申請內(nèi)存空間，不受表長度（即表中元素個(gè)數(shù)）的影響，插入、刪除時(shí)間復(fù)雜度為O35.求出下圖所示無向圖的鄰接表。V0V1V2V3V0V1V2V31320303021Head答：無向圖的鄰接表為：36. 已知一個(gè)圖如下所示，若從頂點(diǎn)0出發(fā)求出其廣度優(yōu)先搜索序列。03425167解答： 廣度優(yōu)先搜索

42、序列：0123456737.一組記錄的關(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, 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, 7

43、0, 69, 8538下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩(wěn)定的？起泡排序, 直接插入排序，歸并排序是穩(wěn)定的。39已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：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把下圖中的二叉樹轉(zhuǎn)化成森林。1268473512684735答案：41.給定表（43,36,56,6,64,32,8,41），按數(shù)據(jù)元素在表中的次

44、序構(gòu)造一棵二叉查找樹，并求其平均查找長度。解答：根據(jù)給定表（43,36,56,6,64,32,8,41），構(gòu)造的二叉查找樹如下圖；其平均查找長度為：23/8。6483241656364342將下圖中的二叉樹，轉(zhuǎn)換成相應(yīng)的森林。ABCHFDJEILKGNM答：森林轉(zhuǎn)化成的二叉樹如下圖。JCHEKFILNMABDG 43. 知二叉樹按中根遍歷所得到的結(jié)點(diǎn)序列為DCBGEAHFIJK， 按后根遍歷所得到的結(jié)點(diǎn)序列為DCEGBFHKJIA，畫出該樹形結(jié)構(gòu)，并按中根遍歷序列進(jìn)行線索化。答：HKFGCIBAJED44.對于下圖所示的二叉樹，試分別寫出先根遍歷、中根遍歷該樹所得到的先根序列、中根序列。GFE

45、DCBALKJIH答：先根遍歷的結(jié)點(diǎn)序列：ABCEIFJDGHKL，中遍歷的結(jié)點(diǎn)序列：EICFJBGDKHLA46把下圖中的二叉樹轉(zhuǎn)化成森林。1268473512684735答：二叉樹轉(zhuǎn)化成的森林如下圖。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, 48, 52, 69, 56, 70, 85第三趟排序 12, 26, 33, 48

46、, 52, 56, 70, 69, 85第四趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85第五趟排序 12, 26, 33, 48, 52, 56, 70, 69, 8548. 設(shè)記錄的關(guān)鍵字集合key=51,28,38,86,70,90,7,30,40,25，試寫出對key進(jìn)行漸減增量排序（增量d = 5，3，1）時(shí)，各趟排序結(jié)束后的結(jié)果。解答：各趟排序結(jié)束后的結(jié)果。初始狀態(tài)：51 28 38 86 70 90 7 30 40 25第一趟排序(d=5): 51 7 30 40 25 90 28 38 86 70第二趟排序(d=3): 28 7 30 40 25

47、86 51 38 90 70第三趟排序(d=1): 7 25 28 30 38 40 51 70 86 90）49.有一棵二叉樹如下圖所示，分別指出其前序、中序遍歷的結(jié)點(diǎn)序列。ABHGFEDCIJ答：它的前序序列為：ABCDEFGHIJ,它的中序序列為：CDBAFGEIHJ。50.已知8個(gè)記錄，對應(yīng)的關(guān)鍵詞為：25,84,21,47,15,27,68,35,20寫出快速排序的第一趟排序過程圖示。答：初始鍵值序列25 84 21 47 15 27 68 35 20 第一次交換 25 84 21 47 15 27 68 35 20 i=2 j=9第二次交換 25 20 21 47 15 27 68

48、 35 84i j掃描交叉 25 20 21 15 47 27 68 35 84j iRm與Rj互換 25 20 21 15 47 27 68 35 84 Rm j分劃表 15 20 21 25 47 27 68 35 8451.給定表（40,9,56,6,39,73,8,23），按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹。答：.二叉排序樹如下。409563986237352.有二叉樹先序序列為：ABCDEF,中序序列為：CBAEDF,試畫出該二叉樹。答：二叉樹如下圖。ACDFEB53.給定表（40,36,56,6,64,73,8,23），按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹，并求其平均查找

49、長度。答：二叉查找樹如下，平均查找長度為3。4036566486237353根據(jù)下圖給出的二叉樹，求出先序、中序遍歷的結(jié)點(diǎn)序列。acedfb答：先序遍歷為：abdcef 中序遍歷為：dbaefc 54. 一組記錄的關(guān)鍵字為（50，79，8，56，32，41，85），給出利用重建堆方法建立的初始堆（堆頂最大），并給出堆排序的過程。 答：1） 建立的初始堆為: 85，79，50，56，32，41，82 ）堆排序的過程如下：8579328504156（C）第2次交換8541328505679（B）第1次交換8413256507985（A）初始建堆8579565041832（f）第5次交換857956

50、5032841（e）第4次交換8579568324150（D）第3次交換8579565041328（g）第6次交換55.答：把下列森林轉(zhuǎn)化為一棵二叉樹。12684735答： 森林轉(zhuǎn)化成的二叉樹如下圖。1268473556.已知數(shù)據(jù)序列為12,5,9,20,6,31,24，對該數(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 9 6 12 20 24 31第四趟排序 5 6 9 12 20 24 3157.給定表（40,36,55,6,64,77,9,41），按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹，并求其平均查找長度。答