1、數據結構習題數據結構習題 第第 8 章章吉林大學計算機科學與技術學院谷方明第第8章作業章作業l8-4l8-7，8-8，8-9，8-10l8-13l8-22，8-238-4l設有關鍵詞為A、B、C和D，按照不同的輸入順序，共可能組成多少種不同的二叉查找樹。請畫出其中高度較小的6種。參考答案參考答案l以A為根的BST共5種lB為第2個元素：2種lC為第2個元素：1種（高度為2）lD為第2個元素：2種l以B為根的BST共2種（高度為2）l以C為根的BST共2種（高度為2）l以D為根的BST共5種（類似A）l一共有14種。高度為2的有6種，為3的有8種8-7l畫出對長度為10的有序表進行折半查找的判定

2、樹，并求其等概率時查找成功的平均查找長度。 參考答案參考答案lASLsucc=(1+2*2+3*4+4*3)/10=29/10lASLunsucc = (5*3 + 6*4)/11 = 39/114528169710a5a8a9a10a2a1a3a6a4a73a28-8l對長度為12的有序表（a1,a2,a12）（其中aiaj，當ij時）進行折半查找，在設定查找不成功的情況時，關鍵詞x a12, aixdata(t) ) THEN(flag FALSE. RETURN.). pre t. BST(right(t),pre,flag). C+bool bst(BinTreeNode* t, Bi

3、nTreeNode*& pre )/*t指向根結點；pre指向t的中根前驅，初值NULL*/ if(t=NULL) return true; if(! bst(left(t),pre) return false; if(pre &pre-data t-data) return false; pre=t; return bst(right(t),pre);8-23l給定整型數組B0.m, 0.n. 已知B中數據在每一維方向上都按從小到大的次序排列。且整型變量x在B中存在。試設計一個算法，找出一對滿足Bi,j = x的i,j值，要求比較次數不超過m+n.l【提示】本題中主要是要確定

4、每次進行比較的對象。其中，二維數組右上角的元素是一個較為特殊的元素。可以逐次跟二維數組右上角的元素進行比較。每次比較有3種可能的結果：若相等則結束比較；若右上角的元素小于x，則可斷定二維數組的最上面一行中肯定不包含x，下次比較時搜索范圍即可減少一行；若右上角的元素大于x，則可斷定二維數組的最右面一列中肯定不包含x，下次比較時搜索范圍即可減少一列。這樣，每次至少可使搜索范圍減少一列或一行，最多經過m+n次即可找到x .參考答案參考答案l算法Find(B,m,n,x)/*在B中查找x，時間復雜度O(m+n)*/F1初始化 i 0. j n.F2比較Bi,j與x WHILE(i=0) DO( IF(

5、Bi,j=x) THEN RETURN TRUE. IF(Bi,jx) THEN i i+1. IF(Bi,jx) THEN j j-1. ) RETURN FALSE. 1. （8分）分）數組A中存放n個整數（0=Ai=10000，1=i=n），設計算法求出數組A中的第k小數（1=k=nk則在(j+1,e)這段里查找第k小位置;若jk，則在(s.j-1)查找第k小位置l時間復雜度（logn*logn）算法描述：算法描述：int search(int k, int n) int s=1,e=n; while(1) int i=s,j=e; while(i=ai&j=i) j-; whi

6、le(aj=ai&j=i) i+; if(ij) s=j+1; if(ki，那么s=i+1,k=k-i; 如果ki，那么e=i-1；（12分）分） 給定無向連通正權圖G和G中的一個結點v. 求G的支撐樹T，并使其滿足如下兩個條件：第一，T的根為v；第二，T中v到任一頂點u的路徑長度等于G中v到u的最短路徑長度。要求：(1) 給出算法的基本設計思想（3分）；(2) 設計圖G和支撐樹T的存儲結構（2分）；(3) 基于以上設計的存儲結構，用算法描述語言描述算法，并要求對算法中的關鍵步驟給出注釋（7分）。（1）算法設計思想： 利用Dijkstra算法求該支撐樹。即在用Dijkstra算法求以v作為源點的最短路的過程中，把每次確定為最短路的點和邊加入到生成樹T中。（2）圖G用鄰接表存儲：邊的存儲結構為Edge(VerAdj,Weight,Link)，頭指針