前言第1章 引論1 1.1 數據結構課程的地位和考試要求1 1.1.1 數據結構課程的地位1 1.1.2 考試要求1 1.1.3 考查的知識點1 1.2 數據結構和算法的預備知識3 1.2.1 數據結構的主要概念3 1.2.2 算法及算法分析4 1.2.3 選擇填空題解析6 1.2.4 綜閤應用題選講8 1.3 使用C/C++的幾個規則11 1.3.1 算法結構11 1.3.2 函數參數11 1.3.3 條件運算11 1.3.4 動態存儲分配12 1.3.5 標準輸入/輸齣12 1.3.6 指針12第2章 綫性錶13 2.1 綫性錶的定義和基本操作13 2.1.1 知識點復習13 2.1.2 關鍵問題點撥13 2.1.3 選擇填空題解析14 2.2 綫性錶的存儲錶示14 2.2.1 知識點復習14 2.2.2 關鍵問題點撥17 2.2.3 選擇填空題解析17 2.2.4 綜閤應用題選講18 2.3 綫性錶的插入和刪除運算19 2.3.1 知識點復習19 2.3.2 關鍵問題點撥21 2.3.3 選擇填空題解析21 2.3.4 綜閤應用題選講24 2.4 綫性錶的應用33第3章 棧、隊列和多維數組39 3.1 棧和隊列的基本概念39 3.1.1 知識點復習39 3.1.2 關鍵問題點撥40 3.1.3 選擇填空題解析40 3.1.4 綜閤應用題選講42 3.2 棧的存儲結構44 3.2.1 知識點復習44 3.2.2 關鍵問題點撥45 3.2.3 選擇填空題解析46 3.2.4 綜閤應用題選講47 3.3 隊列的存儲結構49 3.3.1 知識點復習49 3.3.2 關鍵問題點撥51 3.3.3 選擇填空題解析52 3.3.4 綜閤應用題選講53 3.4 棧和隊列的應用58 3.4.1 知識點復習58 3.4.2 關鍵問題點撥60 3.4.3 選擇填空題解析61 3.4.4 綜閤應用題選講61 3.5 數組與特殊矩陣的壓縮存儲72 3.5.1 知識點復習72 3.5.2 關鍵問題點撥75 3.5.3 選擇填空題解析77 3.5.4 綜閤應用題選講78第4章 樹與二叉樹87 4.1 樹的基本概念87 4.1.1 知識點復習87 4.1.2 關鍵問題點撥88 4.1.3 選擇填空題解析88 4.1.4 綜閤應用題選講88 4.2 二叉樹的定義和特性88 4.2.1 知識點復習88 4.2.2 關鍵問題點撥90 4.2.3 選擇填空題解析90 4.2.4 綜閤應用題選講91 4.3 二叉樹的存儲和遍曆93 4.3.1 知識點復習93 4.3.2 關鍵問題點撥95 4.3.3 選擇填空題解析96 4.3.4 綜閤應用題選講101 4.4 綫索二叉樹110 4.4.1 知識點復習110 4.4.2 關鍵問題點撥112 4.4.3 選擇填空題解析112 4.4.4 綜閤應用題選講113 4.5 樹與森林118 4.5.1 知識點復習118 4.5.2 關鍵問題點撥123 4.5.3 選擇填空題解析124 4.5.4 綜閤應用題選講125 4.6 二叉排序樹131 4.6.1 知識點復習131 4.6.2 關鍵問題點撥134 4.6.3 選擇填空題解析135 4.6.4 綜閤應用題選講136 4.7 平衡二叉樹144 4.7.1 知識點復習144 4.7.2 關鍵問題點撥147 4.7.3 選擇填空題解析148 4.7.4 綜閤應用題選講149 4.8 Huffman樹與Huffman編碼151 4.8.1 知識點復習 151 4.8.2 關鍵問題點撥153 4.8.3 選擇填空題解析153 4.8.4 綜閤應用題選講155 4.9 堆157 4.9.1 知識點復習157 4.9.2 關鍵問題點撥160 4.9.3 選擇填空題解析161 4.9.4 綜閤應用題選講162第5章 圖164 5.1 圖的基本概念164 5.1.1 知識點復習164 5.1.2 關鍵問題點撥165 5.1.3 選擇填空題解析165 5.1.4 綜閤應用題選講166 5.2 圖的存儲及基本操作168 5.2.1 知識點復習168 5.2.2 關鍵問題點撥170 5.2.3 選擇填空題解析171 5.2.4 綜閤應用題選講173 5.3 圖的遍曆177 5.3.1 知識點復習177 5.3.2 關鍵問題點撥179 5.3.3 選擇填空題解析180 5.3.4 綜閤應用題選講182 5.4 最小（代價）生成樹189 5.4.1 知識點復習190 5.4.2 關鍵問題點撥192 5.4.3 選擇填空題解析193 5.4.4 綜閤應用題選講195 5.5 最短路徑200 5.5.1 知識點復習200 5.5.2 關鍵問題點撥202 5.5.3 選擇填空題解析202 5.5.4 綜閤應用題選講204 5.6 拓撲排序211 5.6.1 知識點復習211 5.6.2 關鍵問題點撥212 5.6.3 選擇填空題解析213 5.6.4 綜閤應用題選講214 5.7 關鍵路徑217 5.7.1 知識點復習217 5.7.2 關鍵問題點撥218 5.7.3 選擇填空題解析218 5.7.4 綜閤應用題選講219第6章 查找222 6.1 查找的基本概念222 6.1.1 知識點復習222 6.1.2 關鍵問題點撥222 6.2 順序查找法223 6.2.1 知識點復習223 6.2.2 關鍵問題點撥225 6.2.3 選擇填空題解析226 6.2.4 綜閤應用題選講227 6.3 摺半查找法230 6.3.1 知識點復習230 6.3.2 關鍵問題點撥231 6.3.3 選擇填空題解析231 6.3.4 綜閤應用題選講233 6.4 B樹與B+樹237 6.4.1 知識點復習237 6.4.2 關鍵問題點撥243 6.4.3 選擇填空題解析244 6.4.4 綜閤應用題選講247 6.5 散列錶及其查找252 6.5.1 知識點復習252 6.5.2 關鍵問題點撥257 6.5.3 選擇填空題解析259 6.5.4 綜閤應用題選講261第7章 排序269 7.1 排序的基本概念269 7.1.1 知識點復習269 7.1.2 關鍵問題點撥269 7.2 四種簡單的排序方法270 7.2.1 知識點復習270 7.2.2 關鍵問題點撥272 7.2.3 選擇填空題解析274 7.2.4 綜閤應用題選講276 7.3 希爾排序281 7.3.1 知識點復習281 7.3.2 關鍵問題點撥282 7.3.3 選擇填空題解析283 7.3.4 綜閤應用題選講283 7.4 快速排序285 7.4.1 知識點復習285 7.4.2 關鍵問題點撥286 7.4.3 選擇填空題解析287 7.4.4 綜閤應用題選講288 7.5 堆排序294 7.5.1 知識點復習294 7.5.2 關鍵問題點撥295 7.5.3 選擇填空題解析296 7.5.4 綜閤應用題選講297 7.6 二路歸並排序299 7.6.1 知識點復習299 7.6.2 關鍵問題點撥301 7.6.3 選擇填空題解析302 7.6.4 綜閤應用題選講303 7.7 基數排序307 7.7.1 知識點復習307 7.7.2 關鍵問題點撥310 7.7.3 選擇填空題解析310 7.7.4 綜閤應用題選講310 7.8 各種內排序方法的比較和選擇311 7.8.1 知識點復習311 7.8.2 關鍵問題點撥312 7.8.3 選擇填空題解析313 7.8.4 綜閤應用題選講314第8章 試題分析與備考指南319 8.1 全國碩士研究生入學考試真題分析319 8.1.1 2009年聯考試題數據結構部分319 8.1.2 2010年聯考試題數據結構部分325 8.2 考試復習建議331 8.2.1 試題難度分析331 8.2.2 風險和機遇332 8.2.3 主要知識點的難度級彆和重點級彆332 8.2.4 復習建議342 8.2.5 考試指導343 8.2.6 結束語345模擬試題及參考答案346參考文獻356
· · · · · · (收起)