目 录 

第 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