2020年数据结构考研复习指导PDF电子书下载

第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