正版新书]计算机考研专业课:数据结构一本通(考点详解+习题全解)

第 0 章 导学 · 1. 0.1 学习目标 1. 0.2 大纲 1. 0.3 本书知识结构 1. 第 1 章 绪论 · 3. 1.1 本章导学 3. 1.1.1 知识结构 · 3. 1.1.2 命题特点 · 4. 1.2 基本概念 4. 1.3 数据结构 5. 1.3.1 定义 · 5. 1.3.2 逻辑结构 · 6. 1.3.3 存储结构 · 8. 1.4 算法 10. 1.4.1 定义 · 10. 1.4.2 特征 · 10. 1.4.3 算法和程序 11. 1.4.4 评价 · 11. 1.5 本章小结 13. 第 2 章 线性表 · 14. 2.1 本章导学 14. 2.1.1 知识结构 · 14. 2.1.2 命题特点 · 15. 2.2 线性表概述 15. 2.2.1 定义 · 15. 2.2.2 基本操作 · 16. 2.3 线性表存储结构及操作 实现 · 17. 2.3.1 顺序表 · 17. 2.3.2 链表 · 23. 2.4 栈 56. 2.4.1 定义 · 56. 2.4.2 存储结构 · 57. 2.4.3 应用 · 60. 2.5 队列 62. 2.5.1 定义 · 62. 2.5.2 存储结构 · 63. 2.5.3 应用 · 66. 2.6 特殊矩阵 67. 2.6.1 对称矩阵 · 68. 2.6.2 三角矩阵 · 69. 2.6.3 对角矩阵 · 71. 2.6.4 稀疏矩阵 · 72. 2.7 串 76. 2.7.1 基本概念 · 76. 2.7.2 存储结构 · 76. 2.7.3 基本操作 · 76. 2.7.4 模式匹配 · 79. 2.8 综合应用 85. 2.8.1 两栈共享空间 · 85. 2.8.2 多项式求和 · 87. 2.9 本章小结 89. 第 3 章 树和二叉树 90. 3.1 本章导学 90. 3.1.1 知识结构 · 90. 3.1.2 命题特点 · 90. 3.2 树 91. 3.2.1 定义 · 91. 3.2.2 树的表示形式 · 92. 3.2.3 树的相关概念 · 93. 3.2.4 树的抽象数据类型 · 93. 3.2.5 存储结构 · 94. 3.2.6 树的遍历 · 96. 3.3 二叉树 97. 3.3.1 定义 · 98. 3.3.2 性质 · 99. 3.3.3 存储结构 · 100. 3.3.4 二叉树的遍历 · 103. 3.3.5 线索二叉树 · 112.计算机考研专业课——数据结构一本通（考点详解＋习题全解） IV 3.3.6 二叉排序树 114. 3.3.7 平衡二叉树 119. 3.3.8 哈夫曼树 · 122. 3.4 树和森林 125. 3.4.1 树与二叉树的转化 125. 3.4.2 森林与二叉树的 转化 · 126. 3.4.3 树的遍历 · 126. 3.4.4 森林的遍历 127. 3.5 本章小结 128. 第 4 章 图 129. 4.1 本章导学 129. 4.1.1 知识结构 · 129. 4.1.2 命题特点 · 130. 4.2 基本概念 130. 4.3 存储结构 132. 4.3.1 邻接矩阵 · 132. 4.3.2 邻接表 · 136. 4.3.3 十字链表 · 139. 4.4 遍历 142. 4.4.1 深度优先搜索 142. 4.4.2 广度优先搜索 145. 4.5 最小生成树 150. 4.5.1 普里姆算法 150. 4.5.2 克鲁斯卡尔算法 152. 4.6 最短路径 155. 4.6.1 单源最短路径 155. 4.6.2 任意两个顶点之间的 最短路径 · 158. 4.7 关键路径 160. 4.7.1 关键路径概述 161. 4.7.2 关键路径求解 161. 4.8 拓扑排序 163. 4.9 公共子表达式 164. 4.10 本章小结 164. 第 5 章 查找 · 165. 5.1 本章导学 165. 5.1.1 知识结构 · 165. 5.1.2 命题特点 · 165. 5.2 基本概念 166. 5.3 顺序表的静态查找 · 166. 5.3.1 顺序查找 · 166. 5.3.2 折半查找 · 167. 5.3.3 分块查找 · 169. 5.4 二叉排序树 · 170. 5.5 二叉平衡树 · 171. 5.6 B 树类 · 171. 5.6.1 B 树 · 171. 5.6.2 B+树 176. 5.7 散列表 177. 5.7.1 基本概念 · 177. 5.7.2 散列函数构造 · 178. 5.7.3 处理冲突方法 · 179. 5.7.4 填充因子 · 181. 5.8 本章小结 181. 第 6 章 排序 · 182. 6.1 本章导读 182. 6.1.1 知识结构 · 182. 6.1.2 命题规律 · 183. 6.2 基本概念 183. 6.3 插入排序 184. 6.3.1 直接插入排序 · 184. 6.3.2 折半插入排序 · 185. 6.3.3 希尔排序 · 186. 6.4 交换排序 188. 6.4.1 冒泡排序 · 188. 6.4.2 快速排序 · 189. 6.5 选择排序 191. 6.5.1 直接选择排序 · 191. 6.5.2 堆选择排序 · 192. 6.6 归并排序 194. 6.7 基数排序 196. 6.8 内部排序方法比较 · 199. 6.9 外部排序 200. 6.10 本章小结 201. 主要算法总结 · 202. 参考书目 203

“数据结构”是全国硕士研究生入学考试科目——计算机学科专业综合的考查科目之 一，是研究“非数值计算的程序设计问题中计算机的操作对象及其关系和操作等的学科”， 是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，同时也是计算机科学 与技术专业的专业基础课。课程内容不仅是一般程序设计（特别是非数值计算的程序设 计）的基础，同时也是设计和实现编译程序、操作系统、数据库系统及其他系统程序和 应用程序的重要基础。 “数据结构”主要研究数据及数据之间的关系、数据的存储以及具有关系的数据集上 的操作。主要涉及三种关系：一对一关系（线性表）、一对多关系（树和二叉树）、多对 多关系（图）。常见操作有创建、查找、删除、排序等。考生在复习时首先应熟练掌握理 论内容，单纯的刷题无法解决基础内容的欠缺问题，也无法应对考场上不曾谋面的试题。 然后再通过练习题及真题检验对课程知识的掌握程度。 本书分为两部分，部分是考点详解，第二部分为习题精讲。考点详解部分首先 是导学部分，主要介绍本科目考试大纲和本书各章节知识点分布。第 1 章为绪论，主要 介绍数据结构和算法的基本概念。第 2 章为线性表，主要介绍线性结构的基本概念、算 法及实现，以及特殊线性表（栈和队列）、特殊矩阵等。第 3 章介绍树及二叉树的相关概 念及算法。第 4 章介绍图的定义、算法。第 5 章介绍各种查找算法及其分析。第 6 章介 绍排序算法及其特点。习题精讲部分主要收集全国硕士研究生入学考试计算机学科专业 基础综合（专业课代码 408，本书文中统称 408）及各高校科研院所的历年真题，通过真 题使考生零距离感受考题形式和答题思路，通过做题，熟练、灵活地掌握理论内容，进 一步加强分析题目、求解问题的思维训练。 本书的知识详解部分尽可能多地给出基本操作的伪码实现、注释、算法的流程分析 等，帮助考生深入理解算法本质，为解题打下坚实基础。此外，我们还为本书配备了丰 富的视频讲解，扫描每章和图书封底的二维码即可观看。 备考过程中，考生需注意复习方法。首先应全局把握本书内容，熟悉本书特点、重 点章节等。然后进行系统学习和总结，熟练掌握各知识点。最后通过历年真题分析巩固 各知识点并了解各知识点的出题方式和考查频率。 备考过程漫长辛苦，考生应注意学习方法，提高复习效率，不搞消耗战，不做过多 重复题，以不变应万变。毫无头绪时不妨归本还原，静下心来认真研究基本概念和算法， 或许能打开解题思路。 编者 2019 年 1 月

知识点全面，代码简洁清晰，注释明了易懂，试题覆盖范围广泛，讲解清晰，易于掌握