第1章 数据结构绪论 1
1.1数据结构的概念及分类 1
1.1.1知识点复习 1
1.1.2疑难点辨析 2
1.1.3选择题解析 3
1.1.4应用题选讲 5
1.2算法和算法设计 5
1.2.1知识点复习 5
1.2.2疑难点辨析 7
1.2.3选择题解析 8
1.2.4应用题选讲 8
1.3算法分析 11
1.3.1知识点复习 11
1.3.2疑难点辨析 12
1.3.3选择题解析 13
1.3.4应用题选讲 15
第2章 线性表 19
2.1线性表 19
2.1.1知识点复习 19
2.1.2疑难点辨析 20
2.1.3选择题解析 20
2.1.4应用题选讲 20
2.2顺序表 21
2.2.1知识点复习 21
2.2.2疑难点辨析 23
2.2.3选择题解析 24
2.2.4应用题选讲 25
2.3单链表 30
2.3.1知识点复习 30
2.3.2疑难点辨析 33
2.3.3选择题解析 33
2.3.4应用题选讲 36
2.4线性链表的其他变形 42
2.4.1知识点复习 42
2.4.2疑难点辨析 44
2.4.3选择题解析 45
2.4.4应用题选讲 47
2.5线性表的应用 50
2.5.1知识点复习 50
2.5.2疑难点辨析 53
2.5.3选择题解析 53
2.5.4应用题选讲 54
第3章 栈和队列 65
3.1栈 65
3.1.1知识点复习 65
3.1.2疑难点辨析 68
3.1.3选择题解析 69
3.1.4应用题选讲 71
3.2队列 76
3.2.1知识点复习 76
3.2.2疑难点辨析 79
3.2.3选择题解析 80
3.2.4应用题选讲 82
3.3栈的应用 85
3.3.1知识点复习 85
3.3.2疑难点辨析 86
3.3.3选择题解析 87
3.3.4应用题选讲 89
3.4队列的应用 95
3.4.1知识点复习 95
3.4.2疑难点辨析 96
3.4.3选择题解析 96
3.4.4应用题选讲 97
3.5在算法设计中使用递归 97
3.5.1知识点复习 97
3.5.2疑难点辨析 98
3.5.3选择题解析 99
3.5.4应用题选讲 101
3.6双端队列 108
3.6.1知识点复习 108
3.6.2疑难点辨析 109
3.6.3选择题解析 109
3.6.4应用题选讲 110
第4章 多维数组、字符串与广义表 114
4.1数组 114
4.1.1知识点复习 114
4.1.2疑难点辨析 116
4.1.3选择题解析 116
4.1.4应用题选讲 117
4.2特殊矩阵的压缩存储 126
4.2.1知识点复习 126
4.2.2疑难点辨析 127
4.2.3选择题解析 128
4.2.4应用题选讲 129
4.3稀疏矩阵 134
4.3.1知识点复习 134
4.3.2疑难点辨析 135
4.3.3选择题解析 136
4.3.4应用题选讲 136
4.4字符串 140
4.4.1知识点复习 140
4.4.2疑难点辨析 143
4.4.3选择题解析 145
4.4.4应用题选讲 146
4.5广义表 155
4.5.1知识点复习 155
4.5.2疑难点辨析 156
4.5.3选择题解析 157
4.5.4应用题选讲 163
第5章 树与二叉树 163
5.1树的基本概念 163
5.1.1知识点复习 163
5.1.2疑难点辨析 164
5.1.3选择题解析 164
5.1.4应用题选讲 165
5.2二叉树的定义和特性 165
5.2.1知识点复习 165
5.2.2疑难点辨析 166
5.2.3选择题解析 167
5.2.4应用题选讲 169
5.3二叉树的存储 171
5.3.1知识点复习 171
5.3.2疑难点辨析 172
5.3.3选择题解析 172
5.3.4应用题选讲 173
5.4二叉树的遍历 173
5.4.1知识点复习 173
5.4.2疑难点辨析 175
5.4.3选择题解析 179
5.4.4应用题选讲 184
5.5线索二叉树 195
5.5.1知识点复习 195
5.5.2疑难点辨析 197
5.5.3选择题解析 198
5.5.4应用题选讲 199
5.6树与森林 205
5.6.1知识点复习 205
5.6.2疑难点辨析 209
5.6.3选择题解析 212
5.6.4应用题选讲 213
第6章 树与二叉树的应用 222
6.1二叉查找树 222
6.1.1知识点复习 222
6.1.2疑难点辨析 225
6.1.3选择题解析 226
6.1.4应用题选讲 228
6.2 AVL树 237
6.2.1知识点复习 237
6.2.2疑难点辨析 242
6.2.3选择题解析 244
6.2.4应用题选讲 245
6.3 Huffman树与H uffman编码 249
6.3.1知识点复习 249
6.3.2疑难点辨析 251
6.3.3选择题解析 252
6.3.4应用题选讲 253
6.4堆 258
6.4.1知识点复习 258
6.4.2疑难点辨析 260
6.4.3选择题解析 261
6.4.4应用题选讲 263
6.5并查集 267
6.5.1知识点复习 267
6.5.2疑难点辨析 269
6.5.3选择题解析 269
6.5.4应用题选讲 270
第7章图 273
7.1图的基本概念 273
7.1.1知识点复习 273
7.1.2疑难点辨析 274
7.1.3选择题解析 274
7.1.4应用题选讲 276
7.2图的存储及基本操作 278
7.2.1知识点复习 278
7.2.2疑难点辨析 280
7.2.3选择题解析 281
7.2.4应用题选讲 284
7.3图的遍历 289
7.3.1知识点复习 289
7.3.2疑难点辨析 291
7.3.3选择题解析 293
7.3.4应用题选讲 296
7.4最小生成树 305
7.4.1知识点复习 305
7.4.2疑难点辨析 306
7.4.3选择题解析 307
7.4.4应用题选讲 310
7.5最短路径 316
7.5.1知识点复习 316
7.5.2疑难点辨析 317
7.5.3选择题解析 318
7.5.4应用题选讲 320
7.6拓扑排序和关键路径 328
7.6.1知识点复习 328
7.6.2疑难点辨析 331
7.6.3选择题解析 332
7.6.4应用题选讲 335
第8章 查找 341
8.1查找的基本概念 341
8.1.1知识点复习 341
8.1.2疑难点辨析 342
8.1.3选择题解析 342
8.1.4应用题选讲 343
8.2顺序查找法 344
8.2.1知识点复习 344
8.2.2疑难点辨析 346
8.2.3选择题解析 347
8.2.4应用题选讲 349
8.3折半查找法 352
8.3.1知识点复习 352
8.3.2疑难点辨析 354
8.3.3选择题解析 354
8.3.4应用题选讲 357
8.4 B树 361
8.4.1知识点复习 361
8.4.2疑难点辨析 367
8.4.3选择题解析 368
8.4.4应用题选讲 371
8.5散列表及其查找 377
8.5.1知识点复习 377
8.5.2疑难点辨析 382
8.5.3选择题解析 385
8.5.4应用题选讲 388
第9章 排序 396
9.1排序的基本概念 396
9.1.1知识点复习 396
9.1.2疑难点辨析 397
9.1.3选择题解析 398
9.1.4应用题选讲 398
9.2插入排序 399
9.2.1知识点复习 399
9.2.2疑难点辨析 401
9.2.3选择题解析 404
9.2.4应用题选讲 406
9.3交换排序 410
9.3.1知识点复习 410
9.3.2疑难点辨析 413
9.3.3选择题解析 414
9.3.4应用题选讲 416
9.4选择排序 427
9.4.1知识点复习 427
9.4.2疑难点辨析 432
9.4.3选择题解析 433
9.4.4应用题选讲 435
9.5归并排序 439
9.5.1知识点复习 439
9.5.2疑难点辨析 440
9.5.3选择题解析 442
9.5.4应用题选讲 442
9.6基数排序 448
9.6.1知识点复习 448
9.6.2疑难点辨析 451
9.6.3选择题解析 452
9.6.4应用题选讲 452
9.7各种内部排序方法的比较和选择 453
9.7.1知识点复习 453
9.7.2疑难点辨析 454
9.7.3选择题解析 455
9.7.4应用题选讲 457
第10章 外排序 463
10.1主存储器和外存储器 463
10.1.1知识点复习 463
10.1.2疑难点辨析 464
10.1.3选择题解析 464
10.2磁盘文件的外排序过程 465
10.2.1知识点复习 465
10.2.2疑难点辨析 468
10.2.3选择题解析 470
10.2.4应用题选讲 471
10.3 m路平衡归并 473
10.3.1知识点复习 473
10.3.2疑难点辨析 473
10.3.3选择题解析 474
10.3.4应用题选讲 475
10.4初始归并段的生成 479
10.4.1知识点复习 479
10.4.2疑难点辨析 480
10.4.3选择题解析 481
10.4.4应用题选讲 482
10.5最佳归并树 485
10.5.1知识点复习 485
10.5.2疑难点辨析 486
10.5.3选择题解析 486
10.5.4应用题选讲 487
10.6并行操作的缓冲区处理 488
10.6.1知识点复习 488
10.6.2疑难点辨析 489
10.6.3选择题解析 490
10.6.4应用题选讲 490
10.7磁带归并排序 491
10.7.1知识点复习 491
10.7.2疑难点辨析 491
10.7.3选择题解析 492
10.7.4应用题选讲 493
附录 全国硕士研究生入学考试“数据结构”真题分析 494
参考书目 515