2020年数据结构考研复习指导

第1章 绪论/1
1.1 数据结构的基本概念/1
1.1.1 基本概念和术语/1
1.1.2 数据结构三要素/2
1.1.3 本节试题精选/3
1.1.4 答案与解析/4
1.2 算法和算法评价/5
1.2.1 算法的基本概念/5
1.2.2 算法效率的度量/5
1.2.3 本节试题精选/6
1.2.4 答案与解析/9
归纳总结/10
思维拓展/11
第2章 线性表/12
2.1 线性表的定义和基本操作/12
2.1.1 线性表的定义/12
2.1.2 线性表的基本操作/13
2.1.3 本节试题精选/13
2.1.4 答案与解析/13
2.2 线性表的顺序表示/14
2.2.1 顺序表的定义/14
2.2.2 顺序表上基本操作的实现/15
2.2.3 本节试题精选/17
2.2.4 答案与解析/19
2.3 线性表的链式表示/27
2.3.1 单链表的定义/27
2.3.2 单链表上基本操作的实现/28
2.3.3 双链表/31
2.3.4 循环链表/33
2.3.5 静态链表/33
2.3.6 顺序表和链表的比较/34
2.3.7 本节试题精选/35
2.3.8 答案与解析/41
归纳总结/58
思维拓展/58
第3章 栈和队列/59
3.1 栈/59
3.1.1 栈的基本概念/59
3.1.2 栈的顺序存储结构/60
3.1.3 栈的链式存储结构/62
3.1.4 本节试题精选/62
3.1.5 答案与解析/66
3.2 队列/73
3.2.1 队列的基本概念/73
3.2.2 队列的顺序存储结构/73
3.2.3 队列的链式存储结构/75
3.2.4 双端队列/77
3.2.5 本节试题精选/78
3.2.6 答案与解析/81
3.3 栈和队列的应用/85
3.3.1 栈在括号匹配中的应用/85
3.3.2 栈在表达式求值中的应用/85
3.3.3 栈在递归中的应用/86
3.3.4 队列在层次遍历中的应用/87
3.3.5 队列在计算机系统中的应用/88
3.3.6 本节试题精选/88
3.3.7 答案与解析/90
3.4 特殊矩阵的压缩存储/96
3.4.1 数组的定义/96
3.4.2 数组的存储结构/96
3.4.3 矩阵的压缩存储/97
3.4.4 稀疏矩阵/99
3.4.5 本节试题精选/99
3.4.6 答案与解析/100
归纳总结/102
思维拓展/102
第4章 树与二叉树/103
4.1 树的基本概念/103
4.1.1 树的定义/103
4.1.2 基本术语/104
4.1.3 树的性质/105
4.1.4 本节试题精选/105
4.1.5 答案与解析/106
4.2 二叉树的概念/107
4.2.1 二叉树的定义及其
主要特性/107
4.2.2 二叉树的存储结构/109
4.2.3 本节试题精选/110
4.2.4 答案与解析/113
4.3 二叉树的遍历和线索二叉树/117
4.3.1 二叉树的遍历/117
4.3.2 线索二叉树/120
4.3.3 本节试题精选/122
4.3.4 答案与解析/128
4.4 树、森林/145
4.4.1 树的存储结构/145
4.4.2 树、森林与二叉树的转换/147
4.4.3 树和森林的遍历/148
4.4.4 树的应用—并查集/148
4.4.5 本节试题精选/150
4.4.6 答案与解析/152
4.5 树与二叉树的应用/157
4.5.1 二叉排序树/157
4.5.2 平衡二叉树/160
4.5.3 哈夫曼树和哈夫曼编码/162
4.5.4 本节试题精选/164
4.5.5 答案与解析/169
归纳总结/179
思维拓展/180
第5章 图/181
5.1 图的基本概念/181
5.1.1 图的定义/181
5.1.2 本节试题精选/184
5.1.3 答案与解析/187
5.2 图的存储及基本操作/189
5.2.1 邻接矩阵法/189
5.2.2 邻接表法/190
5.2.3 十字链表/192
5.2.4 邻接多重表/192
5.2.5 图的基本操作/193
5.2.6 本节试题精选/194
5.2.7 答案与解析/196
5.3 图的遍历/199
5.3.1 广度优先搜索/200
5.3.2 深度优先搜索/201
5.3.3 图的遍历与图的连通性/203
5.3.4 本节试题精选/203
5.3.5 答案与解析/206
5.4 图的应用/211
5.4.1 *小生成树/211
5.4.2 *短路径/213
5.4.3 拓扑排序/216
5.4.4 关键路径/217
5.4.5 本节试题精选/219
5.4.6 答案与解析/226
归纳总结/237
思维拓展/238
第6章 查找/239
6.1 查找的基本概念/239
6.2 顺序查找和折半查找/240
6.2.1 顺序查找/240
6.2.2 折半查找/242
6.2.3 分块查找/243
6.2.4 本节试题精选/244
6.2.5 答案与解析/248
6.3 B树和B 树/253
6.3.1 B树及其基本操作/253
6.3.2 B 树的基本概念/256
6.3.3 本节试题精选/257
6.3.4 答案与解析/259
6.4 散列表/263
6.4.1 散列表的基本概念/263
6.4.2 散列函数的构造方法/264
6.4.3 处理冲突的方法/265
6.4.4 散列查找及性能分析/266
6.4.5 本节试题精选/266
6.4.6 答案与解析/269
6.5 串/274
6.5.1 串的定义/274
6.5.2 串的存储结构/275
6.5.3 串的基本操作/276
6.5.4 串的模式匹配/276
6.5.5 改进的模式匹配算法——KMP算法/277
6.5.6 本节试题精选/280
6.5.7 答案与解析/281
归纳总结/289
思维拓展/289
第7章 排序/290
7.1 排序的基本概念/291
7.1.1 排序的定义/291
7.1.2 本节试题精选/291
7.1.3 答案与解析/292
7.2 插入排序/292
7.2.1 直接插入排序/292
7.2.2 折半插入排序/293
7.2.3 希尔排序/294
7.2.4 本节试题精选/295
7.2.5 答案与解析/297
7.3 交换排序/299
7.3.1 冒泡排序/299
7.3.2 快速排序/300
7.3.3 本节试题精选/301
7.3.4 答案与解析/304
7.4 选择排序/309
7.4.1 简单选择排序/309
7.4.2 堆排序/310
7.4.3 本节试题精选/312
7.4.4 答案与解析/315
7.5 归并排序和基数排序/318
7.5.1 归并排序/318
7.5.2 基数排序/319
7.5.3 本节试题精选/320
7.5.4 答案与解析/322
7.6 各种内部排序算法的比较及应用/324
7.6.1 内部排序算法的比较/324
7.6.2 内部排序算法的应用/325
7.6.3 本节试题精选/326
7.6.4 答案与解析/327
7.7 外部排序/330
7.7.1 外部排序的基本概念/330
7.7.2 外部排序的方法/330
7.7.3 多路平衡归并与败者树/331
7.7.4 置换-选择排序（生成初始归并段）/332
7.7.5 *佳归并树/333
7.7.6 本节试题精选/334
7.7.7 答案与解析/336
归纳总结/338
思维拓展/339
参考文献/340