【正文】 至多只有右子樹的二叉樹4．答：（1）T樹的最大深度Kmax=6（除根外，每層均是兩個結點）T樹的最小深度Kmin=4（具有6個葉子的完全二叉樹是其中的一種形態(tài)）（2）非葉子結點數(shù)是5。3．假定一組數(shù)據(jù)的初始堆為（84，79，56，42，40，46，50，38），請寫出在堆排序階段進行前三次對換和篩運算后數(shù)據(jù)的排列情況。9．在一個具有n個頂點的無向圄中，要連通所有頂點則至少需要 條邊。 二、填空題（每空1分，共25分）1．數(shù)據(jù)的邏輯結構被分為 、 、 和 四種。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．在一個順序隊列中，隊首指針指向隊首元素的（ ）位置。4. 已知一個圖的頂點集V和邊集G分別為：　V={0,1,2,3,4,5,6,7,8}。10．高度為8的完全二叉樹至少有______個葉子結點。3．在一個長度為n的順序表中第i個元素（1=i=n）之前插入一個元素時，需向后移動________個元素。qRlink=q。pLlinkRlink=q。 item )數(shù)據(jù)結構作業(yè)題（四）一、選擇題（每題2分，共20分）1．從邏輯上可以把數(shù)據(jù)結構分為（ ）兩大類。（12分）從一維數(shù)組A[n]中二分查找關鍵字為K的元素的遞歸算法，若查找成功則返回對應元素的下標，否則返回1。 ElemType x=item int i=。int a[5] = {15,8,9,26,12}。 已知一個帶權圖的頂點集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 }； 則求出該圖的最小生成樹的權。對于一個具有n個頂點和e條邊的連通圖，其生成樹中頂點數(shù)和邊數(shù)分別為 和 。 在線性表的單鏈接存儲中，若一個元素所在結點的地址為p，則其后繼結點的地址為 ，若假定p為一個數(shù)組a中的下標，則其后繼結點的下標為 。（ ）排序的結果為：12，13，15，18，20，60（ ）排序的結果為：13，15，18，12，20，60（ ）排序的結果為：13，15，20，18，12，604．設T是一棵二叉樹，除葉子結點外，其它結點的度數(shù)皆為2，若 T中有6個葉結點，試問：（1）T樹的最大深度Kmax=?最小可能深度Kmin=?（2）T樹中共有多少非葉結點？(3) 若葉結點的權值分別為1,2,3,4,5,6。7．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則度為0的結點數(shù)分別為 、 、 和 個。A、不一定相同 B、都相同 C、都不相同 D、互為逆序9．圖的鄰接矩陣表示法適用于表示（ ）。 im。 p=HL。1）先序序列和中序序列相同 2）中序序列和后序序列相同 3）先序序列和后序序列相同 4）中序序列與層次遍歷序列相同4．設T是一棵二叉樹，除葉子結點外，其它結點的度數(shù)皆為2，若 T中有6個葉結點，試問：（1）T樹的最大深度Kmax=?最小可能深度Kmin=?（2）T樹中共有多少非葉結點？(3) 若葉結點的權值分別為1,2,3,4,5,6。2．已知一個有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 順序存儲于一維數(shù)組a[12]中，根據(jù)折半搜索過程填寫成功搜索下表中所給元素34, 56, 58, 63, 94時的比較次數(shù)。5．對于一棵具有n個結點的二叉樹，若一個結點的編號為i(1≤i≤n)，則它的左孩子結點的編號為 ，右孩子結點的編號為 ，雙親結點的編號為 。 s=0； for(i=1；in；i++) for(j=1；jn；j++) s+=i*j；A、O (1) B、O (n) C、O (2n) D、O (n2)7．棧是一種操作受限的線性結構，其操作的主要特征是（ ）。A、first == NULL。 D、first != NULL。A、(rearfront1)％n B、(rearfront)％nC、(frontrear+1)％n D、(rearfront+n)％n9．高度為5的完全二叉樹中含有的結點數(shù)至少為（ ）。8．在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要 條邊。試以排序碼序列的變化描述形式說明排序全過程（動態(tài)過程）要求按遞減順序排序。A、HL=p。2．由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ）。 j++) a[i][j]=i*j。2．若對關鍵字序列（43，02，80，48，26，57，15，73，21，24，66）進行一趟增量為3的希爾排序，則得到的結果為 。10．在一個長度為n的順序存儲線性表中，向第i個元素(1≤i≤n+1)之前插入一個新元素時，需要從后向前依次后移 個元素。A、ni B、ni+1 C、ni1 D、i設一個廣義表中結點的個數(shù)為n，則求廣義表深度算法的時間復雜度為 。 后綴表達式“4 5 + 3 * 2 4 + * ”的值為 。 1給定一組數(shù)據(jù){6，2，7，10，3，12}以它構造一棵哈夫曼樹，則樹高為__________，帶權路徑長度WPL的值為__________。 假定一組記錄的排序碼為（46，79，56，38，40，80，25，34），在對其進行快速排序的過程中，對應二叉搜索樹的深度為 ，分支結點數(shù)為 。 i++ ) InsertFront(HL,a[i])。 [i]=[j]。 else if (KA[mid].key ) 。A. O(0) B. O(1) C. O(n) D. O(n2) 5．在雙向鏈表指針p的結點前插入一個指針q的結點操作是（ ）。C. qRlink=p。6．若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是（ ）。若以列序為主序順序存儲，則元素a[45,68]的存儲地址為_ _。2．假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進行先序、中序、后序、按層遍歷的結果。拓撲序列：5．假定一組記錄的排序碼為(46,79,56,38,40,80,25,34)，則對其進行快速排序的第一次劃分后的結果為________________。 6．我們對記錄進行排序的目的是（ ）。4．在廣義表的存儲結構中，每個結點均包含有 個域。12．在索引表中，若一個索引項對應主表中的一條記錄，則稱此索引為 表。四、閱讀算法，回答問題（每題5分，共10分）1．void AA （List＆L）{ InitList（L）； InsertRear （L，30）； InsertFront（L，50）； int a [4]={5，8，12，15} for（int i=0；1＜4；i＋＋＝ InsertRear（L，a [i]）； } 該算法被調(diào)用執(zhí)行后，得到的線性表L為： 。取a與b進行比較，c與d進行比較。 （2分） 后根：e,b,h,i,j,f,g,c,d,a。else BST=BSTright。int A[],n。BT一right= =NULL）return else return Count（BT一left）十Count（BT一right）； }歡迎您的光臨，！希望您提出您寶貴的意見，你的意見是我進步的動力。學習資