數(shù)據(jù)結(jié)構(gòu) 用c++語言描述 習(xí)題答案02.pdf

第七章第七章 集合與搜索樹集合與搜索樹 1 第 137 頁 第 5 建立 37 45 91 25 14 76 56 65 為輸入時的二叉搜索樹 再從該樹上依此刪除 76 45 則樹形分別如何 2 第137頁 第 6 試寫一個判定任意給定的二叉樹是否二叉搜索樹算法 int k bool fail false template void BTree IsBiTree BTNode p int if kelement k p element elsefail true IsBiTree p rchild k fail 3 第137頁 第 8 以下列序列為輸入 從空樹開始構(gòu)造AVL搜索樹 1 A Z B Y C X 2 A V L T R E I S O K 4 第137頁 第 12 5階B 樹的高度為2時 樹中元素個數(shù)最少為多少 答 5 5 第137頁 第 13 題 從空樹開始 以關(guān)鍵字序列 a g f b k d h m j e s i r x 建立 1 4階B 樹 課后答案網(wǎng) 2 5階B 樹 1 4階B 樹 2 5階B 樹 6 第137頁 第 14 題 從上題的4階B 樹上依次刪除a e f h 第八章第八章 散列與跳表散列與跳表 1 第154頁 第 3 題 設(shè)散列表ht 11 散列函數(shù)h key key 11 采用線性探查法解決沖突 試用關(guān)鍵字值序 列 70 25 80 35 60 45 50 55 建立散列表 2 第154頁 第 6 題 給出用拉鏈方法解決沖突的散列表搜索操作的C 函數(shù)實現(xiàn) template bool LinkedHashTable Search const K 課后答案網(wǎng) HNode p ht i 元素結(jié)點類型 Hnode while p if p element k return true p p nextsynonym return false 3 第154頁 第 3 題 設(shè)散列表ht 11 散列函數(shù)h key key 11 采用二次探查法解決沖突 試用關(guān)鍵字值 序列 70 25 80 35 60 45 50 55 建立散列表 4 第154頁 第 4 題 對上題的例子 若采用雙散列法 試以散列函數(shù)h1 key key 11 h2 key key 9 1 建立散列表 第九章第九章 圖圖 1 第188頁 第 1 題 對下面的有向圖求 1 每個頂點的入度和出度 2 強連通分量 3 鄰接矩陣 課后答案網(wǎng) 2 第188頁 第 2 題 當以邊 1 0 1 3 2 1 2 4 3 2 3 4 4 0 4 1 4 5 5 0 的次序從只有 6 個頂點沒有邊的圖開始 通過依此插入這些邊 建立鄰接表結(jié)構(gòu) 畫出該鄰接表 3 第188頁 第 4 題 已知有向圖的鄰接表 試寫出計算各頂點的入度的算法 template void LinkedGraph Degree int d new int n int i ENode p for i 0 i n i d i 0 for i 0 iadjvex p p nextarc for i 0 i n i cout d i d i 4 第188頁 第 6 題 在題 2 所建立的鄰接表上進行以頂點 2 為起始頂點的深度優(yōu)先搜索和廣度優(yōu)先搜索 分別 畫出遍歷所得到的深度優(yōu)先搜索和廣度優(yōu)先搜索的生成森林 或生成樹 課后答案網(wǎng) 5 第188頁 第 8 題 分別設(shè)計算法 在鄰接矩陣上實現(xiàn)有向圖的深度優(yōu)先搜索 template void MGraph DFS int v bool visited visited v true cout v for int j 0 j n j if a v j 6 第188頁 第 10 題 設(shè)某項工程由圖題 9 3 所示的工序組成 若各工序以流水方式進行 即串行進行 1 畫出給工程的 AOV 網(wǎng)絡(luò) 2 給出該工程的全部合理的工程流程 課后答案網(wǎng) 7 第188頁 第 11 題 設(shè)有邊集合 0 1 1 2 4 1 4 5 5 3 2 3 1 求此圖的所有可能的拓撲序列 2 若以此順序通過加入邊的方式建立鄰接表 則在該鄰接表上執(zhí)行拓撲排序算法 TopoSort 則得到的拓撲序列是其中哪一種 8 第188頁 第 13 題 使用普里姆算法以 1 為源點 畫出圖題 9 5 的無向圖的最小代價生成樹 9 第188頁 第 16 題 用迪杰斯特拉算法求圖題9 6的有向圖中以頂點A為源點的單源最短路徑 寫出一維數(shù)組d 和 path在執(zhí)行該算法的過程中各步的狀態(tài) 課后答案網(wǎng) 10 第188頁 第 17 題 用弗洛伊德算法求圖題9 6的有向圖的所有頂點之間的最短路徑 寫出二維數(shù)組d和path在 執(zhí)行該算法的過程中各步的狀態(tài) dpath 1 初始狀態(tài) 源點終點最短路徑路徑長度 AB A B 3 C A B C 4 D A D 4 E A B E 4 G Sd A path A d B path B d C path C d D path D d E path E d G path G A0 13 A 14 A5 A 1 B0 13 A4 B4 A4 B 1 C0 13 A4 B4 A4 B 1 D0 13 A4 B4 A4 B 1 E0 13 A4 B4 A4 B 1 1A 1AA 1 1 1B 1B 1 1 1 1C 1 1 1D 1 1 1 1 1 1 1E 1 1 1 1 1GG 1 03 45 01 1 02 3 0 20 320 課后答案網(wǎng) dApathA dBpathB dCpathC 1A 1AA 1 1 1B 1B 1 1 1 1C 1 1 1D 1 1 1 1 1 1 1E 1 1 1 1 1GG 1 1ABAB 1 1 1B 1B 1 1 1 1C 1 1 1DB 1B 1 1 1 1E 1 1 1 1 1GG 1 1ABAB 1 1 1BCB 1 1 1 1C 1 1 1DB 1B 1 1 1 1E 1 1 03 54 01 1 02 3 0 20 320 03444 01 1 02 3404 20 320 03444 0131 02 3404 20 320 課后答案網(wǎng) dDpathD dE dGpathE pathG 21 第200頁 第 1 題 元素序列 61 87 12 03 08 70 97 75 53 26 按下列算法排序 給出各趟排序結(jié)果 1 簡單選擇排序 2 冒泡排序 3 直接插入排序 4 快速排序 5 兩路合并排序 1 簡單選擇排序 初始序列 61871203087097755326 第 1 趟 03 871261087097755326 第 2 趟 0308 1261877097755326 第 3 趟 030812 61877097755326 第 4 趟 03081226 877097755361 第 5 趟 0308122653 7097758761 第 6 趟 030812265361 97758770 1 1 1GG 1 1ABAB 1 1 1BCB 1 1D 1CB 1 1DB 1B 1 1DBE 1 1 1DBGG 1 1ABAB 1 1 1BCB 1 1D 1CB 1 1DB 1B 1 1DBE 1 1 1DBGG 1 03444 0131 5026 3404 5620 67320 03444 0131 5026 3404 5620 67320 課后答案網(wǎng) 第 7 趟 03081226536170 758797 第 8 趟 0308122653617075 8797 第 9 趟 030812265361707587 97 2 冒泡排序 初始序列 61871203087097755326 第 1 趟61120308708775532697 第 2 趟12030861707553268797 第 3 趟03081261705326758797 第 4 趟03081261532670758797 第 5 趟03081253266170758797 第 6 趟03081226536170758797 第 7 趟03081226536170758797 第 8 趟03081226536170758797 第 9 趟03081226536170758797 3 直接插入排序 初始序列 61 871203087097755326 第 1 趟 6187 1203087097755326 第 2 趟 126187 03087097755326 第 3 趟 03126187 087097755326 第 4 趟 0308126187 7097755326 第 5 趟 030812617087 97755326 第 6 趟 03081261708797 755326 第 7 趟 0308126170758797 5326 第 8 趟 030812536170758797 26 第 9 趟 03081226536170758797 22 第200頁 第 3 題 在帶表頭結(jié)點的單鏈表上實現(xiàn)簡單選擇排序 template void SingleList select sort Node p r small p first link if p for p link p p link for small p r p link r r r link if small data r data small r if small p swap p data small data 直接插入排序 template 用帶表頭節(jié)點的單鏈表存儲 void SingleList DirInsert Node head q p1 p2 if first link 課后答案網(wǎng) head first link link head 是待插入元素的鏈表頭 first link link NULL first 是只有一個節(jié)點的有序鏈表 while head q head head head link 從待插入鏈中取下一個節(jié)點 p1 first p2 first link p1 是 p2 的直接前驅(qū)節(jié)點 while p2p2 p2 link if p2 q 插入在 p1 和 p2 之間 q link p2 p1 link q else q 插入在 p2 之后 即有序鏈的最后 q link NULL p1 link q 10 4 template void sort T a int n int i j k 0 m 1 s t T x while k m s k for i k ia i 1 x a i a i a i 1 a i 1 x s i m s t m for j m j k j 從下向上冒泡 if a j a j 1 x a j a j a j 1 a j 1 x t j k t 10 6 證明 快速排序算法的基本思想時 每次把一個集合劃分成大于和小于某個基準值的兩個子集 合 最壞情況是兩個子集合中總有一個是空集合 即將一個集合分成了一個子集合和一個作為 基準值的元素 即最壞情況下劃分的自己和比原集合的元素只少一個 故要劃分 n 1 次才能使 得子集合中的元素少于 2 而每次劃分子集合都要掃描整個集合 所以時間復(fù)雜度是 O n2 10 7 template 方法一 void sort T a int n int i 0 j n 1 T x a 0 while i 0 找負數(shù) 課后答案網(wǎng) if j i a i a j while a i 0 找正數(shù)if i j a j a i a j x 10 8 template void Merge T A T Temp int i1 int j1 int i2 int j2 int else if A i1 A i2 Temp k A i1 Merge A Temp i1 1 j1 i2 j2 k else Temp k A