【正文】 5678910BDACDDBBCA二、填空題（每空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．集合結(jié)構(gòu)；線性結(jié)構(gòu)；樹型結(jié)構(gòu)；圖形結(jié)構(gòu)10．ni+1三、應(yīng)用題（每題10分，共60分）1．答：可以做到。取a與b進行比較，c與d進行比較。設(shè)ab,cd(ab和cd情況類似)，此時需2次比較，取b和d比較，若bd，則有序abd；若bd時則有序cdb，此時已進行了3次比較。再把另外兩個元素按折半插入排序方法，插入到上述某個序列中共需4次比較，從而共需7次比較。2．該排序方法為快速排序。3．①快速排序 ②冒泡排序 ③直接插入排序4．答：（1）T樹的最大深度Kmax=6（除根外，每層均是兩個結(jié)點）T樹的最小深度Kmin=4（具有6個葉子的完全二叉樹是其中的一種形態(tài)）456123（2）非葉子結(jié)點數(shù)是5。（n2=n01） （3）哈夫曼樹見下圖，其帶權(quán)路徑長度wpl=51 Wpl=4*3+3*3+2*(4+5+6)=515．答：n（n0）個結(jié)點的d度樹共有nd個鏈域，除根結(jié)點外，每個結(jié)點均有一個指針所指，故該樹的空鏈域有nd(n1)=n(d1)+1個。6．答：（1）176 （2）76和108 （3）28和116。習(xí)題三參考答案一、單選題（每題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。 （2分） 后根：e,b,h,i,j,f,g,c,d,a。 （2分） 按層：a,b,c,d,e,f,g,h,i,j。 （2分） 最小生成樹的權(quán)：55 3 1 2 5 6 四、閱讀算法，回答問題（第一題7分，第二題8分） （12，26，9，8，15，30，50） 向HBT堆中插入一個值為item的元素，使得插入后仍是一個堆。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（12分） return mid return Binsch(A , low , mid1 , K) return Binsch(A , mid+1 , high , K)六、編寫算法（14分） 評分標準：請根據(jù)編程情況酌情給分。bool Find( BTreeNode * BST , ElemType amp。 item ){ while ( BST != NULL ) { if ( item == BTdata ) {item = BSTdata。return true。 }else if (itemBSTdata) BST=BSTleft。else BST=BSTright。 } return false。}習(xí)題四參考答案一、選擇題（每題2分，共20分）12345678910CDACCDCDBC二、填空題（每空2分，共30分）1．算法的時間復(fù)雜度和空間復(fù)雜度2．有窮性； 確定性； 可行性。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之前出棧。 得到135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)椋?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結(jié)果135426。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)個元素，為了避免重復(fù)和漏選，可分別求出包括1和不包括1的所有組合。即包括1時，求出集合（2..n）中取出k1個元素的所有組合；不包括1 時，求出集合（2..n）中取出k個元素的所有組合。，將這兩種情況合到一起，就是題目的解。int A[],n。 //設(shè)集合已存于數(shù)組A中。void b(int P[],int i,int k)//從集合（1..n）中選取k（k=n）個元素的所有組合{if (k==0) printf(P)。else if(k=n) {P[i]=A[i]。 b(P,i+1,k1)。 b(P,i+1,k)。 }}//算法結(jié)束習(xí)題五參考答案一、單選題（每題2分，共20分）1．B 2．D 3．A 4．B 5．B6．D 7．C 8．A 9．D 10．A二、填空題（每空1分，共25分）1．集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖形結(jié)構(gòu)2．O（n） O（1）3．行號 列號 元素值（次序無先后）4．35．top= =06．5507．168．最小值 最大值9．n110．O（n2） O（n十e） O（e）11．順序 有序12．稠密稀疏13．O（1og2n） O（n）三、運算題（每題5分，共20分）1．（40，38．35，30，25，20）2．（0，3）2，（4，6）4，（0，2）5，（1，5）6，（0，1）8，（3，6）10，（5，7） 203．（50，42，46，38，40，56 ，79，84）4．［36 38 40 40 46 56 79 80］［25 66 75 84］四、閱讀算法，回答問題（每題5分，共10分）1．（50，30，5，8，12，15）2．12 15 5 30 18五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）（A[i] stn＜x．stn）QuickSort（A，s，j 1） QuickSort（A，j + 1，t）；六、編寫算法（15分） int count（RtreeNOde*BT）／／統(tǒng)計出二叉樹中所有葉子結(jié)點數(shù) { if（BT= =NULL）return 0： else if（BT一left= =NULLamp。amp。BT一right= =NULL）return else return Count（BT一left）十Count（BT一right）； }歡迎您的光臨，！希望您提出您寶貴的意見，你的意見是我進步的動力。贈語； 如果我們做與不做都會有人笑，如果做不好與做得好還會有人笑，那么我們索性就做得更好，來給人笑吧！ 現(xiàn)在你不玩命的學(xué)，以后命玩你。我不知道年少輕狂，我只知道勝者為王。不要做金錢、權(quán)利的奴隸；應(yīng)學(xué)會做“金錢、權(quán)利”的主人。什么時候離光明最近？那就是你覺得黑暗太黑的時候。最值得欣賞的風(fēng)景，是自己奮斗的足跡。壓力不是有人比你努力，而是那些比你牛幾倍的人依然比你努力。學(xué)習(xí)資料