數(shù)據(jù)結(jié)構(gòu)習(xí)題課8

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

2、樹，并求其等概率時(shí)查找成功的平均查找長度。 參考答案參考答案lASLsucc=(1+2*2+3*4+4*3)/10=29/10lASLunsucc = (5*3 + 6*4)/11 = 39/114528169710a5a8a9a10a2a1a3a6a4a73a28-8l對(duì)長度為12的有序表（a1,a2,a12）（其中aiaj，當(dāng)ij時(shí)）進(jìn)行折半查找，在設(shè)定查找不成功的情況時(shí)，關(guān)鍵詞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指向根結(jié)點(diǎn)；pre指向t的中根前驅(qū)，初值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給定整型數(shù)組B0.m, 0.n. 已知B中數(shù)據(jù)在每一維方向上都按從小到大的次序排列。且整型變量x在B中存在。試設(shè)計(jì)一個(gè)算法，找出一對(duì)滿足Bi,j = x的i,j值，要求比較次數(shù)不超過m+n.l【提示】本題中主要是要確定

4、每次進(jìn)行比較的對(duì)象。其中，二維數(shù)組右上角的元素是一個(gè)較為特殊的元素。可以逐次跟二維數(shù)組右上角的元素進(jìn)行比較。每次比較有3種可能的結(jié)果：若相等則結(jié)束比較；若右上角的元素小于x，則可斷定二維數(shù)組的最上面一行中肯定不包含x，下次比較時(shí)搜索范圍即可減少一行；若右上角的元素大于x，則可斷定二維數(shù)組的最右面一列中肯定不包含x，下次比較時(shí)搜索范圍即可減少一列。這樣，每次至少可使搜索范圍減少一列或一行，最多經(jīng)過m+n次即可找到x .參考答案參考答案l算法Find(B,m,n,x)/*在B中查找x，時(shí)間復(fù)雜度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分）分）數(shù)組A中存放n個(gè)整數(shù)（0=Ai=10000，1=i=n），設(shè)計(jì)算法求出數(shù)組A中的第k小數(shù)（1=k=nk則在(j+1,e)這段里查找第k小位置;若jk，則在(s.j-1)查找第k小位置l時(shí)間復(fù)雜度（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分）分） 給定無向連通正權(quán)圖G和G中的一個(gè)結(jié)點(diǎn)v. 求G的支撐樹T，并使其滿足如下兩個(gè)條件：第一，T的根為v；第二，T中v到任一頂點(diǎn)u的路徑長度等于G中v到u的最短路徑長度。要求：(1) 給出算法的基本設(shè)計(jì)思想（3分）；(2) 設(shè)計(jì)圖G和支撐樹T的存儲(chǔ)結(jié)構(gòu)（2分）；(3) 基于以上設(shè)計(jì)的存儲(chǔ)結(jié)構(gòu)，用算法描述語言描述算法，并要求對(duì)算法中的關(guān)鍵步驟給出注釋（7分）。（1）算法設(shè)計(jì)思想： 利用Dijkstra算法求該支撐樹。即在用Dijkstra算法求以v作為源點(diǎn)的最短路的過程中，把每次確定為最短路的點(diǎn)和邊加入到生成樹T中。（2）圖G用鄰接表存儲(chǔ)：邊的存儲(chǔ)結(jié)構(gòu)為Edge(VerAdj,Weight,Link)，頭指針