【正文】 d=q=p。三、算法設(shè)計(jì)題(22分)1． 1．2． 2．3． 3．三、算法設(shè)計(jì)題1. 1. 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。amp。}。 s=hb。 else snext=ha。else if (pkeykey)p=plchild。void adjustheap(int r[ ],int n){ int j=n,i=j/2,temp=r[j1]。 i=i/2。 單選題（每題 2 分，共20分）1. 1. 對一個(gè)算法的評價(jià)，不包括如下（B ）方面的內(nèi)容。 B. pnext=HL。 D. HL=p。A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找7. 7. 若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（ ）參數(shù)。 A. O(n) B. O(1) C. O(log2n) D. O(n2)2. 2.3. 3.4. 4.5. 5.W中第6 行的元素和第4 列的元素共占用＿_(dá)______＿個(gè)字節(jié)。9. 9.10. 10.其余類推，則A[ i ]元素的左孩子元素為________,右孩子元素為_______________，雙親元素為____________。 在線性表的散列存儲中，處理沖突的常用方法有________________________和_____________________________兩種。 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對穩(wěn)定性不作要求時(shí)，宜采用_______________排序；當(dāng)待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時(shí)，宜采用________________________排序。 運(yùn)算題（每題6分，共24分）1. 1.5稀疏矩陣如下所示， 已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為： 圖6 V={1,2,3,4,5,6,7}。四、 四、 while (++i=x) if (n%i==0) break。 InitQueue(Q)。 QInsert(Q,i)。 if(!visited[j]) { coutj39。 } p=pnext。 算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫完整。 //查找成功，返回元素的下標(biāo) else if (K[mid].key) ______________________________________。六、 六、 HL)3. 3. DFS：????… BFS：???…? 4. 4. 拓樸排序?yàn)椋?4 3 6 5 7 2 1 四、 四、 編寫算法（8分）ElemType DeleFront(LNode * amp。HL=HLnext。} 單選題（每題 2 分，共20分）1. 1. 棧和隊(duì)列的共同特點(diǎn)是( )。 5. 5.在這種存儲結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹共有________個(gè)指針域，其中有________個(gè)指針域是存放了地址，有________________個(gè)指針是空指針。 對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有_______個(gè)和________個(gè)。 AOV網(wǎng)是一種___________________的圖。 在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有________條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有________條邊。 假定一個(gè)線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為____________________________、___________________、_______________________和__________________________。 向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度___________。 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為________，整個(gè)堆排序過程的時(shí)間復(fù)雜度為________。 在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。 運(yùn)算題（每題 6 分，共24分）1. 1. A 0 1 2 3 4 5 6 7 data 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。 閱讀算法（每題7分，共14分）1. 1. LinkList mynote(LinkList L) {//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(Lamp。 ABC (BTright)。五、 五、 //查找失敗 else { if (item==BSTdata){ item=BSTdata。 }//if} int CountX(LNode* HL,ElemType x) 填空題（每空1分，共26分）1. 1. 正確性 易讀性 強(qiáng)壯性 高效率2. 2. O(n)3. 3. 9 3 34. 4. 1 3 4 X * + 2 Y * 3 / 5. 5. 2n n1 n+16. 6. e 2e7. 7. 有向無回路8. 8. n(n1)/2 n(n1)9. 9. （12，40） （ ） （74） （23,55，63）10. 10. 運(yùn)算題（每題6分，共24分）1. 1. 線性表為：（78，50，40，60，34，90）2. 2. 鄰接矩陣： 鄰接表如圖11所示：圖113. 3. 用克魯斯卡爾算法得到的最小生成樹為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 4. 見圖124444422255285283452843五、 五、//i為計(jì)數(shù)器 while(p!=NULL) { if (Pdata==x) i++。 p→link=s。 s→link=p。 棧的插入和刪除操作在（ ）進(jìn)行。 a 0 1 2 3 4 5 6 7 8 datanext 一棵高度為5的二叉樹中最少含有_________個(gè)結(jié)點(diǎn)，最多含有________個(gè)結(jié)點(diǎn)；一棵高度為5的理想平衡樹中，最少含有_________個(gè)結(jié)點(diǎn)，最多含有_________個(gè)結(jié)點(diǎn)。三、 三、圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí) 四、 四、假定從鍵盤上輸入一批整數(shù)，依次為：78 63 45 30 91 34 –1，請寫出輸出結(jié)果。鄰接表表示時(shí) 已知一個(gè)圖的頂點(diǎn)集V各邊集G如下：V = {0，1，2，3，4，5，6，7，8，9}；E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}當(dāng)它用鄰接矩陣表示和鄰接表表示時(shí)，分別寫出從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。 在對m階的B_樹插入元素的過程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)索引項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于______個(gè)，則必須把它分裂為_______個(gè)結(jié)點(diǎn)。 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_________,整個(gè)堆排序過程的時(shí)間復(fù)雜度為________________。 假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J））），則樹中所含的結(jié)點(diǎn)數(shù)為_________個(gè)，樹的深度為_________,樹的度為________, 結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為________,孩子結(jié)點(diǎn)為_______________ 。 在一個(gè)索引文件的索引表中，每個(gè)索引項(xiàng)包含對應(yīng)記錄的_________和___________兩項(xiàng)數(shù)據(jù)。 用具有n個(gè)元素的一維數(shù)組存儲一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的___________，該循環(huán)隊(duì)列的最大長度為__________。 74 25 一種抽象數(shù)據(jù)類型包括______________和_____________兩個(gè)部分。 由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ） A 24 B 71 C 48 D 53二、 二、 s→link =p。 s→link=q。A n B n/2 C (n+1)/2 D (n1)/2 在一個(gè)單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個(gè)s所指的結(jié)點(diǎn),則執(zhí)行( )。 數(shù)據(jù)結(jié)構(gòu)（十七）一、 一、 }//while, 出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù) return i。 編寫算法（8分）int CountX(LNode* HL,ElemType x) { int i=0。圖12四、 四、 O(log2n) O(nlog2n)12. 12.數(shù)據(jù)結(jié)構(gòu)16參考答案一、 一、} else if(itemBSTdata) return Find(______________,item)。 算法填空（共8分）二叉搜索樹的查找——遞歸算法:bool Find(BTreeNode* BST,ElemTypeamp。 39。Lnext){ q=L；L=L－next；p=L； S1： while(p－next) p=p－next； S2： p－next=q；q－next=NULL； } return L； } 請回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設(shè)鏈表表示的線性表為（a1,a2, …,an）,寫出算法執(zhí)行后的返回值所表示的線性表。四、 四、 已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為： V={1,2,3,4,5,6,7}。 圖10請畫出圖10的鄰接矩陣和鄰接表。40next357204三、 三、 后綴算式9 2 3 + 10 2 / 的值為__________。 假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J）），則樹中所含的結(jié)點(diǎn)數(shù)為__________個(gè)，樹的深度為___________，樹的度為_________。 一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為________。 通常從四個(gè)方面評價(jià)算法的質(zhì)量：_________、_________、_________和_________。 樹最適合用來表示( )。 A．688 B．678 C．692 D．6965. 5.數(shù)據(jù)結(jié)構(gòu)（十六）一、delete p。exit(1)。五、 五、 （1