【正文】 度 int aPosition = 1, bPosition = 1。 // la和lb的當(dāng)前元素序號(hào) ()。 // 清空lc while (aPosition = aLength amp。amp。 bPosition = bLength ) { // 取出la和lb中數(shù)據(jù)元素進(jìn)行歸并 (aPosition, aItem)。 // 取出la中數(shù)據(jù)元素 (bPosition, bItem)。 // 取出lb中數(shù)據(jù)元素 if (aItem bItem) { // aItem插入到lc aPosition++。 // 指向la下一數(shù)據(jù)元素 } else if (aItem bItem) { // lb后移 bPosition++。 // 指向lb下一數(shù)據(jù)元素 } else { // aItem == bItem，la和lb同時(shí)后移 (() + 1, aItem)。 // 插入aItem到lc aPosition++。 // 指向la下一數(shù)據(jù)元素 bPosition++。 // 指向lb下一數(shù)據(jù)元素 } }}C語言版測試程序見exam6\10C，具體算當(dāng)如下：void interaction(LinkList la,LinkList lb,LinkList amp。lc)// 將鏈表la與lb中共同出現(xiàn)的元素插入到鏈表lc中{ LinkList pa,pb,pc。 lc=new LNode。 //生成lc的頭結(jié)點(diǎn) pc=lc。 //pc永遠(yuǎn)指向lc的尾結(jié)點(diǎn) pa=lanext。 //pa指向la的第一個(gè)元素 while(pa) { pb=lbnext。 while(pbamp。amp。pbdata!=padata) pb=pbnext。 //在pb中定位padata if(pb) //定位成功 { pcnext=new LNode。 //生成lc新的尾結(jié)點(diǎn) pc=pcnext。 //pc指向新的尾結(jié)點(diǎn) pcdata=padata。 //將padata復(fù)制到pc中 } pa=panext。 } pcnext=NULL。 //pc為尾結(jié)點(diǎn)，其后繼為空}*模擬試題（七）注：本套試題選作一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限雙端隊(duì)列得到，也不能由輸出受限雙端隊(duì)列得到的輸出序列是（　　?。?。A）1234 B）4132 C）4231 D）4213（2）將一個(gè)A[1..100,1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[298]中，A中元素a66,65（即該元素下標(biāo)）在B數(shù)組中的位置k為（　　?。僭O(shè)B[0]的位置是1）。 A）198 B）195 C）197 D）198【分析】如下所示，三對角矩陣第1行和最后1行非零元素個(gè)數(shù)為2個(gè)，其余各行的非零元素個(gè)數(shù)是3個(gè)，所知a66,65前面共有2+3*64＝194個(gè)非零元素，a66,65本身是第 195個(gè)非零元。（3）若度為m的哈夫曼樹中，其葉結(jié)點(diǎn)個(gè)數(shù)為n，則非葉結(jié)點(diǎn)的個(gè)數(shù)為（　　?。?。A）n1 B） C） D）（4）若一個(gè)有向圖具有拓?fù)渑判蛐蛄校⑶翼旤c(diǎn)按拓?fù)渑判蛐蛄芯幪?hào)，那么它的鄰接矩陣必定為（　　?。?。A）對稱矩陣 B）稀疏矩陣 C）三角矩陣 D）一般矩陣（5）設(shè)森林 F對應(yīng)的二叉樹為有 m個(gè)結(jié)點(diǎn)，此二叉樹根的左子樹的結(jié)點(diǎn)個(gè)數(shù)為k，則另一棵子樹的結(jié)點(diǎn)個(gè)數(shù)為（　　?。?。A）mk+1 B）k+1 C）mk1 D）mk（6）假定有K個(gè)關(guān)鍵字互為同義詞，若用線性探測法把這K個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行（　　?。┐翁綔y。A）K1次 B）K次 C）K＋l次 D）K(K+1)/2次 （7）一棵深度為k的平衡二叉樹，其每個(gè)非終端結(jié)點(diǎn)的平衡因子均為0，則該樹共有（　　?。﹤€(gè)結(jié)點(diǎn)。A）2k11 B）2k1 C）2k1+1 D）2k1（8）如表r有100000個(gè)元素，前99999個(gè)元素遞增有序，則采用（ ）方法比較次數(shù)較少。A）直接插入排序 B）快速排序 C）歸并排序 D）選擇排序（9）如果只考慮有序樹的情形，那么具有7個(gè)結(jié)點(diǎn)的不同形態(tài)的樹共有（　　?。┛?。A）132 B）154 C）429 D）前面均不正確 （10）對ISAM文件的刪除記錄時(shí)，一般( )A）只需做刪除標(biāo) B）需移動(dòng)記錄C）需改變指針 D）一旦刪除就要做整理二、（本題8分）斐波那契數(shù)列Fn定義如下：F0=0，F(xiàn)1=1，F(xiàn)n=Fn1+Fn2請就此斐波那契數(shù)列，回答下列問題：（1）在遞歸計(jì)算Fn的時(shí)候，需要對較小的Fn1，F(xiàn)n2，…，F(xiàn)1，F(xiàn)0精確計(jì)算多少次？（2）若用有關(guān)大O表示法，試給出遞歸計(jì)算Fn時(shí)遞歸函數(shù)的時(shí)間復(fù)雜度是多少？三、（本題8分）證明：如果一棵二叉樹的后序序列是,…,，中序序列是,…,，則由序列1,2,…,n可通過一個(gè)棧得到序列,…,。四、（本題8分）如下圖所示為5個(gè)鄉(xiāng)鎮(zhèn)之間的交通圖，鄉(xiāng)鎮(zhèn)之間道路的長度如圖中邊上所注?，F(xiàn)在要在這5個(gè)鄉(xiāng)鎮(zhèn)中選擇一個(gè)鄉(xiāng)鎮(zhèn)建立一個(gè)消防站，問這個(gè)消防站應(yīng)建在哪個(gè)鄉(xiāng)鎮(zhèn)，才能使離消防站最遠(yuǎn)的鄉(xiāng)鎮(zhèn)到消防站的路程最短。試回答解決上述問題應(yīng)采用什么算法，并寫出應(yīng)用該算法解答上述問題的每一步計(jì)算結(jié)果。五、（本題8分）證明一個(gè)深度為n的AVL樹中的最少結(jié)點(diǎn)數(shù)為：Nn=Fn+21 (n≥0)其中，F(xiàn)i為Fibonacci數(shù)列的第i項(xiàng)。六、（本題8分）簡單回答有關(guān)AVL樹的問題：（北方名校經(jīng)典試題）（1）在有 n個(gè)結(jié)點(diǎn)的AVL樹中，為結(jié)點(diǎn)增加一個(gè)存放結(jié)點(diǎn)高度的數(shù)據(jù)成員，那么每一個(gè)結(jié)點(diǎn)需要增加多少個(gè)字位（bit）？（2）若每一個(gè)結(jié)點(diǎn)中的高度計(jì)數(shù)器有8bit，那么這樣的AVL樹可以有多少層？最少有多少個(gè)關(guān)鍵碼？七、（本題8分）設(shè)有12個(gè)數(shù)據(jù) {25，40，33，47，12，66，72，87，94，22，5，58}，它們存儲(chǔ)在散列表中，利用線性探測再散列解決沖突，要求插入新數(shù)據(jù)的平均查找次數(shù)不超過3次。（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)在對這段電文用三進(jìn)制進(jìn)行編碼（即碼字由0，l，2組成），問電文編碼總長度至少有多少位？請畫出相應(yīng)的圖。 九、（本題9分）已知一棵度為m的樹中有N1個(gè)度為1的結(jié)點(diǎn)，N2個(gè)度為2的結(jié)點(diǎn)，…，Nm個(gè)度為m的結(jié)點(diǎn)。試問該樹中有多少個(gè)葉子結(jié)點(diǎn)？（北方名校經(jīng)典試題）十、（本題15分）試用遞歸法編寫輸出從n個(gè)數(shù)中挑選 k個(gè)進(jìn)行排列所得序列的算法。模擬試題（七）參考答案一、單項(xiàng)選擇題（每小題 2 分，共20分）（1）參考答案：C）（2）【分析】如下所示，三對角矩陣第1行和最后1行非零元素個(gè)數(shù)為2個(gè)，其余各行的非零元素個(gè)數(shù)是3個(gè)，所知a66,65前面共有2+3*64＝194個(gè)非零元素，a66,65本身是第 195個(gè)非零元。參考答案：B）（3）【分析】在哈夫曼樹的非葉結(jié)點(diǎn)中最多只有1個(gè)結(jié)點(diǎn)的度不為m，設(shè)非葉結(jié)點(diǎn)的個(gè)數(shù)為k，則其中有k1個(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(k1)+u ①n總=k+n ②將②代入①可得：k+n1= m(k1)+u，解得：，由于2≤u≤m，所以可得0≤mu＜m1，所以可得：≤k＜+1，可知。參考答案：C）（4）【分析】設(shè)頂點(diǎn)按拓?fù)渑判蛐蛄袨椋簐0,v1,…,vn1，則對于鄰接矩陣A，只有當(dāng)ij時(shí)，才可能有弧 vi,vj，也就是當(dāng)ij時(shí)，一定沒有弧 vi,vj，所以這時(shí)A[i][j]=0，可知鄰接矩陣為三角矩陣。參考答案：C）（5）【分析】設(shè)另一棵子樹的結(jié)點(diǎn)個(gè)數(shù)為n，所以有 m=n+k+1，可知n= mkl。參考答案：C）（6）【分析】因?yàn)镵個(gè)關(guān)鍵字互為同義詞，只有在存入第一個(gè)關(guān)鍵字的情況下不發(fā)生沖突，所以至少需進(jìn)行1+2+…+K=K(K+1)/2次探測。 參考答案：D）（7）【分析】由于每個(gè)非終端結(jié)點(diǎn)的平衡因子均為0，所以每個(gè)非終端結(jié)點(diǎn)必有左右兩個(gè)孩子，且左子樹的高度和右子樹的高度相同，這樣AVL樹是滿二叉樹。高度為k的滿二叉樹的結(jié)點(diǎn)數(shù)為2kl。 參考答案：D）（8）【分析】本題中只有直接插入排序利用前面有序的子序列這個(gè)性質(zhì)，如用直接插入排序?qū)Ρ绢}只需將最后一個(gè)元素插入到前面99999個(gè)元素的有序子序列中即可，顯然比較次數(shù)較少。參考答案：A）（9）【分析】具有n個(gè)結(jié)點(diǎn)有不同形態(tài)的樹的數(shù)目和具有nl個(gè)結(jié)點(diǎn)互不相似的二叉樹的數(shù)目相同（將樹轉(zhuǎn)化為二叉樹時(shí)，根結(jié)點(diǎn)右子樹為空，所以除根結(jié)點(diǎn)而外只有左子樹，其不相似的二叉樹的等價(jià)于不相似的左子樹）。具有n個(gè)結(jié)點(diǎn)互不相似的二又樹的數(shù)目為，本題中應(yīng)為。參考答案：A）（9）參考答案：A）二、（本題8分）【解答】（1）設(shè)在計(jì)算Fn時(shí)，由Fn1+Fn2可知Fn1要精確計(jì)算1次；由Fn1=Fn2+Fn3可知Fn=2Fn2+Fn3，F(xiàn)n2要精確計(jì)算2次；由Fn2=Fn3+Fn4可知Fn=3Fn3+2Fn4，F(xiàn)n3要精確計(jì)算3次，F(xiàn)n=3Fn3+2Fn4公式中Fn3的系數(shù)為Fn3要精確計(jì)算次數(shù)，而Fn4的系數(shù)為Fn2要精確計(jì)算次數(shù)，以此類推，設(shè)Fnj的精確計(jì)算次為aj，則有：Fn=aj*Fnj+aj1*Fnj1。由Fnj=Fnj1+Fnj2可知Fn=(aj+ aj1)*Fnj1+aj*Fnj2 ，F(xiàn)nj1的精確計(jì)算次數(shù)為aj+1，所以有：aj+1=aj+aj1由于Fn1要精確計(jì)算a1為1次，即a1=1，即可知Fn1，F(xiàn)n2，…，F(xiàn)1，F(xiàn)0的精確計(jì)算次為：1，2，3，5，……，aj=aj1+aj2……與斐波那契數(shù)列數(shù)列：0，1，2，3，5，……，F(xiàn)n=Fn1+Fn2……比較可知aj=Fj+1。（2）由于Fn的計(jì)算最終要轉(zhuǎn)化為F0與F1之和，其加法的計(jì)算次數(shù)為F0與F1的精確計(jì)算次數(shù)之和再減1之差，由于F0=Fnn與F1=Fn(n1)，所以計(jì)算Fn時(shí)，加法計(jì)算次數(shù)為：an+an11=Fn+1+Fn1由于Fn= ，可知時(shí)間復(fù)雜度為O()。三、（本題8分）【解答】當(dāng)n=1時(shí)，結(jié)論顯然成立。設(shè)n=k時(shí)結(jié)論成立，當(dāng)n=k+1時(shí)，設(shè)一棵二叉樹的后序序列是,…,，中序序列是,…,，可知是二叉樹的根結(jié)點(diǎn)，設(shè)，可知{,…,}是左子樹的結(jié)點(diǎn)集合，{,…, }是右子樹的結(jié)點(diǎn)集合，進(jìn)一步可知：（1）左子樹的后序序列是,…,，中序序列是,…,，由歸納假設(shè)知序列1,2,…,j1可以通過一個(gè)棧得序列,…,。（2）右子樹的后序序列是,…, ，中序序列是,…, ，設(shè)，…，；，…，則，…，由歸納假設(shè)知序列1,2,…,nj可以通過一個(gè)棧得序列，…，顯然按同樣的方式，j,j+1,…,n1 可以通過一個(gè)棧得序列,…,，也就是，…。由（1）（2）及可知由1,2,…,n可通過一個(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分）【解答】對n用歸納法證明。當(dāng)n＝1時(shí)，有N1=F3l=2l=1到。當(dāng)n=2時(shí)，有N2=F41=31=2。設(shè)nk時(shí)也成立，即有Nn=Fn+21成立。當(dāng)n=k+1，對于一個(gè)k+l層深度的平衡二叉樹而言，其左右子樹都是平衡的。結(jié)點(diǎn)數(shù)為最少的極端情況，故左右子樹中的結(jié)點(diǎn)數(shù)是不相等的，設(shè)其中一個(gè)是k層深度的二叉平衡樹，另一個(gè)是kl層深度的二叉平衡樹。所以有：Nk+1=1+Nk+Nk1==1+(Fk+21)+(Fk+11)= Fk+2+Fk+11= Fk+3 1當(dāng)n=k+1時(shí)成立，由此可知深度為n都等式都成立。六、（本題8分）【解答】n個(gè)結(jié)點(diǎn)的平衡二叉樹的最大高度為，設(shè)表示高度需xbit，則有關(guān)系式：2x≥h＞2x1，所以有：（2）設(shè)深度為h的平衡二叉樹的最少關(guān)鍵字?jǐn)?shù)為nh，則有公式：，本題中8bit的計(jì)數(shù)器共可以表示28=256層，即高度為256，從而可知最少有個(gè)關(guān)鍵字。七、（本題8分）【解答】（1）線性探測再散列的哈希表查找成功的平均查找長度為：≤3，解得α≤4／5，也就是12/m≤4／5， 所以m≥15，可取m=15。（2）散列函數(shù)可取為H(key)=key % 13（3）散列表如表74所示。散列表012345678910111213144066