数据结构 题解与拓展 作者：翁惠玉，俞勇

数据结构 题解与拓展 出版社：高等教育出版社

数据结构 题解与拓展 内容简介

《国家精品课程主讲教材·数据结构：题解与拓展》总结了主教材各章的主要内容以及重点难点，并对主教材中的习题进行了分析和解答。作为对主教材的补充，本书在大多数章中都增加了一个拓展部分，使学有余力的学生能够进一步深入地学习数据结构。本书概念清楚，内容丰富，通过学习，可以帮助学生进一步巩固数据结构的知识。

《国家精品课程主讲教材·数据结构：题解与拓展》可作为高等学校计算机及相关专业“数据结构”课程的教学辅导教材，也可以作为全同计算机专业硕士研究生入学考试的辅导用书。

数据结构 题解与拓展 目录

第1章 绪论

1.1 重点难点

1.2 主要内容

1.2.1 数据的逻辑结构

1.2.2 数据结构的存储实现

1.2.3 算法分析

1.3 习题解答

1.3.1 简答题

1.3.2 程序设计题

1.4 进一步拓展

1.4.1 最大公因子问题

1.4.2 递归函数的时间复杂度的计算

第2章 线性表

2.1 重点难点

2.2 主要内容

2.2.1 线性表的定义及基本运算

2.2.2 线性表的顺序实现

2.2.3 线性表的链接实现

2.3 习题解答

.2.3.1 简答题

2.3.2 程序设计题

2.4 进一步拓展

2.4.1 字符串的存储与匹配

2.4.2 模拟动态内存分配

第3章 栈

3.1 重点难点

3.2 主要内容

3.2.1 栈的基本概念

3.2.2 栈的顺序实现

3.2.3 栈的链接实现

3.3 习题解答

3.3.1 简答题

3.3.2 程序设计题

3.4 进一步拓展

3.4.1 基于线性表的栈的实现

3.4.2 迷宫问题

第4章 队列

4.1 重点难点

4.2 主要内容

4.2.1 队列的概念

4.2.2 队列的顺序实现

4.2.3 队列的链接实现

4.3 习题解答

4.3.1 简答题

4.3.2 程序设计题

4.4 进一步拓展

4.4.1 迷宫问题

4.4.2 火车车厢重排

第5章 树

5.1 重点难点

5.2 主要内容

5.2.1 树的定义和基本概念

5.2.2 二叉树的基本概念

5.2.3 二叉树的顺序实现

5.2.4 二叉树的链接实现

5.2.5 二叉树遍历的非递归实现

5.2.6 哈夫曼树和哈夫曼编码

5.2.7 树、森林和二叉树

5.3 习题解答

5.3.1 简答题

5.3.2 程序设汁题

5.4 进一步拓展

5.4.1 中序线索树

5.4.2 中序线索树的存储

5.4.3 构造中序穿线

5.4.4 遍历二叉线索树

第6章 优先级队列

6.1 重点难点

6.2 主要内容

6.2.1 优先级队列的概念

6.2.2 二叉堆

6.2.3 贝努里队列

6.3 习题解答

6.3.1 简答题

6.3.2 程序设计题

6.4 进一步拓展

6.4.1 双端队列

6.4.2 最小语言集

第7章 集合与静态查找表

7.1 重点难点

7.2 主要内容

7.2.1 集合的基本概念

7.2.2 查找及静态查找表

7.2.3 无序表的查找

7.2.4 有序表的查找

7.3 习题解答

7.3.1 简答题

7.3.2 程序设计题

第8章 查找树

8.1 重点难点

8.2 主要内容

8.2.1 二叉查找树

8.2.2 avl树

8.2.3 红黑树

8.2.4 伸展树

8.2.5 b+树

8.3 习题解答

8.3.1 简答题

8.3.2 程序设计题

8.4 进一步拓展

8.4.1 线段树

8.4.2 道路问题

第9章 散列表

9.1 重点难点

9.2 主要内容

9.2.1 散列函数

9.2.2 碰撞的解决

9.3 习题解答

9.3.1 简答题

9.3.2 程序设计题

9.4 进一步拓展

第10章 排序

10.1 重点难点

10.2 主要内容

10.2.1 基本概念

10.2.2 插入排序

10.2.3 选择排序

10.2.4 交换排序

10.2.5 归并排序

10.2.6 外排序

10.3 习题解答

10.3.1 简答题

10.3.2 程序设计题

10.4 进一步拓展

10.4.1 基数排序的思想

10.4.2 基数排序的实现

10.4.3 基数排序的性能

第11章 不相交集

11.1 重点难点

11.2 主要内容

11.2.1 不相交集的定义

11.2.2 不相交集的实现

11.3 习题解答

11.3.1 简答题

11.3.2 程序设计题

11.4 进一步拓展

第12章 图

12.1 重点难点

12.2 主要内容

12.2.1 图的定义及术语

12.2.2 图的存储

12.2.3 图的遍历

12.3 习题解答

12.3.1 简答题

12.3.2 程序设计题

12.4 进一步拓展

12.4.1 逆邻接表

12.4.2 十字链表

12.4.3 邻接多重表

第13章 最小生成树

13.1 重点难点

13.2 主要内容

13.2.1 kruslal算法

13.2.2 prim算法

13.3 习题解答

13.3.1 简答题

13.3.2 程序设计题

13.4 进一步拓展

第14章 最短路径问题

14.1 重点难点

14.2 主要内容

14.2.1 单源最短路径

14.2.2 所有结点对的最短路径

14.3 习题解答

14.3.1 简答题

14.3.2 程序设计题

第15章 算法设计基础

15.1 重点难点

15.2 主要内容

15.2.1 枚举法

15.2.2 贪婪法

15.2.3 分治法

15.2.4 动态规划

15.2.5 回溯法

15.2.6 随机算法

15.3 习题解答

15.3.1 简答题

15.3.2 程序设计题

参考文献

数据结构 题解与拓展 精彩文摘

15.2.5 回溯法

回溯法也称试探法。该方法首先暂时放弃问题规模大小的限制，从最小规模开始将问题的候选解按某种顺序逐一枚举和检验。当发现候选解不可能是解时，就选择下一候选解。如果当前候选解虽不满足规模要求，但满足其他所有要求，则继续扩大当前候选解的规模，并继续试探。如果当前的候选解满足包括问题规模在内的所有要求，该候选解就是问题的一个解。寻找下一候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。

15.2.6 随机算法

所谓的随机算法，是指在算法中至少有一个地方使用随机数做决策。例如，在快速排序中，很重要的一个步骤是选择中间元素。前面介绍过用第一个元素作为中间元素，也可以选择一个样本，让样本的中值作为中间元素。也可以随机选择一个元素作为中间元素，那么，快速排序就成为一个随机算法。此外，在第11章中的迷宫问题中，采用随机数来确定选择哪一堵墙。因此，迷宫问题也是用随机算法实现的。正是因为解决迷宫问题的算法是一个随机算法，这个程序每次运行才能得到不同的迷宫。

随机算法的时间复杂度一般用期望的运行时间来表示。