數(shù)據(jù)結(jié)構(gòu)原理與分析0134318日下復(fù)習(xí)資料(編輯修改稿)
2025-05-14 00:37 本頁面
【文章內(nèi)容簡(jiǎn)介】 03∧02∧1Head答：無向圖的鄰接表為：36. 已知一個(gè)圖如下所示，若從頂點(diǎn)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．把下圖中的二叉樹轉(zhuǎn)化成森林。1268473512684735答案：（43,36,56,6,64,32,8,41），按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹，并求其平均查找長(zhǎng)度。解答：根據(jù)給定表（43,36,56,6,64,32,8,41），構(gòu)造的二叉查找樹如下圖；其平均查找長(zhǎng)度為：23/8。6483241656364342．將下圖中的二叉樹，轉(zhuǎn)換成相應(yīng)的森林。ABCHFDJEILKGNM答：森林轉(zhuǎn)化成的二叉樹如下圖。JCHEKFILNMABDG 43. 知二叉樹按中根遍歷所得到的結(jié)點(diǎn)序列為DCBGEAHFIJK， 按后根遍歷所得到的結(jié)點(diǎn)序列為DCEGBFHKJIA，畫出該樹形結(jié)構(gòu)，并按中根遍歷序列進(jìn)行線索化。答：HKFGCIBAJED，試分別寫出先根遍歷、中根遍歷該樹所得到的先根序列、中根序列。GFEDCBALKJIH答：先根遍歷的結(jié)點(diǎn)序列：ABCEIFJDGHKL，中遍歷的結(jié)點(diǎn)序列：EICFJBGDKHLA46．把下圖中的二叉樹轉(zhuǎn)化成森林。1268473512684735答：二叉樹轉(zhuǎn)化成的森林如下圖。(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. 設(shè)記錄的關(guān)鍵字集合key={51,28,38,86,70,90,7,30,40,25}，試寫出對(duì)key進(jìn)行漸減增量排序（增量d = 5，3，1）時(shí)，各趟排序結(jié)束后的結(jié)果。解答：各趟排序結(jié)束后的結(jié)果。初始狀態(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），分別指出其前序、中序遍歷的結(jié)點(diǎn)序列。ABHGFEDCIJ答：它的前序序列為：ABCDEFGHIJ,它的中序序列為：CDBAFGEIHJ。，對(duì)應(yīng)的關(guān)鍵詞為：{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ù)元素在表中的次序構(gòu)造一棵二叉查找樹。答：.二叉排序樹如下。4095639862373：ABCDEF,中序序列為：CBAEDF,試畫出該二叉樹。答：二叉樹如下圖。ACDFEB（40,36,56,6,64,73,8,23），按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹，并求其平均查找長(zhǎng)度。答：二叉查找樹如下，平均查找長(zhǎng)度為3。4036566486237353．根據(jù)下圖給出的二叉樹，求出先序、中序遍歷的結(jié)點(diǎn)序列。acedfb答：先序遍歷為：abdcef 中序遍歷為：dbaefc 54. 一組記錄的關(guān)鍵字為（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次交換：把下列森林轉(zhuǎn)化為一棵二叉樹。12684735答： 森林轉(zhuǎn)化成的二叉樹如下圖。12684735,5,9,20,6,31,24，對(duì)該數(shù)據(jù)序列進(jìn)行排序，試寫出冒泡排序每趟的結(jié)果。答： 初始鍵值序列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ù)元素在表中的次序構(gòu)造一棵二叉查找樹，并求其平均查找長(zhǎng)度。答：構(gòu)造的二叉查找樹如下圖，其平均查找長(zhǎng)度為11/4。4035556496417758. 對(duì)于下圖所示的二叉樹，試分別寫出先根遍歷、中根遍歷和后根遍歷該樹所得到的先根序列、中根序列和后根序列。GFEDCBALKJIH解答：先根遍歷的結(jié)點(diǎn)序列：ABCEIFJDGHKL中遍歷的結(jié)點(diǎn)序列：EICFJBGDKHLA后根遍歷的結(jié)點(diǎn)序列：IEJFCGKLHDBA,5,9,20,6,31,24，對(duì)該數(shù)據(jù)序列進(jìn)行排序，試寫出歸并排序每趟的結(jié)果。解答：初始鍵值序列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)中，用二分法查找關(guān)鍵詞36，進(jìn)行多少次比較后查找成功？寫出查找過程。 解答：經(jīng)過4次比較查找成功。查找過程如下：5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58j=11m=6i=1（A）第1次與25進(jìn)行比較j=115, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58i=7m=9（B）第2次與45進(jìn)行比較5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58j=8i=7m=7（C）第3次與30進(jìn)行比較i=85, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58j=8m=8（D）第4次與36進(jìn)行比較(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
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1