【正文】 性質(zhì)相同的數(shù)據(jù)元素的集合D、相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合6．在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（ ）。 i++) for(int j=0。A、*(a+i) B、a+i C、*a+i D、amp。 D、pnext=HLnext。 B、pnext=HL。請構(gòu)造一棵哈曼夫樹，并計(jì)算該哈曼夫樹的帶權(quán)路徑長度wpl。試以排序碼序列的變化描述形式說明排序全過程（動態(tài)過程）要求按遞減順序排序。元素值3456586394比較次數(shù)四、應(yīng)用題（每題10分，共50分）1．設(shè)待排序的記錄共7個，排序碼分別為8，3，2，5，9，1，6。10．一棵含999個結(jié)點(diǎn)的完全二叉樹的深度為 。6．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)被分為 、 、 和 四種。2．在一棵AVL樹中，每個結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對值不超過 。A、先進(jìn)先出 B、后進(jìn)先出 C、進(jìn)優(yōu)于出 D、出優(yōu)于進(jìn)8．假設(shè)以數(shù)組A[n]存放循環(huán)隊(duì)列的元素，其頭、尾指針分別為front和rear。A、分支結(jié)點(diǎn) B、葉結(jié)點(diǎn) C、樹根結(jié)點(diǎn) D、空結(jié)點(diǎn)4．在有向圖中每個頂點(diǎn)的度等于該頂點(diǎn)的（ ）。 B、firstlink == NULL。. . . .東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)作業(yè)題（一）一、選擇題（每題2分，共20分）1．在一個長度為n的順序表的任一位置插入一個新元素的漸進(jìn)時間復(fù)雜度為（ ）。C、firstlink == first。A、入度 B、出度C、入度與出度之和 D、入度與出度之差5．對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（ ）的值除以9。若設(shè)定尾指針指向隊(duì)列中的隊(duì)尾元素，頭指針指向隊(duì)列中隊(duì)頭元素的前一個位置，則當(dāng)前存于隊(duì)列中的元素個數(shù)為（ ）。3．已知8個數(shù)據(jù)元素為（34，76，45，18，26，54，92，65），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，則該樹的深度為 。7．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則樹中所含的結(jié)點(diǎn)數(shù)為 個，樹的深度為 ，樹的度為 。三、運(yùn)算題（每題5分，共10分）1．設(shè)有一個10180。（1）用直接插入排序。2．判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請將它們調(diào)整為堆）。5．一棵有n(n0)個結(jié)點(diǎn)的d度樹，若用多重鏈表表示，樹中每個結(jié)點(diǎn)都有d個鏈域，則在表示該樹的多重鏈表中有多少個空鏈域? 為什么?儲，則A[7,1]和A[2,4]的第一個字節(jié)的地址是多少？數(shù)據(jù)結(jié)構(gòu)作業(yè)題（二）一、選擇題（每題2分，共20分）1．在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點(diǎn)，則執(zhí)行（ ）。 HL=p。 HLnext=p。a+i 4．下面程序段的時間復(fù)雜度為（ ）。 jn。A、插入 B、刪除 C、排序 D、定位7．若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為（ ）。A、f,c,b B、f,d,b C、g,c,b D、g,d,b二、填空題（每空2分，共40分）1．含n個頂點(diǎn)的無向連通圖中至少含有 條邊。5．快速排序在平均情況下的時間復(fù)雜度為 ，在最壞情況下的時間復(fù)雜度為 。9．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)被分為 、 、 和 四種。設(shè)一數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。5．一棵有n(n0)個結(jié)點(diǎn)的d度樹，若用多重鏈表表示，樹中每個結(jié)點(diǎn)都有d個鏈域，則在表示該樹的多重鏈表中有多少個空鏈域? 為什么?6．有一個二維數(shù)組A[0:8,1:5]，每個數(shù)組元素用相鄰的4個字節(jié)存儲,存儲器按字節(jié)編址，假設(shè)存儲數(shù)組元素A[0,1]的第一個字節(jié)的地址是0，那么存儲數(shù)組的最后一個元素的第一個字節(jié)的地址是多少？若按行存儲,則A[3,5]和A[5,3]的第一個字節(jié)的地址是多少？若按列存儲，則A[7,1]和A[2,4]的第一個字節(jié)的地址是多少？數(shù)據(jù)結(jié)構(gòu)作業(yè)題（三）一、單選題（每題2分，共10分）在長度為n的順序存儲的線性表中，刪除第i個元素（1≤i≤n）時，需要從前向后依次前移 個元素。A、2 B、3 C、4 D、5 適用于折半查找的表的存儲方式及元素排列要求為 。 棧又稱為 表，隊(duì)列又稱為 表。 從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結(jié)點(diǎn)的值，則表明 ，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向 查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向 查找。1在歸并排序中，進(jìn)行每趟歸并的時間復(fù)雜度為 ，整個排序過程的時間復(fù)雜度為 ，空間復(fù)雜度為 。后根： 。 對于線性表（18,25,63,50,42,32,90,66）進(jìn)行散列存儲時，若選用H(K)=K%9作為散列函數(shù)，則散列地址為0的元素有 個，散列地址為3的元素有 個，散列地址為5的元素有 個。 InsertRear(HL,30)。 i5。 HBT , const ElemType item) // HBT為一個小根堆{ []=item。 if ( x=[j]) break。 } 該算法的功能為： 。if ( K==A[mid].key) 。 }六、編寫算法（14分）編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為item的結(jié)點(diǎn)的非遞歸算法，若查找成功則由item帶回整個結(jié)點(diǎn)的值并返回true，否則返回false。A．一定連續(xù) B．一定不連續(xù) C．不一定連續(xù) D．部分連續(xù)，部分不連續(xù)4．若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（ ）。pLlinkRlink=q。qLlink=pLlink。pLlink=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)中評價算法的兩個重要指標(biāo)是 和 。5．設(shè)數(shù)組a[1..50,1..80]的基地址為2000，每個元素占2個存儲單元，若以行序?yàn)橹餍蝽樞虼鎯Γ瑒t元素a[45,68]的存儲地址為_ _。8．具有256個結(jié)點(diǎn)的完全二叉樹的深度為______。請說明為什么不能或如何才能得到。　　按照普里姆算法從頂點(diǎn)0出發(fā)得到最小生成樹，試寫出在生成最小生成樹的過程中依次得到的各條邊。若存儲它采用鄰接表，并且每個頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號從小到大的次序鏈接的，則按主教材中介紹的進(jìn)行拓?fù)渑判虻乃惴?，寫出得到的拓?fù)湫蛄校ㄌ崾荆合犬嫵鰧?yīng)的圖形，然后再運(yùn)算）。數(shù)據(jù)結(jié)構(gòu)作業(yè)題（五）一、選擇題（每題2分，共20分）1．若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為（ ）參數(shù)。A O（1） B O（1og2n）C O（n） D O（nlog2n）5．假設(shè)有兩個串A和B，求B在A中首次出現(xiàn)的位置的操作，我們稱為（ ）。A.(B, E , F, G) B.( ) C.（A，B， E，F(xiàn)，G) D.（G）9．線性表如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，要求內(nèi)存中的存儲單元的地址（ ）。3．在一個稀疏矩陣中，每個非零元素所對應(yīng)的三元組包括該元素的