【文章內容簡介】 03∧02∧1Head答：無向圖的鄰接表為：36. 已知一個圖如下所示，若從頂點0出發(fā)求出其廣度優(yōu)先搜索序列。03425167解答： 廣度優(yōu)先搜索序列：01234567(52, 56, 26, 12, 69, 85, 33, 48, 70)，給出快速排序的過程。解答：解：52, 56, 26, 12, 69, 85, 33, 48, 70第一趟排序 33, 48, 26, 12, 52, 85, 69, 56, 70第二趟排序 26, 12, 33, 48, 52, 69, 56, 70, 85第三趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85第四趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85第五趟排序 12, 26, 33, 48, 52, 56, 70, 69, 8538．下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩(wěn)定的？起泡排序, 直接插入排序，歸并排序是穩(wěn)定的。39．已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J中序序列：C, B, A, F, E, D, I, H, J, G答：后序序列為：C, B, F, E, I, J, H, G, D, A40．把下圖中的二叉樹轉化成森林。1268473512684735答案：（43,36,56,6,64,32,8,41），按數(shù)據(jù)元素在表中的次序構造一棵二叉查找樹，并求其平均查找長度。解答：根據(jù)給定表（43,36,56,6,64,32,8,41），構造的二叉查找樹如下圖；其平均查找長度為：23/8。6483241656364342．將下圖中的二叉樹，轉換成相應的森林。ABCHFDJEILKGNM答：森林轉化成的二叉樹如下圖。JCHEKFILNMABDG 43. 知二叉樹按中根遍歷所得到的結點序列為DCBGEAHFIJK， 按后根遍歷所得到的結點序列為DCEGBFHKJIA，畫出該樹形結構，并按中根遍歷序列進行線索化。答：HKFGCIBAJED，試分別寫出先根遍歷、中根遍歷該樹所得到的先根序列、中根序列。GFEDCBALKJIH答：先根遍歷的結點序列：ABCEIFJDGHKL，中遍歷的結點序列：EICFJBGDKHLA46．把下圖中的二叉樹轉化成森林。1268473512684735答：二叉樹轉化成的森林如下圖。(52, 56, 26, 12, 69, 85, 33, 48, 70)，給出快速排序的過程。解答：解：52, 56, 26, 12, 69, 85, 33, 48, 70第一趟排序 33, 48, 26, 12, 52, 85, 69, 56, 70第二趟排序 26, 12, 33, 48, 52, 69, 56, 70, 85第三趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85第四趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85第五趟排序 12, 26, 33, 48, 52, 56, 70, 69, 8548. 設記錄的關鍵字集合key={51,28,38,86,70,90,7,30,40,25}，試寫出對key進行漸減增量排序（增量d = 5，3，1）時，各趟排序結束后的結果。解答：各趟排序結束后的結果。初始狀態(tài)：51 28 38 86 70 90 7 30 40 25第一趟排序(d=5): 51 7 30 40 25 90 28 38 86 70第二趟排序(d=3): 28 7 30 40 25 86 51 38 90 70第三趟排序(d=1): 7 25 28 30 38 40 51 70 86 90），分別指出其前序、中序遍歷的結點序列。ABHGFEDCIJ答：它的前序序列為：ABCDEFGHIJ,它的中序序列為：CDBAFGEIHJ。，對應的關鍵詞為：{25,84,21,47,15,27,68,35,20}寫出快速排序的第一趟排序過程圖示。答：初始鍵值序列[25 84 21 47 15 27 68 35 20] 第一次交換 [25 84 21 47 15 27 68 35 20] ↑i=2 ↑j=9第二次交換 [25 20 21 47 15 27 68 35 84]i ↑ ↑j掃描交叉 [25 20 21 15 47 27 68 35 84]j ↑ ↑iRm與Rj互換 [25 20 21 15 47 27 68 35 84] Rm ↑ j↑分劃表 [15 20 21] 25 [47 27 68 35 84]（40,9,56,6,39,73,8,23），按數(shù)據(jù)元素在表中的次序構造一棵二叉查找樹。答：.二叉排序樹如下。4095639862373：ABCDEF,中序序列為：CBAEDF,試畫出該二叉樹。答：二叉樹如下圖。ACDFEB（40,36,56,6,64,73,8,23），按數(shù)據(jù)元素在表中的次序構造一棵二叉查找樹，并求其平均查找長度。答：二叉查找樹如下，平均查找長度為3。4036566486237353．根據(jù)下圖給出的二叉樹，求出先序、中序遍歷的結點序列。acedfb答：先序遍歷為：abdcef 中序遍歷為：dbaefc 54. 一組記錄的關鍵字為（50，79，8，56，32，41，85），給出利用重建堆方法建立的初始堆（堆頂最大），并給出堆排序的過程。 答：1） 建立的初始堆為: 85，79，50，56，32，41，82 ）堆排序的過程如下：8579328504156（C）第2次交換8541328505679（B）第1次交換8413256507985（A）初始建堆8579565041832（f）第5次交換8579565032841（e）第4次交換8579568324150（D）第3次交換8579565041328（g）第6次交換：把下列森林轉化為一棵二叉樹。12684735答： 森林轉化成的二叉樹如下圖。12684735,5,9,20,6,31,24，對該數(shù)據(jù)序列進行排序，試寫出冒泡排序每趟的結果。答： 初始鍵值序列12 5 9 20 6 31 24 第一趟排序 [5 9 12 6 20 24] 31 第二趟排序 [5 9 6 12 20] 24 31第三趟排序 [5 9 6 12] 20 24 31第四趟排序 5 6 9 12 20 24 31（40,36,55,6,64,77,9,41），按數(shù)據(jù)元素在表中的次序構造一棵二叉查找樹，并求其平均查找長度。答：構造的二叉查找樹如下圖，其平均查找長度為11/4。4035556496417758. 對于下圖所示的二叉樹，試分別寫出先根遍歷、中根遍歷和后根遍歷該樹所得到的先根序列、中根序列和后根序列。GFEDCBALKJIH解答：先根遍歷的結點序列：ABCEIFJDGHKL中遍歷的結點序列：EICFJBGDKHLA后根遍歷的結點序列：IEJFCGKLHDBA,5,9,20,6,31,24，對該數(shù)據(jù)序列進行排序，試寫出歸并排序每趟的結果。解答：初始鍵值序列12 5 9 20 6 31 24第一趟排序 [5 12] [9 20] [6 31] [24] 第二趟排序 [5 9 12 20] [6 24 31] 第三趟排序 5 6 9 12 20 24 31（）(5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58)中，用二分法查找關鍵詞36，進行多少次比較后查找成功？寫出查找過程。 解答：經過4次比較查找成功。查找過程如下：5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58j=11m=6i=1（A）第1次與25進行比較j=115, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58i=7m=9（B）第2次與45進行比較5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58j=8i=7m=7（C）第3次與30進行比較i=85, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58j=8m=8（D）第4次與36進行比較(52, 56, 26, 12, 69, 85, 33, 48, 70)，給出快速排序的過程。 解答：52, 56, 26, 12, 69, 85, 33, 48, 70第一趟排序 33, 48, 26, 12, 52, 85, 69, 56, 70第二趟排序 26, 12, 33, 48, 52