1、 一、單項選擇題（每小題 2 分，共20分）（1）以下數據結構中哪一個是線性結構？（）a）有向圖 b）隊列 c）線索二叉樹 d）b樹（2）在一個單鏈表hl中，若要在當前由指針p指向的結點后面插入一個由q指向的結點，則執行如下（）語句序列。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）由權值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權路徑長度為（）。a）11 b）35 c）19 d）53以下6-8題基于下圖：（6）該二叉樹結點的前序遍歷的序列為（）。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）該二叉樹結點的中序遍歷的序列為（）。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）下面關于圖的存儲的敘述中正確的是（）。a）用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關b）用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數和結點個數都有關c）用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結點個數和邊數都有關d）用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數有關，而與結點個數無關（10）設有關鍵碼序列(q,g,m,z,a,n,p,x,h)，下面哪一個序列是從上述序列出發建堆的結果?（）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分）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內容，并畫出該二叉樹。先序序列： b f iceh g中序序列：d kfia ejc 后序序列： k fbhj g a八、（每小題2分，共8分）設有序列：w=23,24,27,80,28，試給出：（1）二叉排序樹；（2）哈夫曼樹；（3）平衡二叉樹；（4）對于增量d=2按降序執行一遍希爾排序的結果。十、（本題15分

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

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

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

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

9、數最多為（）。a）2k-1 b）2k+1 c）2k-1 d）2k-1（7）對線性表進行二分法查找，其前提條件是（）。a）線性表以鏈接方式存儲，并且按關鍵碼值排好序 b）線性表以順序方式存儲，并且按關鍵碼值的檢索頻率排好序c）線性表以順序方式存儲，并且按關鍵碼值排好序d）線性表以鏈接方式存儲，并且按關鍵碼值的檢索頻率排好序（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作為散列函數，則散列地址為0的元素有（）個。a）1 b）

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

11、46, 25, 78, 62, 12, 80 , 試畫出從空樹起，逐個輸入各個數據而生成的二叉搜索樹。十、（本題15分）以二叉鏈表作存儲結構，試編寫計算二叉樹中葉子結點數目的遞歸算法。一、單項選擇題（每小題 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分）樹的遍歷方法有先根序遍歷和后根序遍歷，它們分別對應于把樹轉變為二叉樹后的先序遍歷與中序遍歷方法。五

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分）本題只要在遍歷二叉樹的過程序中對葉子結點進行記數即可。c語言版測試程序見exam210c，具體算當如下：long leafcount(bitree t)/計算二叉樹中葉子結點數目if(t=null)return 0;/空樹返回0else if(t-lchild=null&t-rchild=null)return 1;/只有一個結點的樹返回1else/葉子結點數為左右子樹的葉子結點數之和return

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

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

15、中，每個單鏈表中的結點都具有相同的（）。a）行號 b）列號 c）元素值 d）非零元素個數（9）快速排序在最壞情況下的時間復雜度為（）。a）o(log2n) b）o(nlog2n) c）o(n) d）o(n2)（10）從二叉搜索樹中查找一個元素時，其時間復雜度大致為（）。a）o(n) b）o(1) c）o(log2n) d）o(n2)五、（本題8分）如果在1000000個記錄中找出兩個最小的記錄，你認為采用什么樣的排序方法所需的關鍵字比較次數最少？最多比較多少次？六、（本題8分）假設把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）以下數據結構中哪一個是線性結構？（）a）有向圖 b）棧 c）二叉樹 d）b樹（2）若某鏈表最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，則采用（）存儲方式最節省時間。a）單鏈表b）雙鏈表c）帶頭結點的雙循環鏈表d）單循環鏈表（3）（）不是隊列的基本運算。a）在隊列第i個元素之后插入一個元素 b）從隊頭刪除一個元素c）判斷一個隊列是否為空 d）讀取隊頭元素的值（4）字符a、b、c

17、、d依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個不同的字符串？a）15 b）14 c）16 d）21（5）由權值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權路徑長度為（）。a）11 b）37 c）19 d）53以下6-8題基于下面的敘述：若某二叉樹結點的中序遍歷的序列為a、b、c、d、e、f、g，后序遍歷的序列為b、d、c、a、f、g、e。（6）則該二叉樹結點的前序遍歷的序列為（）。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）設有關鍵碼序列(q,g,m,z,a)，（）序列是從上述序列出發建的小根堆的結果。a）a,g ,m,q,zb）a,g,m,z,qc）g,m,q,a,zd）g, m, a,q,z三、（本題8分）設有一個輸入數據的序列是 46, 25, 78, 62, 12, 80 ，試畫出從空樹起，逐個輸入各個數據而生成的二叉排序樹。四、（本題8分）給定一個關鍵字序列24，19，32，43，38，6，13，

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

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

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

22、變的。九、（本題9分）先由先序序列的第一個結點確定二叉樹的根結點，再由根結點在中序序列中左側部分為左子樹結點，在右側部分為右子樹結點，再由先序序列的第一個結點確定根結點的左右孩子結點，由類似的方法可確定其他結點，如下圖所示。十、（本題15分）由于二叉排序樹是中序有序的，因此對二叉排序樹采用中序遍歷依次輸出大于等于k的結點即可。c語言版測試程序見exam410c，具體算當如下：void displaykey(bitree t,keytype k)/從小到大輸出該二叉排序樹中所有關鍵字值k的結點的關鍵字的值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個記錄的文件，如關鍵字位數為d，基數為r，則基數排序共要進行（）遍分配與收集。a）nb）dc）rd）n - d （3）在二叉樹結點的先序序列、中序序列和后序序列中，所有葉子結點的先后順序（）。a）都不相同b）完全相同c）先序和中序相同，而與后序不同d）中序和后序相同，而與先序不同（4）限定在一端加入和刪除元素的線性表稱為（）。a）雙向鏈表b）單向鏈表c）棧d）隊列（5）快速排序執行一遍之后，已經到位的

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

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分）判斷以下序列是否是小根堆? 如果不是，將它調整為小根堆。（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分）設有12個數據25,40,33,47,12,66,72,87,94,22,5,58，它們存儲在散列表中，利用線性探測再散列處理沖突，取散列函數為h(key)=key % 13。（1）順次將各個數據散列到表中，并同時列出各元素的比較次數。（2）計算查找成功的平均查找次數。八、（本題8分）已知一棵樹邊的結點為：(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）哪個是根結點？（2）哪些是葉子結點？（3）樹的深度是多少？九、（本題9分）給出一

27、組關鍵字t=(12,2,16,30,8,28,4,10,20,6,18)。寫出用下列算法從小到大排序時第一趟結束時的序列。（1）希爾排序（第一趟排序的增量為5）（2）快速排序（選第一個記錄為樞軸）十、（本題15分）編寫復制一棵二叉樹的非遞歸算法。一、單項選擇題（每小題 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）不是小根堆。調整為：12,24,33,65,33,56,48,92,86,70 （2）是小根堆。六、（每小題2分，共8分）（1）取散列函數為h(key)=key % 13。（2）順次將各個數據散列到

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

29、即可。c語言版測試程序見exam510c，具體算當如下：void copybitree(bitree t_from,bitree &t_to)/復制二叉樹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;/復制根結點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)/復制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)/復制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）下列文件的物理結構中，不利于文件長度動態增長的文件物理結構是（）。a）順序結構b）鏈接結構 c）索引結構d）hash結構（2）在數據結構中，數據元素可由（）。a）實體b）域c）數據項d）字段（3）對于有n個頂點的有向圖，由弗洛伊德（floyd）算法求每一對頂之間的最短路

32、徑的時間復雜度是（）。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的結點b）度為1的結點c）度為2的結點d）帶權的結點（6）設d=a,b,c,d，r=,，則數據結構(d,r)是（）。a）樹b）圖b）線性表d）前面都正確（7）（）關鍵碼序列不符合堆的定義。 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、假定關鍵字k=442205883，允許存儲地址為四位十進制數，并且hash地址為6111，則所采用的構造hash函數的方法是（）。a）直接定址法b）平方取中法c）除留余數法，模為97d）折疊法（9）在算法的時間復雜度中，n表示問題規模，f(n)表示基本操作重復執行的次數，則隨問題的規模n的增大，算法執行時間的增長率同（）相同。a）f(n)b）nc）o(n)d）前面都不正確（10）對線性表進行二分法查找，其前提條件是（）。a）線性表以順序方式存儲，并且按關鍵碼值排好序b）線性表以順序方式存儲，并且按關鍵碼值的檢索頻率排好序c）線性表以鏈接方式存儲，并且按關鍵碼值排好序d）線性表以鏈接方式存儲，并

34、且按關鍵碼值的檢索頻率排好序二、（本題8分）在如下表所示的數組a中鏈接存儲了一個線性表，表頭指針存放在a0.next，試寫出該線性表。線性表a01234567data605078903440next4052713三、（本題8分）已知一棵二叉樹的前序遍歷的結果是abkcdfghij，中序遍歷的結果是kbcdafhigj，試畫出這棵二叉樹。五、（本題8分）向最小根堆中依次插入數據4, 2, 5, 8, 3, 6, 10, 1時，畫出每插入一個數據后堆的變化。八、（本題8分）給出一組關鍵字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）堆排序，先建成一個堆，然后每從堆頂取下一個元素后，將堆調整一次。 九