【正文】 sert（Q，遷6）； QInsert（Q，QDelete（Q））； QInsert（Q，30）； QInsert（Q，QDelete（Q）＋10）； whi1e（！QueueEmpty（Q）） cout＜＜QDeleie（Q）＜＜”； } 該算法被調(diào)用后得到的輸出結(jié)果為： 。設(shè)ab,cd(ab和cd情況類似)，此時(shí)需2次比較，取b和d比較，若bd，則有序abd；若bd時(shí)則有序cdb，此時(shí)已進(jìn)行了3次比較。 （2分） 按層：a,b,c,d,e,f,g,h,i,j。 } return false。 //設(shè)集合已存于數(shù)組A中。贈(zèng)語(yǔ)； 如果我們做與不做都會(huì)有人笑，如果做不好與做得好還會(huì)有人笑，那么我們索性就做得更好，來(lái)給人笑吧！ 現(xiàn)在你不玩命的學(xué)，以后命玩你。壓力不是有人比你努力，而是那些比你牛幾倍的人依然比你努力。amp。將這兩種情況合到一起，就是題目的解。 }else if (itemBSTdata) BST=BSTleft。習(xí)題三參考答案一、單選題（每題2分，共10分） A B D D D二、填空題（每空1分，共25分） 1:1 1:N M:N （或者 1對(duì)1 1對(duì)N M對(duì)N） pnext a[p].next 引用 后進(jìn)先出 先進(jìn)先出 162 31 21 6 查找成功 左子樹 右子樹 n2 n n11二叉搜索樹 理想平衡樹 （次序無(wú)先后） 1O(n) O(nlog2n) O(n) 15 96 三、運(yùn)算題（每題6分，共24分） 先根：a,b,e,c,f,h,i,j,g,d。習(xí)題二參考答案一、選擇題（每題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．集合結(jié)構(gòu)；線性結(jié)構(gòu)；樹型結(jié)構(gòu)；圖形結(jié)構(gòu)10．ni+1三、應(yīng)用題（每題10分，共60分）1．答：可以做到。4．假定一組記錄的徘序碼為（46，79，56，38，40，80，36，40，75，66，84，24），對(duì)其進(jìn)行歸并排序的過(guò)程中，第三趟歸并后的結(jié)果為： 。11．以二分查找方法查找一個(gè)線性表時(shí)，此線性表必須是 存儲(chǔ)的 表。3．在一個(gè)稀疏矩陣中，每個(gè)非零元素所對(duì)應(yīng)的三元組包括該元素的 、 和 三項(xiàng)。A O（1） B O（1og2n）C O（n） D O（nlog2n）5．假設(shè)有兩個(gè)串A和B，求B在A中首次出現(xiàn)的位置的操作，我們稱為（ ）。若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，則按主教材中介紹的進(jìn)行拓?fù)渑判虻乃惴?，寫出得到的拓?fù)湫蛄校ㄌ崾荆合犬嫵鰧?duì)應(yīng)的圖形，然后再運(yùn)算）。請(qǐng)說(shuō)明為什么不能或如何才能得到。5．設(shè)數(shù)組a[1..50,1..80]的基地址為2000，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[45,68]的存儲(chǔ)地址為_ _。pLlink=q。qLlink=pLlink。A．一定連續(xù) B．一定不連續(xù) C．不一定連續(xù) D．部分連續(xù)，部分不連續(xù)4．若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ ）。if ( K==A[mid].key) 。 if ( x=[j]) break。 i5。 對(duì)于線性表（18,25,63,50,42,32,90,66）進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%9作為散列函數(shù)，則散列地址為0的元素有 個(gè)，散列地址為3的元素有 個(gè)，散列地址為5的元素有 個(gè)。1在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為 ，整個(gè)排序過(guò)程的時(shí)間復(fù)雜度為 ，空間復(fù)雜度為 。 棧又稱為 表，隊(duì)列又稱為 表。5．一棵有n(n0)個(gè)結(jié)點(diǎn)的d度樹，若用多重鏈表表示，樹中每個(gè)結(jié)點(diǎn)都有d個(gè)鏈域，則在表示該樹的多重鏈表中有多少個(gè)空鏈域? 為什么?6．有一個(gè)二維數(shù)組A[0:8,1:5]，每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲(chǔ),存儲(chǔ)器按字節(jié)編址，假設(shè)存儲(chǔ)數(shù)組元素A[0,1]的第一個(gè)字節(jié)的地址是0，那么存儲(chǔ)數(shù)組的最后一個(gè)元素的第一個(gè)字節(jié)的地址是多少？若按行存儲(chǔ),則A[3,5]和A[5,3]的第一個(gè)字節(jié)的地址是多少？若按列存儲(chǔ)，則A[7,1]和A[2,4]的第一個(gè)字節(jié)的地址是多少？數(shù)據(jù)結(jié)構(gòu)作業(yè)題（三）一、單選題（每題2分，共10分）在長(zhǎng)度為n的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素（1≤i≤n）時(shí)，需要從前向后依次前移 個(gè)元素。9．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)被分為 、 、 和 四種。A、f,c,b B、f,d,b C、g,c,b D、g,d,b二、填空題（每空2分，共40分）1．含n個(gè)頂點(diǎn)的無(wú)向連通圖中至少含有 條邊。 jn。 HLnext=p。5．一棵有n(n0)個(gè)結(jié)點(diǎn)的d度樹，若用多重鏈表表示，樹中每個(gè)結(jié)點(diǎn)都有d個(gè)鏈域，則在表示該樹的多重鏈表中有多少個(gè)空鏈域? 為什么?儲(chǔ)，則A[7,1]和A[2,4]的第一個(gè)字節(jié)的地址是多少？數(shù)據(jù)結(jié)構(gòu)作業(yè)題（二）一、選擇題（每題2分，共20分）1．在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（ ）。（1）用直接插入排序。7．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則樹中所含的結(jié)點(diǎn)數(shù)為 個(gè)，樹的深度為 ，樹的度為 。若設(shè)定尾指針指向隊(duì)列中的隊(duì)尾元素，頭指針指向隊(duì)列中隊(duì)頭元素的前一個(gè)位置，則當(dāng)前存于隊(duì)列中的元素個(gè)數(shù)為（ ）。C、firstlink == first。 B、firstlink == NULL。A、先進(jìn)先出 B、后進(jìn)先出 C、進(jìn)優(yōu)于出 D、出優(yōu)于進(jìn)8．假設(shè)以數(shù)組A[n]存放循環(huán)隊(duì)列的元素，其頭、尾指針?lè)謩e為front和rear。6．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為 、 、 和 四種。元素值3456586394比較次數(shù)四、應(yīng)用題（每題10分，共50分）1．設(shè)待排序的記錄共7個(gè)，排序碼分別為8，3，2，5，9，1，6。請(qǐng)構(gòu)造一棵哈曼夫樹，并計(jì)算該哈曼夫樹的帶權(quán)路徑長(zhǎng)度wpl。 D、pnext=HLnext。 i++) for(int j=0。A、無(wú)向圖 B、有向圖 C、稠密圖 D、稀疏圖10．若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵字b的過(guò)程中，先后進(jìn)行比較的關(guān)鍵字依次為（ ）。8．在一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)數(shù)為 個(gè)。請(qǐng)構(gòu)造一棵哈曼夫樹，并計(jì)算該哈曼夫樹的帶權(quán)路徑長(zhǎng)度wpl。 在初始化一個(gè)稀疏矩陣的函數(shù)定義中，矩陣形參應(yīng)說(shuō)明為 參數(shù)。 1二分查找過(guò)程所對(duì)應(yīng)的判定樹既是一棵 ，又是一棵 。最小生成樹的權(quán)： 。for ( int i=0。 while ( i != 0 ){ int j=(i1)/2。int Binsch( ElemTy