本书是为了配合高等学校数据结构课程的学习与考试(课程学习或考研)而编写的辅导用书。全书共分11章，每章包括5个板块：本章知识结构图，疑难解惑，典型例题与考研题分析，重要习题精选精解，两级训练题。本书从指导课程学习、考试的角度，通过对重难点及易混淆的知识点的详细解释、典型例题的解答与总结，帮助读者掌握数据结构的概念和算法思想，提高运用这些知识解决实际问题的能力，旨在读者对数据结构真正做到融会贯通、并为掌握程序设计和软件开发方法奠定扎实的理论基础。 本书系统全面，重点突出，难点解析清楚，注重解题思路及技巧的培养，具有较强的实用性，非常适合高等院校计算机专业的学生配合数据结构课程的学习使用，同时也适用于报考计算机专业研究生进行专业课的复习，还可作为广大相关领域的技术人员和读者自学的辅导书。

目 录
第1章 绪论 1
1.1 本章知识结构图 1
1.2 疑难解惑 2
1.2.1 怎样理解数据结构在计算机 课程中的核心地位 2
1.2.2 怎样理解数据的逻辑 结构和存储结构 2
1.2.3 为什么要用数据类型来 描述数据结构 2
1.2.4 算法和程序的区别 3
1.2.5 如何计算算法的时间复杂度 3
1.3 典型例题与考研题分析 4
1.3.1 典型例题分析 4
1.3.2 考研题分析 4
1.4 重要习题精选精解 6
1.5 两级训练题 7
1.5.1 达标训练题 7
1.5.2 考研挑战题 8
第2章 线性表 9
2.1 本章知识结构图 9
2.2 疑难解惑 9
2.2.1 如何理解线性表数据结构 9
2.2.2 线性表的顺序存储结构和 链式存储结构的区别 10
2.2.3 带头结点的单链表和不带 头结点的单链表的区别 10
2.2.4 链表的指针修改的次序对 结果的影响 12
2.2.5 各种链表存储结构的特点 13
2.2.6 顺序存储结构上的算法如 何移植到链式存储结构上 13

2.2.7 如何利用循环单链表 实现队列的操作 14
2.2.8 如何应用线性表 14
2.3 典型例题与考研题分析 15
2.3.1 典型例题分析 15
2.3.2 考研题分析 21
2.4 重要习题精选精解 30
2.5 两级训练题 33
2.5.1 达标训练题 33
2.5.2 考研挑战题 37
第3章 栈和队列 39
3.1 本章知识结构图 39
3.2 疑难解惑 39
3.2.1 怎样理解栈 39
3.2.2 栈的顺序存储结构和 链式存储结构的区别 40
3.2.3 在进行入栈和出栈时 应注意的问题 40
3.2.4 如何理解多栈的作用 40
3.2.5 如何应用栈 41
3.2.6 怎样理解队列 42
3.2.7 如何处理循环队列中 的边界条件 43
3.2.8 队列的顺序存储结构和 链式存储结构的区别 43
3.2.9 如何理解双队列的作用 43
3.2.10 如何应用队列 44
3.3 典型例题与考研题分析 44
3.3.1 典型例题分析 44
3.3.2 考研题分析 53
3.4 重要习题精选精解 56
3.5 两级训练题 60
3.5.1 达标训练题 60
3.5.2 考研挑战题 60
第4章 串 62
4.1 本章知识结构图 62
4.2 疑难解惑 62
4.2.1 怎样理解串 62
4.2.2 串的顺序存储结构和 链式存储结构的优缺点 63
4.2.3 共享堆求子串 64
4.2.4 如何理解KMP 算法的思路 65
4.2.5 如何应用串 66
4.3 典型例题与考研题分析 67
4.3.1 典型例题分析 67
4.3.2 考研题分析 72
4.4 重要习题精选精解 74
4.5 两级训练题 76
4.5.1 达标训练题 76
4.5.2 考研挑战题 76
第5章 数组和广义表 77
5.1 本章知识结构图 77
5.2 疑难解惑 78
5.2.1 数组存储地址的确定 78
5.2.2 如何得到特殊矩阵的 压缩存储地址 78
5.2.3 如何由压缩存储地址 得到矩阵元素的行和列 79
5.2.4 如何理解稀疏矩阵的 三元组存储结构 79
5.2.5 如何灵活运用广义表 的表头和表尾操作 81
5.2.6 如何由广义表表示得到 其动态存储表示 82
5.2.7 如何由广义表的动态存储 表示求广义表表示 82
5.2.8 如何理解广义表表示和 二叉树的内在联系 83
5.3 典型例题与考研题分析 83
5.3.1 典型例题分析 83
5.3.2 考研题分析 86
5.4 重要习题精选精解 89
5.5 两级训练题 93
5.5.1 达标训练题 93
5.5.2 考研挑战题 94
第6章 树 96
6.1 本章知识结构图 96
6.2 疑难解惑 97
6.2.1 深刻理解树的递归定义 97
6.2.2 如何理解树的性质 和基本概念 97
6.2.3 深刻理解二叉树的 递归定义 98
6.2.4 如何理解二叉树的 性质及其推广 98
6.2.5 深刻理解二叉树遍历的 非递归算法 99
6.2.6 如何理解用线索二叉树实现 二叉树的非递归算法 102
6.2.7 介绍二叉树与树或森林 转换的目的 103
6.2.8 建立二叉树的若干方法 104
6.2.9 如何理解广义表表示和 二叉树的内在联系 105
6.2.10 哈夫曼树的建立和 哈夫曼编码的构造 105
6.2.11 如何利用树型结构 求解集合的幂 106
6.2.12 二叉树的应用 108
6.3 典型例题与考研题分析 110
6.3.1 典型例题分析 110
6.3.2 考研题分析 119
6.4 重要习题精选精解 134
6.5 两级训练题 156
6.5.1 达标训练题 156
6.5.2 考研挑战题 157
第7章 图 160
7.1 本章知识结构图 160
7.2 疑难解惑 161
7.2.1 深刻理解图的定义 161
7.2.2 如何合理地应用图的 各种存储结构 161
7.2.3 图遍历的非递归算法 162
7.2.4 如何理解图的最小生成树 164
7.2.5 用图框架及其遍历 解决“背包”问题 164
7.2.6 如何理解拓扑 排序的作用 168
7.2.7 深刻理解Dijkstra算法 和Floyd算法的优缺点 168
7.2.8 如何理解关键路径 169
7.2.9 图的其他应用 169
7.3 典型例题与考研题分析 170
7.3.1 典型例题分析 170
7.3.2 考研题分析 181
7.4 重要习题精选精解 201
7.5 两级训练题 210
7.5.1 达标训练题 210
7.5.2 考研挑战题 211
第8章 查找 213
8.1 本章知识结构图 213
8.2 疑难解惑 213
8.2.1 理解查找的基本概念 213
8.2.2 如何理解顺序查找中 的监视哨作用 214
8.2.3 折半查找的前提条件 及其优缺点 215
8.2.4 分块查找的由来 216
8.2.5 深刻理解二叉 排序树的特点 216
8.2.6 文件作为二叉排序树 的输入和输出 217
8.2.7 如何调整平衡二叉树 218

8.2.8 深刻理解B-树的定义 及其动态调整 218
8.2.9 哈希表构造及“成功”和 “不成功”的性能分析 219
8.3 典型例题与考研题分析 219
8.3.1 典型例题分析 219
8.3.2 考研题分析 225
8.4 重要习题精选精解 232
8.5 两级训练题 237
8.5.1 达标训练题 237
8.5.2 考研挑战题 238
第9章 内排序 240
9.1 本章知识结构图 240
9.2 疑难解惑 240
9.2.1 理解排序算法的稳定性 240
9.2.2 如何合理地采用适当 的排序方法 241
9.2.3 如何将顺序存储结构上 的排序算法移植到链表上 241
9.2.4 如何理解堆排序 243
9.2.5 如何在r进制下运用 基数排序 243
9.3 典型例题与考研题分析 245
9.3.1 典型例题分析 245
9.3.2 考研题分析 249
9.4 重要习题精选精解 259
9.5 两级训练题 265
9.5.1 达标训练题 265
9.5.2 考研挑战题 268
第10章 外排序 270
10.1 本章知识结构图 270
10.2 疑难解惑 270
10.2.1 外排序概念的理解 270
10.2.2 败者树的作用 271
10.2.3 置换选择排序的 用途及策略 271
10.2.4 k路归并方法的理解 271
10.2.5 最佳归并树的含义 272
10.3 典型例题与考研题分析 272
10.3.1 典型例题分析 272
10.3.2 考研题分析 274
10.4 重要习题精选精解 275
10.5 两级训练题 277
10.5.1 达标训练题 277
10.5.2 考研挑战题 277
第11章 文件 278
11.1 本章知识结构图 278
11.2 疑难解惑 278
11.2.1 文件基本概念的理解 278
11.2.2 文件各种组织 方式的优缺点 279
11.3 典型例题与考研题分析 279
11.3.1 典型例题分析 279
11.3.2 考研题分析 282
11.4 重要习题精选精解 282
11.5 两级训练题 284
11.5.1 达标训练题 284
11.5.2 考研挑战题 284
附录A 达标模拟题一及其答案 285
附录B 达标模拟题二及其答案 295
附录C 考研模拟题一及其答案 306
附录D 考研模拟题二及其答案 316
附录E 各章两级训练题参考答案 327
参考文献 386