【正文】 、 和 三項。7．在一棵二叉樹中，第5層上的結點數(shù)最多為 。11．以二分查找方法查找一個線性表時，此線性表必須是 存儲的 表。2．已知一個圖的頂點集V和邊集6分別為： V={0，1，2，3，4，5，6，7}； E={（04）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}； 按照克魯斯卡爾算法得到最小生成材，拭寫出在最小生成樹中依次得到的各條邊。4．假定一組記錄的徘序碼為（46，79，56，38，40，80，36，40，75，66，84，24），對其進行歸并排序的過程中，第三趟歸并后的結果為： 。void QuickSort（ElemType A [ ]， int s， int t）{ int i=s j=t十1； ElemType x=A[s]； d0｛ do i++； while ；／／填寫一個循環(huán)條件 do j ； while（A [ j ] ．stn＞x．stn）； if（Ij） { ElemType temp = A［i］；A［i］= A［j］；A［j］＝temp；} } while（i＜j）； A[s]=A[j]；A[j]=x； if（s＜i一1） ； if（j十1＜t） ； }六、編寫算法（15分）編寫一個遞歸算法，統(tǒng)計并返回以BT為樹根指針的二叉樹中的葉子結點的個數(shù)。習題二參考答案一、選擇題（每題2分，共20分）12345678910BDACDDBBCA二、填空題（每空2分，共40分）1．n12．（15，02，21，24，26，57，43，66，81，48，73）3．O（n）4．HLnext==NULL HLnext==HL5．O(nlog2n) ；O(n2)6．6； 31； 197．2； 1； 1； 68． 6 9．集合結構；線性結構；樹型結構；圖形結構10．ni+1三、應用題（每題10分，共60分）1．答：可以做到。2．該排序方法為快速排序。習題三參考答案一、單選題（每題2分，共10分） A B D D D二、填空題（每空1分，共25分） 1:1 1:N M:N （或者 1對1 1對N M對N） pnext a[p].next 引用 后進先出 先進先出 162 31 21 6 查找成功 左子樹 右子樹 n2 n n11二叉搜索樹 理想平衡樹 （次序無先后） 1O(n) O(nlog2n) O(n) 15 96 三、運算題（每題6分，共24分） 先根：a,b,e,c,f,h,i,j,g,d。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（12分） return mid return Binsch(A , low , mid1 , K) return Binsch(A , mid+1 , high , K)六、編寫算法（14分） 評分標準：請根據(jù)編程情況酌情給分。 }else if (itemBSTdata) BST=BSTleft。3．ni+1 4．4 25．9174 8788 6．非零元很少(tm*n)且分布沒有規(guī)律7．深度 8． 9 9．12 10．64三、計算題（每題6分，共30分）1．輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。將這兩種情況合到一起，就是題目的解。else if(k=n) {P[i]=A[i]。amp。不要做金錢、權利的奴隸；應學會做“金錢、權利”的主人。壓力不是有人比你努力，而是那些比你牛幾倍的人依然比你努力。最值得欣賞的風景，是自己奮斗的足跡。贈語； 如果我們做與不做都會有人笑，如果做不好與做得好還會有人笑，那么我們索性就做得更好，來給人笑吧！ 現(xiàn)在你不玩命的學，以后命玩你。 b(P,i+1,k)。 //設集合已存于數(shù)組A中。2． 先序： a,b,c,d,e,f中序： c,b,a,e,d,f 后序： c,b,e,f,d,a 按層： a,b,d,c,e,f 3． (0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4, (5,7)204．拓撲序列：1,3,6,0,2,5,4,7,8 5．[40 34 25 38] 46 [80 56 79]四、算法填空（10分）1． BSTleft=BSTright=NULL　　Insert(BSTleft, item)Insert(BSTright, item)五、編程（10分）2．從集合（1..n）中選出k(本題中k=2)個元素，為了避免重復和漏選，可分別求出包括1和不包括1的所有組合。 } return false。 item ){ while ( BST != NULL ) { if ( item == BTdata ) {item = BSTdata。 （2分） 按層：a,b,c,d,e,f,g,h,i,j。（n2=n01） （3）哈夫曼樹見下圖，其帶權路徑長度wpl=51 Wpl=4*3+3*3+2*(4+5+6)=515．答：n（n0）個結點的d度樹共有nd個鏈域，除根結點外，每個結點均有一個指針所指，故該樹的空鏈域有nd(n1)=n(d1)+1個。設ab,cd(ab和cd情況類似)，此時需2次比較，取b和d比較，若bd，則有序abd；若bd時則有序cdb，此時已進行了3次比較。2．判斷結果元素值3456586394比較次數(shù)21344四、應用題（每題10分，共50分）1．答： (1)直接插入排序第一趟 (3)[8,3],2,5,9,1,6 第二趟 (2)[8,3,2],5,9,1,6 第三趟 (5)[8,5,3,2],9,1,6 第四趟 (9)[9,8,5,3,2],1,6 第五趟 (1)[9,8,5,3,2,1],6 第六趟 (6)[9,8,6,5,3,2,1](2)直接選擇排序（第六趟后僅剩一個元素，是最小的，直接選擇排序結束）第一趟 (9)[9],3,2,5,8,1,6 第二趟 (8)[9,8],2,5,3,1,6 第三趟 (6)[9,8,6],5,3,1,2 第四趟 (5)[9,8,6,5],3,1,2 第五趟 (3)[9,8,6,5,3],1,2 第六趟 (2)[9,8,6,5,3,2],12．(1)是大堆； (2)是大堆；（4）是小堆；(3)不是堆，調(diào)成大堆 100，98，66，85，80，60，40，77，82，10，203．答：先序遍歷二叉樹的順序是“根—左子樹—右子樹”，中序遍歷“左子樹—根—右子樹”，后序遍歷順序是：“左子樹—右子樹―根＂，根據(jù)以上原則，本題解答如下：（1）若先序序列與后序序列相同，則或為空樹，或為只有根結點的二叉樹（2）若中序序列與后序序列相同，則或為空樹，或為任一結點至多只有左子樹的二叉樹．（3）若先序序列與中序序列相同，則或為空樹，或為任一結點至多只有右子樹的二叉樹．（4）若中序序列與層次遍歷序列相同，則或為空樹，或為任一結點至多只有右子樹的二叉樹4．答：（1）T樹的最大深度Kmax=6（除根外，每層均是兩個結點）T樹的最小深度Kmin=4（具有6個葉子的完全二叉樹是其中的一種形態(tài)）（2）非葉子結點數(shù)是5。2．void AF（Queue＆Q）{ InitQueue（Q）： int a [4]={5，8，12，15} for（int i一0；i＜4；i斗＋＝ Qlnsert