数据结构 考前复习(精品·公开课件).ppt

1.线性表上的查找： 主要分为三种线性结构：顺序表，有序顺序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比较。对于及有序顺序表我们采用二分查找法。对于第三种索引结构，我们采用索引查找算法。考生需要注意这三种表下的ASL值以及三种算法的实现。其中，二分查找还要特别注意适用条件以及其递归实现方法。 2.树表上的查找： 这是本章的重点和难点。由于这一节介绍的内容是使用树表进行的查找，所以很容易与树一间的某些概念相混淆。本节内容与树一章的内容有联系，但也有很多不同，应注意归纳。树表主要分为以下几种：二叉排序树，平衡二叉树，B树。其中，尤以前两种结构为重。由于二叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就更为紧密，二叉树一章学好了，这里也就不难了。 回顾：查找（三） 2.树表上的查找（续）： 二叉排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。常考给定记录序列，建立相应的二叉排序树及其查找长度分析。平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二叉排序树，“判断某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，所以应该掌握平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。 回顾：查找（四） 2.树表上的查找（续）： B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树，主要用于文件系统，减少外存读次数。除B树的查找算法外，应该特别注意一下B树的插入和删除算法。因为这两种算法涉及到B树结点的分裂和合并，是一个难点。另外，也有考B树的结点数与高度相关关系的题目。 3.基本哈希表的查找算法： 哈希一词，是外来词，译自“hash”一词，意为：散列或杂凑的意思。哈希表查找的基本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进行转换后，其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。 回顾：查找（五） 我们课程所讲的排序都是内部排序。内部排序是数据结构课程中最后一个重要的章节，建立在此章之上的考题可以有多种类型：填空，选择，判断乃至大型算法题。但是，归结到一点，就是考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标（时间复杂度）能否了如指掌。 这一章，我们对重点的归纳将跟以上各章不同。我们将从以下几个侧面来对排序一章进行不同的规纳，以期能更全面的理解排序一章的总体结构及各种算法。 回顾：排序（一） 从排序算法的种类来分，本章主要阐述了以下几种排序方法：插入、选择、交换、归并、基数等五种排序方法。 其中，在插入排序中又可分为：直接插入、折半插入、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。 回顾：排序（二） 交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。快速排序，在处理的“问题规模”这个概念上，是先处理一个较大规模，然后逐渐把处理的规模降低，最终达到排序的目的。 选择排序，相对于前面几种排序算法来说，难度大一点。具体来说，它可以分为：简单选择、堆排序。这两种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数；堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。 回顾：排序（三） 归并排序，故名思义，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比较简单，有一点，要铭记在心：归并排序是稳定排序。 基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比较适合于一些特别的场合，比如扑克牌排序问题等。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一个有序序列。 回顾：排序（四） 本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的，学习时要多注意规纳、总结、对比。此外，对于教材中10.7节的表格，即各种排序算法的时间复杂度及其特点，要求必须熟记，在理解的基础上记忆，这一节几乎成为很多学