出版社:高等教育出版社
出版日期:2011-7
ISBN:9787040326390
页数:437页
章节摘录
15.2.5 回溯法 回溯法也称试探法。该方法首先暂时放弃问题规模大小的限制，从最小规模开始将问题的候选解按某种顺序逐一枚举和检验。当发现候选解不可能是解时，就选择下一候选解。如果当前候选解虽不满足规模要求，但满足其他所有要求，则继续扩大当前候选解的规模，并继续试探。如果当前的候选解满足包括问题规模在内的所有要求，该候选解就是问题的一个解。寻找下一候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。 15.2.6 随机算法 所谓的随机算法，是指在算法中至少有一个地方使用随机数做决策。例如，在快速排序中，很重要的一个步骤是选择中间元素。前面介绍过用第一个元素作为中间元素，也可以选择一个样本，让样本的中值作为中间元素。也可以随机选择一个元素作为中间元素，那么，快速排序就成为一个随机算法。此外，在 第11章中的迷宫问题中，采用随机数来确定选择哪一堵墙。因此，迷宫问题也是用随机算法实现的。正是因为解决迷宫问题的算法是一个随机算法，这个程序每次运行才能得到不同的迷宫。 随机算法的时间复杂度一般用期望的运行时间来表示。 ……
内容概要
翁惠玉，毕业子上海交通大学，获博士学位。现为上海交通大学计算机系副教授，主要从事计算机网络和信息系统的研究，并长期承担程序设计的教学工作，主讲计算机系ACM试点班和电信学院大平台的程序设计课程，该课程于2004年被评为上海市精品课程。
书籍目录
第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 程序设计题参考文献
作者简介
《数据结构:题解与拓展》是同家精品课程“数据结构”（上海交通大学）的主讲教材之一，并与主教材《数据结构：思想与实现》（翁惠玉、俞勇编著）相配套。《数据结构:题解与拓展》总结了主教材各章的主要内容以及重点难点，并对主教材中的习题进行了分析和解答。作为对主教材的补充，《数据结构:题解与拓展》在大多数章中都增加了一个拓展部分，使学有余力的学生能够进一步深入地学习数据结构。《数据结构:题解与拓展》概念清楚，内容丰富，通过学习，可以帮助学生进一步巩固数据结构的知识。
《数据结构:题解与拓展》可作为高等学校计算机及相关专业“数据结构”课程的教学辅导教材，也可以作为全同计算机专业硕士研究生入学考试的辅导用书。