數(shù)據(jù)結(jié)構(gòu)習(xí)題解答與實(shí)驗(yàn)指導(dǎo)（第四版）

第一篇 學(xué)習(xí)提要和習(xí)題解答 第 1 章 緒論............. 1 1.1 重點(diǎn)難點(diǎn)指導(dǎo).. 1 1.1.1 相關(guān)術(shù)語(yǔ)............................................ 1 1.1.2 算法的描述和分析 ............................. 3 1.2 典型例題解析.. 4 1.2.1 選擇題.. 4 1.2.2 判斷題.. 5 1.2.3 填空題.. 6 1.2.4 簡(jiǎn)答題.. 6 1.3 主教材習(xí)題解答 ............................................ 7 1.3.1 選擇題.. 7 1.3.2 簡(jiǎn)答題.. 8 第 2 章 線(xiàn)性表....... 12 2.1 重點(diǎn)難點(diǎn)指導(dǎo).12 2.1.1 相關(guān)術(shù)語(yǔ)...........................................12 2.1.2 線(xiàn)性表的順序存儲(chǔ) ............................13 2.1.3 鏈表 ....15 2.1.4 線(xiàn)性表的基本運(yùn)算 ............................17 2.2 典型例題解析.20 2.2.1 選擇題.20 2.2.2 判斷題.23 2.2.3 簡(jiǎn)答題.24 2.2.4 算法設(shè)計(jì)題 .......................................26 2.3 主教材習(xí)題解答 ...........................................29 2.3.1 選擇題.29 2.3.2 判斷題.30 2.3.3 算法設(shè)計(jì)題 .......................................31 第 3章 棧和隊(duì)列.... 36 3.1 重點(diǎn)難點(diǎn)指導(dǎo).36 3.1.1 相關(guān)術(shù)語(yǔ)...........................................36 3.1.2 棧........37 3.1.3 隊(duì)列 ....39 3.1.4 棧的應(yīng)用...........................................43 3.1.5 隊(duì)列的應(yīng)用 .......................................43 3.2 典型例題解析.44 3.2.1 選擇題.44 3.2.2 填空題.45 3.2.3 簡(jiǎn)答題.46 3.2.4 算法設(shè)計(jì)題 .......................................47 3.3 主教材習(xí)題解答 ...........................................52 3.3.1 選擇題.52 3.3.2 簡(jiǎn)答題.53 3.3.3 算法設(shè)計(jì)題 .......................................53 第 4 章 串.............. 56 4.1 重點(diǎn)難點(diǎn)指導(dǎo).56 4.1.1 相關(guān)術(shù)語(yǔ)...........................................56 4.1.2 串的基本運(yùn)算....................................57 4.1.3 串的存儲(chǔ)結(jié)構(gòu)....................................57 4.1.4 字符串匹配算法實(shí)現(xiàn).........................59 4.2 典型例題解析.60 4.2.1 選擇題.60 4.2.2 填空題.60 4.2.3 基本運(yùn)算題 .......................................61 4.2.4 算法設(shè)計(jì)題 .......................................61 4.3 主教材習(xí)題解答 ...........................................64 4.3.1 選擇題.64 4.3.2 算法設(shè)計(jì)題 .......................................65 第 5章 數(shù)組和廣義表........................................... 67 5.1 重點(diǎn)難點(diǎn)指導(dǎo).67 5.1.1 相關(guān)術(shù)語(yǔ)...........................................67 5.1.2 多維數(shù)組...........................................68 5.1.3 特殊矩陣...........................................68 5.1.4 稀疏矩陣...........................................70 5.1.5 廣義表.72 5.2 典型例題解析.74 5.2.1 選擇題.74 5.2.2 填空題.75 5.2.3 簡(jiǎn)答題.76 5.2.4 算法設(shè)計(jì)題 .......................................77 5.3 主教材習(xí)題解答 ...........................................81 5.3.1 選擇題.81 5.3.2 簡(jiǎn)答題.82 5.3.3 算法設(shè)計(jì)題 .......................................84 第 6 章 二叉樹(shù)....... 87 6.1 重點(diǎn)難點(diǎn)指導(dǎo).87 6.1.1 相關(guān)術(shù)語(yǔ)...........................................87 6.1.2 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) ............................89 6.1.3 二叉樹(shù)的遍歷運(yùn)算 ............................90 6.1.4 二叉樹(shù)的基本應(yīng)用 ............................91 6.2 典型例題解析.92 6.2.1 選擇題.92 6.2.2 判斷題.93 6.2.3 填空題.94 6.2.4 簡(jiǎn)答題.95 6.2.5 算法設(shè)計(jì)題 .......................................97 6.3 主教材習(xí)題解答 .........................................101 6.3.1 選擇題.............................................101 6.3.2 簡(jiǎn)答題.............................................103 6.3.3 算法設(shè)計(jì)題 .....................................104 第 7章 樹(shù)與森林.. 108 7.1 重點(diǎn)難點(diǎn)指導(dǎo).............................................108 7.1.1 相關(guān)術(shù)語(yǔ).........................................108 7.1.2 樹(shù)的存儲(chǔ)結(jié)構(gòu)..................................109 7.1.3 樹(shù)的基本運(yùn)算..................................110 7.1.4 樹(shù)、森林和二叉樹(shù)的相互轉(zhuǎn)換........ 111 7.2 典型例題解析............................................. 111 7.2.1 選擇題............................................. 111 7.2.2 判斷題.............................................112 7.2.3 填空題.............................................113 7.2.4 簡(jiǎn)答題.............................................113 7.2.5 算法設(shè)計(jì)題 .....................................114 7.3 主教材習(xí)題解答 .........................................116 7.3.1 選擇題.............................................116 7.3.2 簡(jiǎn)答題.............................................116 7.3.3 算法設(shè)計(jì)題 .....................................118 第 8 章 圖............ 120 8.1 重點(diǎn)難點(diǎn)指導(dǎo).............................................120 8.1.1 相關(guān)術(shù)語(yǔ).........................................120 8.1.2 圖的基本操作..................................122 8.1.3 圖的存儲(chǔ)表示..................................122 8.1.4 圖的遍歷.........................................125 8.1.5 圖的應(yīng)用.........................................126 8.2 典型例題解析.............................................129 8.2.1 選擇題.............................................129 8.2.2 判斷題.............................................130 8.2.3 填空題.............................................132 8.2.4 簡(jiǎn)答題.............................................132 8.2.5 算法設(shè)計(jì)題 .....................................134 8.3 主教材習(xí)題解答 .........................................139 8.3.1 選擇題.............................................139 8.3.2 簡(jiǎn)答題.............................................141 8.3.3 算法設(shè)計(jì).........................................144 第 9 章 查找......... 151 9.1 重點(diǎn)難點(diǎn)指導(dǎo).............................................151 9.1.1 相關(guān)術(shù)語(yǔ).........................................151 9.1.2 線(xiàn)性表查找 .....................................152 9.1.3 排序樹(shù)上的查找..............................153 9.1.4 哈希表.............................................156 9.2 典型例題解析.............................................157 9.2.1 選擇題.............................................157 9.2.2 判斷題.............................................158 9.2.3 簡(jiǎn)答題.............................................159 9.2.4 算法設(shè)計(jì)題 .....................................160 9.3 主教材習(xí)題解答 .........................................165 9.3.1 選擇題.............................................165 9.3.2 簡(jiǎn)答題.............................................166 9.3.3 算法設(shè)計(jì)題 .....................................169 第 10 章 排序....... 173 10.1 重點(diǎn)難點(diǎn)指導(dǎo)...........................................173 10.1.1 相關(guān)術(shù)語(yǔ) .......................................173 10.1.2 插入排序 .......................................174 10.1.3 交換排序 .......................................175 10.1.4 選擇排序 .......................................176 10.1.5 歸并排序 .......................................177 10.1.6 基數(shù)排序 .......................................177 10.1.7 外部排序 .......................................178 10.2 典型例題解析...........................................178 10.2.1 選擇題...........................................178 10.2.2 判斷題...........................................179 10.2.3 填空題...........................................180 10.2.4 算法設(shè)計(jì)題 ...................................182 10.3 主教材習(xí)題解答 .......................................185 10.3.1 選擇題...........................................185 10.3.2 簡(jiǎn)答題...........................................187 10.3.3 算法設(shè)計(jì)題 ...................................190 第二篇 課程實(shí)驗(yàn)與設(shè)計(jì)指導(dǎo) 第 11章 課程實(shí)驗(yàn)與設(shè)計(jì)的一般步驟.................. 194 11.1 概述............194 11.2 課程實(shí)驗(yàn)與設(shè)計(jì)步驟 ................................195 第 12章 課程實(shí)驗(yàn)與設(shè)計(jì)安排............................ 197 12.1 線(xiàn)性結(jié)構(gòu) ....197 實(shí)驗(yàn) 1 約瑟夫環(huán)問(wèn)題...............................197 實(shí)驗(yàn) 2 一元多項(xiàng)式運(yùn)算 ...........................199 實(shí)驗(yàn) 3 模擬停車(chē)場(chǎng)管理 ...........................201 12.2 樹(shù)形結(jié)構(gòu) ....206 實(shí)驗(yàn) 1 哈夫曼編碼/譯碼器 ......................206 實(shí)驗(yàn) 2 二叉樹(shù)遍歷...................................208 12.3 圖形結(jié)構(gòu) ....208 實(shí)驗(yàn) 1 校園導(dǎo)游程序...............................208 實(shí)驗(yàn) 2 教學(xué)計(jì)劃編排...............................210 12.4 查找和排序.210 實(shí)驗(yàn) 1 職工信息檢索系統(tǒng)........................210 實(shí)驗(yàn) 2 各種內(nèi)部排序的性能比較.............211 參考文獻(xiàn) ...........................212