第1章 数据结构概念理解 1
1.1答疑解惑 1
1.1.1为什么要用数据类型来描述数据结构？ 1
1.1.2算法和程序有何区别？ 1
1.1.3怎样理解数据的逻辑结构和存储结构？ 1
1.1.4怎样理解数据结构在计算机课程中的核心地位？ 2
1.1.5如何计算算法的时间复杂度？ 2
1.1.6如何评价算法的好坏？ 2
1.2典型题解 3
题型1数据结构基础知识 3
题型2时间与空间复杂度的计算 4
第2章 线性表 6
2.1答疑解惑 6
2.1.1如何理解线性表数据结构？ 6
2.1.2线性表的顺序存储结构和链式存储结构的区别是什么？ 6
2.1.3带头结点的单链表和不带头结点的单链表的区别是什么？ 7
2.1.4链表的指针修改的次序对结果的影响是什么？ 7
2.1.5各种链表存储结构的特点是什么？ 8
2.1.6顺序存储结构上的算法如何移植到链式存储结构上？ 8
2.1.7如何利用循环单链表实现队列的操作？ 9
2.1.8如何应用线性表？ 9
2.1.9顺序表的基本运算用C语言如何描述？ 9
2.2典型题解 12
题型1线性表的基本概念 12
题型2线性表的存储结构 13
题型3链表的插入和删除 15
题型4线性表元素查找 17
题型5递归 20
题型6归并 21
题型7单链表的应用 24
题型8单链表的应用 30
题型9其他链表及应用 32
第3章 栈与队列 36
3.1答疑解惑 36
3.1.1怎样理解栈？ 36
3.1.2栈的顺序存储结构和链式存储结构的区别是什么？ 36
3.1.3在进行入栈和出栈时应注意什么问题？ 37
3.1.4如何理解多栈的作用？ 37
3.1.5如何让两个栈共享同一存储空间？ 37
3.1.6如何应用栈？ 37
3.1.7怎样理解队列？ 39
3.1.8如何处理循环队列中的边界条件？ 39
3.1.9队列的顺序存储结构和链式存储结构的区别是什么？ 39
3.1.10如何理解双队列的作用？ 39
3.1.11如何应用队列 40
3.2典型题解 40
题型1栈和队列的基本概念 40
题型2栈和队列的基本操作 41
题型3栈和队列的状态分析 47
题型4递归算法和递归工作栈 49
题型5用栈求表达式的值 52
题型6栈和队列的应用 53
第4章串 61
4.1答疑解惑 61
4.1.1怎样理解串？ 61
4.1.2串的顺序存储结构和链式存储结构的优缺点 61
4.1.3 C语言的串的基本操作 62
4.1.4共享堆求子串 63
4.1.5如何理解KMP算法 64
4.1.6串有何应用？ 65
4.2典型题解 65
题型1串的性质和存储 65
题型2串的基本运算 66
题型3串的模式匹配 67
第5章 数组与广义表 70
5.1答疑解惑 70
5.1.1数组存储地址的确定 70
5.1.2对称矩阵的压缩存储 70
5.1.3对称矩阵的地址计算公式 71
5.1.4三角矩阵的压缩存储 71
5.1.5对角矩阵 72
5.1.6稀疏矩阵的三元组存储结构理解 72
5.1.7如何灵活运用广义表的表头和表尾操作？ 74
5.1.8如何由广义表表示得到其动态存储表示？ 74
5.1.9如何由广义表的动态存储表示求广义表表示？ 75
5.1.10广义表的运算 75
5.1.11如何理解广义表表示和二叉树的内在联系？ 76
5.2典型题解 76
题型1多维数组 76
题型2特殊矩阵 79
题型3稀疏矩阵 82
题型4广义表 86
第6章 树和二叉树 90
6.1答疑解惑 90
6.1.1树的递归定义如何理解？ 90
6.1.2如何理解树的性质和基本概念？ 90
6.1.3如何理解二叉树的性质及其推广？ 90
6.1.4如何理解二叉树遍历的非递归？ 91
6.1.5如何理解线索二叉树实现二叉树的非递归？ 93
6.1.6如何理解二叉树中序线索化的算法？ 94
6.1.7二叉树与树或森林转换的目的是什么？ 95
6.1.8建立二叉树有哪些方法？ 95
6.1.9森林的两种遍历都是哪些？ 95
6.1.10如何理解广义表表示和二叉树的内在联系？ 96
6.1.11霍夫曼树的建立和霍夫曼编码的构造？ 96
6.1.12霍夫曼树的建立和霍夫曼编码的构造？ 97
6.1.13二叉树有哪些应用？ 97
6.1.14如何用二叉树表示表达式？ 99
6.2典型题解 99
题型1树的性质 99
题型2二叉树的性质 100
题型3条件运算 106
题型4二叉树的遍历 107
题型5根据遍历结果还原树 114
题型6线索二叉树 119
题型7树与森林 125
第7章图 132
7.1答疑解惑 132
7.2.1如何理解图的定义？ 132
7.2.2如何理解图的各种存储结构？ 132
7.2.3如何理解图的遍历？ 133
7.2.4如何理解图遍历的非递归算法？ 134
7.2.5如何理解图的最小生成树？ 135
7.2.6如何用图的框架及其遍历方法解决背包问题？ 136
7.2.7如何理解拓扑排序的作用？ 138
7.2.8如何理解Dijkstra算法和Floyd算法的优缺点？ 139
7.2.9如何理解关键路径？ 139
7.2.10图的应用有哪些？ 140
7.2典型题解 140
题型1图的基本概念 140
题型2图的存储结构 142
题型3图的遍历 147
题型4图的生成树 159
题型5图的最短路 168
题型6图的拓扑排序 174
题型7图的应用 185
第8章 查找 191
8.1答疑解惑 191
8.1.1如何理解查找的基本概念？ 191
8.1.2如何理解顺序查找中的监视哨作用？ 191
8.1.3如何理解平均查找长度？ 192
8.1.4折半查找的前提条件及其优缺点有哪些？ 192
8.1.5什么情况下使用分块查找 193
8.1.6二叉排序树的特点有哪些？ 194
8.1.7如何调整平衡二叉树？ 194
8.1.8深刻理解B-树的定义及其动态调整 196
8.1.9如何理解散列表的性质？ 196
8.1.10如何理解散列表的冲突？ 196
8.1.11常用的散列函数有哪些？ 197
8.2典型题解 198
题型1顺序查找 198
题型2二分查找 199
题型3一维数组元素的移动 204
题型4一维数组的排序 205
题型5平衡二叉树 210
题型6 B树 214
题型7哈希表 219
第9章 排序 225
9.1答疑解惑 225
9.1.1如何理解排序算法的稳定性？ 225
9.1.2内部排序和外部排序有什么区别？ 225
9.1.3如何将顺序存储结构上的排序算法移植到链表上？ 225
9.1.4希尔排序为何比一般的插入排序要高效？ 227
9.1.5如何理解堆排序？ 227
9.1.6如何在r进制下运用基数排序？ 227
9.1.7如何合理地采用适当的内部排序方法？ 229
9.1.8如何在k路归并方法中使用败者树？ 229
9.2典型题解 230
题型1排序基本概念 230
题型2插入排序 233
题型3冒泡排序 237
题型4选择排序 246
题型5归并排序 254
题型6基数排序 259
题型7各种内部排序的比较 262
题型8外部排序 266
第10章 课程测试与考研真题 267
10.1课程测试 267
10.2考研真题 269
10.3课程测试解析 270
10.4考研真题解析 272
附录1 2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题 274
附录2 2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题 283
参考文献 291