数据结构与算法 学习指导与习题解析PDF电子书下载

第1章　概论 1

1.1　知识点总结 1

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

1.1.2　什么是数据结构 1

1.1.3　抽象数据类型 2

1.1.4　算法及其特性 3

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

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

1.2　教材习题解答 4

1.3　增补习题 9

1.4　增补上机题 11

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

2.1　知识点总结 12

2.1.1 线性表 12

2.1.2　栈 14

2.1.3 队列 14

2.1.4　限制存取点的表 15

2.2　教材习题解答 15

2.3　增补习题 36

2.4　增补上机题 37

3.1.3　字符串的运算 38

3.1.2　字符串的存储结构 38

3.1　知识点总结 38

第3章　字符串 38

3.1.1 基本概念 38

3.1.4　字符串的模式匹配 39

3.2　教材习题解答 39

3.3　教材上机题解答 43

3.4　增补习题 46

3.5　增补上机题 47

4.1　知识点总结 48

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

第4章　二叉树 48

4.1.2　二叉树的性质 49

4.1.3　主要方法 49

4.2　教材习题解答 51

4.3　教材上机题解答 68

4.4　增补习题 85

4.5　增补上机题 86

第5章　树 87

5.1　树的概念和表示法 87

5.1.1　基本概念 87

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

5.2　树的周游 88

5.1.2　相关术语 88

5.1.3　树的性质和表示法 88

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

5.3　树的存储 89

5.3.1　树的链式存储 89

5.3.2　树的顺序存储 90

5.4　K叉树 91

5.5　教材习题解答 91

5.6　教材上机题解答 107

5.7　增补习题 125

5.8　增补上机题 127

第6章　图 128

6.1　知识点总结 128

6.1.1　图的存储结构 129

6.1.2　图的周游 129

6.1.3　图的拓扑排序 130

6.1.4　最短路径问题 130

6.1.5　图的最小支撑树 131

6.1.6　图的最小支撑树 131

6.2　教材习题解答 131

6.3　教材上机题解答 154

6.4　增补习题 159

6.5　增补上机题 161

第7章　内排序 162

7.1 内排序知识点总结 162

7.1.1 内排序概念 162

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

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

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

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

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

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

7.2　内排序性能总结 167

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

7.3　内排序知识扩充 170

7.3.1　索引排序和地址排序 170

7.3.2　海豚算法 175

7.4　教材习题解答 177

7.5　教材上机题解答 216

7.6　增补习题 223

7.7　增补上机题 225

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

8.1　知识点总结 226

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

8.1.2　磁盘访问时间估算 227

8.1.3　置换选择排序 227

8.1.4　二路外排序 228

8.2　教材习题解答 228

8.3　教材上机题解答 238

8.4　增补习题 241

8.5　增补上机题 242

9.1.1　检索概念 244

9.1　知识点总结 244

第9章　检索 244

9.1.2　检索算法的基本分类 245

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

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

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

9.2　教材习题解答 249

9.3　教材上机题解答 271

9.4　增补习题 278

9.5　增补上机题 279

10.1　知识点总结 280

10.1.1　索引概念 280

第10章　索引技术 280

10.1.2　索引技术的简单分类 281

10.1.3　线性索引（重点） 281

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

10.2　教材习题解答 283

10.3　教材上机题解答 294

10.4　增补习题 303

10.5　增补上机题 303

11.1.1　基本概念 304

11.1.2　多维数组 304

11.1　知识点总结 304

第11章　高级线性结构 304

11.1.3　广义表 305

11.1.4　存储管理技术 306

11.2　教材习题解答 307

11.3　教材上机题解答 314

11.4　增补习题 322

11.5　增补上机题 323

第12章　高级树结构 324

12.1　知识点总结 324

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

12.1.2　二叉搜索树BST的几个变体（重点） 324

12.1.4　树形结构的两个应用 325

12.1.3　空间数据结构 325

12.2.1　红黑树的定义 326

12.2　扩充知识——红黑树 326

12.2.2　红黑树相关性质 327

12.2.3　插入结点算法 327

12.2.4　删除结点算法 331

12.3　教材习题解答 333

12.4　教材上机题解答 364

12.5　增补习题 389

12.6　增补上机题 392

13.1　基本数据结构的应用 397

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

13.2　穷举法 400

13.3　搜索和剪枝 403

13.4　动态规划 410

13.5　贪心法 412

13.6　图算法 415

13.7　实习范例 419

13.8　增补习题 426

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

14.1.1　2004年期中考试试题 438

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

14.1.2　2004年期末考试试题 441

14.2　北京大学信息学院2004年“数据结构与算法”试题参考答案 444

14.2.1 2004年期中考试试题参考答案 444

14.2.2　2004年期末考试试题参考答案 450

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

14.3.1　1999年试题 458

14.3.2　2000年试题 461

14.3.3　2001年试题 462

14.3.4　2002年试题 464

14.3.5　2003年试题 466

14.3.6　2004年试题 468

14.3.7　2005年试题 472

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

14.4.1　1999年试题参考答案 475

14.4.2　2000年试题参考答案 478

14.4.3　2001年试题参考答案 479

14.4.4　2002年试题参考答案 483

14.4.5　2003年试题参考答案 484

14.4.6　2004年试题参考答案 486

14.4.7　2005年试题参考答案 493

参考文献 504