數(shù)據(jù)結(jié)構(gòu)與算法分析六套期末復習題含答案

1、試題一一、單項選擇題(每小題2分，共20分)(1)以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？()A)有向圖B)隊列C)線索二叉科D)B樹(2)在一個單鏈表HL中，若要在當前由指針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

2、、B、C依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成()個不同的字符串。A)14B)5C)6D)8(5)由權值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權路徑長度為()。A)11B)35C)19D)53以下6-8題基于下圖：(6)該二叉樹結(jié)點的前序遍歷的序列為()。A)E、G、F、A、C、D、BB)E、A、G、C、F、B、DC)E、A、C、B、D、G、FD)E、G、A、C、D、F、B(7)該二叉樹結(jié)點的中序遍歷的序列為()。A)A、B、C、D、E、G、FB)E、A、G、C、F、B、DD）B、D、C、A、F、G、E）°B）E、A、C、B、D、G、FD）E、G、

3、A、C、D、F、BC）E、A、C、B、D、G、F（8）該二叉樹的按層遍歷的序列為（A）E、G、F、A、C、D、BC）E、A、G、C、F、B、D（9）下面關于圖的存儲的敘述中正確的是（）。A）用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關，而與結(jié)點個數(shù)無關B）用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點個數(shù)都有關C）用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結(jié)點個數(shù)和邊數(shù)都有關D）用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關，而與結(jié)點個數(shù)無關(10)設有關鍵碼序列(q,g,m,z,a,n,p,x,h),下面哪一個序列是從上述序列出發(fā)建堆的結(jié)果()A)a,g,h,m,n,

4、p,q,x,zB)a,g,m,h,q,n,p,x,zC)g,m,q,a,n,p,x,h,zD)h,g,m,p,a,n,q,x,z（本題8分）對于序列8,18,6,16,29,28，試寫出堆頂元素最小的初始堆三、（本題8分）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA四、(每小題2分，共8分)設有序列：w=23,24,27,80,28，試給出：(1)二叉排序樹；(2)哈夫曼樹；(3)平衡二叉樹；(4)對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果五、(本題15分)假設二

5、叉樹中每個結(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,16中序中依次填BHG,后序中依次填DIECo四、（每小題2分，共8分）(1)二叉排序樹如下圖所示:(2)哈夫曼樹如下圖所示:(3)平衡二叉樹如下圖所示:(4)對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果：28,80,27,24,23五、（本題15分）/顯示右子樹/顯示新行/確保在第level列顯示結(jié)點/顯示

6、結(jié)點/顯7K左子樹從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個結(jié)點，從上至下是先顯示右子樹，再顯示根，最后最左子樹，也就是以先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結(jié)點。C語言版測試程序見exam110c,具體算當如下:voidDisplayBTWithTreeShape(BiTreeT,intlevel=1)/按樹狀形式顯示二叉樹，level為層次數(shù)，可設根結(jié)點的層次數(shù)為1if(T)/空樹不顯式，只顯式非空樹DisplayBTWithTreeShape(T->rchild,level+1);cout<<endl;for

7、(inti=0;i<level-1;i+)cout<<""cout<<T->data;DisplayBTWithTreeShape(T->lchild,level+1);試題二一、單項選擇題(每小題2分，共20分)(1)設Huffman樹的葉子結(jié)點數(shù)為m,則結(jié)點總數(shù)為()。A)2mB)2m-1C)2m+1D)m+1(2)若順序存儲的循環(huán)隊列的QueueMaxSize=n,則該隊列最多可存儲()個元素。A)nB)n-1C)n+1D)不確定(3)下述哪一條是順序存儲方式的優(yōu)點？()A)存儲密度大B)插入和刪除運算方便C)獲取符合某種條件

8、的元素方便D)查找運算速度快(4)設有一個二維數(shù)組Amn，假設A00存放位置在600(10),A33存放位置在678(10),每個元素占一個空間，問A23(10)存放在什么位置？(腳注(10)表示用10進制表示，m>3)()。A)658B)648C)633D)653(5)下列關于二叉樹遍歷的敘述中，正確的是()。A)若一個葉子是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序遍歷最后一個結(jié)點B)若一個結(jié)點是某二叉樹的前序遍歷最后一個結(jié)點，則它必是該二叉樹的中序遍歷的最后一個結(jié)點C)若一個結(jié)點是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序最后一個結(jié)點D)若一個樹葉是某二

9、叉樹的前序最后一個結(jié)點，則它必是該二叉樹的中序遍歷最后一個結(jié)點(6) k層二叉樹的結(jié)點總數(shù)最多為()。A)2k-1B)2k+1C)K-1D)k-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

10、(K)=K%7作為散列函數(shù)，則散列地址為0的元素有()個。A)1B)2C)3D)4(10)下列關于數(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分)樹有哪些遍歷方法？它們分別對應于把樹轉(zhuǎn)變?yōu)槎鏄涞哪男┍闅v方法？四、(本題8分)設有數(shù)組A-1:3,0:6,-2:3,按行為主序存放在2000開始的連續(xù)空間中，如元素的長度是5,試計算出A1

11、,1,1的存儲位置。五、(本題8分)設有一個輸入數(shù)據(jù)的序列是46,25,78,62,12,80),試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。六、(本題15分)以二叉鏈表作存儲結(jié)構(gòu)，試編寫計算二叉樹中葉子結(jié)點數(shù)目的遞歸算法?！敬鸢浮?一、單項選擇題(每小題2分，共20分)(1)B(2)BA(4)DA(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分）樹的遍歷方法有先根序遍歷和后根序遍歷，它們分別對應于把樹轉(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六、（本題15分）本題只要在遍歷二叉樹的過程序中對葉子結(jié)點進行記數(shù)即可C語言版測試程序見exam210c,具體算當如下：longLeafCount（BiTreeT）/計算二叉樹中葉子結(jié)點數(shù)目if（T=NULL）return0;/空樹返回0elseif(T->lchild=NULL&&T->rchild=NULL)return1;只有一個結(jié)點的樹返回1else/葉子結(jié)點數(shù)為左右子樹的葉子結(jié)點

13、數(shù)之和returnLeafCount(T->lchild)+LeafCount(T->rchild);試題三一、單項選擇題（每小題2分，共20分）（1）對一個算法的評價，不包括如下（）方面的內(nèi)容。A）健壯性和可讀性B）并行性C）正確TD）時空復雜度（2）在帶有頭結(jié)點的單鏈表HL中,要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行（）A）p->next=HL->next;HL->next=pB）p->next=HL;HL=pC）p->next=HL;p=HLD）HL=p;p->next=HL（3）對線性表，在下列哪種情況下應當采用鏈表表示？（）A）經(jīng)常需

14、要隨機地存取元素B）經(jīng)常需要進行插入和刪除操作C）表中元素需要占據(jù)一片連續(xù)的存儲空間D）表中元素的個數(shù)不變（4） 一個棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是（）。A）231B）321C）312D）123(5)每一趟都能選出一個元素放在其最終位置上，并且不穩(wěn)定的排序算法是()A)冒泡排序B)簡單選擇排序C)希爾排序D)直接插入排序(6)采用開放定址法處理散列表的沖突時，其平均查找長度()。A)低于鏈接法處理沖突B)高于鏈接法處理沖突C)與鏈接法處理沖突相同D)高于二分查找(7)若需要利用形參直接訪問實參時，應將形參變量說明為()參數(shù)。A)值B)函數(shù)C)指針D)引用(8)在稀疏

15、矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的()A)行號B)列號C)元素值D)非零元素個數(shù)(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個記錄中找出兩個最小的記錄，你認為采用什么樣的排序方法所需的關鍵字比較次數(shù)最少？最多比較多少次？三、(本題8分)假設把n個元素的序列(a1,a2,-an)滿足條件ak<maxat|1<t<k的元素ak稱為“

16、逆序元素”若在一個無序序列中有一對元素ai>aj(i<j),試問，當ai與aj相互交換后，該序列中逆序元素的個數(shù)一定不會增加，這句話對不對？如果對，請說明為什么？如果不對，請舉一例說明。四、(每小題4分，共8分)設內(nèi)存有大小為6個記錄的緩沖區(qū)供內(nèi)排序使用，文件的關鍵字序列為29,50,70,33,38,60,28,31,43,36,25,9,80,100,57,18,65,2,78,30,14,20,17,99),試列出：(1)用內(nèi)排序求出初始歸并段；(2)用置換一選擇排序求初始歸并段。五、(本題9分)已知關鍵字序列23,13,5,28,14,25,試構(gòu)造二叉排序樹六、(本題15分

17、)編寫一個算法求二又樹的深度?！敬鸢浮?-、單項選擇題(每小題2分，共20分)(1)B(2)A(3)B(4)C(6)B(7)D(8)A(9)D(10)C最多比較次數(shù)=999999+log21000000(本題8分)采用樹形選擇排序方法所需的關鍵字比較次數(shù)最少,=1000019次。三、（本題8分）不對，例如序列3、3、4、2、1的“逆序元素”個數(shù)是2,2和1是“逆序元素”；但是將第二個3和2交換后，成為3、2、4、3、1,止匕時“逆序元素”個數(shù)是3,2、3和1是“逆序元素”。然而交換后一定減少的是“逆序?qū)Α钡膫€數(shù)，例如上例中3、3、4、2、1的逆序?qū)Φ膫€數(shù)是7,交換第二個3和2后，3、2、4、3

18、、1的逆序?qū)Φ膫€數(shù)是6。四、(每小題4分，共8分)(1)用內(nèi)排序求出初始歸并段為：歸并段1:29,33,38,50,60,70:歸并段2:9,25,28,31,36,43歸并段3:2,18,57,65,80,100:歸并段4:14,17,20,30,78,99.(2)用置換一選擇排序求初始歸并段為：歸并段1:29,33,38,50,60,70,80,100歸并段2:9,18,25,28,31,36,57,65,78,99;歸并段3:2,14,17,20,30.五、（本題9分）構(gòu)造二叉排序樹的過程如下圖所示。U)構(gòu)造的二叉排序樹如下圖所示:六、(本題15分)若二叉樹為空，深度為0;若二叉樹不空，

19、則二叉樹的深度為左右子樹深度的最大值加1。本題最簡單算法是遞歸算法。C語言版測試程序見exam310c,具體算當如下：intBiTreeDepth(BiTreeT)/求二叉樹的深度if(T=NULL)return0;/空二叉樹的深度為0elseintd_lsub,d_rsub;d_lsub=BiTreeDepth(T->lchild);/左子樹的深度d_rsub=BiTreeDepth(T->rchild);/右子樹的深度/返回左右子樹的7度最大值加1return(d_lsub>d_rsub)?d_lsub:d_rsub)+1;試題四一、單項選擇題(每小題2分，共20分)(1

20、)以下數(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、D依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成()個不同的字符串？A)15B)14C)16D)21(5)由權值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權路徑長度為()。A)11B)

21、37C)19D)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、BC)E、A、C、B、D、GF(7)該二叉樹有()個葉子,A)3B)2(8)該二叉樹的按層遍歷的序列為(A) E、G、F、A、C、D、BC)E、A、G、C、F、B、DB) E、A、GC、F、B、DD)E、G、A、C、D、F、BC) 5D)4)。B)E、A、C、B、D、G、FD) E、GA、C、D、F、B(9)下面的二叉樹中，(C)不是完全二叉樹(10)設有關鍵碼序列(q,g,

22、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ù)據(jù)的序列是46,25,78,62,12,80，試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。三、(本題8分)給定一個關鍵字序列24,19,32,43,38,6,13,22,請寫出快速排序第一趟的結(jié)果;堆排序時所建的初始堆；然后回答上述兩種排序方法中哪一種方法使用的輔助空間最小，在最壞情況下哪種方法的時間復雜度最差？四、(本題8分)設二維數(shù)組A0:10,-5:0,按行優(yōu)先順序存儲，每個元素占4個單元，A0卜5的存儲地址為

23、1000,則A9-2的存儲地址為多少？五、(本題8分)用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL請寫出后序遍歷該二叉樹的訪問結(jié)點序列。六、(本題8分)請說明對一棵二叉樹進行前序、中序和后序遍歷，其葉結(jié)點的相對次序是否會發(fā)生改變？為什么？七、(本題9分)已知一棵二叉樹的先序序列與中序序列分別如下，試畫出此二叉樹。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI八、(本題15分)已知二叉排序樹采用二叉鏈表存儲結(jié)構(gòu)，根結(jié)點的指針為T,請寫出遞歸算法，從小到大輸出該二叉排序樹中所有關鍵字值AK的結(jié)點的關鍵字的值。【答案】=一、單項選擇題(每小題2分，共20分)(1)B(2)C

24、(3)A(4)BB(6)C(7)A(8)C(9)C(10)B二、(本題8分)如下圖所示：U)(b)而<e)三、(本題8分)快速排序的第一趟結(jié)果為22,19,13,6,24,38,43,12;堆排序時所建立的初始大頂堆如所圖所示：兩種排序方法所需輔助空間：堆是0(1)，快速排序是O(logn),可見堆排序所需輔助空間較少；在最壞情況下兩種排序方法所需時間：堆是O(nlogn),快速排序是0(n2),所以，可見快速排序時間復雜度最差。注意：快速排序的平均時排序速度最快，但在最壞情況下不一定比其他排序方法快。四、(本題8分)依題意A的起始地址為1000,則有：Loc(9,-2)=1000+(9

25、-0)*(0-(-5)+1)+(-2-(-5)*4=1228。五、(本題8分)先畫出該二叉樹的樹形結(jié)構(gòu)。對其進行后序遍歷得到后序序列為：HIDJKEBLFGCA六、(本題8分)二叉樹任兩個中葉結(jié)點必在某結(jié)點的左/右子樹中，三種遍歷方法對左右子樹的遍歷都是按左子樹在前、右子樹在后的順序進行遍歷的。所以在三種遍歷序列中葉結(jié)點的相對次序是不會發(fā)生改變的。七、(本題9分)先由先序序列的第一個結(jié)點確定二叉樹的根結(jié)點，再由根結(jié)點在中序序列中左側(cè)部分為左子樹結(jié)點，在右側(cè)部分為右子樹結(jié)點，再由先序序列的第一個結(jié)點確定根結(jié)點的左右孩子結(jié)點，由類似的方法可確定其他結(jié)點，如下圖所示。八、(本題15分)由于二叉排序樹

26、是中序有序的，因此對二叉排序樹采用中序遍歷依次輸出大于等于K的結(jié)點即可。C語言版測試程序見exam410c,具體算當如下：voidDisplayKey(BiTreeT,KeyTypeK)/從小到大輸出該二叉排序樹中所有關鍵字值)K的結(jié)點的關鍵字的值if(T)DisplayKey(T->lchild,K);/輸出左子樹if(T->data.key>=K)cout<<T->data.key<<""/輸出滿足條件的關鍵值DisplayKey(T->rchild,K);/輸出右子樹試題五2分，共20分）遍分n,一、單項選擇題（每

27、小題（1）隊列的特點是（）。A）先進后出B）先進先出C）任意位置進出D）前面都不正確（2）有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)到位的元素個數(shù)是（）。nnA）1B）3C）4D）2（6）設森林F對應的二叉樹為B,它有m個結(jié)點，B的根為p,p的右子樹上的

28、結(jié)點個數(shù)為森林F中第一棵樹的結(jié)點個數(shù)是（）。A）m-n-1B）n+1C）m-n+1D）m-n（7）設有198個初始歸并段，如采用K-路平衡歸并三遍完成排序，則K值最大為（A) 12B) 13C) 14D) 15（8）下面關于廣義表的敘述中，不正確的是（）。A）廣義表可以是一個多層次的結(jié)構(gòu)B）廣義表至少有一個元素C）廣義表可以被其他廣義表所共享D）廣義表可以是一個遞歸表（9）設二叉樹根結(jié)點的層次為0,一棵深度（高度）為k的滿二叉樹和同樣深度完全二叉樹各有f個結(jié)點和c個結(jié)點，下列關系式不正確的是（）。A)f>=cB)c>fC)f=2k+1-aD)c>sk-1(10)從L=(app

29、le,pear),(orange,banana)中，取出banana元素的表達式為()。A)head(tail(L)C)tail(head(tail(L)Bhead(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六、（每小題2分，共8分）設有12個數(shù)據(jù)25,40,33,47,12,66,72,87,94,22,5,58,它們存儲在散列表中，禾用線

30、性探測再散列處理沖突，取散列函數(shù)為H（key尸key%13。（3） 順次將各個數(shù)據(jù)散列到表中，并同時列出各元素的比較次數(shù)。（4） 計算查找成功的平均查找次數(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分)給出一組關鍵字T=(12,2,16,30,8,28,4,10,20,6,18)。寫出用下列算法從小到大排序時第一趟結(jié)束時的序列。(1)希爾排

31、序(第一趟排序的增量為5)(2)快速排序(選第一個記錄為樞軸)十、(本題15分)編寫復制一棵二叉樹的非遞歸算法?！敬鸢浮?一、單項選擇題(每小題2分，共20分)(1)B(2)B(3)B(4)CA(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ù)散列到表中，并同時列出各元素的比較次數(shù)如下表所示。各元素的比較次數(shù)地址01234567891011121314關鍵字406694558334772

32、87222512比較121111132312(4)計算查找成功的平均查找次數(shù)=(1X7+2X3+3X2)/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)(6,2,10,4,8,12,28,30,20,16,18)十、(本題15分)可采用層次遍歷的方式進行復制，將已復制的結(jié)點進入一個隊列中即可C語言版測試程序見exam510c,具體算當如下：voidCopyBiTree(BiTreeT_from,BiTree&T_t

33、o)/復制二叉樹T_from到T_to的非遞歸算法if(T_from=NULL)/空二叉樹的處理T_to=NULL;return;)LinkQueueQ_from,Q_to;BiTNode*e_from,*e_to;InitQueue(Q_from);InitQueue(Q_to);T_to=newBiTNode;T_to->data=T_from->data;/復制根結(jié)點EnQueue(Q_from,T_from);EnQueue(Q_to,T_to);/入隊while(QueueEmpty(Q_from)=FALSE)DeQueue(Q_from,e_from);DeQueue

34、(Q_to,e_to);出隊if(e_from->lchild!=NULL)/復制e_from左孩子e_to->lchild=newBiTNode;e_to->lchild->data=e_from->lchild->data;EnQueue(Q_from,e_from->lchild);EnQueue(Q_to,e_to->lchild);入隊)else/左孩子為空e_to->lchild=NULL;if(e_from->rchild!=NULL)/復制e_from右孩子e_to->rchild=newBiTNode;e_to

35、->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)算法求每一對頂之間的

36、最短路徑的時間復雜度是()。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)帶權的結(jié)點(6)設D=A,B,C,D,R=<E,A>,<A,B>,<B,D>,<D,E>,<D,A>則數(shù)據(jù)結(jié)構(gòu)(D,R)是()。A)樹B)圖B)線性表D)前面都正確(7)()關鍵碼序列不符合堆的定義。A) A、C、D、G、H、M、P、Q、R、XB) A、C

37、、M、D、H、P、X、G、QRC) A、D、P、R、C、Q、X、M、H、GD) A、D、C、M、P、G、H、X、R、Q(8)假定關鍵字K=442205883,允許存儲地址為四位十進制數(shù)，并且Hash地址為6111,則所采用白構(gòu)造Hash函數(shù)的方法是()。A)直接定址法B)平方取中法C)除留余數(shù)法，模為97D)折疊法(9)在算法的時間復雜度中，n表示問題規(guī)模，f(n)表示基本操作重復執(zhí)行的次數(shù)，則隨問題的規(guī)模n的增大，算法執(zhí)行時間的增長率同()相同。A)f(n)B)nC)O(n)D)前面都不正確（10）對線性表進行二分法查找，其前提條件是（）A）線性表以順序方式存儲，并且按關鍵碼值排好序B）線性

38、表以順序方式存儲，并且按關鍵碼值的檢索頻率排好序C）線性表以鏈接方式存儲，并且按關鍵碼值排好序D）線性表以鏈接方式存儲，并且按關鍵碼值的檢索頻率排好序二、（本題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分）給出一組關鍵字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)5