【正文】 !=null) { Lnode*q=p。 3是： Binsch(A,mid+1,high,K)。 該算法的輸入結(jié)果是：34 91 30 45 63 78 150312： m 、 m 1三、運算題（每小題6分，共24分）劃分次序劃分結(jié)果第一次[38 24 40] 46 [56 80 95 79]第二次24 [38 40] 46 [56 80 95 79]第三次24 38 40 46 [56 80 95 79]第四次24 38 40 46 56 [80 95 79]第五次24 38 40 46 56 79 [80 95]第六次24 38 40 46 56 79 80 95 編寫算法（10分） else if ( K A[mid].key) return 2 else return 3}else return 4 undnown(p→rightchild)。 if (p!=NULL) { temp = p→leftchild。}while (!stackempty (a)) cout pop (a) ”” 。 int x。 int top。假定從鍵盤上輸入一批整數(shù)，依次為：78 63 45 30 91 34 –1，請寫出輸出結(jié)果。四、 四、 圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時三、 三、 一棵高度為5的二叉樹中最少含有_________個結(jié)點，最多含有________個結(jié)點；一棵高度為5的理想平衡樹中，最少含有_________個結(jié)點，最多含有_________個結(jié)點。datanext a 0 1 2 3 4 5 6 7 8 棧的插入和刪除操作在（ ）進行。 s→link=p。 p→link=s。//i為計數(shù)器 while(p!=NULL) { if (Pdata==x) i++。五、 五、 見圖124444422255285283452843 用克魯斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 4. 鄰接矩陣： 鄰接表如圖11所示：圖113. 3. 線性表為：（78，50，40，60，34，90）2. 2. 運算題（每題6分，共24分）1. 1. （12，40） （ ） （74） （23,55，63）10. 10. n(n1)/2 n(n1)9. 9. 有向無回路8. 8. e 2e7. 7. 2n n1 n+16. 6. 1 3 4 X * + 2 Y * 3 / 5. 5. 9 3 34. 4. O(n)3. 3. 正確性 易讀性 強壯性 高效率2. 2. 填空題（每空1分，共26分）1. 1. int CountX(LNode* HL,ElemType x) }//if} //查找失敗 else { if (item==BSTdata){ item=BSTdata。五、 五、 ABC (BTright)。 LinkList mynote(LinkList L) {//L是不帶頭結(jié)點的單鏈表的頭指針 if(Lamp。 閱讀算法（每題7分，共14分）1. 1. 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化。 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。 A 0 1 2 3 4 5 6 7 data 運算題（每題 6 分，共24分）1. 1. 在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。 在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為________，整個堆排序過程的時間復(fù)雜度為________。 向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度___________。 假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為____________________________、___________________、_______________________和__________________________。 在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。 AOV網(wǎng)是一種___________________的圖。 對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點分別有_______個和________個。在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。5. 5. 棧和隊列的共同特點是( )。 單選題（每題 2 分，共20分）1. 1.} HL=HLnext。 編寫算法（8分）ElemType DeleFront(LNode * amp。 拓樸排序為： 4 3 6 5 7 2 1 四、 四、 DFS：????… BFS：???…? 4. 4.3. 3. HL)六、 六、 //查找成功，返回元素的下標(biāo) else if (K[mid].key) ______________________________________。 算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫完整。 } p=pnext。 if(!visited[j]) { coutj39。 QInsert(Q,i)。 InitQueue(Q)。 while (++i=x) if (n%i==0) break。四、 四、 已知一個圖的頂點集V和邊集E分別為： 圖6 V={1,2,3,4,5,6,7}。5稀疏矩陣如下所示， 運算題（每題6分，共24分）1. 1. 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用_______________排序；當(dāng)待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用________________________排序。 在線性表的散列存儲中，處理沖突的常用方法有________________________和_____________________________兩種。其余類推，則A[ i ]元素的左孩子元素為________,右孩子元素為_______________，雙親元素為____________。10. 10.9. 9.W中第6 行的元素和第4 列的元素共占用＿_______＿個字節(jié)。5. 5.4. 4.3. 3.2. 2. A. O(n) B. O(1) C. O(log2n) D. O(n2) 若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為（ ）參數(shù)。A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找7. 7. D. HL=p。 B. pnext=HL。 對一個算法的評價，不包括如下（B ）方面的內(nèi)容。 單選題（每題 2 分，共20分）1. 1. HLnext=p。 p=HL。 A．有向圖 B．無向圖 C．無向無環(huán)圖 D．有向無環(huán)圖6. 6. 采用開放定址法處理散列表的沖突時，其平均查找長度（ ）。A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10. 10. 從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為( )。 運算題（每題 6 分，共24分）1. 1.當(dāng)結(jié)點之間存在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_____________________。 隊列的插入操作是在隊列的___尾______進行，刪除操作是在隊列的____首______進行。 當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用top==N表示棧空，則表示棧滿的條件是___top==0___(要超出才為滿)_______________。 對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為_________，在表尾插入元素的時間復(fù)雜度為____________。 設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標(biāo)i從0到7 ，列下標(biāo)j從0到3 ，則二維數(shù)組W的數(shù)據(jù)元素共占用＿_____＿個字節(jié)。8. 8.對一棵由算術(shù)表達式組成的二叉語法樹進行后序遍歷得到的結(jié)點序列是該算術(shù)表達式的__________________。 對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_____________個，其中_______________個用于指向孩子，_________________個指針是空閑的。 若對一棵完全二叉樹從0開始進行結(jié)點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點存儲到A[0]中。 已知一個6180。試：（1） （1） int x=(int) sqrt(n)。 } (1) (1) 指出該算法的功能；(2) (2) 該算法的時間復(fù)雜度是多少？2. 2. 寫出下述算法的功能： void AJ(adjlist GL, int i, int n) { Queue Q。 visited[i]=true。 while(p!=NULL) { int j=padjvex。 QInsert(Q,j)。while (low=high){int mid=_______________________________；if (K==A[mid].key) return mid。 //查找失敗，返回1}ElemType DeleFront(LNode * amp。2. 2. 圖8如圖8所示。 算法填空（8 分） (low+high)/2 high=mid1 low=mid+1 六、 六、}LNode* p=HL。return temp。 6. 6. 二叉樹的第k層的結(jié)點數(shù)最多為( ). A．2k1 +1 　　　D. 2k17. 7. 若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標(biāo)依次為( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，38. 8. 對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為 A. O（1） 　　B. O（n）　　 C. O（1og2n） D. O（n2）9. 9. 對于線性表（7，34，55，25，64，46，20，10）進行