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

試題一一、單項(xiàng)選擇題（每小題2分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（）A）有向圖B）隊(duì)列C）線索二叉樹D）B樹（2）在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，則執(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）（）不是隊(duì)列的基本運(yùn)算。A）在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B）從隊(duì)頭刪除一個(gè)元素C）判斷一個(gè)隊(duì)列是否為空D）讀取隊(duì)頭元素的值（4）字符A、B、C依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個(gè)不同的字符串。A）14（5）由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。A）11B）35C）19D）53以下6-8題基于下圖：B）5C）6D）8（6）該二叉樹結(jié)點(diǎn)的前序遍歷的序列為（）。A）E、G、F、A、C、D、BC）E、A、C、B、D、G、FB）E、A、G、C、F、B、DD）E、G、A、C、D、F、B（7）該二叉樹結(jié)點(diǎn)的中序遍歷的序列為（）。A）A、B、C、D、E、G、FC）E、A、C、B、D、G、FB）E、A、G、C、F、B、DD）B、D、C、A、F、G、E（8）該二叉樹的按層遍歷的序列為（）。A）E、G、F、A、C、D、BB）E、A、C、B、D、G、FC）E、A、G、C、F、B、DD）E、G、A、C、D、F、B（9）下面關(guān)于圖的存儲的敘述中正確的是（）。A）用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)B）用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān)C）用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)D）用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(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,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分）設(shè)有序列：w={23,24,27,80,28}，試給出：（1）二叉排序樹；（2）哈夫曼樹；（3）平衡二叉樹；（4）對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果。五、（本題15分）假設(shè)二叉樹中每個(gè)結(jié)點(diǎn)所含數(shù)據(jù)元素均為單字母，以二叉鏈表為存儲結(jié)構(gòu)，試編寫算法按如下圖所示的樹狀顯示二叉樹?！敬鸢浮?=================================一、單項(xiàng)選擇題（1）B（6）C（2）D（7）A（3）A（4）B（8）C（9）B（5）B（10）B二、（本題8分）所構(gòu)造的堆如下圖所示：三、（本題8分）在先序序列空格中依次填A(yù)DKJ，中序中依次填BHG，后序中依次填DIEC。四、（每小題2分，共8分）（1）二叉排序樹如下圖所示：（2）哈夫曼樹如下圖所示：（3）平衡二叉樹如下圖所示：（4）對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果：28,80,27,24,23五、（本題15分）從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個(gè)結(jié)點(diǎn)，從上至下是先顯示右子樹，再顯示根，最后最左子樹，也就是以先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結(jié)點(diǎn)。C語言版測試程序見exam1\10c，具體算當(dāng)如下：voidDisplayBTWithTreeShape(BiTreeT,intlevel=1)//按樹狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點(diǎn)的層次數(shù)為1{if(T){//空樹不顯式，只顯式非空樹DisplayBTWithTreeShape(T->rchild,level+1);//顯示右子樹cout<<endl;//顯示新行for(inti=0;i<level-1;i++)cout<<"";//確保在第level列顯示結(jié)點(diǎn)//顯示結(jié)點(diǎn)cout<<T->data;DisplayBTWithTreeShape(T->lchild,level+1);//顯示左子樹}}=========================================================================試題二一、單項(xiàng)選擇題（每小題2分，共20分）（1）設(shè)Huffman樹的葉子結(jié)點(diǎn)數(shù)為m，則結(jié)點(diǎn)總數(shù)為（）。A）2mB）2m-1D）m+1C）2m+1（2）若順序存儲的循環(huán)隊(duì)列的QueueMaxSize=n，則該隊(duì)列最多可存儲（）個(gè)元素。A）nB）n-1C）n+1D）不確定（3）下述哪一條是順序存儲方式的優(yōu)點(diǎn)？（）A）存儲密度大B）插入和刪除運(yùn)算方便D）查找運(yùn)算速度快C）獲取符合某種條件的元素方便（4）設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每個(gè)元素占一個(gè)空間，問A[2][3](10)存放在什么位置？（腳注(10)表示用10進(jìn)制表示，m>3）（）。A）658B）648C）633D）653（5）下列關(guān)于二叉樹遍歷的敘述中，正確的是（）。A）若一個(gè)葉子是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)B）若一個(gè)結(jié)點(diǎn)是某二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)C）若一個(gè)結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序最后一個(gè)結(jié)點(diǎn)D）若一個(gè)樹葉是某二叉樹的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個(gè)結(jié)點(diǎn)（6）k層二叉樹的結(jié)點(diǎn)總數(shù)最多為（）。A）2k-1B）2k+1C）K-1D）k-1（7）對線性表進(jìn)行二分法查找，其前提條件是（）。A）線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序B）線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序C）線性表以順序方式存儲，并且按關(guān)鍵碼值排好序D）線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序（8）對n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲空間為（）。A）O(1og2n)B）O(n)C）O(1)D）O(n2)（9）對于線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲時(shí)，若選用H（K）=K%7作為散列函數(shù)，則散列地址為0的元素有（）個(gè)。A）1B）2C）3D）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))，分別寫出對它進(jìn)行先序、中序、后序、按層遍歷的結(jié)果。三、（本題8分）樹有哪些遍歷方法？它們分別對應(yīng)于把樹轉(zhuǎn)變?yōu)槎鏄涞哪男┍闅v方法？四、（本題8分）設(shè)有數(shù)組A[-1:3,0:6,-2:3]，按行為主序存放在2000開始的連續(xù)空間中，如元素的長度是5，試計(jì)算出A[1,1,1]的存儲位置。五、（本題8分）設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。六、（本題15分）以二叉鏈表作存儲結(jié)構(gòu)，試編寫計(jì)算二叉樹中葉子結(jié)點(diǎn)數(shù)目的遞歸算法。【答案】==================================一、單項(xiàng)選擇題（每小題2分，共20分）（1）B（6）A（2）B（7）C（3）A（8）C（4）D（5）A（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與中序遍歷方法。四、（本題8分）A[1,1,1]的存儲位置=2000+((1-(-1))*(6-0+1)*(3-(-2)+1)+(1-0)*(3-(-2)+1)+(1-(-2)))*5=2465。五、（本題8分）六、（本題15分）本題只要在遍歷二叉樹的過程序中對葉子結(jié)點(diǎn)進(jìn)行記數(shù)即可。C語言版測試程序見exam2\10c，具體算當(dāng)如下：longLeafCount(BiTreeT)//計(jì)算二叉樹中葉子結(jié)點(diǎn)數(shù)目{if(T==NULL)return0;//空樹返回0elseif(T->lchild==NULL&&T->rchild==NULL)return1;else//只有一個(gè)結(jié)點(diǎn)的樹返回1//葉子結(jié)點(diǎn)數(shù)為左右子樹的葉子結(jié)點(diǎn)數(shù)之和returnLeafCount(T->lchild)+LeafCount(T->rchild);}試題三一、單項(xiàng)選擇題（每小題2分，共20分）（1）對一個(gè)算法的評價(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=pB）p->next=HL;HL=pC）p->next=HL;p=HLD）HL=p;p->next=HL（3）對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）A）經(jīng)常需要隨機(jī)地存取元素B）經(jīng)常需要進(jìn)行插入和刪除操作C）表中元素需要占據(jù)一片連續(xù)的存儲空間D）表中元素的個(gè)數(shù)不變（4）一個(gè)棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是（）。A）231（5）每一趟都能選出一個(gè)元素放在其最終位置上，并且不穩(wěn)定的排序算法是（）。A）冒泡排序B）簡單選擇排序C）希爾排序D）直接插入排序（6）采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（）。B）321C）312D）123A）低于鏈接法處理沖突C）與鏈接法處理沖突相同B）高于鏈接法處理沖突D）高于二分查找（7）若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（）參數(shù)。A）值（8）在稀疏矩陣的帶行指針向量的鏈接存儲中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（）。A）行號B）列號C）元素值D）非零元素個(gè)數(shù)（9）快速排序在最壞情況下的時(shí)間復(fù)雜度為（）。A）O(log2n)B）O(nlog2n)C）O(n)D）O(n2)（10）從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（）。A）O(n)B）O(1)C）O(log2n)D）O(n2)二、（本題8分）B）函數(shù)C）指針D）引用如果在1000000個(gè)記錄中找出兩個(gè)最小的記錄，你認(rèn)為采用什么樣的排序方法所需的關(guān)鍵字比較次數(shù)最少？最多比較多少次？三、（本題8分）假設(shè)把n個(gè)元素的序列（a1,a2,…an）滿足條件ak<max{at|1≤t≤k}的元素ak稱為“逆序元素”。若在一個(gè)無序序列中有一對元素ai>aj(i<j)，試問，當(dāng)ai與aj相互交換后，該序列中逆序元素的個(gè)數(shù)一定不會增加，這句話對不對？如果對，請說明為什么？如果不對，請舉一例說明。四、（每小題4分，共8分）設(shè)內(nèi)存有大小為6個(gè)記錄的緩沖區(qū)供內(nèi)排序使用，文件的關(guān)鍵字序列為｛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)排序求出初始?xì)w并段；（2）用置換一選擇排序求初始?xì)w并段。五、（本題9分）已知關(guān)鍵字序列{23，13，5，28，14，25}，試構(gòu)造二叉排序樹。六、（本題15分）編寫一個(gè)算法求二又樹的深度?！敬鸢浮?=================================一、單項(xiàng)選擇題（每小題2分，共20分）（1）B（6）B（2）A（3）B（4）C（5）B（10）C（7）D（8）A（9）D二、（本題8分）采用樹形選擇排序方法所需的關(guān)鍵字比較次數(shù)最少，最多比較次數(shù)=999999+=1000019次。三、（本題8分）不對，例如序列｛3、3、4、2、l｝的“逆序元素”個(gè)數(shù)是2，2和1是“逆序元素”；但是將第二個(gè)3和2交換后，成為｛3、2、4、3、l｝，此時(shí)“逆序元素”個(gè)數(shù)是3，2、3和1是“逆序元素”。然而交換后一定減少的是“逆序?qū)Α钡膫€(gè)數(shù)，例如上例中｛3、3、4、2、l｝的逆序?qū)Φ膫€(gè)數(shù)是7，交換第二個(gè)3和2后，｛3、2、4、3、1｝的逆序?qū)Φ膫€(gè)數(shù)是6。四、（每小題4分，共8分）（1）用內(nèi)排序求出初始?xì)w并段為：歸并段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）用置換一選擇排序求初始?xì)w并段為：歸并段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)造二叉排序樹的過程如下圖所示。構(gòu)造的二叉排序樹如下圖所示：六、（本題15分）若二叉樹為空，深度為0；若二叉樹不空，則二叉樹的深度為左右子樹深度的最大值加1。本題最簡單算法是遞歸算法。C語言版測試程序見exam3\10c，具體算當(dāng)如下：intBiTreeDepth(BiTreeT)//求二叉樹的深度{if(T==NULL)return0;//空二叉樹的深度為0else{intd_lsub,d_rsub;d_lsub=BiTreeDepth(T->lchild);//左子樹的深度d_rsub=BiTreeDepth(T->rchild);//右子樹的深度//返回左右子樹的深度最大值加1return((d_lsub>d_rsub)?d_lsub:d_rsub)+1;}}試題四一、單項(xiàng)選擇題（每小題2分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（）A）有向圖B）棧C）二叉樹D）B樹（2）若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用（）存儲方式最節(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、D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個(gè)不同的字符串？A）15（5）由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。A）11B）37C）19D）53以下6-8題基于下面的敘述：B）14C）16D）21若某二叉樹結(jié)點(diǎn)的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E。（6）則該二叉樹結(jié)點(diǎn)的前序遍歷的序列為（）。A）E、G、F、A、C、D、BC）E、A、C、B、D、G、F（7）該二叉樹有（）個(gè)葉子。B）E、A、G、C、F、B、DD）E、G、A、C、D、F、BA）3B）2C）5D）4（8）該二叉樹的按層遍歷的序列為（）。A）E、G、F、A、C、D、BC）E、A、G、C、F、B、DB）E、A、C、B、D、G、FD）E、G、A、C、D、F、B（9）下面的二叉樹中，（C）不是完全二叉樹。（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}，試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹。三、（本題8分）給定一個(gè)關(guān)鍵字序列｛24，19，32，43，38，6，13，22｝，請寫出快速排序第一趟的結(jié)果；堆排序時(shí)所建的初始堆；然后回答上述兩種排序方法中哪一種方法使用的輔助空間最小，在最壞情況下哪種方法的時(shí)間復(fù)雜度最差？四、（本題8分）設(shè)二維數(shù)組A[0:10,-5:0]，按行優(yōu)先順序存儲，每個(gè)元素占4個(gè)單元，A[0][-5]的存儲地址為1000，則A[9][-2]的存儲地址為多少？五、（本題8分）用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL。請寫出后序遍歷該二叉樹的訪問結(jié)點(diǎn)序列。六、（本題8分）請說明對一棵二叉樹進(jìn)行前序、中序和后序遍歷，其葉結(jié)點(diǎn)的相對次序是否會發(fā)生改變？為什么？七、（本題9分）已知一棵二叉樹的先序序列與中序序列分別如下，試畫出此二叉樹。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI八、（本題15分）已知二叉排序樹采用二叉鏈表存儲結(jié)構(gòu)，根結(jié)點(diǎn)的指針為T，請寫出遞歸算法，從小到大輸出該二叉排序樹中所有關(guān)鍵字值≥K的結(jié)點(diǎn)的關(guān)鍵字的值。【答案】==================================一、單項(xiàng)選擇題（每小題2分，共20分）（1）B（6）C（2）C（3）A（4）B（9）C（5）B（7）A（8）C（10）B二、（本題8分）如下圖所示：三、（本題8分）快速排序的第一趟結(jié)果為｛22,19,13,6,24,38,43,12｝；堆排序時(shí)所建立的初始大頂堆如所圖所示：兩種排序方法所需輔助空間：堆是O(1)，快速排序是O(logn)，可見堆排序所需輔助空間較少；在最壞情況下兩種排序方法所需時(shí)間：堆是O(nlogn)，快速排序是O(n2)，所以，可見快速排序時(shí)間復(fù)雜度最差。注意：快速排序的平均時(shí)排序速度最快，但在最壞情況下不一定比其他排序方法快。四、（本題8分）依題意A的起始地址為1000，則有：Loc(9,-2)=1000+[(9-0)*(0-(-5)+1)+(-2-(-5))]*4=1228。五、（本題8分）先畫出該二叉樹的樹形結(jié)構(gòu)。對其進(jìn)行后序遍歷得到后序序列為：HIDJKEBLFGCA。六、（本題8分）二叉樹任兩個(gè)中葉結(jié)點(diǎn)必在某結(jié)點(diǎn)的左/右子樹中，三種遍歷方法對左右子樹的遍歷都是按左子樹在前、右子樹在后的順序進(jìn)行遍歷的。所以在三種遍歷序列中葉結(jié)點(diǎn)的相對次序是不會發(fā)生改變的。七、（本題9分）先由先序序列的第一個(gè)結(jié)點(diǎn)確定二叉樹的根結(jié)點(diǎn)，再由根結(jié)點(diǎn)在中序序列中左側(cè)部分為左子樹結(jié)點(diǎn)，在右側(cè)部分為右子樹結(jié)點(diǎn)，再由先序序列的第一個(gè)結(jié)點(diǎn)確定根結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)，由類似的方法可確定其他結(jié)點(diǎn)，如下圖所示。八、（本題15分）由于二叉排序樹是中序有序的，因此對二叉排序樹采用中序遍歷依次輸出大于等于K的結(jié)點(diǎn)即可。C語言版測試程序見exam4\10c，具體算當(dāng)如下：voidDisplayKey(BiTreeT,KeyTypeK)//從小到大輸出該二叉排序樹中所有關(guān)鍵字值≥K的結(jié)點(diǎn)的關(guān)鍵字的值{if(T){DisplayKey(T->lchild,K);if(T->data.key>=K)//輸出左子樹cout<<T->data.key<<"";//輸出滿足條件的關(guān)鍵值DisplayKey(T->rchild,K);//輸出右子樹}}試題五一、單項(xiàng)選擇題（每小題2分，共20分）（1）隊(duì)列的特點(diǎn)是（）。A）先進(jìn)后出B）先進(jìn)先出D）前面都不正確C）任意位置進(jìn)出（2）有n個(gè)記錄的文件，如關(guān)鍵字位數(shù)為d，基數(shù)為r，則基數(shù)排序共要進(jìn)行（）遍分配與收集。A）nB）dC）rD）n-d（3）在二叉樹結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）。A）都不相同C）先序和中序相同，而與后序不同（4）限定在一端加入和刪除元素的線性表稱為（）。A）雙向鏈表B）單向鏈表C）棧D）隊(duì)列（5）快速排序執(zhí)行一遍之后，已經(jīng)到位的元素個(gè)數(shù)是（）。B）完全相同D）中序和后序相同，而與先序不同A）1B）3C）D）（6）設(shè)森林F對應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹上的結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹的結(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)C）廣義表可以被其他廣義表所共享B）廣義表至少有一個(gè)元素D）廣義表可以是一個(gè)遞歸表（9）設(shè)二叉樹根結(jié)點(diǎn)的層次為0，一棵深度（高度）為k的滿二叉樹和同樣深度完全二叉樹各有f個(gè)結(jié)點(diǎn)和c個(gè)結(jié)點(diǎn)，下列關(guān)系式不正確的是（）。A）f>=cB）c>fC）f=2k+1-aD）c>sk-1（10）從L=((apple,pear),(orange,banana))中，取出banana元素的表達(dá)式為（）。A）head(tail(L))B）head(head(tail(L)))C）tail(head(tail(L)))四、（每小題4分，共8分）D）head(tail(head(tail(L))))判斷以下序列是否是小根堆?如果不是，將它調(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分）設(shè)有12個(gè)數(shù)據(jù)25,40,33,47,12,66,72,87,94,22,5,58，它們存儲在散列表中，利用線性探測再散列處理沖突，取散列函數(shù)為H(key)=key%13。（1）順次將各個(gè)數(shù)據(jù)散列到表中，并同時(shí)列出各元素的比較次數(shù)。（2）計(jì)算查找成功的平均查找次數(shù)。八、（本題8分）已知一棵樹邊的結(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)}試畫出這棵樹，并回答下列問題：（1）哪個(gè)是根結(jié)點(diǎn)？（2）哪些是葉子結(jié)點(diǎn)？（3）樹的深度是多少？九、（本題9分）給出一組關(guān)鍵字T=(12,2,16,30,8,28,4,10,20,6,18)。寫出用下列算法從小到大排序時(shí)第一趟結(jié)束時(shí)的序列。（1）希爾排序（第一趟排序的增量為5）（2）快速排序（選第一個(gè)記錄為樞軸）十、（本題15分）編寫復(fù)制一棵二叉樹的非遞歸算法?！敬鸢浮?=================================一、單項(xiàng)選擇題（每小題2分，共20分）（1）B（6）D（2）B（7）C（3）B（8）B（4）C（9）B（5）A（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ù)散列到表中，并同時(shí)列出各元素的比較次數(shù)如下表所示。各元素的比較次數(shù)地址關(guān)鍵字比較0140669412345516581733184772191087211223122511312214213（4）計(jì)算查找成功的平均查找次數(shù)=（1×7+2×3+3×2）/12=19/12。八、（本題8分）【解答】樹，如下圖所示：（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ì)列中即可。C語言版測試程序見exam5\10c，具體算當(dāng)如下：voidCopyBiTree(BiTreeT_from,BiTree&T_to)//復(fù)制二叉樹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;//復(fù)制根結(jié)點(diǎn)//入隊(duì)EnQueue(Q_from,T_from);EnQueue(Q_to,T_to);while(QueueEmpty(Q_from)==FALSE){DeQueue(Q_from,e_from);DeQueue(Q_to,e_to);if(e_from->lchild!=NULL)//出隊(duì){//復(fù)制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);//入隊(duì)}elsee_to->lchild=NULL;//左孩子為空if(e_from->rchild!=NULL){//復(fù)制e_from右孩子e_to->rchild=newBiTNode;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)中，不利于文件長度動態(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）實(shí)體B）域C）數(shù)據(jù)項(xiàng)D）字段（3）對于有n個(gè)頂點(diǎn)的有向圖，由弗洛伊德（Floyd）算法求每一對頂之間的最短路徑的時(shí)間復(fù)雜度是（）。A）O(1)B）O(n)C）O(n)D）O(n3)（4）對n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間為（）。A）O（1）B）O（log2n）C）O（n）D）O（n2）（5）哈夫曼樹中一定不存在（）。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={<E,A>,<A,B>,<B,D>,<D,E>,<D,A>}，則數(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）假定關(guān)鍵字K=442205883，允許存儲地址為四位十進(jìn)制數(shù)，并且Hash地址為6111，則所采用的構(gòu)造Hash函數(shù)的方法是（）。A）直接定址法B）平方取中法C）除留余數(shù)法，模為97D）折疊法（9）在算法的時(shí)間復(fù)雜度中，n表示問題規(guī)模，f(n)表示基本操作重復(fù)執(zhí)行的次數(shù)，則隨問題的規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率同（）相同。A）f(n)B）nC）O(n)D）前面都不正確（10）對線性表進(jìn)行二分法查找，其前提條件是（）。A）線性表以順序方式存儲，并且按關(guān)鍵碼值排好序B）線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序C）線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序D）線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序二、（本題8分）在如下表所示的數(shù)組A中鏈接存儲了一個(gè)線性表，表頭指針存放在A[0].next，試寫出該線性表。線性表ADatanext041600250537824907534167403三、（本題8分）已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ，中序遍歷的結(jié)果是KBCDAFHIGJ，試畫出這棵二叉樹。五、（本題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í)的變化過程：（1）歸并排序，每歸并一次書寫一個(gè)次序。（2）快速排序，每劃分一次書寫一個(gè)次序以及最后