下面我们看一下图这一章的主要考点以及这些考点的考查方式
考查有关图的基本概念问题
这些概念是进行图一章学习的基础这一章的概念包括图的定义和特点无向图有向图入度出度完全图生成子图路径长度回路(强)连通图(强)连通分量等概念与这些概念相联系的相关计算题也应该掌握
考查图的几种存储形式
图的存储形式包括邻接矩阵(逆)邻接表十字链表及邻接多重表在考查时有的学校是给出一种存储形式要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式
考查图的两种遍历算法深度遍历和广度遍历
深度遍历和广度遍历是图的两种基本的遍历算法这两个算法对图一章的重要性等同于先序中序后序遍历对于二叉树一章的重要性在考查时图一章的算法设计题常常是基于这两种基本的遍历算法而设计的比如求最长的最短路径问题和判断两顶点间是否存在长为K的简单路径问题就分别用到了广度遍历和深度遍历算法
生成树最小生成树的概念以及最小生成树的构造PRIM算法和KRUSKAL算法
考查时一般不要求写出算法源码而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树
拓扑排序问题
拓扑排序有两种方法一是无前趋的顶点优先算法二是无后继的顶点优先算法换句话说一种是从前向后的排序一种是从后向前排当然后一种排序出来的结果是逆拓扑有序的
关键路径问题
这个问题是图一章的难点问题理解关键路径的关键有三个方面一是何谓关键路径二是最早时间是什么意思如何求三是最晚时间是什么意思如何求简单地说最早时间是通过从前向后的方法求的而最晚时间是通过从后向前的方法求解的并且要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行这个问题拿来直接考算法源码的不多一般是要求按照书上的算法描述求解的过程和步骤
在实际设计关键路径的算法时还应该注意以下这一点采用邻接表的存储结构求最早时间和最晚时间要采用不同的处理方法即在算法初始时应该首先将所有顶点的最早时间全部置为关键路径问题是工程进度控制的重要方法具有很强的实用性
最短路径问题
与关键路径问题并称为图一章的两只拦路虎概念理解是比较容易的关键是算法的理解最短路径问题分为两种一是求从某一点出发到其余各点的最短路径;二是求图中每一对顶点之间的最短路径这个问题也具有非常实用的背景特色一个典型的应该就是旅游景点及旅游路线的选择问题解决第一个问题用DIJSKTRA算法解决第二个问题用FLOYD算法注意区分
第七章查找
在不少数据结构的教材中是把查找与排序放入高级数据结构中的应该说查找和排序两章是前面我们所学的知识的综合运用用到了树也用到了链表等知识对这些数据结构某一方面的运用就构成了查找和排序
现实生活中search几乎无处不在特别是现在的网络时代万事离不开search小到文档内文字的搜索大到INTERNET上的搜索search占据了我们上网的大部分时间
在复习这一章的知识时你需要先弄清楚以下几个概念
关键字主关键字次关键字的含义;静态查找与动态查找的含义及区别;平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果特别是一些典型结构的ASL值应该记住
在DS的教材中一般将search分为三类st在顺序表上的查找;nd在树表上的查找;rd在哈希表上的查找下面详细介绍其考查知识点及考查方式
线性表上的查找
主要分为三种线性结构顺序表有序顺序表索引顺序表对于第一种我们采用传统查找方法逐个比较对于及有序顺序表我们采用二分查找法对于第三种索引结构我们采用索引查找算法考生需要注意这三种表下的ASL值以及三种算法的实现其中二分查找还要特别注意适用条件以及其递归实现方法
树表上的查找
这是本章的重点和难点由于这一节介绍的内容是使用树表进行的查找所以很容易与树一间的某些概念相混淆本节内容与树一章的内容有联系但也有很多不同应注意规纳树表主要分为以下几种二叉排序树平衡二叉树B树键树其中尤以前两种结构为重也有部分名校偏爱考B树的由于二叉排序树与平衡二叉树是一种特殊的二叉树所以与二叉树的联系就更为紧密二叉树一章学好了这里也就不难了
二叉排序树简言之就是左小右大它的中序遍历结果是一个递增的有序序列平衡二叉树是二叉排序树的优化其本质也是一种二叉排序树只不过平衡二叉树对左右子树的深度有了限定深度之差的绝对值不得大于对于二叉排序树判断某棵二叉树是否二叉排序树这一算法经常被考到可用递归也可以用非递归平衡二叉树的建立也是一个常考点但该知识点归根结底还是关注的平衡二叉树的四种调整算法所以应该掌握平衡二叉树的四种调整算法调整的一个参照是调整前后的中序遍历结果相同
B树是二叉排序树的进一步改进也可以把B树理解为三叉四叉排序树除B树的查找算法外应该特别注意一下B树的插入和删除算法因为这两种算法涉及到B树结点的分裂和合并是一个难点B树是报考名校的同学应该关注的焦点之一
键树也称字符树特别适用于查找英文单词的场合一般不要求能完整描述算法源码多是根据算法思想建立键树及描述其大致查找过程
基本哈希表的查找算法
哈希一词是外来词译自hash一词意为散列或杂凑的意思哈希表查找的基本思想是根据当前待查找数据的特征以记录关键字为自变量设计一个function该函数对关键字进行转换后其解释结果为待查的地址基于哈希表的考查点有哈希函数的设计沖突解决方法的选择及沖突处理过程的描述
第八章内部排序
内排是DS课程中最后一个重要的章节建立在此章之上的考题可以有多种类型填空选择判断乃至大型算法题但是归结到一点就是考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标(时间复杂度)能否了如指掌
这一章我们对重点的规纳将跟以上各章不同我们将从以下几个侧面来对排序一章进行不同的规纳以期能更全面的理解排序一章的总体结构及各种算法
从排序算法的种类来分本章主要阐述了以下几种排序方法插入选择交换归并计数等五种排序方法
其中在插入排序中又可分为直接插入折半插入路插入希尔排序这几种插入排序算法的最根本的不同点说到底就是根据什么规则寻找新元素的插入点直接插入是依次寻找折半插入是折半寻找希尔排序是通过控制每次参与排序的数的总范围由小到大的增量来实现排序效率提高的目的
交换排序又称冒泡排序在交换排序的基础上改进又可以得到快速排序快速排序的思想一语以敝之用中间数将待排数据组一分为二快速排序在处理的问题规模这个概念上与希尔有点相反快速排序是先处理一个较大规模然后逐渐把处理的规模降低最终达到排序的目的
选择排序相对于前面几种排序算法来说难度大一点具体来说它可以分为简单选择树选择堆排这三种方法的不同点是根据什么规则选取最小的数简单选择是通过简单的数组遍历方案确定最小数;树选择是通过锦标赛类似的思想让两数相比不断淘汰较大(小)者最终选出最小(大)数;而堆排序是利用堆这种数据结构的性质通过堆元素的删除调整等一系列操作将最小数选出放在堆顶堆排序中的堆建立堆调整是重要考点树选择排序也曾经在一些学校中的大型算法题中出现请大家注意
归并排序故名思义是通过归并这种操作完成排序的目的既然是归并就必须是两者以上的数据集合才可能实现归并所以在归并排序中关注最多的就是路归并算法思想比较简单有一点要铭记在心归并排序是稳定排序
基数排序是一种很特别的排序方法也正是由于它的特殊所以基数排序就比较适合于一些特别的场合比如扑克牌排序问题等基数排序又分为两种多关键字的排序(扑克牌排序)链式排序(整数排序)基数排序的核心思想也是利用基数空间这个概念将问题规模规范变小并且在排序的过程中只要按照基排的思想是不用进行关键字比较的这样得出的最终序列就是一个有序序列
本章各种排序算法的思想以及伪代码实现及其时间复杂度都是必须掌握的学习时要多注意规纳总结对比此外对于教材中的节要求必须熟记在理解的基础上记忆这一节几乎成为很多学校每年的必考点
[] [] [] []
![数据结构复习重点归纳（适于清华严版教材)[2]](/UploadFiles/6.jpg)