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

...wd......wd......wd...試題一一、單項(xiàng)選擇題〔每題2分，共20分〕〔1〕以下數(shù)據(jù)構(gòu)造中哪一個(gè)是線性構(gòu)造〔〕A〕有向圖B〕隊(duì)列C〕線索二叉樹(shù)D〕B樹(shù)〔2〕在一個(gè)單鏈表HL中，假設(shè)要在當(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è)棧，按出棧的先后順序組成不同的字符串，至多可以組成〔〕個(gè)不同的字符串。A〕14B〕5C〕6D〕8〔5〕由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為〔〕。A〕11B〕35C〕19D〕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、F B〕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、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)于圖的存儲(chǔ)的表達(dá)中正確的選項(xiàng)是〔〕。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,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分〕對(duì)于序列{8,18,6,16,29,28}，試寫(xiě)出堆頂元素最小的初始堆。三、〔此題8分〕一棵二叉樹(shù)的先序、中序和后序序列分別如下，其中有一局部未顯示出來(lái)。試求出空格處的內(nèi)容，并畫(huà)出該二叉樹(shù)。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA四、〔每題2分，共8分〕設(shè)有序列：w={23,24,27,80,28}，試給出：〔1〕二叉排序樹(shù)；〔2〕哈夫曼樹(shù)；〔3〕平衡二叉樹(shù)；〔4〕對(duì)于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果。五、〔此題15分〕假設(shè)二叉樹(shù)中每個(gè)結(jié)點(diǎn)所含數(shù)據(jù)元素均為單字母，以二叉鏈表為存儲(chǔ)構(gòu)造，試編寫(xiě)算法按如以以下圖所示的樹(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分〕在先序序列空格中依次填A(yù)DKJ，中序中依次填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ù)的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個(gè)結(jié)點(diǎn)，從上至下是先顯示右子樹(shù)，再顯示根，最后最左子樹(shù)，也就是以先遍歷右子樹(shù)，最后遍歷左子樹(shù)的中序遍歷次序顯示各結(jié)點(diǎn)。C語(yǔ)言版測(cè)試程序見(jiàn)exam1\10c，具體算當(dāng)如下：voidDisplayBTWithTreeShape(BiTreeT,intlevel=1)// 按樹(shù)狀形式顯示二叉樹(shù)，level為層次數(shù)，可設(shè)根結(jié)點(diǎn)的層次數(shù)為1{ if(T){ //空樹(shù)不顯式，只顯式非空樹(shù)DisplayBTWithTreeShape(T->rchild,level+1); //顯示右子樹(shù) cout<<endl; //顯示新行 for(inti=0;i<level-1;i++) cout<<""; //確保在第level列顯示結(jié)點(diǎn)cout<<T->data; //顯示結(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〕2mB〕2m-1C〕2m+1 D〕m+1〔2〕假設(shè)順序存儲(chǔ)的循環(huán)隊(duì)列的QueueMaxSize=n，則該隊(duì)列最多可存儲(chǔ)〔〕個(gè)元素。A〕nB〕n-1C〕n+1D〕不確定〔3〕下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)〔〕A〕存儲(chǔ)密度大B〕插入和刪除運(yùn)算方便C〕獲取符合某種條件的元素方便D〕查找運(yùn)算速度快〔4〕設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每個(gè)元素占一個(gè)空間，問(wèn)A[2][3](10)存放在什么位置〔腳注(10)表示用10進(jìn)制表示，m>3〕〔〕。A〕658 B〕648 C〕633D〕653〔5〕以下關(guān)于二叉樹(shù)遍歷的表達(dá)中，正確的選項(xiàng)是〔〕。A〕假設(shè)一個(gè)葉子是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)B〕假設(shè)一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)C〕假設(shè)一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)D〕假設(shè)一個(gè)樹(shù)葉是某二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的中序遍歷最后一個(gè)結(jié)點(diǎn)〔6〕k層二叉樹(shù)的結(jié)點(diǎn)總數(shù)最多為〔〕。A〕2k-1B〕2k+1C〕K-1D〕k-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í)，假設(shè)選用H〔K〕=K%7作為散列函數(shù)，則散列地址為0的元素有〔〕個(gè)。A〕1 B〕2 C〕3 D〕4〔10〕以下關(guān)于數(shù)據(jù)構(gòu)造的表達(dá)中，正確的選項(xiàng)是〔〕。A〕數(shù)組是不同類型值的集合B〕遞歸算法的程序構(gòu)造比迭代算法的程序構(gòu)造更為精煉C〕樹(shù)是一種線性構(gòu)造D〕用一維數(shù)組存儲(chǔ)一棵完全二叉樹(shù)是有效的存儲(chǔ)方法二、〔此題8分〕假定一棵二叉樹(shù)廣義表表示為a(b(c),d(e,f))，分別寫(xiě)出對(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)場(chǎng)的連續(xù)空間中，如元素的長(zhǎng)度是5，試計(jì)算出A[1,1,1]的存儲(chǔ)位置。五、〔此題8分〕設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹(shù)。六、〔此題15分〕以二叉鏈表作存儲(chǔ)構(gòu)造，試編寫(xiě)計(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ù)后的先序遍歷與中序遍歷方法。四、〔此題8分〕A[1,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)exam2\10c，具體算當(dāng)如下：longLeafCount(BiTreeT)// 計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)目{ if(T==NULL) return0; //空樹(shù)返回0elseif(T->lchild==NULL&&T->rchild==NULL) return1; //只有一個(gè)結(jié)點(diǎn)的樹(shù)返回1 else //葉子結(jié)點(diǎn)數(shù)為左右子樹(shù)的葉子結(jié)點(diǎn)數(shù)之和 returnLeafCount(T->lchild)+LeafCount(T->rchild); }試題三一、單項(xiàng)選擇題〔每題2分，共20分〕〔1〕對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下〔〕方面的內(nèi)容。A〕強(qiáng)健性和可讀性 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〕對(duì)線性表，在以下哪種情況下應(yīng)當(dāng)采用鏈表表示〔〕A〕經(jīng)常需要隨機(jī)地存取元素B〕經(jīng)常需要進(jìn)展插入和刪除操作C〕表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間 D〕表中元素的個(gè)數(shù)不變〔4〕一個(gè)棧的輸入序列為123，則以下序列中不可能是棧的輸出序列的是〔〕。A〕231 B〕321C〕312 D〕123〔5〕每一趟都能選出一個(gè)元素放在其最終位置上，并且不穩(wěn)定的排序算法是〔〕。A〕冒泡排序 B〕簡(jiǎn)單項(xiàng)選擇擇排序C〕希爾排序 D〕直接插入排序〔6〕采用開(kāi)放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度〔〕。A〕低于鏈接法處理沖突 B〕高于鏈接法處理沖突C〕與鏈接法處理沖突一樣 D〕高于二分查找〔7〕假設(shè)需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為〔〕參數(shù)。A〕值 B〕函數(shù) C〕指針 D〕引用〔8〕在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(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〕滿足條件ak<max{at|1≤t≤k}的元素ak稱為“逆序元素〞。假設(shè)在一個(gè)無(wú)序序列中有一對(duì)元素ai>aj(i<j)，試問(wèn)，當(dāng)ai與aj相互交換后，該序列中逆序元素的個(gè)數(shù)一定不會(huì)增加，這句話對(duì)不對(duì)如果對(duì)，請(qǐng)說(shuō)明為什么如果不對(duì)，請(qǐng)舉一例說(shuō)明。四、〔每題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)造二叉排序樹(shù)。六、〔此題15分〕編寫(xiě)一個(gè)算法求二又樹(shù)的深度。【答案】==================================一、單項(xiàng)選擇題〔每題2分，共20分〕〔1〕B 〔2〕A 〔3〕B 〔4〕C 〔5〕B〔6〕B 〔7〕D 〔8〕A 〔9〕D 〔10〕C二、〔此題8分〕采用樹(shù)形選擇排序方法所需的關(guān)鍵字比擬次數(shù)最少，最多比擬次數(shù)=999999+=1000019次。三、〔此題8分〕不對(duì)，例如序列｛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)造二叉排序樹(shù)的過(guò)程如以以下圖所示。構(gòu)造的二叉排序樹(shù)如以以下圖所示：六、〔此題15分〕假設(shè)二叉樹(shù)為空，深度為0；假設(shè)二叉樹(shù)不空，則二叉樹(shù)的深度為左右子樹(shù)深度的最大值加1。此題最簡(jiǎn)單算法是遞歸算法。C語(yǔ)言版測(cè)試程序見(jiàn)exam3\10c，具體算當(dāng)如下：intBiTreeDepth(BiTreeT)// 求二叉樹(shù)的深度{ if(T==NULL) return0; //空二叉樹(shù)的深度為0else { intd_lsub,d_rsub;d_lsub=BiTreeDepth(T->lchild); //左子樹(shù)的深度 d_rsub=BiTreeDepth(T->rchild); //右子樹(shù)的深度 //返回左右子樹(shù)的深度最大值加1 return((d_lsub>d_rsub)?d_lsub:d_rsub)+1; }}試題四一、單項(xiàng)選擇題〔每題2分，共20分〕〔1〕以下數(shù)據(jù)構(gòu)造中哪一個(gè)是線性構(gòu)造〔〕A〕有向圖B〕棧C〕二叉樹(shù)D〕B樹(shù)〔2〕假設(shè)某鏈表最常用的操作是在最后一個(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、D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成〔〕個(gè)不同的字符串A〕15B〕14C〕16D〕21〔5〕由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為〔〕。A〕11B〕37C〕19D〕53以下6-8題基于下面的表達(dá)：假設(shè)某二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為A、B、C、D、E、F、G，后序遍歷的序列為B、D、C、A、F、G、E?！?〕則該二叉樹(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、FD〕E、G、A、C、D、F、B〔7〕該二叉樹(shù)有〔〕個(gè)葉子。A〕3B〕2C〕5D〕4〔8〕該二叉樹(shù)的按層遍歷的序列為〔〕。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〕下面的二叉樹(shù)中，〔C〕不是完全二叉樹(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}，試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹(shù)。三、〔此題8分〕給定一個(gè)關(guān)鍵字序列｛24，19，32，43，38，6，13，22｝，請(qǐng)寫(xiě)出快速排序第一趟的結(jié)果；堆排序時(shí)所建的初始堆；然后答復(fù)上述兩種排序方法中哪一種方法使用的輔助空間最小，在最壞情況下哪種方法的時(shí)間復(fù)雜度最差四、〔此題8分〕設(shè)二維數(shù)組A[0:10,-5:0]，按行優(yōu)先順序存儲(chǔ)，每個(gè)元素占4個(gè)單元，A[0][-5]的存儲(chǔ)地址為1000，則A[9][-2]的存儲(chǔ)地址為多少五、〔此題8分〕用一維數(shù)組存放的一棵完全二叉樹(shù)：ABCDEFGHIJKL。請(qǐng)寫(xiě)出后序遍歷該二叉樹(shù)的訪問(wèn)結(jié)點(diǎn)序列。六、〔此題8分〕請(qǐng)說(shuō)明對(duì)一棵二叉樹(shù)進(jìn)展前序、中序和后序遍歷，其葉結(jié)點(diǎn)的相對(duì)次序是否會(huì)發(fā)生改變?yōu)槭裁雌?、〔此題9分〕一棵二叉樹(shù)的先序序列與中序序列分別如下，試畫(huà)出此二叉樹(shù)。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI八、〔此題15分〕二叉排序樹(shù)采用二叉鏈表存儲(chǔ)構(gòu)造，根結(jié)點(diǎn)的指針為T(mén)，請(qǐng)寫(xiě)出遞歸算法，從小到大輸出該二叉排序樹(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í)所建設(shè)的初始大頂堆如所圖所示：兩種排序方法所需輔助空間：堆是O(1)，快速排序是O(logn)，可見(jiàn)堆排序所需輔助空間較少；在最壞情況下兩種排序方法所需時(shí)間：堆是O(nlogn)，快速排序是O(n2)，所以，可見(jiàn)快速排序時(shí)間復(fù)雜度最差。注意：快速排序的平均時(shí)排序速度最快，但在最壞情況下不一定比其他排序方法快。四、〔此題8分〕依題意A的起始地址為1000，則有：Loc(9,-2)=1000+[(9-0)*(0-(-5)+1)+(-2-(-5))]*4=1228。五、〔此題8分〕先畫(huà)出該二叉樹(shù)的樹(shù)形構(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ā)生改變的。七、〔此題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)exam4\10c，具體算當(dāng)如下：voidDisplayKey(BiTreeT,KeyTypeK)// 從小到大輸出該二叉排序樹(shù)中所有關(guān)鍵字值≥K的結(jié)點(diǎn)的關(guān)鍵字的值{if(T) { DisplayKey(T->lchild,K); //輸出左子樹(shù)if(T->data.key>=K)cout<<T->data.key<<""; //輸出滿足條件的關(guān)鍵值 DisplayKey(T->rchild,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〕n B〕d C〕r D〕n-d〔3〕在二叉樹(shù)結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序〔〕。A〕都不一樣 B〕完全一樣C〕先序和中序一樣，而與后序不同 D〕中序和后序一樣，而與先序不同〔4〕限定在一端參加和刪除元素的線性表稱為〔〕。A〕雙向鏈表 B〕單向鏈表 C〕棧D〕隊(duì)列〔5〕快速排序執(zhí)行一遍之后，已經(jīng)到位的元素個(gè)數(shù)是〔〕。A〕1 B〕3 C〕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-1 B〕n+1 C〕m-n+1D〕m-n〔7〕設(shè)有198個(gè)初始?xì)w并段，如采用K-路平衡歸并三遍完成排序，則K值最大為〔〕。A〕12 B〕13 C〕14D〕15〔8〕下面關(guān)于廣義表的表達(dá)中，不正確的選項(xiàng)是〔〕。A〕廣義表可以是一個(gè)多層次的構(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)系式不正確的選項(xiàng)是〔〕。A〕f>=cB〕c>f C〕f=2k+1-a D〕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)))D〕head(tail(head(tail(L))))四、〔每題4分，共8分〕判斷以下序列是否是小根堆?如果不是，將它調(diào)整為小根堆?！?〕{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，它們存儲(chǔ)在散列表中，利用線性探測(cè)再散列處理沖突，取散列函數(shù)為H(key)=key%13?！?〕順次將各個(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)}試畫(huà)出這棵樹(shù)，并答復(fù)以下問(wèn)題：〔1〕哪個(gè)是根結(jié)點(diǎn)〔2〕哪些是葉子結(jié)點(diǎn)〔3〕樹(shù)的深度是多少九、〔此題9分〕給出一組關(guān)鍵字T=(12,2,16,30,8,28,4,10,20,6,18)。寫(xiě)出用以下算法從小到大排序時(shí)第一趟完畢時(shí)的序列?！?〕希爾排序〔第一趟排序的增量為5〕〔2〕快速排序〔選第一個(gè)記錄為樞軸〕十、〔此題15分〕編寫(xiě)復(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ù)散列到表中，并同時(shí)列出各元素的比擬次數(shù)如下表所示。各元素的比擬次數(shù)地址01234567891011121314關(guān)鍵字40669455833477287222512比擬121111132312〔4〕計(jì)算查找成功的平均查找次數(shù)=〔1×7+2×3+3×2〕/12=19/12。八、〔此題8分〕【解答】樹(shù)，如以以下圖所示：〔1〕C是根結(jié)點(diǎn)?！?〕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語(yǔ)言版測(cè)試程序見(jiàn)exam5\10c，具體算當(dāng)如下：voidCopyBiTree(BiTreeT_from,BiTree&T_to)// 復(fù)制二叉樹(shù)T_from到T_to的非遞歸算法{if(T_from==NULL) { //空二叉樹(shù)的處理 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) EnQueue(Q_from,T_from);EnQueue(Q_to,T_to); //入隊(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=newBiTNode; e_to->lchild->data=e_from->lchild->data; EnQueue(Q_from,e_from->lchild);EnQueue(Q_to,e_to->lchild);//入隊(duì) } else e_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ì) } else e_to->rchild=NULL; //右孩子為空 }}試題六一、單項(xiàng)選擇題〔每題2分，共20分〕〔1〕以下文件的物理構(gòu)造中，不利于文件長(zhǎng)度動(dòng)態(tài)增長(zhǎng)的文件物理構(gòu)造是〔〕。A〕順序構(gòu)造B〕鏈接構(gòu)造C〕索引構(gòu)造D〕Hash構(gòu)造〔2〕在數(shù)據(jù)構(gòu)造中，數(shù)據(jù)元素可由〔〕。A〕實(shí)體 B〕域 C〕數(shù)據(jù)項(xiàng) D〕字段〔3〕對(duì)于有n個(gè)頂點(diǎn)的有向圖，由弗洛伊德〔Floyd〕算法求每一對(duì)頂之間的最短路徑的時(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={<E,A>,<A,B>,<B,D>,<D,E>,<D,A>}，則數(shù)據(jù)構(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〕假定關(guān)鍵字K=442205883，允許存儲(chǔ)地址為四位十進(jìn)制數(shù)，并且Hash地址為6111，則所采用的構(gòu)造Hash函數(shù)的方法是〔〕。A〕直接定址法 B〕平方取中法 C〕除留余數(shù)法，模為97 D〕折疊法〔9〕在算法的時(shí)間復(fù)雜度中，n表示問(wèn)題規(guī)模，f(n)表示根本操作重復(fù)執(zhí)行的次數(shù)，則隨問(wèn)題的規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率同〔〕一樣。A〕f(n)B〕n C〕O(n) D〕前面都不正確〔10〕對(duì)線性表進(jìn)展二分法查找，其前提條件是〔〕。A〕線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序B〕線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C〕線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D〕線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序二、〔此題8分〕在如下表所示的數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針存放在A[0].next，試寫(xiě)出該線性表。線性表A01234567Data605078903440next4052713三、〔此題8分〕一棵二叉樹(shù)的前序遍歷的結(jié)果是ABKCDFGHIJ，中序遍歷的結(jié)果是KBCDAFHIGJ，試畫(huà)出這棵二叉樹(shù)。五、〔此題8分〕向最小根堆中依次插入數(shù)據(jù)4,2,5,8,3,6,10,1時(shí)，畫(huà)出每插入一個(gè)數(shù)據(jù)后堆的變化。八、〔此題8分〕給出一組關(guān)鍵字29、18、25、47、58、12、51、10，分別寫(xiě)出按以下各種排序方法進(jìn)展排序時(shí)的變化過(guò)程：〔1〕歸并排序，每歸并一次書(shū)寫(xiě)一個(gè)次序。〔2〕快速排序，每劃分一次書(shū)寫(xiě)一個(gè)次序以及最后排好序后的序列?！?〕快速排序： (10,18,25,12)29(58,5