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

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