數(shù)據(jù)結(jié)構(gòu)期終復(fù)習(xí)

1、 一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（）a）有向圖 b）隊(duì)列 c）線索二叉樹(shù) d）b樹(shù)（2）在一個(gè)單鏈表hl中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，則執(zhí)行如下（）語(yǔ)句序列。a）p=q; p-next=q; b）p-next=q; q-next=p;c）p-next=q-next; p=q; d）q-next=p-next; p-next=q;（3）（）不是隊(duì)列的基本運(yùn)算。a）在隊(duì)列第i個(gè)元素之后插入一個(gè)元素b）從隊(duì)頭刪除一個(gè)元素c）判斷一個(gè)隊(duì)列是否為空 d）讀取隊(duì)頭元素的值（4）字符a、b、c依次進(jìn)入一個(gè)棧，按出棧的先后順序組成

2、不同的字符串，至多可以組成（）個(gè)不同的字符串。a）14 b）5 c）6 d）8（5）由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（）。a）11 b）35 c）19 d）53以下6-8題基于下圖：（6）該二叉樹(shù)結(jié)點(diǎn)的前序遍歷的序列為（）。a）e、g、f、a、c、d、b b）e、a、g、c、f、b、dc）e、a、c、b、d、g、f d）e、g、a、c、d、f、b（7）該二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為（）。a）a、b、c、d、e、g、fb）e、a、g、c、f、b、dc）e、a、c、b、d、g、f d）b、d、c、a、f、g、e （8）該二叉樹(shù)的按層遍歷的序列為（）。a）e、g、

3、f、a、c、d、b b）e、a、c、b、d、g、fc）e、a、g、c、f、b、d d）e、g、a、c、d、f、b（9）下面關(guān)于圖的存儲(chǔ)的敘述中正確的是（）。a）用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)b）用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān)c）用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)d）用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)（10）設(shè)有關(guān)鍵碼序列(q,g,m,z,a,n,p,x,h)，下面哪一個(gè)序列是從上述序列出發(fā)建堆的結(jié)果?（）a）a,g,h,m,n,p,q,x,z b）a,g,

4、m,h,q,n,p,x,z c）g,m,q,a,n,p,x,h,z d）h,g,m,p,a,n,q,x,z六、（本題8分）對(duì)于序列8,18,6,16,29,28，試寫出堆頂元素最小的初始堆。七、（本題8分）一棵二叉樹(shù)的先序、中序和后序序列分別如下，其中有一部分未顯示出來(lái)。試求出空格處的內(nèi)容，并畫出該二叉樹(shù)。先序序列： b f iceh g中序序列：d kfia ejc 后序序列： k fbhj g a八、（每小題2分，共8分）設(shè)有序列：w=23,24,27,80,28，試給出：（1）二叉排序樹(shù)；（2）哈夫曼樹(shù)；（3）平衡二叉樹(shù)；（4）對(duì)于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果。十、（本題15分

5、）假設(shè)二叉樹(shù)中每個(gè)結(jié)點(diǎn)所含數(shù)據(jù)元素均為單字母，以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，試編寫算法按如下圖所示的樹(shù)狀顯示二叉樹(shù)。一、單項(xiàng)選擇題（1）b （2）d （3）a （4）b（5）b（6）c（7）a（8）c（9）b（10）b六、（本題8分）所構(gòu)造的堆如下圖所示：七、（本題8分）在先序序列空格中依次填adkj，中序中依次填bhg，后序中依次填diec。八、（每小題2分，共8分）（1）二叉排序樹(shù)如下圖所示：（2）哈夫曼樹(shù)如下圖所示：（3）平衡二叉樹(shù)如下圖所示：（4）對(duì)于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果：28,80,27,24,23十、（本題15分）從上圖來(lái)看，二叉樹(shù)的第一層顯示在第一列，第二層顯示在第二列

6、，第三層顯示在第三列；每行顯示一個(gè)結(jié)點(diǎn)，從上至下是先顯示右子樹(shù)，再顯示根，最后最左子樹(shù)，也就是以先遍歷右子樹(shù)，最后遍歷左子樹(shù)的中序遍歷次序顯示各結(jié)點(diǎn)。c語(yǔ)言版測(cè)試程序見(jiàn)exam110c，具體算當(dāng)如下：void displaybtwithtreeshape(bitree t,int level=1)/按樹(shù)狀形式顯示二叉樹(shù)，level為層次數(shù)，可設(shè)根結(jié)點(diǎn)的層次數(shù)為1if(t)/空樹(shù)不顯式，只顯式非空樹(shù)displaybtwithtreeshape(t-rchild,level+1);/顯示右子樹(shù)coutendl;/顯示新行for(int i=0;ilevel-1;i+)cout ;/確保在第leve

7、l列顯示結(jié)點(diǎn)coutdata;/顯示結(jié)點(diǎn)displaybtwithtreeshape(t-lchild,level+1);/顯示左子樹(shù)一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）設(shè)huffman樹(shù)的葉子結(jié)點(diǎn)數(shù)為m，則結(jié)點(diǎn)總數(shù)為（）。a）2m b）2m-1c）2m+1 d）m+1（2）若順序存儲(chǔ)的循環(huán)隊(duì)列的queuemaxsize=n，則該隊(duì)列最多可存儲(chǔ)（）個(gè)元素。a）n b）n-1 c）n+1 d）不確定（3）下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？（）a）存儲(chǔ)密度大 b）插入和刪除運(yùn)算方便 c）獲取符合某種條件的元素方便 d）查找運(yùn)算速度快（4）設(shè)有一個(gè)二維數(shù)組amn，假設(shè)a00存放位置在600

8、(10)，a33存放位置在678(10)，每個(gè)元素占一個(gè)空間，問(wèn)a23(10)存放在什么位置？（腳注(10)表示用10進(jìn)制表示，m3）（）。a）658 b）648 c）633 d）653（5）下列關(guān)于二叉樹(shù)遍歷的敘述中，正確的是（）。a）若一個(gè)葉子是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)b）若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)c）若一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)d）若一個(gè)樹(shù)葉是某二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷最后一個(gè)結(jié)點(diǎn)（6）k層二叉樹(shù)的結(jié)點(diǎn)總

9、數(shù)最多為（）。a）2k-1 b）2k+1 c）2k-1 d）2k-1（7）對(duì)線性表進(jìn)行二分法查找，其前提條件是（）。a）線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序 b）線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序c）線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序d）線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序（8）對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為（）。a）o(1og2n) b）o(n) c）o(1) d）o(n2)（9）對(duì)于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲(chǔ)時(shí)，若選用h（k）=k%7作為散列函數(shù)，則散列地址為0的元素有（）個(gè)。a）1 b）

10、2 c）3 d）4（10）下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（）。a）數(shù)組是不同類型值的集合 b）遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉c）樹(shù)是一種線性結(jié)構(gòu)d）用一維數(shù)組存儲(chǔ)一棵完全二叉樹(shù)是有效的存儲(chǔ)方法二、（本題8分）假定一棵二叉樹(shù)廣義表表示為a(b(c),d(e,f)，分別寫出對(duì)它進(jìn)行先序、中序、后序、按層遍歷的結(jié)果。四、（本題8分）樹(shù)有哪些遍歷方法？它們分別對(duì)應(yīng)于把樹(shù)轉(zhuǎn)變?yōu)槎鏄?shù)的哪些遍歷方法？五、（本題8分）設(shè)有數(shù)組a-1:3,0:6,-2:3，按行為主序存放在2000開(kāi)始的連續(xù)空間中，如元素的長(zhǎng)度是5，試計(jì)算出a1,1,1的存儲(chǔ)位置。八、（本題8分）設(shè)有一個(gè)輸入數(shù)據(jù)的序列是

11、46, 25, 78, 62, 12, 80 , 試畫出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹(shù)。十、（本題15分）以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，試編寫計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)目的遞歸算法。一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）b（2）b（3）a（4）d（5）a （6）a （7）c （8）c （9）d （10）d二、（本題8分）先序： a,b,c,d,e,f 中序： c,b,a,e,d,f 后序： c,b,e,f,d,a 按層： a,b,d,c,e,f 遍歷序列為：abedc。四、（本題8分）樹(shù)的遍歷方法有先根序遍歷和后根序遍歷，它們分別對(duì)應(yīng)于把樹(shù)轉(zhuǎn)變?yōu)槎鏄?shù)后的先序遍歷與中序遍歷方法。五

12、、（本題8分）a1,1,1的存儲(chǔ)位置=2000+(1-(-1)*(6-0+1)*(3-(-2)+1)+(1-0)*(3-(-2)+1)+(1-(-2)*5=2465。八、（本題8分）十、（本題15分）本題只要在遍歷二叉樹(shù)的過(guò)程序中對(duì)葉子結(jié)點(diǎn)進(jìn)行記數(shù)即可。c語(yǔ)言版測(cè)試程序見(jiàn)exam210c，具體算當(dāng)如下：long leafcount(bitree t)/計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)目if(t=null)return 0;/空樹(shù)返回0else if(t-lchild=null&t-rchild=null)return 1;/只有一個(gè)結(jié)點(diǎn)的樹(shù)返回1else/葉子結(jié)點(diǎn)數(shù)為左右子樹(shù)的葉子結(jié)點(diǎn)數(shù)之和return

13、 leafcount(t-lchild)+leafcount(t-rchild);一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（）方面的內(nèi)容。a）健壯性和可讀性 b）并行性 c）正確性 d）時(shí)空復(fù)雜度（2）在帶有頭結(jié)點(diǎn)的單鏈表hl中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（）。a）p-next=hl-next; hl-next=p b）p-next=hl; hl=pc）p-next=hl; p=hl d）hl=p; p-next=hl（3）對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）a）經(jīng)常需要隨機(jī)地存取元素 b）經(jīng)常需要進(jìn)行插入和刪除操作c）表中元素需

14、要占據(jù)一片連續(xù)的存儲(chǔ)空間d）表中元素的個(gè)數(shù)不變（4）一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是（）。a）2 3 1b）3 2 1c）3 1 2 d）1 2 3（5）每一趟都能選出一個(gè)元素放在其最終位置上，并且不穩(wěn)定的排序算法是（）。a）冒泡排序b）簡(jiǎn)單選擇排序c）希爾排序d）直接插入排序（6）采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度（）。a）低于鏈接法處理沖突 b）高于鏈接法處理沖突c）與鏈接法處理沖突相同 d）高于二分查找（7）若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為（）參數(shù)。a）值 b）函數(shù) c）指針 d）引用（8）在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)

15、中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（）。a）行號(hào) b）列號(hào) c）元素值 d）非零元素個(gè)數(shù)（9）快速排序在最壞情況下的時(shí)間復(fù)雜度為（）。a）o(log2n) b）o(nlog2n) c）o(n) d）o(n2)（10）從二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（）。a）o(n) b）o(1) c）o(log2n) d）o(n2)五、（本題8分）如果在1000000個(gè)記錄中找出兩個(gè)最小的記錄，你認(rèn)為采用什么樣的排序方法所需的關(guān)鍵字比較次數(shù)最少？最多比較多少次？六、（本題8分）假設(shè)把n個(gè)元素的序列（a1,a2,an）滿足條件akaj(ilchild);/左子樹(shù)的深度d_rsub=bitreed

16、epth(t-rchild);/右子樹(shù)的深度/返回左右子樹(shù)的深度最大值加1 return (d_lsubd_rsub)?d_lsub:d_rsub)+1;一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（）a）有向圖 b）棧 c）二叉樹(shù) d）b樹(shù)（2）若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。a）單鏈表b）雙鏈表c）帶頭結(jié)點(diǎn)的雙循環(huán)鏈表d）單循環(huán)鏈表（3）（）不是隊(duì)列的基本運(yùn)算。a）在隊(duì)列第i個(gè)元素之后插入一個(gè)元素 b）從隊(duì)頭刪除一個(gè)元素c）判斷一個(gè)隊(duì)列是否為空 d）讀取隊(duì)頭元素的值（4）字符a、b、c

17、、d依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個(gè)不同的字符串？a）15 b）14 c）16 d）21（5）由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（）。a）11 b）37 c）19 d）53以下6-8題基于下面的敘述：若某二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為a、b、c、d、e、f、g，后序遍歷的序列為b、d、c、a、f、g、e。（6）則該二叉樹(shù)結(jié)點(diǎn)的前序遍歷的序列為（）。a）e、g、f、a、c、d、bb）e、a、g、c、f、b、dc）e、a、c、b、d、g、f d）e、g、a、c、d、f、b（7）該二叉樹(shù)有（）個(gè)葉子。a）3 b）2 c）5 d）4（

18、8）該二叉樹(shù)的按層遍歷的序列為（）。a）e、g、f、a、c、d、b b）e、a、c、b、d、g、fc）e、a、g、c、f、b、d d）e、g、a、c、d、f、b（9）下面的二叉樹(shù)中，（）不是完全二叉樹(shù)。（10）設(shè)有關(guān)鍵碼序列(q,g,m,z,a)，（）序列是從上述序列出發(fā)建的小根堆的結(jié)果。a）a,g ,m,q,zb）a,g,m,z,qc）g,m,q,a,zd）g, m, a,q,z三、（本題8分）設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 ，試畫出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹(shù)。四、（本題8分）給定一個(gè)關(guān)鍵字序列24，19，32，43，38，6，13，

19、22，請(qǐng)寫出快速排序第一趟的結(jié)果；堆排序時(shí)所建的初始堆；然后回答上述兩種排序方法中哪一種方法使用的輔助空間最小，在最壞情況下哪種方法的時(shí)間復(fù)雜度最差？五、（本題8分）設(shè)二維數(shù)組a0:10,-5:0，按行優(yōu)先順序存儲(chǔ)，每個(gè)元素占4個(gè)單元，a0-5的存儲(chǔ)地址為1000，則a9-2的存儲(chǔ)地址為多少？六、（本題8分）用一維數(shù)組存放的一棵完全二叉樹(shù)：abcdefghijkl。請(qǐng)寫出后序遍歷該二叉樹(shù)的訪問(wèn)結(jié)點(diǎn)序列。七、（本題8分）請(qǐng)說(shuō)明對(duì)一棵二叉樹(shù)進(jìn)行前序、中序和后序遍歷，其葉結(jié)點(diǎn)的相對(duì)次序是否會(huì)發(fā)生改變？為什么？九、（本題9分）已知一棵二叉樹(shù)的先序序列與中序序列分別如下，試畫出此二叉樹(shù)。先序序列：abc

20、defghij中序序列：cbedaghfji十、（本題15分）已知二叉排序樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，根結(jié)點(diǎn)的指針為t，請(qǐng)寫出遞歸算法，從小到大輸出該二叉排序樹(shù)中所有關(guān)鍵字值k的結(jié)點(diǎn)的關(guān)鍵字的值。一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）b （2）c （3）a （4）b （5）b （6）c （7）a （8）c （9）c （10）b三、（本題8分）如下圖所示：四、（本題8分）快速排序的第一趟結(jié)果為22,19,13,6,24,38,43,12；堆排序時(shí)所建立的初始大頂堆如所圖所示：兩種排序方法所需輔助空間：堆是o(1)，快速排序是o(logn)，可見(jiàn)堆排序所需輔助空間較少；在最壞情況下兩種排序方

21、法所需時(shí)間：堆是o(nlogn)，快速排序是o(n2)，所以，可見(jiàn)快速排序時(shí)間復(fù)雜度最差。u 注意：快速排序的平均時(shí)排序速度最快，但在最壞情況下不一定比其他排序方法快。五、（本題8分）依題意a的起始地址為1000，則有：loc(9,-2)=1000+(9-0)*(0-(-5)+1)+(-2-(-5)*4=1228。六、（本題8分）先畫出該二叉樹(shù)的樹(shù)形結(jié)構(gòu)。對(duì)其進(jìn)行后序遍歷得到后序序列為：hidjkeblfgca。七、（本題8分）二叉樹(shù)任兩個(gè)中葉結(jié)點(diǎn)必在某結(jié)點(diǎn)的左/右子樹(shù)中，三種遍歷方法對(duì)左右子樹(shù)的遍歷都是按左子樹(shù)在前、右子樹(shù)在后的順序進(jìn)行遍歷的。所以在三種遍歷序列中葉結(jié)點(diǎn)的相對(duì)次序是不會(huì)發(fā)生改

22、變的。九、（本題9分）先由先序序列的第一個(gè)結(jié)點(diǎn)確定二叉樹(shù)的根結(jié)點(diǎn)，再由根結(jié)點(diǎn)在中序序列中左側(cè)部分為左子樹(shù)結(jié)點(diǎn)，在右側(cè)部分為右子樹(shù)結(jié)點(diǎn)，再由先序序列的第一個(gè)結(jié)點(diǎn)確定根結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)，由類似的方法可確定其他結(jié)點(diǎn)，如下圖所示。十、（本題15分）由于二叉排序樹(shù)是中序有序的，因此對(duì)二叉排序樹(shù)采用中序遍歷依次輸出大于等于k的結(jié)點(diǎn)即可。c語(yǔ)言版測(cè)試程序見(jiàn)exam410c，具體算當(dāng)如下：void displaykey(bitree t,keytype k)/從小到大輸出該二叉排序樹(shù)中所有關(guān)鍵字值k的結(jié)點(diǎn)的關(guān)鍵字的值if(t)displaykey(t-lchild,k);/輸出左子樹(shù)if(t-data.ke

23、y=k)coutdata.keyrchild,k);/輸出右子樹(shù)一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）隊(duì)列的特點(diǎn)是（）。a）先進(jìn)后出b）先進(jìn)先出c）任意位置進(jìn)出d）前面都不正確（2）有n個(gè)記錄的文件，如關(guān)鍵字位數(shù)為d，基數(shù)為r，則基數(shù)排序共要進(jìn)行（）遍分配與收集。a）nb）dc）rd）n - d （3）在二叉樹(shù)結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）。a）都不相同b）完全相同c）先序和中序相同，而與后序不同d）中序和后序相同，而與先序不同（4）限定在一端加入和刪除元素的線性表稱為（）。a）雙向鏈表b）單向鏈表c）棧d）隊(duì)列（5）快速排序執(zhí)行一遍之后，已經(jīng)到位的

24、元素個(gè)數(shù)是（）。a）1b）3c）d）（6）設(shè)森林f對(duì)應(yīng)的二叉樹(shù)為b，它有m個(gè)結(jié)點(diǎn)，b的根為p，p的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)為n，森林f中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是（）。a）m-n-1b）n+1c）m-n+1d）m-n（7）設(shè)有198個(gè)初始?xì)w并段，如采用k-路平衡歸并三遍完成排序，則k值最大為（）。a）12b）13c）14d）15（8）下面關(guān)于廣義表的敘述中，不正確的是（）。a）廣義表可以是一個(gè)多層次的結(jié)構(gòu)b）廣義表至少有一個(gè)元素c）廣義表可以被其他廣義表所共享d）廣義表可以是一個(gè)遞歸表（9）設(shè)二叉樹(shù)根結(jié)點(diǎn)的層次為0，一棵深度（高度）為k的滿二叉樹(shù)和同樣深度完全二叉樹(shù)各有f個(gè)結(jié)點(diǎn)和c個(gè)結(jié)點(diǎn)，下列關(guān)系式不正確

25、的是（）。a）f=cb）cfc）f=2k+1-ad）csk-1（10）從l=(apple,pear),(orange,banana)中，取出banana元素的表達(dá)式為（）。a）head(tail(l)b）head(head(tail(l)c）tail(head(tail(l)d）head(tail(head(tail(l)四、（每小題4分，共8分）判斷以下序列是否是小根堆? 如果不是，將它調(diào)整為小根堆。（1） 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 （2） 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 六、

26、（每小題2分，共8分）設(shè)有12個(gè)數(shù)據(jù)25,40,33,47,12,66,72,87,94,22,5,58，它們存儲(chǔ)在散列表中，利用線性探測(cè)再散列處理沖突，取散列函數(shù)為h(key)=key % 13。（1）順次將各個(gè)數(shù)據(jù)散列到表中，并同時(shí)列出各元素的比較次數(shù)。（2）計(jì)算查找成功的平均查找次數(shù)。八、（本題8分）已知一棵樹(shù)邊的結(jié)點(diǎn)為：(i,m),(i,n),(e,i),(b,e),(b,d),(c,b),(g,j),(g,k),(a,g),(a,f),(h,l),(a,h),(c,a)試畫出這棵樹(shù)，并回答下列問(wèn)題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）樹(shù)的深度是多少？九、（本題9分）給出一

27、組關(guān)鍵字t=(12,2,16,30,8,28,4,10,20,6,18)。寫出用下列算法從小到大排序時(shí)第一趟結(jié)束時(shí)的序列。（1）希爾排序（第一趟排序的增量為5）（2）快速排序（選第一個(gè)記錄為樞軸）十、（本題15分）編寫復(fù)制一棵二叉樹(shù)的非遞歸算法。一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）b（2）b（3）b（4）c（5）a（6）d（7）c（8）b（9）b（10）d四、（每小題4分，共8分）（1）不是小根堆。調(diào)整為：12,24,33,65,33,56,48,92,86,70 （2）是小根堆。六、（每小題2分，共8分）（1）取散列函數(shù)為h(key)=key % 13。（2）順次將各個(gè)數(shù)據(jù)散列到

28、表中，并同時(shí)列出各元素的比較次數(shù)如下表所示。各元素的比較次數(shù)地址01234567891011121314關(guān)鍵字40669455833477287222512比較121111132312（4）計(jì)算查找成功的平均查找次數(shù)=（17+23+32）/12=19/12。八、（本題8分）【解答】樹(shù)，如下圖所示：（1）c是根結(jié)點(diǎn)。（2）f，k，l，h，d，m，n是葉子結(jié)點(diǎn)。（3）深度是5。九、（本題9分）（1）（12,2,10,20,6,18,4,16,30,8,28）（2）（6,2,10,4,8,12,28,30,20,16,18）十、（本題15分）可采用層次遍歷的方式進(jìn)行復(fù)制，將已復(fù)制的結(jié)點(diǎn)進(jìn)入一個(gè)隊(duì)列中

29、即可。c語(yǔ)言版測(cè)試程序見(jiàn)exam510c，具體算當(dāng)如下：void copybitree(bitree t_from,bitree &t_to)/復(fù)制二叉樹(shù)t_from到t_to的非遞歸算法if(t_from=null)/空二叉樹(shù)的處理t_to=null;return;linkqueue q_from,q_to;bitnode *e_from,*e_to;initqueue(q_from);initqueue(q_to);t_to=new bitnode;t_to-data=t_from-data;/復(fù)制根結(jié)點(diǎn)enqueue(q_from,t_from);enqueue(q_to,t_to);/

30、入隊(duì)while(queueempty(q_from)=false)dequeue(q_from,e_from);dequeue(q_to,e_to);/出隊(duì) if(e_from-lchild!=null)/復(fù)制e_from左孩子e_to-lchild=new bitnode;e_to-lchild-data=e_from-lchild-data;enqueue(q_from,e_from-lchild);enqueue(q_to,e_to-lchild);/入隊(duì)elsee_to-lchild=null;/左孩子為空if(e_from-rchild!=null)/復(fù)制e_from右孩子e_to-

31、rchild=new bitnode;e_to-rchild-data=e_from-rchild-data;enqueue(q_from,e_from-rchild);enqueue(q_to,e_to-rchild);/入隊(duì)elsee_to-rchild=null;/右孩子為空一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）下列文件的物理結(jié)構(gòu)中，不利于文件長(zhǎng)度動(dòng)態(tài)增長(zhǎng)的文件物理結(jié)構(gòu)是（）。a）順序結(jié)構(gòu)b）鏈接結(jié)構(gòu) c）索引結(jié)構(gòu)d）hash結(jié)構(gòu)（2）在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素可由（）。a）實(shí)體b）域c）數(shù)據(jù)項(xiàng)d）字段（3）對(duì)于有n個(gè)頂點(diǎn)的有向圖，由弗洛伊德（floyd）算法求每一對(duì)頂之間的最短路

32、徑的時(shí)間復(fù)雜度是（）。a）o(1)b）o(n)c）o(n)d）o(n3)（4）對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間為（）。a）o（1）b）o（log2n）c）o（n）d）o（n2）（5）哈夫曼樹(shù)中一定不存在（）。a）度為0的結(jié)點(diǎn)b）度為1的結(jié)點(diǎn)c）度為2的結(jié)點(diǎn)d）帶權(quán)的結(jié)點(diǎn)（6）設(shè)d=a,b,c,d，r=,，則數(shù)據(jù)結(jié)構(gòu)(d,r)是（）。a）樹(shù)b）圖b）線性表d）前面都正確（7）（）關(guān)鍵碼序列不符合堆的定義。 a）a、c、d、g、h、m、p、q、r、xb）a、c、m、d、h、p、x、g、q、rc）a、d、p、r、c、q、x、m、h、gd）a、d、c、m、p、g、h、x、r、q（8）

33、假定關(guān)鍵字k=442205883，允許存儲(chǔ)地址為四位十進(jìn)制數(shù)，并且hash地址為6111，則所采用的構(gòu)造hash函數(shù)的方法是（）。a）直接定址法b）平方取中法c）除留余數(shù)法，模為97d）折疊法（9）在算法的時(shí)間復(fù)雜度中，n表示問(wèn)題規(guī)模，f(n)表示基本操作重復(fù)執(zhí)行的次數(shù)，則隨問(wèn)題的規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率同（）相同。a）f(n)b）nc）o(n)d）前面都不正確（10）對(duì)線性表進(jìn)行二分法查找，其前提條件是（）。a）線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序b）線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序c）線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序d）線性表以鏈接方式存儲(chǔ)，并

34、且按關(guān)鍵碼值的檢索頻率排好序二、（本題8分）在如下表所示的數(shù)組a中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針存放在a0.next，試寫出該線性表。線性表a01234567data605078903440next4052713三、（本題8分）已知一棵二叉樹(shù)的前序遍歷的結(jié)果是abkcdfghij，中序遍歷的結(jié)果是kbcdafhigj，試畫出這棵二叉樹(shù)。五、（本題8分）向最小根堆中依次插入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 1時(shí)，畫出每插入一個(gè)數(shù)據(jù)后堆的變化。八、（本題8分）給出一組關(guān)鍵字29、18、25、47、58、12、51、10，分別寫出按下列各種排序方法進(jìn)行排序時(shí)的變化過(guò)程：（1）歸并排序，每歸并一次書(shū)寫一個(gè)次序。（2）快速排序，每劃分一次書(shū)寫一個(gè)次序以及最后排好序后的序列。（2）快速排序：(10,18,25,12)29(58,51,47)(10(18,25,12)29(47,51)58)(10(12)18(25)29(47(51)58)(10,12,18,25,29,47,51,58)（3）堆排序，先建成一個(gè)堆，然后每從堆頂取下一個(gè)元素后，將堆調(diào)整一次。 九