数据结构（C++版）答疑解惑与典型题解PDF电子书下载

第1章 数据结构基本概念 1

1.1 答疑解惑 1

1.1.1 为什么要用数据类型来描述数据结构？ 1

1.1.2 何为抽象数据类型（ADT）？ 1

1.1.3 算法和程序有何区别？ 2

1.1.4 怎样理解数据的逻辑结构和存储结构？ 2

1.1.5 怎样理解数据结构在计算机课程中的核心地位？ 2

1.1.6 如何计算算法的时间复杂度？ 3

1.1.7 如何评价算法的好坏？ 3

1.2 典型题解 3

题型1 数据结构基础知识 3

题型2 时间与空间复杂度的计算 4

第2章 线性表 7

2.1 答疑解惑 7

2.1.1 如何理解线性表数据结构？ 7

2.1.2 线性表的顺序存储结构和链式存储结构的区别是什么？ 7

2.1.3 带头结点的单链表和不带头结点的单链表的区别是什么？ 8

2.1.4 链表的指针修改的次序对结果的影响是什么？ 8

2.1.5 各种链表存储结构的特点是什么？ 9

2.1.6 如何利用循环单链表实现队列的操作？ 9

2.1.7 如何应用线性表？ 9

2.1.8 顺序表的声明和基本运算用C＋＋如何描述？ 9

2.2 典型题解 12

题型1 线性表的基本概念 12

题型2 线性表的存储结构 14

题型3 链表的插入和删除 15

题型4 线性表元素查找 18

题型5 递归 19

题型6 归并 20

题型7 单链表的应用 24

题型8 其他链表及应用 31

第3章 栈与队列 35

3.1 答疑解惑 35

3.1.1 怎样理解栈？ 35

3.1.2 栈的顺序存储结构和链式存储结构的区别是什么？ 35

3.1.3 在进行入栈和出栈时应注意的问题是什么？ 36

3.1.4 如何理解多栈的作用？ 36

3.1.5 两个栈如何共享同一存储空间？ 36

3.1.6 如何应用栈？ 36

3.1.7 怎样理解队列？ 38

3.1.8 如何处理循环队列中的边界条件？ 38

3.1.9 队列的顺序存储结构和链式存储结构的区别是什么？ 38

3.1.10 如何理解双队列的作用？ 39

3.1.11 如何应用队列？ 39

3.2 典型题解 39

题型1 栈和队列的基本概念 39

题型2 栈和队列的基本操作 40

题型3 栈和队列的状态分析 47

题型4 递归算法和递归工作栈 49

题型5 用栈求表达式的值 52

题型6 栈和队列的应用 53

第4章 串 61

4.1 答疑解惑 61

4.1.1 怎样理解串？ 61

4.1.2 串的顺序存储结构和链式存储结构的优缺点是什么？ 61

4.1.3 串的基本操作 62

4.1.4 怎样用共享堆求子串？ 62

4.1.5 如何理解KMP算法？ 63

4.1.6 串有何应用？ 64

4.2 典型题解 65

题型1 串的性质和存储 65

题型2 串的基本运算 66

题型3 串的模式匹配 66

第5章 数组与广义表 69

5.1 答疑解惑 69

5.1.1 数组存储地址如何确定？ 69

5.1.2 对称矩阵如何压缩存储？ 69

5.1.3 对称矩阵的地址计算公式是什么？ 70

5.1.4 三角矩阵如何压缩存储？ 71

5.1.5 对角矩阵的概念是什么？ 71

5.1.6 稀疏矩阵的三元组存储结构如何理解？ 72

5.1.7 如何灵活运用广义表的表头和表尾操作？ 73

5.1.8 如何由广义表表示得到其动态存储表示？ 74

5.1.9 如何由广义表的动态存储表示求广义表表示？ 74

5.1.10 广义表如何运算？ 75

5.1.11 如何理解广义表表示和二叉树的内在联系？ 75

5.2 典型题解 75

题型1 多维数组 75

题型2 特殊矩阵 79

题型3 稀疏矩阵 81

题型4 广义表 86

第6章 树与二叉树 90

6.1 答疑解惑 90

6.1.1 树的递归定义如何理解？ 90

6.1.2 如何理解树的性质和基本概念？ 90

6.1.3 如何理解二叉树的性质及其推广？ 91

6.1.4 如何理解二叉树遍历的非递归？ 92

6.1.5 如何理解线索二叉树实现二叉树的非递归？ 92

6.1.6 如何理解二叉树中序线索化的算法？ 93

6.1.7 二叉树与树或森林转换的目的是什么？ 93

6.1.8 建立二叉树有哪些方法？ 94

6.1.9 森林的两种遍历都是哪些？ 94

6.1.10 如何理解广义表表示和二叉树的内在联系？ 95

6.1.11 哈夫曼树的建立和哈夫曼编码的构造？ 95

6.1.12 如何用二叉树表示表达式？ 96

6.2 典型题解 96

题型1 树的性质 96

题型2 二叉树的性质 97

题型3 条件运算 103

题型4 二叉树的遍历 104

题型5 根据遍历结果还原树 111

题型6 线索二叉树 117

题型7 树与森林 122

题型8 树与森林 126

第7章 图 130

7.1 答疑解惑 130

7.1.1 如何理解图的定义？ 130

7.1.2 如何理解图的各种存储结构？ 130

7.1.3 如何理解图的遍历？ 131

7.1.4 如何理解图遍历的非递归算法？ 132

7.1.5 如何理解图的最小生成树？ 133

7.1.6 如何用图的框架及其遍历方法解决背包问题？ 134

7.1.7 如何理解拓扑排序的作用？ 137

7.1.8 如何理解Dijkstra算法和Floyd算法的优缺点？ 137

7.1.9 如何理解关键路径？ 138

7.1.10 图的应用有哪些？ 138

7.2 典型题解 139

题型1 图的基本概念 139

题型2 图的存储结构 140

题型3 图的遍历 146

题型4 图的生成树 159

题型5 图的最短路 168

题型6 图的拓扑排序 175

题型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 二叉排序树的特点有哪些？ 193

8.1.7 如何调整平衡二叉树？ 195

8.1.8 深刻理解B－树的定义及其动态调整 197

8.1.9 如何理解散列表的性质？ 197

8.1.10 如何理解散列表的冲突？ 197

8.1.11 常用的散列函数有哪些？ 198

8.2 典型题解 198

题型1 顺序查找 198

题型2 二分查找 199

题型3 一维数组元素的移动 205

题型4 一维数组的排序 205

题型5 平衡二叉树 211

题型6 B树 215

题型7 哈希表 219

第9章 排序 226

9.1 答疑解惑 226

9.1.1 如何理解排序算法的稳定性？ 226

9.1.2 内部排序和外部排序有什么区别？ 226

9.1.3 如何将顺序存储结构上的排序算法移植到链表上？ 226

9.1.4 希尔排序为何比一般的插入排序要高效？ 228

9.1.5 如何理解堆排序？ 228

9.1.6 如何在r进制下运用基数排序？ 229

9.1.7 如何合理地采用适当的内部排序方法？ 230

9.1.8 如何在k路归并方法中使用败者树？ 230

9.2 典型题解 231

题型1 排序基本概念 231

题型2 插入排序 234

题型3 冒泡排序 239

题型4 选择排序 250

题型5 归并排序 258

题型6 基数排序 262

题型7 各种内部排序的比较 266

题型8 外部排序 269

第10章 课程测试与考研真题 271

10.1 课程测试 271

10.2 考研真题 273

10.3 课程测试解析 275

10.4 考研真题解析 277

参考文献 278