【正文】 ，在最壞情況下的時(shí)間復(fù)雜度為 。6．假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行二分查找，則對(duì)應(yīng)的判定樹高度為________，判定樹中前5層的結(jié)點(diǎn)數(shù)為________，最后一層的結(jié)點(diǎn)數(shù)為________。7．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則度為0的結(jié)點(diǎn)數(shù)分別為 、 、 和 個(gè)。8．在一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)數(shù)為 個(gè)。9．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)被分為 、 、 和 四種。10．在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中，向第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移 個(gè)元素。三、應(yīng)用題（每題10分，共60分）1．設(shè)有5個(gè)互不相同的元素a、b、c、d、e，能否通過7次比較就將其排好序？如果能，請(qǐng)列出其比較過程；如果不能，則說明原因。2．有一隨機(jī)數(shù)組(25,84,21,46,13,27,68,35,20),現(xiàn)采用某種方法對(duì)它們進(jìn)行排序,其每趟排序結(jié)果如下, 則該排序方法是什么? 初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84 3．請(qǐng)?jiān)冢? ）內(nèi)填入正確的排序方法。設(shè)一數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。下面是一組由不同排序方法進(jìn)行一遍排序后的結(jié)果。（ ）排序的結(jié)果為：12，13，15，18，20，60（ ）排序的結(jié)果為：13，15，18，12，20，60（ ）排序的結(jié)果為：13，15，20，18，12，604．設(shè)T是一棵二叉樹，除葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)的度數(shù)皆為2，若 T中有6個(gè)葉結(jié)點(diǎn)，試問：（1）T樹的最大深度Kmax=?最小可能深度Kmin=?（2）T樹中共有多少非葉結(jié)點(diǎn)？(3) 若葉結(jié)點(diǎn)的權(quán)值分別為1,2,3,4,5,6。請(qǐng)構(gòu)造一棵哈曼夫樹，并計(jì)算該哈曼夫樹的帶權(quán)路徑長(zhǎng)度wpl。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è)元素。A、ni B、ni+1 C、ni1 D、i設(shè)一個(gè)廣義表中結(jié)點(diǎn)的個(gè)數(shù)為n，則求廣義表深度算法的時(shí)間復(fù)雜度為 。A、O(1) B、O(n) C、O(n2) D、O(log 2 n)假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空的條件為 。A、f+1==r B、r+1==f C、f==0 D、f==r由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹 。A、2 B、3 C、4 D、5 適用于折半查找的表的存儲(chǔ)方式及元素排列要求為 。 A、鏈接方式存儲(chǔ)，元素?zé)o序 B．鏈接方式存儲(chǔ)，元素有序 C、順序方式存儲(chǔ)，元素?zé)o序 D．順序方式存儲(chǔ)，元素有序二、填空題（每空1分，共25分）在線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著 、 和 的聯(lián)系。 在線性表的單鏈接存儲(chǔ)中，若一個(gè)元素所在結(jié)點(diǎn)的地址為p，則其后繼結(jié)點(diǎn)的地址為 ，若假定p為一個(gè)數(shù)組a中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)為 。 在初始化一個(gè)稀疏矩陣的函數(shù)定義中，矩陣形參應(yīng)說明為 參數(shù)。 棧又稱為 表，隊(duì)列又稱為 表。 后綴表達(dá)式“4 5 + 3 * 2 4 + * ”的值為 。 一棵深度為5的滿二叉樹中的結(jié)點(diǎn)數(shù)為 個(gè)，一棵深度為3的滿四叉樹中的結(jié)點(diǎn)數(shù)為 個(gè)。 對(duì)于一棵含有40個(gè)結(jié)點(diǎn)的理想平衡樹，它的高度為 。 從一棵二叉搜索樹中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明 ，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向 查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向 查找。 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小為 。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹中頂點(diǎn)數(shù)和邊數(shù)分別為 和 。 1二分查找過程所對(duì)應(yīng)的判定樹既是一棵 ，又是一棵 。1在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為 ，整個(gè)排序過程的時(shí)間復(fù)雜度為 ，空間復(fù)雜度為 。 1給定一組數(shù)據(jù){6，2，7，10，3，12}以它構(gòu)造一棵哈夫曼樹，則樹高為__________，帶權(quán)路徑長(zhǎng)度WPL的值為__________。三、運(yùn)算題（每題6分，共24分） 假定一棵普通樹的廣義表表示為 a(b(e),c(f(h,i,j),g),d)，分別寫出先根、后根、按層遍歷的結(jié)果。先根： 。后根： 。按層： 。 已知一個(gè)帶權(quán)圖的頂點(diǎn)集V和邊集G分別為： V = { 0，1，2，3，4，5，6，7}； E = {（0，1）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 }； 則求出該圖的最小生成樹的權(quán)。最小生成樹的權(quán)： 。 對(duì)于線性表（18,25,63,50,42,32,90,66）進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%9作為散列函數(shù)，則散列地址為0的元素有 個(gè)，散列地址為3的元素有 個(gè)，散列地址為5的元素有 個(gè)。 假定一組記錄的排序碼為（46，79，56，38，40，80，25，34），在對(duì)其進(jìn)行快速排序的過程中，對(duì)應(yīng)二叉搜索樹的深度為 ，分支結(jié)點(diǎn)數(shù)為 。四、閱讀算法（第一題7分，第二題8分） void AA(LNode * amp。 HL){ InitList(HL)。 InsertRear(HL,30)。 InsertRear(HL,50)。int a[5] = {15,8,9,26,12}。for ( int i=0。 i5。 i++ ) InsertFront(HL,a[i])。 } 該算法被調(diào)用執(zhí)行后，得到的以HL為表頭指針的單鏈表中的數(shù)據(jù)元素依次為： 。void AH(Heap amp。 HBT , const ElemType item) // HBT為一個(gè)小根堆{ []=item。 ++。 ElemType x=item int i=。 while ( i != 0 ){ int j=(i1)/2。 if ( x=[j]) break。 [i]=[j]。 i=j。 } [i]=x。 } 該算法的功能為：