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

（1）若以1234作為雙端隊列的輸入序列，則既不能由輸入受限雙端隊列得到，也不能由輸出受限雙端隊列得到的輸出序列是（）。A）1234 B）4132 C）4231 D）4213（2）將一個A[1..100,1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[298]中，A中元素a66,65在B數(shù)組中的位置k為（）（假設(shè)B[0]的位置是1）。 A）198 B）195 C）197 D）198（3）若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為（）。A）n-1 B） C） D）（4）若一個有向圖具有拓撲排序序列，并且頂點按拓撲排序序列編號，那么它的鄰接矩陣必定為（）。A）對稱矩陣 B）稀疏矩陣 C）三角矩陣 D）一般矩陣（5）設(shè)森林F對應(yīng)的二叉樹為有m個結(jié)點，此二叉樹根的左子樹的結(jié)點個數(shù)為k，則另一棵子樹的結(jié)點個數(shù)為（）。A）m-k+1 B）k+1 C）m-k-1 D）m-k（6）假定有K個關(guān)鍵字互為同義詞，若用線性探測法把這K個關(guān)鍵字存入散列表中，至少要進行（）次探測。A）K-1次 B）K次 C）K＋l次 D）K(K+1)/2次（7）一棵深度為k的平衡二叉樹，其每個非終端結(jié)點的平衡因子均為0，則該樹共有（）個結(jié)點。A）2k-1-1 B）2k-1 C）2k-1+1 D）2k-1（8）如表r有100000個元素，前99999個元素遞增有序，則采用（）方法比較次數(shù)較少。A）直接插入排序 B）快速排序 C）歸并排序 D）選擇排序（9）如果只考慮有序樹的情形，那么具有7個結(jié)點的不同形態(tài)的樹共有（）棵。A）132 B）154 C）429 D）前面均不正確（10）對n(n>=2)個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（）。A）該樹一定是一棵完全二叉樹B）樹中一定沒有度為1的結(jié)點C）樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D）樹中任一非葉結(jié)點的權(quán)值一定不小于下一任一結(jié)點的權(quán)值二、（本題8分）斐波那契數(shù)列Fn定義如下：F0=0，F(xiàn)1=1，F(xiàn)n=Fn-1+Fn-2請就此斐波那契數(shù)列，回答下列問題：（1）在遞歸計算Fn的時候，需要對較小的Fn-1，F(xiàn)n-2，…，F(xiàn)1，F(xiàn)0精確計算多少次？（2）若用有關(guān)大O表示法，試給出遞歸計算Fn時遞歸函數(shù)的時間復(fù)雜度是多少？三、（本題8分）證明：如果一棵二叉樹的后序序列是,,…,，中序序列是,,…,，則由序列1,2,…,n可通過一個棧得到序列,,…,。四、（本題8分）如下圖所示為5個鄉(xiāng)鎮(zhèn)之間的交通圖，鄉(xiāng)鎮(zhèn)之間道路的長度如圖中邊上所注?，F(xiàn)在要在這5個鄉(xiāng)鎮(zhèn)中選擇一個鄉(xiāng)鎮(zhèn)建立一個消防站，問這個消防站應(yīng)建在哪個鄉(xiāng)鎮(zhèn)，才能使離消防站最遠的鄉(xiāng)鎮(zhèn)到消防站的路程最短。試回答解決上述問題應(yīng)采用什么算法，并寫出應(yīng)用該算法解答上述問題的每一步計算結(jié)果。五、（本題8分）證明一個深度為n的AVL樹中的最少結(jié)點數(shù)為：Nn=Fn+2-1(n≥0)其中，F(xiàn)i為Fibonacci數(shù)列的第i項。六、（本題8分）簡單回答有關(guān)AVL樹的問題：（北方名校經(jīng)典試題）（1）在有n個結(jié)點的AVL樹中，為結(jié)點增加一個存放結(jié)點高度的數(shù)據(jù)成員，那么每一個結(jié)點需要增加多少個字位（bit）？（2）若每一個結(jié)點中的高度計數(shù)器有8bit，那么這樣的AVL樹可以有多少層？最少有多少個關(guān)鍵字？七、（本題8分）（1）該散列表的大小m應(yīng)設(shè)計多大？（2）試為該散列表設(shè)計相應(yīng)的散列函數(shù)。（3）順次將各個數(shù)據(jù)散列到表中。（4）計算查找成功的平均查找次數(shù)。八、（本題8分）已知某電文中共出現(xiàn)了10種不同的字母，每個字母出現(xiàn)的頻率分別為A：8，B：5，C：3，D：2，E：7，F(xiàn)：23，G：9，H：11，I：2，J：35，現(xiàn)在對這段電文用三進制進行編碼（即碼字由0，l，2組成），問電文編碼總長度至少有多少位？請畫出相應(yīng)的圖。九、（本題9分）已知一棵度為m的樹中有N1個度為1的結(jié)點，N2個度為2的結(jié)點，…，Nm個度為m的結(jié)點。試問該樹中有多少個葉子結(jié)點？（北方名校經(jīng)典試題）十、（本題15分）試用遞歸法編寫輸出從n個數(shù)中挑選k個進行排列所得序列的算法。模擬試題（七）參考答案一、單項選擇題（每小題2分，共20分）（1）參考答案：C）（2）【參考答案：B）（3）【分析】在哈夫曼樹的非葉結(jié)點中最多只有1個結(jié)點的度不為m，設(shè)非葉結(jié)點的個數(shù)為k，則其中有k-1個結(jié)點的度為m，設(shè)另1個結(jié)點的度為u，則2≤u≤m，設(shè)結(jié)點總數(shù)為n總，則有如下關(guān)系：n總-1=m(k-1)+u ①n總=k+n ②將②代入①可得：k+n-1=m(k-1)+u，解得：，由于2≤u≤m，所以可得0≤m-u＜m-1，所以可得：≤k＜+1，可知。參考答案：C）（4）【分析】設(shè)頂點按拓撲排序序列為：v0,v1,…,vn-1，則對于鄰接矩陣A，只有當i<j時，才可能有弧<vi,vj>，也就是當i>j時，一定沒有弧<vi,vj>，所以這時A[i][j]=0，可知鄰接矩陣為三角矩陣。參考答案：C）（5）【分析】設(shè)另一棵子樹的結(jié)點個數(shù)為n，所以有m=n+k+1，可知n=m-k-l。參考答案：C）（6）【分析】因為K個關(guān)鍵字互為同義詞，只有在存入第一個關(guān)鍵字的情況下不發(fā)生沖突，所以至少需進行1+2+…+K=K(K+1)/2次探測。參考答案：D）（7）【分析】由于每個非終端結(jié)點的平衡因子均為0，所以每個非終端結(jié)點必有左右兩個孩子，且左子樹的高度和右子樹的高度相同，這樣AVL樹是滿二叉樹。高度為k的滿二叉樹的結(jié)點數(shù)為2k-l。參考答案：D）（8）【參考答案：A）（9）【分析】具有n個結(jié)點有不同形態(tài)的樹的數(shù)目和具有n-l個結(jié)點互不相似的二叉樹的數(shù)目相同（將樹轉(zhuǎn)化為二叉樹時，根結(jié)點右子樹為空，所以除根結(jié)點而外只有左子樹，其不相似的二叉樹的等價于不相似的左子樹）。具有n個結(jié)點互不相似的二又樹的數(shù)目為，本題中應(yīng)為。參考答案：A）（10）參考答案：A）二、（本題8分）【解答】（1）設(shè)在計算Fn時，由Fn-1+Fn-2可知Fn-1要精確計算1次；由Fn-1=Fn-2+Fn-3可知Fn=2Fn-2+Fn-3，F(xiàn)n-2要精確計算2次；由Fn-2=Fn-3+Fn-4可知Fn=3Fn-3+2Fn-4，F(xiàn)n-3要精確計算3次，F(xiàn)n=3Fn-3+2Fn-4公式中Fn-3的系數(shù)為Fn-3要精確計算次數(shù)，而Fn-4的系數(shù)為Fn-2要精確計算次數(shù)，以此類推，設(shè)Fn-j的精確計算次為aj，則有：Fn=aj*Fn-j+aj-1*Fn-j-1。由Fn-j=Fn-j-1+Fn-j-2可知Fn=(aj+aj-1)*Fn-j-1+aj*Fn-j-2，F(xiàn)n-j-1的精確計算次數(shù)為aj+1，所以有：aj+1=aj+aj-1由于Fn-1要精確計算a1為1次，即a1=1，即可知Fn-1，F(xiàn)n-2，…，F(xiàn)1，F(xiàn)0的精確計算次為：1，2，3，5，……，aj=aj-1+aj-2……與斐波那契數(shù)列數(shù)列：0，1，2，3，5，……，F(xiàn)n=Fn-1+Fn-2……比較可知aj=Fj+1。（2）由于Fn的計算最終要轉(zhuǎn)化為F0與F1之和，其加法的計算次數(shù)為F0與F1的精確計算次數(shù)之和再減1之差，由于F0=Fn-n與F1=Fn-(n-1)，所以計算Fn時，加法計算次數(shù)為：an+an-1-1=Fn+1+Fn-1由于Fn=，可知時間復(fù)雜度為O()。三、（本題8分）【解答】當n=1時，結(jié)論顯然成立。設(shè)n<=k時結(jié)論成立，當n=k+1時，設(shè)一棵二叉樹的后序序列是,,…,，中序序列是,,…,，可知是二叉樹的根結(jié)點，設(shè)，可知{,,…,}是左子樹的結(jié)點集合，{,,…,}是右子樹的結(jié)點集合，進一步可知：（1）左子樹的后序序列是,,…,，中序序列是,,…,，由歸納假設(shè)知序列1,2,…,j-1可以通過一個棧得序列,,…,。（2）右子樹的后序序列是,,…,，中序序列是,,…,，設(shè)，，…，；，，…，，則，，…，，由歸納假設(shè)知序列1,2,…,n-j可以通過一個棧得序列，，…，，顯然按同樣的方式，j,j+1,…,n-1可以通過一個棧得序列,,…,，也就是，，…，。由（1）（2）及可知由1,2,…,n可通過一個棧得到序列,,…,。由數(shù)學(xué)歸納法可知本題結(jié)論成立。四、（本題8分）【解答】由弗洛伊德（Floyd）算法進行求解，具體步驟如下：，；，；，。設(shè)鄉(xiāng)鎮(zhèn)vi到其他各鄉(xiāng)鎮(zhèn)的最遠距離為max_disdance(vi)，則有：max_disdance(v1)=12，max_disdance(v2)=15，max_disdance(v3)=10，max_disdance(v4)=10，max_disdance(v5)=15，所以可知消防站應(yīng)建在v3或v4鄉(xiāng)鎮(zhèn)，才能使離消防站最遠的鄉(xiāng)鎮(zhèn)到消防站的路程最短。五、（本題8分）【解答】對n用歸納法證明。當n＝1時，有N1=F3-l=2-l=1到。當n=2時，有N2=F4-1=3-1=2。設(shè)n<k時也成立，即有Nn=Fn+2-1成立。當n=k+1，對于一個k+l層深度的平衡二叉樹而言，其左右子樹都是平衡的。結(jié)點數(shù)為最少的極端情況，故左右子樹中的結(jié)點數(shù)是不相等的，設(shè)其中一個是k層深度的二叉平衡樹，另一個是k-l層深度的二叉平衡樹。所以有：Nk+1=1+Nk+Nk-1==1+(Fk+2-1)+(Fk+1-1)=Fk+2+Fk+1-1=Fk+3-1當n=k+1時成立，由此可知深度為n都等式都成立。六、（本題8分）【解答】n個結(jié)點的平衡二叉樹的最大高度為，設(shè)表示高度需xbit，則有關(guān)系式：2x≥h＞2x-1，所以有：（2）設(shè)深度為h的平衡二叉樹的最少關(guān)鍵字數(shù)為nh，則有公式：，本題中8bit的計數(shù)器共可以表示28=256層，即高度為256，從而可知最少有個關(guān)鍵字。七、（本題8分）【解答】（1）線性探測再散列的哈希表查找成功的平均查找長度為：≤3，解得α≤4／5，也就是12/m≤4／5，所以m≥15，可取m=15。（2）散列函數(shù)可取為H(key)=key%13（3）散列表如表7-4所示。散列表0123456789101112131440669455833477287222512（4）12個數(shù)據(jù){25，40，33，47，12，66，72，87，94，22，5，58｝的比較次數(shù)分別是：1，1，1，1，2，2，3，2，1，3，1，1?？芍檎页晒Φ钠骄檎掖螖?shù)=(1+1+1+1+2+2+3+2+1+3+1+1)/12=1.25八、（本題8分）【解答】有n個葉子結(jié)點的帶權(quán)路徑長度最短的二叉樹稱哈夫曼樹，同理，存在有n個葉子結(jié)點的帶權(quán)路徑長度最短的三叉、四叉、……、k叉樹，也稱為哈夫曼樹。如葉子結(jié)點數(shù)目不足以構(gòu)成正則的k叉樹（樹中只有度為k或0的結(jié)點），即不滿足(n-l)MOD(k-l)=0，需要添加權(quán)為0的結(jié)點，添加權(quán)為0的結(jié)點的個數(shù)為：k-(n-1)MOD(k-1)-1。添加的位置應(yīng)該是距離根結(jié)點的最遠處。所構(gòu)造出的哈夫曼樹如下圖所示：其中，每個字母的編碼長度等于葉子結(jié)點的路徑長度，電文的總長度為=191。注釋：對于正則的k叉樹，設(shè)葉結(jié)點數(shù)為n，度為k的結(jié)點數(shù)為nk，結(jié)點總數(shù)為m,則有m-1=knk，m=nk+n，兩式相減可得n-1=(k-1)nk，即(n-l)MOD(k-l)=0；如n與k不滿足此關(guān)系，n加上k-(n-1)MOD(k-1)-1后，n’=n+(k-(n-1)MOD(k-1)-1)，這時：(n’-l)MOD(k-l)=(n+(k-(n-1)MOD(k-1)-1)-l)MOD(k-l)=((n-1)+(k-1)-(n-1)MOD(k-1))MOD(k-l)=((n-1)-(n-1)MOD(k-1))MOD(k-l)=0。現(xiàn)有12個初始歸并段，其記錄數(shù)分別為｛30,44,8,6,3,20,60,18,9,62,68,85｝，采用3-路平衡歸并，畫出最佳歸并樹。九、（本題9分）【解答】設(shè)該樹中結(jié)點總數(shù)為N，葉子結(jié)點個數(shù)為N0，則有： （1） （2）由（2）-（1）再經(jīng)過移項可得：十、（本題15分）【解答】對于排列的解空間可構(gòu)造一個虛擬的解空間樹，比如n=5，k=3時的解空間樹如下圖所示，可采用對此樹進行先序遍歷方式進行遍歷，并用遞歸法進行遞歸輸出從n個數(shù)中挑選k個進行排列所得序列。具體算法實現(xiàn)如下：//文件路徑名:exam7\alg.htemplate<classElemType>voidArrage(ElemTypea[],intk,intn,intoutlen=0)//操作結(jié)果:回溯法輸出排列序列，a[0..k-1]為k個數(shù)的排列序列outlen為當前所求排列// 序列的長度，其中outlen=k時的排列序列為所求；n為list數(shù)組長度{ if(k<0||k>=n)return; //此時無排列 inti; //臨時變量 if(outlen==k+1) { //得到一個排列 for(i=0;i<k;i++) { //輸出一個排列 cout<<a[i]; //輸出a[i] } cout<<""; //用空格分隔不同排列 } else { //對解空間進行前序遍歷，a[outlen..n]有多個排列，遞歸的生成排列 for(i=outlen;i<n;i++) { //處理a[i] Swap(a[outlen+1],a[i]); //交換a[outlen+1]與a[i] Arrage(a,k,n,outlen+1); //對序列長度outlen+1遞歸 Swap(a[outlen+1],a[i]); //交換a[outlen+1]與a[i] } }}*模擬試題（八）注：本套試題選作一、單項選擇題（每小題2分，共20分）（1）一個n*n的帶狀矩陣A=[aij]如下：將帶狀區(qū)域中的元素aij（|i-j|≤1）按行序為主序存儲在一維數(shù)組B[3n-2]中，元素aij在B中的存儲位置是（）。A）i+2j-2 B）2i+j-3 C）3i-j D）i+j+1（2）一n×n的三角矩陣A=[aij]如下：將三角矩陣中元素aij(i≤j)按行序為主序的順序存儲在一維數(shù)組B[n(n+1)/2]中，則aij在B中的位置是（）。A）(i-1)(2n+i)/2+i-j B）(i-1)(2n-i+2)/2+j-iC）(i-1)(2n-i)/2+j-i-1 D）(i-1)(2n-i+2)/2+j-i-1 （3）設(shè)有一棵度為3的樹，其葉結(jié)點數(shù)為n0，度為1的結(jié)點數(shù)為n1，度為2的結(jié)點數(shù)為n2，度為3的結(jié)點數(shù)為n3，則n0與n1，n2，n3滿足關(guān)系（）。A）n0=n2+1 B）n0=n1+2n3+1 C）n0=n2+n3+1 D）n0=n1+n2+n3（4）G是一個非連通無向圖，共有28條邊，則該圖至少有（）個頂點。A）6 B）7 C）8 D）9（5）設(shè)圖G用鄰結(jié)表存儲，則拓撲排序的時間復(fù)雜度為（）。A）O(n) B）O(n+e) C）O(n2) D）O(n×e)（6）用n個鍵值構(gòu)造一棵二叉排序樹，最低高度為（）。A） B） C）nlog2n D）（7）若需在O(nlogn)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。A）快速排序 B）堆排序 C）歸并排序 D）直接插入排序（8）在文件“局部有序”或文件長度較小的情況下，最佳內(nèi)部排序的方法是（）。（北方名校經(jīng)典試題）A）直接插入排序 B）起泡排序 C）簡單選擇排序D）基數(shù)排序（9）一棵有124個葉結(jié)點的完全二叉樹，最多有（）個結(jié)點。A）247 B）248 C）249 D）250（10）一個序列中有10000個元素，若只想得到其中前10個最小元素，最好采用( )方法。A）快速排序 B）堆排序C）插入排序 D）二路歸并排序二、（本題8分）要借助棧由輸入序列是輸入1,2,3,…,n得到的輸出序列為p1,p2,p3,…,pn(此輸出序列是輸入序列經(jīng)過棧操作后的某個排列)，則在輸出序列中不可能出現(xiàn)當i<j<k時有pj<pk<pi的情況。三、（本題8分）已知某一完全k叉樹只有度為k的結(jié)點及葉結(jié)點，設(shè)葉結(jié)點數(shù)為n0，試求它的樹高h。（南方名校經(jīng)典試題）四、（本題8分）試討論怎樣在一棵中序線索二叉樹上查找給定結(jié)點x在后序序列中的后繼。五、（本題8分）六、（本題8分）對長度為12的有序表(a1，a2，…，a12)（其中ai<aj當i<j時）進行折半查找，在設(shè)定查找不成功時，關(guān)鍵字x<a1、x>a12以及ai<x<ai+1(i=1,2,…,11)等情況發(fā)生的概率相等，則查找不成功的平均查找長度是多少？八、（本題8分）（1）設(shè)T是具有n個內(nèi)結(jié)點的判斷二叉樹，I是它的內(nèi)路徑長度，E是它的外路徑長度，試利用歸納法證明E＝I＋2n，n＞0。（2）利用（1）的結(jié)果，試說明，成功查找的平均比較次數(shù)s與不成功查找的平均比較次數(shù)u之間的關(guān)系，可用公式，n＞0表示。提示：判斷二叉樹只有度為0或度為2的結(jié)點；判斷二叉樹成功查找的比較次數(shù)為內(nèi)路徑長度與內(nèi)結(jié)點數(shù)之和，不成功查找的比較次數(shù)為外路徑長度。九、（本題9分）一個深度為h的滿m叉樹有如下性質(zhì)：第h層上的結(jié)點都是葉結(jié)點，其余各層上每個結(jié)點有m棵非空子樹。問：（1）第k層有多少個結(jié)點？（k≤h）（2）整棵樹有多少個結(jié)點？（十、（本題15分）設(shè)散列表的關(guān)鍵字取值范圍為0~m-1，n為對散列表的最大插入次數(shù)，設(shè)計散列表，允許使用以O(shè)(m+n)空間，要求查找、插入和刪除算法的時間復(fù)雜度都是O(1)。模擬試題（八）參考答案一、單項選擇題（每小題2分，共20分）（1）參考答案：B）（2）【分析】存儲位置=n+(n-1)+…+(n-i+2)+i-j=(i-1)(2n-i+2)/2+j-i。參考答案：B）（3）【分析】用n表示結(jié)點總數(shù)，則有：n=n0+n1+n2+n3；由于除根結(jié)點而外，結(jié)點與分支一一對應(yīng)，而分支數(shù)=n1+2n2+3n3，即有：n-1=n1+2n2+3n3。由上面兩式可得：n0=n1+2n3+1參考答案：B）（4）【分析】本題中由于是非連圖，至少有一個頂點與其他頂點不連，這個頂點是孤立點，其他頂點可組成一個連通圖，由于8個頂點的完全圖共有28條邊，所以具體28個頂點的連通圖的頂點個數(shù)至少為8，這樣非連通圖至少有9個頂點。參考答案：D）（5）【分析】對于有n個頂點e條邊的有向圖，建立各頂點的入度時間復(fù)雜度為O(e)，建立入度為零的棧的時間復(fù)雜度為O(n)，在拓撲排序過程中，最多每個頂點進一次棧，入度減1的操作最多總共執(zhí)行e次，可知總的時間復(fù)雜度為O(n+e)參考答案：B）（6）【分析】當用n個鍵值構(gòu)造一棵二叉排序樹是一棵完全二叉樹時，高度最低，此時高度為。參考答案：D）（7）【分析】快速排序和堆排序都是不穩(wěn)定的，應(yīng)排除；歸并排序穩(wěn)定，時間復(fù)雜度O(nlogn)，滿足條件；直接插入排序，時間復(fù)雜度為O(n2)，排除。參考答案：C）（8）【分析】對直接插入排序而言，算法時間復(fù)雜度為O(n2)，但若待排記錄序列為“正序”時，其時間復(fù)雜度可提高至O(n)。若待排記錄序列按關(guān)鍵字“基本有序”，直接插入排序的效率就可大大提高，此外由于直接插入排序算法簡單，在n值很小時效率也高。參考答案：A）（9）【分析】完全二叉樹中度為1的結(jié)點最多只有1個，由二叉樹的度和結(jié)點的關(guān)系：n=n0+n1+n2 (1)n=n1+2n2+1 (2)由2(1)-(2)得，n=2n0+n1-1=247+n1≤248，所以本題應(yīng)選擇B）。參考答案：A）（10）參考答案：B）二、（本題8分）【解答】設(shè)pj<pk<pi成立，則表示在pi出棧之前pj和pk都已入棧，并且還留在棧中，但要滿足pj<pk的出棧次序是不可能的，由于按照i<j<k的次序，當pj和pk同時在棧中時，必然pk被pj蓋住，由棧的后進先出的性質(zhì)，當i<j<k有pk<pj<pi，與假設(shè)矛盾。三、（本題8分）【解答】設(shè)度為k的結(jié)點數(shù)為nk，結(jié)點總數(shù)為n，則有如下關(guān)系： n=nk+n0 ①又由于樹中只有n-1條邊，所以：n-1=k×nk ②由①與②可得：nk=(n0-1)/(k-1)，進而有n=對于k叉完全樹有如下關(guān)系：kh-1-1＜n×(k-1)≤kh-1即有：kh-1≤n×(k-1)＜kh，從而：h-1≤logk(n×(k-1))＜h，進而：所以：h=四、（本題8分）【解答】由于后序遍歷二叉樹需要知道的關(guān)鍵是訪問當前結(jié)點的雙親結(jié)點，需要由中序線索樹才能得到當前結(jié)點的雙親，中序線索樹有如下性質(zhì)：若x是parent的左孩子，則parent是x的最右子孫的右線索；若x是parent的右孩子，則parent是x的最左子孫的左線索。用以上性質(zhì)能找到x的雙親結(jié)點parent。若x是parent的右孩子，則parent結(jié)點就是x的后序序列的后繼結(jié)點；如下圖（1）中結(jié)點①的后繼是結(jié)點②。若x是parent的左孩子，則：如果parent的右指針域為線索的話，那么parent就是x的后序序列的后繼結(jié)點，如下圖（2）中結(jié)點②的后繼是結(jié)點③。否則parent右子樹中最左邊第一個左右孩子均為線索的結(jié)點，就是x的后序序列的后繼結(jié)點。如下圖（3）中結(jié)點②的后繼是結(jié)點③。五、（本題8分）【解答】樹的查找路徑是從根結(jié)點開始到所要查找的結(jié)點的路徑，最大不會超過B-樹的深度。在B樹中，除根結(jié)點外所有非終端結(jié)點都含有棵子樹，所以有n個關(guān)鍵字的B-樹的最大深度為根結(jié)點具有兩棵子樹，其余非終端點有棵子樹，設(shè)最大路徑長度是x，由于葉子結(jié)點表示查找不成功，葉子結(jié)點不含關(guān)鍵字，可知B-樹的深度為x+1，第1層共有1個結(jié)點，含1個關(guān)鍵字；第2層共有2個結(jié)點，含2(-1)個關(guān)鍵字；第3層共有2個結(jié)點，含2(-1)個關(guān)鍵字；……第x層共有2個結(jié)點，含2(-1)個關(guān)鍵字；故，共含有的關(guān)鍵個數(shù)為：1+2(-1)+2(-1)+…+2(-1)＝由此可得：，解得：，這就是具有n個關(guān)鍵宇的B一樹的查找的最大路徑長度。六、（本題8分）【解答】折半查找對應(yīng)的判定樹如下圖所示。查找不成功的對應(yīng)于外部結(jié)點。查找不成功所走的路徑是從根結(jié)點到每個外部結(jié)點（圖中方塊結(jié)點），和給定值進行比較的關(guān)鍵字個數(shù)等于該路徑上內(nèi)部結(jié)點個數(shù)。在不成功情況下，一共比較的次數(shù)為3*3+4*10=49次。平均查找長度為49/13≈3.77七、（本題8分）【解答】對于a來說，在S2中總可找到離a最近的祖先結(jié)點d，這時a<d，這時如d為b的右孩子，則有a在b的右子樹上，所以a>b，也就是說a<b并不總是成立，同理b<c也并不總是成立。八、（本題8分）【解答】（1）證明：n=1時顯然成立，設(shè)n=k時成立，即Ek=Ik＋2k，當n=k+1時，設(shè)所增加的結(jié)點的路徑長度為Dk，則有：Ik+1=Ik+DkEk+1=Ek-Dk+2(Dk+1)=Ek+Dk+2=Ik+2k+Dk+2=Ik+1+2(k+1)=Ik+1+2n結(jié)論也成立。（2）根據(jù)二叉樹性質(zhì)：度為0的結(jié)點數(shù)=度為2的結(jié)點數(shù)+1，所以外結(jié)點數(shù)=n＋l。s=查找成功總的比較次數(shù)/內(nèi)結(jié)點數(shù)=(I+n)/n ①u=查找失敗總的比較次數(shù)/外結(jié)點數(shù)=E/(n+1)=(I+2n)/(n+1) ②由①得：I=ns-n，由②得：I=(n+1)u-2n，所以可得：ns-n=(n+1)u-2n，進一步得：。九、（本題9分）【解答】（1）設(shè)第v層有u個結(jié)點(m<h)，則由于第v層的每個結(jié)點有m個孩子，所以第v+1層的結(jié)點個數(shù)為mu。第1層有1個結(jié)點，第2層有m個結(jié)點，第3層有m2結(jié)點，用數(shù)學(xué)歸納法易知k層共有mk-1個結(jié)點。（2）整棵樹結(jié)點數(shù)=1+m+m2+…+mh-1=。（3）設(shè)編號為i的結(jié)點雙親的結(jié)點編號為x，將編號為i的結(jié)點視為完全二叉樹的最后一個結(jié)點，因此，此完全m叉樹中至少有x-l個度為m的結(jié)點，而x號結(jié)點的度d（1≤d≤m），其余的結(jié)點均為葉子結(jié)點，而編號i就是此完全m又樹的總結(jié)局數(shù)，于是有：(x-1)m+d+1=i所以有，由于1≤d≤m，所以有：可知：。設(shè)編號為i的第j個子結(jié)點為完全m叉樹的最后一個結(jié)點n，此完全m叉樹中有i-1個度為m的結(jié)點，一個度為j的結(jié)點，其他結(jié)點均為葉子結(jié)點，可得：n=(i-l)×m+j+1十、（本題15分）【解答】在具體算法實現(xiàn)當如下：//文件路徑名:exam8\alg.h//理想散列表類template<classElemType,classKeyType>classIdealHashTable{protected://散列表的的數(shù)據(jù)成員: int*ht; //用作elem的索引 ElemType*elem; //在放插入的哈希表的元素 intlastE; //計數(shù)器，表示上次用到的elem位置 intn; //最大插入次數(shù) intm; //關(guān)鍵字范圍0~m-1public://理想散列表方法聲明及重載編譯系統(tǒng)默認方法聲明:IdealHashTable(intmaxInsertCount,intsize); //構(gòu)造函數(shù)~IdealHashTable(); //析造函數(shù)voidTraverse(void(*Visit)(constElemType&))const; //遍歷散列表 boolSearch(constKeyType&key,ElemType&e)const; //查尋關(guān)鍵字為key的元素 boolInsert(constElemType&e); //插入元素e boolDelete(constKeyType&key,ElemType&e);//刪除關(guān)鍵字為key的元素，用e返回元素值IdealHashTable(constIdealHashTable<ElemType,KeyType>©); //復(fù)制構(gòu)造函數(shù)IdealHashTable<ElemType,KeyType>&operator= (constIdealHashTable<ElemType,KeyType>©); //賦值語句重載};//理想散列表類的實現(xiàn)部分template<classElemType,classKeyType>IdealHashTable<ElemType,KeyType>::IdealHashTable(intmaxInsertCount,intsize)//操作結(jié)果:構(gòu)造最大插入次數(shù)為maxInsertCount,關(guān)鍵字范圍為0~size-1的空理想散列表{ n=maxInsertCount; //最大插入次數(shù) m=size; //關(guān)鍵字范圍為0~size-1 ht=newint[n]; //為elem索引表分配存儲空間 elem=newElemType[m]; //為元素分配存儲空間 lastE=-1; //初始化lastE for(intpos=0;pos<n;pos++) { //初始化ht ht[pos]=-1; }}template<classElemType,classKeyType>IdealHashTable<ElemType,KeyType>::~IdealHashTable()//操作結(jié)果:銷毀散列表{ delete[]ht; //釋放ht delete[]elem; //釋放elem}template<classElemType,classKeyType>voidIdealHashTable<ElemType,KeyType>::Traverse(void(*Visit)(constElemType&))const//操作結(jié)果:依次對散列表的每個元素調(diào)用函數(shù)(*visit){ for(intpos=0;pos<m;pos++) { //對散列表的每個元素調(diào)用函數(shù)(*visit) if(ht[pos]!=-1)(*Visit)(elem[ht[pos]]); }}template<classElemType,classKeyType>boolIdealHashTable<ElemType,KeyType>::Search(constKeyType&key,ElemType&e)const//初始條件:關(guān)鍵字key的范圍為0~m-1，ht[key]的范圍為0~lastE//操作結(jié)果:查尋關(guān)鍵字為key的元素的值,如果查找成功,返回true,并用e返回元素的值,// 否則返回false{ if(key<0||key>=m) { //范圍錯 returnfalse; //查找失敗 } elseif(ht[key]<0||ht[key]>lastE||elem[ht[key]]!=key) { //表中沒有要查找的元素 returnfalse; //查找失敗 } else { //存在要查找的元素 e=elem[ht[key]]; //用e返回元素值 returntrue; //查找成功 }}template<classElemType,classKeyType>boolIdealHashTable<ElemType,KeyType>::Insert(constElemType&e)//操作結(jié)果:將元素插入到elem數(shù)組lastE位置，同時修改索引值{ KeyTypekey=e; //e的關(guān)鍵字 ElemTypeeTmp; //臨時變量 if(key<0||key>=m) { //范圍錯 returnfalse; //插入失敗 } elseif(Search(key,eTmp)) { //查找成功 returnfalse; //插入失敗 } elseif(lastE==n-1) { //超過最大插入次數(shù) returnfalse; //插入失敗 } else { elem[++lastE]=e; //修改計數(shù)器，將元素插入到表中 ht[key]=lastE; //索引表ht中ht[key]記錄關(guān)鍵字為key的元素在elem中的位置 returntrue; //插入成功 }}template<classElemType,classKeyType>boolIdealHashTable<ElemType,KeyType>::Delete(constKeyType&key,ElemType&e)//操作結(jié)果:刪除關(guān)鍵字為key的數(shù)據(jù)元素,刪除成功返回true,并用e返回元素值，否則返回false,// 通過將lastE位置元素移到刪除位置，lastE指向倒數(shù)第二個元素，從邏輯上完成刪除{ if(!Search(key,e)) { //查找失敗 returnfalse;