数据结构与算法:学习指导与习题解析

第1章 概论. 1

1.1 概论部分的主要知识点总结 1

1.1.1 学习数据结构的目的和目标 1

1.1.2 什么是数据结构 1

1.1.3 抽象数据类型 2

1.1.4 算法及其特性 2

1.1.5 算法的执行效率及其度量 3

1.1.6 数据结构的选择和评价 4

1.2 概论部分的习题解析 4

1.3 概论部分增补习题 8

1.4 概论部分增补上机题 10

第2章 线性表、栈和队列 11

2.1 线性表的主要知识点总结 11

2.1.1 线性表 11

2.1.2 栈 12

2.1.3 队列 13

2.1.4 限制存取点的表 14

2.2 线性表习题参考答案 14

2.3 线性表增补习题 34

2.4 线性表增补上机题 35

.第3章 字符串 36

3.1 字符串的主要知识点总结 36

3.1.1 基本概念 36

3.1.2 字符串的存储结构 36

3.1.3 字符串的运算 36

3.1.4 字符串的模式匹配 37

3.2 字符串习题部分的参考答案 37

3.3 字符串上机题部分的参考答案 40

3.4 字符串增补习题 43

3.5 字符串增补上机题 44

第4章 二叉树 45

4.1 二叉树知识点总结 45

4.1.1 二叉树的定义及相关概念 45

4.1.2 二叉树的性质 46

4.1.3 主要方法 46

4.2 二叉树习题解答 48

4.3 二叉树上机题解答 63

4.4 二叉树增补习题 79

4.5 二叉树增补上机题 80

第5章 树 81

5.1 树的概念和表示法 81

5.1.1 基本概念： 81

5.1.2 相关术语： 81

5.1.3 树的性质和表示法： 82

5.2 树的周游 82

5.2.1 按深度的方向周游树和森林： 82

5.2.2 按广度的方向周游树和森林： 82

5.3 树的存储 83

5.3.1 树的链式存储： 83

5.3.2 树的顺序存储： 84

5.4 k叉树 84

5.5 树习题解答 84

5.5 树上机题解答 100

5.6 树增补习题 119

5.7 树补充上机题 120

第6章 图 121

6.1 图知识点总结 121

6.2 图习题解答 123

6.3 图上机题解答 147

6.4 图增补习题 152

6.5 图增补上机题 154

第7章 内排序 155

7.1 内排序知识点总结 155

7.1.1 内排序概念 155

7.1.2 内排序的性质（重点） 156

7.1.3 评价一个排序算法的好坏（重点）.. 156

7.1.4 基于比较的排序问题的下限 156

7.1.5 几种重要的排序算法 （重点，难点） 157

7.2 内排序性能总结 159

7.2.1 简单排序算法的时间代价比较 159

7.2.2 排序算法的时间代价和空间代价 160

7.2.3 排序算法的实验性能比较 160

7.3 内排序知识扩充 162

7.3.1 索引排序和地址排序 162

7.3.2 海豚算法 166

7.4 内排序习题解答 168

7.5 内排序上机题解答 203

7.6 内排序增补习题 209

7.7 内排序增补上机题 211

第8章 文件管理和外排序 212

8.1 文件管理和外排序知识点总结 212

8.1.1 文件管理和外排序的基本概念 212

8.2 文件管理和外排序习题解答 214

8.3 文件管理和外排序上机题解答 222

8.4 文件管理和外排序增补习题 225

8.5 文件管理和外排序增补上机题 226

第9章 检索 227

9.1 检索知识点总结 227

9.1.1 检索概念 227

9.1.2 检索算法的基本分类 228

9.1.3 衡量检索算法的效率（重点） 228

9.1.4 基于线性表的检索（重点） 228

9.1.5 基于散列表的检索（重点、难点） 229

9.2 检索习题解答 231

9.3 上机题解答 251

9.4 检索增补习题 258

9.5 检索增补上机题 259

第10章 索引技术 260

10.1 检索知识点总结 260

10.1.1 索引概念 260

10.1.2 索引技术的简单分类 260

10.1.3 线性索引（重点） 261

10.1.4 动态索引（重点、难点） 261

10.2 索引技术习题解答 262

10.3 索引技术上机题解答 272

10.4 索引技术增补习题 281

10.5 索引技术增补上机题 282

第11章 高级线性结构 283

11.1 高级线性结构的主要知识点总结 283

11.1.1 基本概念 283

11.1.2 多维数组 283

11.1.3 广义表 284

11.1.4 存储管理技术 285

11.2 高级线性结构的习题参考答案 286

11.3 高级线性结构的上机题参考答案 292

11.4 高级线性结构增补习题 300

11.5 高级线性结构增补上机题 301

第12章 高级树结构 302

12.1 高级树结构知识点总结 302

12.1.1 适用于存储、检索字符串组的树型结构 302

12.1.2 二叉搜索树bst的几个变体（重点） 302

12.1.3 空间数据结构 303

12.1.4 树型结构的两个应用 303

12.2 扩充知识——红黑树 304

12.2.1 红黑树的定义 304

12.2.2 红黑树相关性质 304

12.2.3 插入结点算法 305

12.2.4 删除结点算法 308

12.3 高级树习题解答 310

12.4 高级树结构上机题解答 338

12.5 高级树结构增补习题 362

12.6 高级树结构补充上机题 365

第13章 数据结构与算法实习指导 369

13.1 基本数据结构的应用 369

13.2 穷举法 371

13.3 搜索和剪枝 374

13.4 动态规划 380

13.5 贪心法 382

13.6 图算法 385

13.7 实习范例 389

13.8 增补习题 395

第14章 北京大学计算机系“数据结构与算法”试题选 423

14.1 北京大学信息学院2004年“数据结构与算法”试题 423

14.1.1 2004年期中考试试题 423

14.1.2 2004年期末考试试题 426

14.2 2004年秋季学期试题参考答案 429

14.2.1 2004年期中考试参考答案 429

14.2.2 2004年期末考试参考答案 435

14.3 北京大学硕士研究生入学考试“数据结构”试题 443

14.3.1 北京大学1999年研究生入学考试“数据结构”试题 443

14.3.2 北京大学2000年研究生入学考试“数据结构”试题 446

14.3.3 北京大学2001年研究生入学考试“数据结构”试题 447

14.3.4 北京大学2002年研究生入学考试“数据结构”试题 450

14.3.5 北京大学2003年研究生入学考试“数据结构”试题 452

14.3.6 北京大学2004年研究生入学考试“数据结构”试题 455

14.3.7 北京大学2005年研究生入学考试“数据结构”试题 459

14.4 北京大学硕士研究生入学考试“数据结构”参考答案 462

14.4.1 1999年研究生试题参考答案 462

14.4.2 2000年研究生试题参考答案 465

14.4.3 2001年研究生试题参考答案 466

14.4.4 2002年研究生试题参考答案 470

14.4.5 2003年研究生试题参考答案 472

14.4.6 2004年研究生试题参考答案 473

14.4.7 2005年研究生试题参考答案 480

参考文献...