【正文】 過程（動態(tài)過程）要求按遞減順序排序。 （1）100，85，98，77，80，60，82，40，20，10，66 （2）100，98，85，82，80，77，66，60，40，20，10 （3）100，85，40，77，80，60，66，98，82，10，20（4）10，20，40，60，66，77，80， 82，85，98，1003．試找出分別滿足下列條件的所有二叉樹。請構(gòu)造一棵哈曼夫樹，并計算該哈曼夫樹的帶權(quán)路徑長度wpl。A、HL=p。 B、pnext=HL。C、pnext=HL。 D、pnext=HLnext。2．由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ）。A、*(a+i) B、a+i C、*a+i D、amp。 for(int i=0。 i++) for(int j=0。 j++) a[i][j]=i*j。A、一種數(shù)據(jù)類型B、數(shù)據(jù)的存儲結(jié)構(gòu)C、一組性質(zhì)相同的數(shù)據(jù)元素的集合D、相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合6．在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關系的運算是（ ）。A、3，2，6，1，4，5 B、3，4，2，1，6，5C、1，2，5，3，4，6 D、5，6，4，2，3，18．在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關系（ ）。A、無向圖 B、有向圖 C、稠密圖 D、稀疏圖10．若有序表的關鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關鍵字b的過程中，先后進行比較的關鍵字依次為（ ）。2．若對關鍵字序列（43，02，80，48，26，57，15，73，21，24，66）進行一趟增量為3的希爾排序，則得到的結(jié)果為 。4．在以HL為表頭指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為 和 。6．假定對長度n=50的有序表進行二分查找，則對應的判定樹高度為________，判定樹中前5層的結(jié)點數(shù)為________，最后一層的結(jié)點數(shù)為________。8．在一棵二叉樹中，假定雙分支結(jié)點數(shù)為5個，單分支結(jié)點數(shù)為6個，則葉子結(jié)點數(shù)為 個。10．在一個長度為n的順序存儲線性表中，向第i個元素(1≤i≤n+1)之前插入一個新元素時，需要從后向前依次后移 個元素。2．有一隨機數(shù)組(25,84,21,46,13,27,68,35,20),現(xià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．請在（ ）內(nèi)填入正確的排序方法。下面是一組由不同排序方法進行一遍排序后的結(jié)果。請構(gòu)造一棵哈曼夫樹，并計算該哈曼夫樹的帶權(quán)路徑長度wpl。A、ni B、ni+1 C、ni1 D、i設一個廣義表中結(jié)點的個數(shù)為n，則求廣義表深度算法的時間復雜度為 。A、f+1==r B、r+1==f C、f==0 D、f==r由3 個結(jié)點可以構(gòu)造出多少種不同的二叉樹 。 A、鏈接方式存儲，元素無序 B．鏈接方式存儲，元素有序 C、順序方式存儲，元素無序 D．順序方式存儲，元素有序二、填空題（每空1分，共25分）在線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點之間分別存在著 、 和 的聯(lián)系。 在初始化一個稀疏矩陣的函數(shù)定義中，矩陣形參應說明為 參數(shù)。 后綴表達式“4 5 + 3 * 2 4 + * ”的值為 。 對于一棵含有40個結(jié)點的理想平衡樹，它的高度為 。 對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為 。 1二分查找過程所對應的判定樹既是一棵 ，又是一棵 。 1給定一組數(shù)據(jù){6，2，7，10，3，12}以它構(gòu)造一棵哈夫曼樹，則樹高為__________，帶權(quán)路徑長度WPL的值為__________。先根： 。按層： 。最小生成樹的權(quán)： 。 假定一組記錄的排序碼為（46，79，56，38，40，80，25，34），在對其進行快速排序的過程中，對應二叉搜索樹的深度為 ，分支結(jié)點數(shù)為 。 HL){ InitList(HL)。 InsertRear(HL,50)。for ( int i=0。 i++ ) InsertFront(HL,a[i])。void AH(Heap amp。 ++。 while ( i != 0 ){ int j=(i1)/2。 [i]=[j]。 } [i]=x。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容。int Binsch( ElemType A[] , int low , int high , KeyType K ){ if ( low=high ){int mid = (low+high)/2。 else if (KA[mid].key ) 。}else return 1。 bool Find( BTreeNode * BST , ElemType amp。A．動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B．順序結(jié)構(gòu)、鏈式結(jié)構(gòu) C．線性結(jié)構(gòu)、非線性結(jié)構(gòu) D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2．以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（ ）？ A．廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串3．連續(xù)存儲設計時，存儲單元的地址（ ）。A. O(0) B. O(1) C. O(n) D. O(n2) 5．在雙向鏈表指針p的結(jié)點前插入一個指針q的結(jié)點操作是（ ）。qRlink=p。qLlink=q；B. pLlink=q。qRlink=p。C. qRlink=p。pLlinkRlink=q。D. qLlink=pLlink。pLlink=q。6．若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是（ ）。A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改9．若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 10．棧和隊列的共同點是（ ）。2．一個算法具有5個特性: 、 、 ，有零個或多個輸入、有一個或多個輸出。4．對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共 ______個，單鏈表為_______個。若以列序為主序順序存儲，則元素a[45,68]的存儲地址為_ _。7．廣義表的_______ 定義為廣義表中括弧的重數(shù)。9．已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有______個葉子結(jié)點。三、計算題（每題6分，共30分）1．如果輸入序列為1 2 3 4 5 6,試問能否通過棧結(jié)構(gòu)得到以下兩個序列:4 3 5 6 1 2和1 3 5 4 2 6。2．假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進行先序、中序、后序、按層遍歷的結(jié)果。　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,(6,7)30}。　　________, ________, ________, _____