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

第七章第七章 集合與搜索樹(shù)集合與搜索樹(shù) 1 第 137 頁(yè) 第 5 建立 37 45 91 25 14 76 56 65 為輸入時(shí)的二叉搜索樹(shù) 再?gòu)脑摌?shù)上依此刪除 76 45 則樹(shù)形分別如何 2 第137頁(yè) 第 6 試寫(xiě)一個(gè)判定任意給定的二叉樹(shù)是否二叉搜索樹(shù)算法 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頁(yè) 第 8 以下列序列為輸入 從空樹(shù)開(kāi)始構(gòu)造AVL搜索樹(shù) 1 A Z B Y C X 2 A V L T R E I S O K 4 第137頁(yè) 第 12 5階B 樹(shù)的高度為2時(shí) 樹(shù)中元素個(gè)數(shù)最少為多少 答 5 5 第137頁(yè) 第 13 題 從空樹(shù)開(kāi)始 以關(guān)鍵字序列 a g f b k d h m j e s i r x 建立 1 4階B 樹(shù) 課后答案網(wǎng) 2 5階B 樹(shù) 1 4階B 樹(shù) 2 5階B 樹(shù) 6 第137頁(yè) 第 14 題 從上題的4階B 樹(shù)上依次刪除a e f h 第八章第八章 散列與跳表散列與跳表 1 第154頁(yè) 第 3 題 設(shè)散列表ht 11 散列函數(shù)h key key 11 采用線性探查法解決沖突 試用關(guān)鍵字值序 列 70 25 80 35 60 45 50 55 建立散列表 2 第154頁(yè) 第 6 題 給出用拉鏈方法解決沖突的散列表搜索操作的C 函數(shù)實(shí)現(xiàn) template bool LinkedHashTable Search const K 課后答案網(wǎng) HNode p ht i 元素結(jié)點(diǎn)類(lèi)型 Hnode while p if p element k return true p p nextsynonym return false 3 第154頁(yè) 第 3 題 設(shè)散列表ht 11 散列函數(shù)h key key 11 采用二次探查法解決沖突 試用關(guān)鍵字值 序列 70 25 80 35 60 45 50 55 建立散列表 4 第154頁(yè) 第 4 題 對(duì)上題的例子 若采用雙散列法 試以散列函數(shù)h1 key key 11 h2 key key 9 1 建立散列表 第九章第九章 圖圖 1 第188頁(yè) 第 1 題 對(duì)下面的有向圖求 1 每個(gè)頂點(diǎn)的入度和出度 2 強(qiáng)連通分量 3 鄰接矩陣 課后答案網(wǎng) 2 第188頁(yè) 第 2 題 當(dāng)以邊 1 0 1 3 2 1 2 4 3 2 3 4 4 0 4 1 4 5 5 0 的次序從只有 6 個(gè)頂點(diǎn)沒(méi)有邊的圖開(kāi)始 通過(guò)依此插入這些邊 建立鄰接表結(jié)構(gòu) 畫(huà)出該鄰接表 3 第188頁(yè) 第 4 題 已知有向圖的鄰接表 試寫(xiě)出計(jì)算各頂點(diǎn)的入度的算法 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頁(yè) 第 6 題 在題 2 所建立的鄰接表上進(jìn)行以頂點(diǎn) 2 為起始頂點(diǎn)的深度優(yōu)先搜索和廣度優(yōu)先搜索 分別 畫(huà)出遍歷所得到的深度優(yōu)先搜索和廣度優(yōu)先搜索的生成森林 或生成樹(shù) 課后答案網(wǎng) 5 第188頁(yè) 第 8 題 分別設(shè)計(jì)算法 在鄰接矩陣上實(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頁(yè) 第 10 題 設(shè)某項(xiàng)工程由圖題 9 3 所示的工序組成 若各工序以流水方式進(jìn)行 即串行進(jìn)行 1 畫(huà)出給工程的 AOV 網(wǎng)絡(luò) 2 給出該工程的全部合理的工程流程 課后答案網(wǎng) 7 第188頁(yè) 第 11 題 設(shè)有邊集合 0 1 1 2 4 1 4 5 5 3 2 3 1 求此圖的所有可能的拓?fù)湫蛄?2 若以此順序通過(guò)加入邊的方式建立鄰接表 則在該鄰接表上執(zhí)行拓?fù)渑判蛩惴?TopoSort 則得到的拓?fù)湫蛄惺瞧渲心囊环N 8 第188頁(yè) 第 13 題 使用普里姆算法以 1 為源點(diǎn) 畫(huà)出圖題 9 5 的無(wú)向圖的最小代價(jià)生成樹(shù) 9 第188頁(yè) 第 16 題 用迪杰斯特拉算法求圖題9 6的有向圖中以頂點(diǎn)A為源點(diǎn)的單源最短路徑 寫(xiě)出一維數(shù)組d 和 path在執(zhí)行該算法的過(guò)程中各步的狀態(tài) 課后答案網(wǎng) 10 第188頁(yè) 第 17 題 用弗洛伊德算法求圖題9 6的有向圖的所有頂點(diǎn)之間的最短路徑 寫(xiě)出二維數(shù)組d和path在 執(zhí)行該算法的過(guò)程中各步的狀態(tài) dpath 1 初始狀態(tài) 源點(diǎn)終點(diǎn)最短路徑路徑長(zhǎng)度 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頁(yè) 第 1 題 元素序列 61 87 12 03 08 70 97 75 53 26 按下列算法排序 給出各趟排序結(jié)果 1 簡(jiǎn)單選擇排序 2 冒泡排序 3 直接插入排序 4 快速排序 5 兩路合并排序 1 簡(jiǎn)單選擇排序 初始序列 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頁(yè) 第 3 題 在帶表頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)簡(jiǎ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é)點(diǎn)的單鏈表存儲(chǔ) void SingleList DirInsert Node head q p1 p2 if first link 課后答案網(wǎng) head first link link head 是待插入元素的鏈表頭 first link link NULL first 是只有一個(gè)節(jié)點(diǎn)的有序鏈表 while head q head head head link 從待插入鏈中取下一個(gè)節(jié)點(diǎn) p1 first p2 first link p1 是 p2 的直接前驅(qū)節(jié)點(diǎn) 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 證明 快速排序算法的基本思想時(shí) 每次把一個(gè)集合劃分成大于和小于某個(gè)基準(zhǔn)值的兩個(gè)子集 合 最壞情況是兩個(gè)子集合中總有一個(gè)是空集合 即將一個(gè)集合分成了一個(gè)子集合和一個(gè)作為 基準(zhǔn)值的元素 即最壞情況下劃分的自己和比原集合的元素只少一個(gè) 故要?jiǎng)澐?n 1 次才能使 得子集合中的元素少于 2 而每次劃分子集合都要掃描整個(gè)集合 所以時(shí)間復(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 找負(fù)數(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