【正文】 一個圖的頂點集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}； 按照克魯斯卡爾算法得到最小生成材，拭寫出在最小生成樹中依次得到的各條邊。13．快速排序在平均情況下的空間復(fù)雜度為 ，在最壞情況下的空間復(fù)雜度為 。11．以二分查找方法查找一個線性表時，此線性表必須是 存儲的 表。9．在一個具有n個頂點的無向圄中，要連通所有頂點則至少需要 條邊。7．在一棵二叉樹中，第5層上的結(jié)點數(shù)最多為 。5．當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top = =N表示?？?，則表示棧滿的條件為 。3．在一個稀疏矩陣中，每個非零元素所對應(yīng)的三元組包括該元素的 、 和 三項。 二、填空題（每空1分，共25分）1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)被分為 、 、 和 四種。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)存中的存儲單元的地址（ ）。 7．在最壞的情況下，冒泡排序法的時間復(fù)雜度為（ ）。A O（1） B O（1og2n）C O（n） D O（nlog2n）5．假設(shè)有兩個串A和B，求B在A中首次出現(xiàn)的位置的操作，我們稱為（ ）。A q一next=p一next；p一next=q；B p一next=q一next；q=p；C 9一next=p一next；p一next=q；D p一next=q一next；q一next=p；3．在一個順序隊列中，隊首指針指向隊首元素的（ ）位置。數(shù)據(jù)結(jié)構(gòu)作業(yè)題（五）一、選擇題（每題2分，共20分）1．若需要利用形參直接訪問實參，則應(yīng)把形參變量說明為（ ）參數(shù)。四、算法填空（10分）1． 五、編程（10分）1．設(shè)計算法以求解從集合{1..n}中選取k（k=n）個元素的所有組合。若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，則按主教材中介紹的進(jìn)行拓?fù)渑判虻乃惴?，寫出得到的拓?fù)湫蛄校ㄌ崾荆合犬嫵鰧?yīng)的圖形，然后再運算）。4. 已知一個圖的頂點集V和邊集G分別為：　V={0,1,2,3,4,5,6,7,8}?！　“凑掌绽锬匪惴◤捻旤c0出發(fā)得到最小生成樹，試寫出在生成最小生成樹的過程中依次得到的各條邊。先序：中序：后序：按層：3．已知一個圖的頂點集V和邊集G分別為：V={0,1,2,3,4,5,6,7}。請說明為什么不能或如何才能得到。10．高度為8的完全二叉樹至少有______個葉子結(jié)點。8．具有256個結(jié)點的完全二叉樹的深度為______。6．所謂稀疏矩陣指的是_______。5．設(shè)數(shù)組a[1..50,1..80]的基地址為2000，每個元素占2個存儲單元，若以行序為主序順序存儲，則元素a[45,68]的存儲地址為_ _。3．在一個長度為n的順序表中第i個元素（1=i=n）之前插入一個元素時，需向后移動________個元素。A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點二、填空題（每空2分，共30分）1．?dāng)?shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是 和 。 A. ij1 B. ij C. ji+1 D. 不確定的7．有六個元素6，5，4，3，2，1 的順序進(jìn)棧，問下列哪一個不是合法的出棧序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 8．用鏈接方式存儲的隊列，在進(jìn)行刪除運算時（ ）。pLlink=q。qRlink=q。pLlink=q。qLlink=pLlink。qLlink=pLlink。pLlinkRlink=q。pLlinkRlink=q。A. pLlink=q。A．一定連續(xù) B．一定不連續(xù) C．不一定連續(xù) D．部分連續(xù)，部分不連續(xù)4．若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（ ）。 item )數(shù)據(jù)結(jié)構(gòu)作業(yè)題（四）一、選擇題（每題2分，共20分）1．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。 }六、編寫算法（14分）編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為item的結(jié)點的非遞歸算法，若查找成功則由item帶回整個結(jié)點的值并返回true，否則返回false。 else 。if ( K==A[mid].key) 。（12分）從一維數(shù)組A[n]中二分查找關(guān)鍵字為K的元素的遞歸算法，若查找成功則返回對應(yīng)元素的下標(biāo)，否則返回1。 } 該算法的功能為： 。 i=j。 if ( x=[j]) break。 ElemType x=item int i=。 HBT , const ElemType item) // HBT為一個小根堆{ []=item。 } 該算法被調(diào)用執(zhí)行后，得到的以HL為表頭指針的單鏈表中的數(shù)據(jù)元素依次為： 。 i5。int a[5] = {15,8,9,26,12}。 InsertRear(HL,30)。四、閱讀算法（第一題7分，第二題8分） void AA(LNode * amp。 對于線性表（18,25,63,50,42,32,90,66）進(jìn)行散列存儲時，若選用H(K)=K%9作為散列函數(shù)，則散列地址為0的元素有 個，散列地址為3的元素有 個，散列地址為5的元素有 個。 已知一個帶權(quá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)。后根： 。三、運算題（每題6分，共24分） 假定一棵普通樹的廣義表表示為 a(b(e),c(f(h,i,j),g),d)，分別寫出先根、后根、按層遍歷的結(jié)果。1在歸并排序中，進(jìn)行每趟歸并的時間復(fù)雜度為 ，整個排序過程的時間復(fù)雜度為 ，空間復(fù)雜度為 。對于一個具有n個頂點和e條邊的連通圖，其生成樹中頂點數(shù)和邊數(shù)分別為 和 。 從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結(jié)點的值，則表明 ，若元素的值小于根結(jié)點的值，則繼續(xù)向 查找，若元素的值大于根結(jié)點的值，則繼續(xù)向 查找。 一棵深度為5的滿二叉樹中的結(jié)點數(shù)為 個，一棵深度為3的滿四叉樹中的結(jié)點數(shù)為 個。 棧又稱為 表，隊列又稱為 表。 在線性表的單鏈接存儲中，若一個元素所在結(jié)點的地址為p，則其后繼結(jié)點的地址為 ，若假定p為一個數(shù)組a中的下標(biāo)，則其后繼結(jié)點的下標(biāo)為 。A、2 B、3 C、4 D、5 適用于折半查找的表的存儲方式及元素排列要求為 。A、O(1) B、O(n) C、O(n2) D、O(log 2 n)假定一個順序隊列的隊首和隊尾指針分別為