【正文】 ______、___________________、_______________________和__________________________。10. 10. 向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度___________。11. 11. 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為________，整個堆排序過程的時間復(fù)雜度為________。12. 12. 在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。三、 三、 運(yùn)算題（每題 6 分，共24分）1. 1. 在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A [0].next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next35720412. 2. 圖10請畫出圖10的鄰接矩陣和鄰接表。3. 3. 已知一個圖的頂點(diǎn)集V和邊集E分別為： V={1,2,3,4,5,6,7}。 E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}。 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4. 4. 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化。四、 四、 閱讀算法（每題7分，共14分）1. 1. LinkList mynote(LinkList L) {//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(Lamp。amp。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í)行后的返回值所表示的線性表。2. 2. void ABC(BTNode * BT){ if BT { ABC (BTleft)。 ABC (BTright)。 coutBTdata39。 39。 } } 該算法的功能是：五、 五、 算法填空（共8分）二叉搜索樹的查找——遞歸算法:bool Find(BTreeNode* BST,ElemTypeamp。 item){ if (BST==NULL) return false。 //查找失敗 else { if (item==BSTdata){ item=BSTdata。//查找成功 return ___________。} else if(itemBSTdata) return Find(______________,item)。 else return Find(_______________,item)。 }//if}六、 六、 編寫算法（共8分）統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。 int CountX(LNode* HL,ElemType x)數(shù)據(jù)結(jié)構(gòu)16參考答案一、 一、 單選題（每題2分，共20分） 二、 二、 填空題（每空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. 增加111. 11. O(log2n) O(nlog2n)12. 12. 歸并三、 三、 運(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圖12四、 四、 閱讀算法（每題7分，共14分）1. 1. （1）查詢鏈表的尾結(jié)點(diǎn)（2）將第一個結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) （3）返回的線性表為（a2,a3,…,an,a1） 2. 2. 遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄?。五?五、 算法填空（每空2分，共8 分）true BSTleft BSTright 六、 六、 編寫算法（8分）int CountX(LNode* HL,ElemType x) { int i=0。 LNode* p=HL。//i為計(jì)數(shù)器 while(p!=NULL) { if (Pdata==x) i++。 p=pnext。 }//while, 出循環(huán)時i中的值即為x結(jié)點(diǎn)個數(shù) return i。 }//CountX 數(shù)據(jù)結(jié)構(gòu)（十七）一、 一、 單選題（每小題2分，共8分） 在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為 ( )。A n B n/2 C (n+1)/2 D (n1)/2 在一個單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個s所指的結(jié)點(diǎn),則執(zhí)行( )。 A s→link=p→link。 p→link=s。 B p→link=s。 s→link=q。 C p→link=s→link。 s→link=p。 D q →link=s。 s→link =p。 棧的插入和刪除操作在（ ）進(jìn)行。A 棧頂 B 棧底 C 任意位置 D 指定位置 由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ） A 24 B 71 C 48 D 53二、 二、 填空題（每空1分，共32分） 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為__________、 ___________ 、________和________四種。 一種抽象數(shù)據(jù)類型包括______________和_____________兩個部分。 在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[o].next，則該線性表為_________________________________________________。 a 0 1 2 3 4 5 6 7 8 60 56 42 38 74 25 4 3 7 6 2 0 1datanext 在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為________________和____________________。 用具有n個元素的一維數(shù)組存儲一個循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的___________，該循環(huán)隊(duì)列的最大長度為__________。 當(dāng)堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用———————表示；當(dāng)堆棧采用鏈接存儲結(jié)構(gòu)時，棧頂元素的值可用_______________表示。 一棵高度為5的二叉樹中最少含有_________個結(jié)點(diǎn)，最多含有________個結(jié)點(diǎn)；一棵高度為5的理想平衡樹中，最少含有_________個結(jié)點(diǎn)，最多含有_________個結(jié)點(diǎn)。 在圖的鄰接表中，每個結(jié)點(diǎn)被稱為____________，通常它包含三個域：一是_____________；二是___________；三是_____________。 在一個索引文件的索引表中，每個索引項(xiàng)包含對應(yīng)記錄的_________和___________兩項(xiàng)數(shù)據(jù)。 假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J））），則樹中所含的結(jié)點(diǎn)數(shù)為_________個，樹的深度為_________,樹的度為________, 結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為________,孩子結(jié)點(diǎn)為_______________ 。1 1 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為_________,整個堆排序過程的時間復(fù)雜度為________________。1 1 在對m階的B_樹插入元素的過程中，每向一個結(jié)點(diǎn)插入一個索引項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于______個，則必須把它分裂為_______個結(jié)點(diǎn)。三、 三、 運(yùn)算題（每小題6分，共24分） 已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進(jìn)行快速排序的每一次劃分結(jié)果。 一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT[0..12]，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長度。 已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。 已知一個圖的頂點(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)它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。假定每個頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時鄰接表表示時 四、 四、 閱讀算法，回答問題（每小題8分，共16分）假定從鍵盤上輸入一批整數(shù)，依次為：78 63 45 30 91 34 –1，請寫出輸出結(jié)果。 include include consst