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

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

2、不同的字符串，至多可以組成（）個不同的字符串。a）14 b）5 c）6 d）8（5）由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。a）11 b）35 c）19 d）53以下6-8題基于下圖：（6）該二叉樹結(jié)點的前序遍歷的序列為（）。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）該二叉樹結(jié)點的中序遍歷的序列為（）。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）該二叉樹的按層遍歷的序列為（）。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)于圖的存儲的敘述中正確的是（）。a）用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)b）用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點個數(shù)都有關(guān)c）用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān)d）用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)（10）設(shè)有關(guān)鍵碼序列(q,g,m,z,a,n,p,x,h)，下面哪一個序列是從上述序列出發(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分）對于序列8,18,6,16,29,28，試寫出堆頂元素最小的初始堆。七、（本題8分）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列： b f iceh g中序序列：d kfia ejc 后序序列： k fbhj g a八、（每小題2分，共8分）設(shè)有序列：w=23,24,27,80,28，試給出：（1）二叉排序樹；（2）哈夫曼樹；（3）平衡二叉樹；（4）對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果。十、（本題15分

5、）假設(shè)二叉樹中每個結(jié)點所含數(shù)據(jù)元素均為單字母，以二叉鏈表為存儲結(jié)構(gòu)，試編寫算法按如下圖所示的樹狀顯示二叉樹。一、單項選擇題（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）二叉排序樹如下圖所示：（2）哈夫曼樹如下圖所示：（3）平衡二叉樹如下圖所示：（4）對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果：28,80,27,24,23十、（本題15分）從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列

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

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

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

9、數(shù)最多為（）。a）2k-1 b）2k+1 c）2k-1 d）2k-1（7）對線性表進行二分法查找，其前提條件是（）。a）線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序 b）線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序c）線性表以順序方式存儲，并且按關(guān)鍵碼值排好序d）線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序（8）對n個記錄進行堆排序，所需要的輔助存儲空間為（）。a）o(1og2n) b）o(n) c）o(1) d）o(n2)（9）對于線性表（7，34，77，25，64，49，20，14）進行散列存儲時，若選用h（k）=k%7作為散列函數(shù)，則散列地址為0的元素有（）個。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）樹是一種線性結(jié)構(gòu)d）用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法二、（本題8分）假定一棵二叉樹廣義表表示為a(b(c),d(e,f)，分別寫出對它進行先序、中序、后序、按層遍歷的結(jié)果。四、（本題8分）樹有哪些遍歷方法？它們分別對應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄涞哪男┍闅v方法？五、（本題8分）設(shè)有數(shù)組a-1:3,0:6,-2:3，按行為主序存放在2000開始的連續(xù)空間中，如元素的長度是5，試計算出a1,1,1的存儲位置。八、（本題8分）設(shè)有一個輸入數(shù)據(jù)的序列是

11、46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。十、（本題15分）以二叉鏈表作存儲結(jié)構(gòu)，試編寫計算二叉樹中葉子結(jié)點數(shù)目的遞歸算法。一、單項選擇題（每小題 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分）樹的遍歷方法有先根序遍歷和后根序遍歷，它們分別對應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄浜蟮南刃虮闅v與中序遍歷方法。五

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

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

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

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

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

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

18、8）該二叉樹的按層遍歷的序列為（）。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）下面的二叉樹中，（）不是完全二叉樹。（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è)有一個輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12, 80 ，試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。四、（本題8分）給定一個關(guān)鍵字序列24，19，32，43，38，6，13，

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

20、defghij中序序列：cbedaghfji十、（本題15分）已知二叉排序樹采用二叉鏈表存儲結(jié)構(gòu)，根結(jié)點的指針為t，請寫出遞歸算法，從小到大輸出該二叉排序樹中所有關(guān)鍵字值k的結(jié)點的關(guān)鍵字的值。一、單項選擇題（每小題 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；堆排序時所建立的初始大頂堆如所圖所示：兩種排序方法所需輔助空間：堆是o(1)，快速排序是o(logn)，可見堆排序所需輔助空間較少；在最壞情況下兩種排序方

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

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

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

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

25、的是（）。a）f=cb）cfc）f=2k+1-ad）csk-1（10）從l=(apple,pear),(orange,banana)中，取出banana元素的表達式為（）。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個數(shù)據(jù)25,40,33,47,12,66,72,87,94,22,5,58，它們存儲在散列表中，利用線性探測再散列處理沖突，取散列函數(shù)為h(key)=key % 13。（1）順次將各個數(shù)據(jù)散列到表中，并同時列出各元素的比較次數(shù)。（2）計算查找成功的平均查找次數(shù)。八、（本題8分）已知一棵樹邊的結(jié)點為：(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)試畫出這棵樹，并回答下列問題：（1）哪個是根結(jié)點？（2）哪些是葉子結(jié)點？（3）樹的深度是多少？九、（本題9分）給出一

27、組關(guān)鍵字t=(12,2,16,30,8,28,4,10,20,6,18)。寫出用下列算法從小到大排序時第一趟結(jié)束時的序列。（1）希爾排序（第一趟排序的增量為5）（2）快速排序（選第一個記錄為樞軸）十、（本題15分）編寫復(fù)制一棵二叉樹的非遞歸算法。一、單項選擇題（每小題 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）順次將各個數(shù)據(jù)散列到

28、表中，并同時列出各元素的比較次數(shù)如下表所示。各元素的比較次數(shù)地址01234567891011121314關(guān)鍵字40669455833477287222512比較121111132312（4）計算查找成功的平均查找次數(shù)=（17+23+32）/12=19/12。八、（本題8分）【解答】樹，如下圖所示：（1）c是根結(jié)點。（2）f，k，l，h，d，m，n是葉子結(jié)點。（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分）可采用層次遍歷的方式進行復(fù)制，將已復(fù)制的結(jié)點進入一個隊列中

29、即可。c語言版測試程序見exam510c，具體算當(dāng)如下：void copybitree(bitree t_from,bitree &t_to)/復(fù)制二叉樹t_from到t_to的非遞歸算法if(t_from=null)/空二叉樹的處理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é)點enqueue(q_from,t_from);enqueue(q_to,t_to);/

30、入隊while(queueempty(q_from)=false)dequeue(q_from,e_from);dequeue(q_to,e_to);/出隊 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);/入隊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);/入隊elsee_to-rchild=null;/右孩子為空一、單項選擇題（每小題 2 分，共20分）（1）下列文件的物理結(jié)構(gòu)中，不利于文件長度動態(tài)增長的文件物理結(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）實體b）域c）數(shù)據(jù)項d）字段（3）對于有n個頂點的有向圖，由弗洛伊德（floyd）算法求每一對頂之間的最短路

32、徑的時間復(fù)雜度是（）。a）o(1)b）o(n)c）o(n)d）o(n3)（4）對n個記錄的文件進行快速排序，所需要的輔助存儲空間為（）。a）o（1）b）o（log2n）c）o（n）d）o（n2）（5）哈夫曼樹中一定不存在（）。a）度為0的結(jié)點b）度為1的結(jié)點c）度為2的結(jié)點d）帶權(quán)的結(jié)點（6）設(shè)d=a,b,c,d，r=,，則數(shù)據(jù)結(jié)構(gòu)(d,r)是（）。a）樹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，允許存儲地址為四位十進制數(shù)，并且hash地址為6111，則所采用的構(gòu)造hash函數(shù)的方法是（）。a）直接定址法b）平方取中法c）除留余數(shù)法，模為97d）折疊法（9）在算法的時間復(fù)雜度中，n表示問題規(guī)模，f(n)表示基本操作重復(fù)執(zhí)行的次數(shù)，則隨問題的規(guī)模n的增大，算法執(zhí)行時間的增長率同（）相同。a）f(n)b）nc）o(n)d）前面都不正確（10）對線性表進行二分法查找，其前提條件是（）。a）線性表以順序方式存儲，并且按關(guān)鍵碼值排好序b）線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序c）線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序d）線性表以鏈接方式存儲，并

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