【正文】 題（一）一、選擇題（每題2分，共20分）1．在一個(gè)長度為n的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（ ）。A、入度 B、出度C、入度與出度之和 D、入度與出度之差5．對(duì)于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（ ）的值除以9。3．已知8個(gè)數(shù)據(jù)元素為（34，76，45，18，26，54，92，65），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，則該樹的深度為 。三、運(yùn)算題（每題5分，共10分）1．設(shè)有一個(gè)10180。2．判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請(qǐng)將它們調(diào)整為堆）。 HL=p。a+i 4．下面程序段的時(shí)間復(fù)雜度為（ ）。A、插入 B、刪除 C、排序 D、定位7．若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插進(jìn)行，則可能出現(xiàn)的出棧序列為（ ）。5．快速排序在平均情況下的時(shí)間復(fù)雜度為 ，在最壞情況下的時(shí)間復(fù)雜度為 。設(shè)一數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。A、2 B、3 C、4 D、5 適用于折半查找的表的存儲(chǔ)方式及元素排列要求為 。 從一棵二叉搜索樹中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明 ，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向 查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向 查找。后根： 。 InsertRear(HL,30)。 HBT , const ElemType item) // HBT為一個(gè)小根堆{ []=item。 } 該算法的功能為： 。 }六、編寫算法（14分）編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為item的結(jié)點(diǎn)的非遞歸算法，若查找成功則由item帶回整個(gè)結(jié)點(diǎn)的值并返回true，否則返回false。pLlinkRlink=q。pLlink=q。A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn)二、填空題（每空2分，共30分）1．?dāng)?shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是 和 。8．具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為______?！　“凑掌绽锬匪惴◤捻旤c(diǎn)0出發(fā)得到最小生成樹，試寫出在生成最小生成樹的過程中依次得到的各條邊。數(shù)據(jù)結(jié)構(gòu)作業(yè)題（五）一、選擇題（每題2分，共20分）1．若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為（ ）參數(shù)。A.(B, E , F, G) B.( ) C.（A，B， E，F(xiàn)，G) D.（G）9．線性表如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，要求內(nèi)存中的存儲(chǔ)單元的地址（ ）。7．在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多為 。2．已知一個(gè)圖的頂點(diǎn)集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}； 按照克魯斯卡爾算法得到最小生成材，拭寫出在最小生成樹中依次得到的各條邊。void QuickSort（ElemType A [ ]， int s， int t）{ int i=s j=t十1； ElemType x=A[s]； d0｛ do i++； while ；／／填寫一個(gè)循環(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分）編寫一個(gè)遞歸算法，統(tǒng)計(jì)并返回以BT為樹根指針的二叉樹中的葉子結(jié)點(diǎn)的個(gè)數(shù)。2．該排序方法為快速排序。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（12分） return mid return Binsch(A , low , mid1 , K) return Binsch(A , mid+1 , high , K)六、編寫算法（14分） 評(píng)分標(biāo)準(zhǔn)：請(qǐng)根據(jù)編程情況酌情給分。3．ni+1 4．4 25．9174 8788 6．非零元很少(tm*n)且分布沒有規(guī)律7．深度 8． 9 9．12 10．64三、計(jì)算題（每題6分，共30分）1．輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個(gè)元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。else if(k=n) {P[i]=A[i]。不要做金錢、權(quán)利的奴隸；應(yīng)學(xué)會(huì)做“金錢、權(quán)利”的主人。最值得欣賞的風(fēng)景，是自己奮斗的足跡。 b(P,i+1,k)。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．拓?fù)湫蛄校?,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)個(gè)元素，為了避免重復(fù)和漏選，可分別求出包括1和不包括1的所有組合。 item ){ while ( BST != NULL ) { if ( item == BTdata ) {item = BSTdata。（n2=n01） （3）哈夫曼樹見下圖，其帶權(quán)路徑長度wpl=51 Wpl=4*3+3*3+2*(4+5+6)=515．答：n（n0）個(gè)結(jié)點(diǎn)的d度樹共有nd個(gè)鏈域，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均有一個(gè)指針?biāo)?，故該樹的空鏈域有nd(n1)=n(d1)+1個(gè)。2．判斷結(jié)果元素值3456586394比較次數(shù)21344四、應(yīng)用題（每題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)直接選擇排序（第六趟后僅剩一個(gè)元素，是最小的，直接選擇排序結(jié)束）第一趟 (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）若先序序列與后序序列相同，則或?yàn)榭諛?，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹（2）若中序序列與后序序列相同，則或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹的二叉樹．（3）若先序序列與中序序列相同，則或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹．（4）若中序序列與層次遍歷序列相同，則或?yàn)榭諛洌驗(yàn)槿我唤Y(jié)點(diǎn)