资源预览内容
第1页 / 共32页
第2页 / 共32页
第3页 / 共32页
第4页 / 共32页
第5页 / 共32页
第6页 / 共32页
第7页 / 共32页
第8页 / 共32页
第9页 / 共32页
第10页 / 共32页
亲,该文档总共32页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
专业好文档数据结构复习重点归纳一、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为:概论,线性表,栈和队列,串,多维数组和广义表,树和二叉树,图,查找,内排,外排,文件,动态存储分配。对于绝大多数的学校而言,“外排,文件,动态存储分配”三章基本上是不考的,在大多数高校的计算机本科教学过程中,这三章也是基本上不作讲授的。所以,大家在这三章上可以不必花费过多的精力,只要知道基本的概念即可。但是,对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史,那么这部分朋友就要留意这三章了。按照以上我们给出的章节以及对后三章的介绍,数据结构的章节比重大致为:概论:内容很少,概念简单,分数大多只有几分,有的学校甚至不考。线性表:基础章节,必考内容之一。考题多数为基本概念题,名校考题中,鲜有大型算法设计题。如果有,也是与其它章节内容相结合。栈和队列:基础章节,容易出基本概念题,必考内容之一。而栈常与其它章节配合考查,也常与递归等概念相联系进行考查。串 :基础章节,概念较为简单。专门针对于此章的大型算法设计题很少,较常见的是根据KMP进行算法分析。多维数组及广义表 :基础章节,基于数组的算法题也是常见的,分数比例波动较大,是出题的“可选单元”或“侯补单元”。一般如果要出题,多数不会作为大题出。数组常与“查找,排序”等章节结合来作为大题考查。树和二叉树 :重点难点章节,各校必考章节。各校在此章出题的不同之处在于,是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析,绝大多数学校在本章都曾有过出大型算法设计题的历史。图 :重点难点章节,名校尤爱考。如果作为重点来考,则多出现于分析与设计题型当中,可与树一章共同构成算法设计大题的题型设计。查找 :重点难点章节,概念较多,联系较为紧密,容易混淆。出题时可以作为分析型题目给出,在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查,也可以与树一章结合来考查。排序 :与查找一章类似,本章同属于重点难点章节,且概念更多,联系更为紧密,概念之间更容易混淆。在基本概念的考查中,尤爱考各种排序算法的优劣比较此类的题。算法设计大题中,如果作为出题,那么常与数组结合来考查。二、数据结构各章节重点勾划:第0章概述本章主要起到总领作用,为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点:数据结构的基本概念,时间和空间复杂度的概念及度量方法,算法设计时的注意事项。本章考点不多,只要稍加注意理解即可。第一章线性表作为线性结构的开篇章节,线性表一章在线性结构的学习乃至整个数据结构学科的学习中,其作用都是不可低估的。在这一章,第一次系统性地引入链式存储的概念,链式存储概念将是整个数据结构学科的重中之重,无论哪一章都涉及到了这个概念。总体来说,线性表一章可供考查的重要考点有以下几个方面:1.线性表的相关基本概念,如:前驱、后继、表长、空表、首元结点,头结点,头指针等概念。2.线性表的结构特点,主要是指:除第一及最后一个元素外,每个结点都只有一个前趋和只有一个后继。3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现:表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。4.线性表的链式存储方式及以下几种常用链表的特点和运算:单链表、循环链表,双向链表,双向循环链表。其中,单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。此外,近年来在不少学校中还多次出现要求用递归算法实现单链表输出(可能是顺序也可能是倒序)的问题。在链表的小题型中,经常考到一些诸如:判表空的题。在不同的链表中,其判表空的方式是不一样的,请大家注意。5.线性表的顺序存储及链式存储情况下,其不同的优缺点比较,即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。第二章栈与队列栈与队列,是很多学习DS的同学遇到第一只拦路虎,很多人从这一章开始坐晕车,一直晕到现在。所以,理解栈与队列,是走向DS高手的一条必由之路,。学习此章前,你可以问一下自己是不是已经知道了以下几点:1.栈、队列的定义及其相关数据结构的概念,包括:顺序栈,链栈,共享栈,循环队列,链队等。栈与队列存取数据(请注意包括:存和取两部分)的特点。2.递归算法。栈与递归的关系,以及借助栈将递归转向于非递归的经典算法:n!阶乘问题,fib数列问题,hanoi问题,背包问题,二叉树的递归和非递归遍历问题,图的深度遍历与栈的关系等。其中,涉及到树与图的问题,多半会在树与图的相关章节中进行考查。3.栈的应用:数值表达式的求解,括号的配对等的原理,只作原理性了解,具体要求考查此为题目的算法设计题不多。4.循环队列中判队空、队满条件,循环队列中入队与出队算法。如果你已经对上面的几点了如指掌,栈与队列一章可以不看书了。注意,我说的是可以不看书,并不是可以不作题哦。第三章串经历了栈一章的痛苦煎熬后,终于迎来了串一章的柳暗花明。串,在概念上是比较少的一个章节,也是最容易自学的章节之一,但正如每个过来人所了解的,KMP算法是这一章的重要关隘,突破此关隘后,走过去又是一马平川的大好DS山河了,呵呵。串一章需要攻破的主要堡垒有:1.串的基本概念,串与线性表的关系(串是其元素均为字符型数据的特殊线性表),空串与空格串的区别,串相等的条件2.串的基本操作,以及这些基本函数的使用,包括:取子串,串连接,串替换,求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。3.顺序串与链串及块链串的区别和联系,实现方式。4.KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足,明确next数组需要改进之外。其中,理解算法是核心,会求数组是得分点。不用我多说,这一节内容是本章的重中之重。可能进行的考查方式是:求next和nextval数组值,根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。第四章数组与广义表学过程序语言的朋友,数组的概念我们已经不是第一次见到了,应该已经“一回生,二回熟”了,所以,在概念上,不会存在太大障碍。但作为考研课程来说,本章的考查重点可能与大学里的程序语言所关注的不太一样,下面会作介绍。广义表的概念,是数据结构里第一次出现的。它是线性表或表元素的有限序列,构成该结构的每个子表或元素也是线性结构的,所以,这一章也归入线性结构中。本章的考查重点有:1.多维数组中某数组元素的position求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数,然后要求你求出该数组中的某个元素所在的位置。2.明确按行存储和按列存储的区别和联系,并能够按照这两种不同的存储方式求解1中类型的题。3.将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括:对称矩阵,三角矩阵,具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式:三元组,带辅助行向量的二元组,十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。4.广义表的概念,特别应该明确表头与表尾的定义。这一点,是理解整个广义表一节算法的基础。近来,在一些学校中,出现了这样一种题目类型:给出对某个广义表L若干个求了若干次的取头和取尾操作后的串值,要求求出原广义表L。大家要留意。5.与广义表有关的递归算法。由于广义表的定义就是递归的,所以,与广义表有关的算法也常是递归形式的。比如:求表深度,复制广义表等。这种题目,可以根据不同角度广义表的表现形式运用两种不同的方式解答:一是把一个广义表看作是表头和表尾两部分,分别对表头和表尾进行操作;二是把一个广义表看作是若干个子表,分别对每个子表进行操作。第五章树与二叉树从对线性结构的研究过度到对树形结构的研究,是数据结构课程学习的一次跃变,此次跃变完成的好坏,将直接关系到你到实际的考试中是否可以拿到高分,而这所有的一切,将最终影响你的专业课总分。所以,树这一章的重要性,已经不说自明了。总体来说,树一章的知识点包括:二叉树的概念、性质和存储结构,二叉树遍历的三种算法(递归与非递归),在三种基本遍历算法的基础上实现二叉树的其它算法,线索二叉树的概念和线索化算法以及线索化后的查找算法,最优二叉树的概念、构成和应用,树的概念和存储形式,树与森林的遍历算法及其与二叉树遍历算法的联系,树与森林和二叉树的转换。下面我们看一下图这一章的主要考点以及这些考点的考查方式:1.考查有关图的基本概念问题:这些概念是进行图一章学习的基础,这一章的概念包括:图的定义和特点,无向图,有向图,入度,出度,完全图,生成子图,路径长度,回路,(强)连通图,(强)连通分量等概念。与这些概念相联系的相关计算题也应该掌握。2.考查图的几种存储形式:图的存储形式包括:邻接矩阵,(逆)邻接表,十字链表及邻接多重表。在考查时,有的学校是给出一种存储形式,要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。3.考查图的两种遍历算法:深度遍历和广度遍历深度遍历和广度遍历是图的两种基本的遍历算法,这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时,图一章的算法设计题常常是基于这两种基本的遍历算法而设计的,比如:“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”,就分别用到了广度遍历和深度遍历算法。4.生成树、最小生成树的概念以及最小生成树的构造:PRIM算法和KRUSKAL算法。考查时,一般不要求写出算法源码,而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。5.拓扑排序问题:拓扑排序有两种方法,一是无前趋的顶点优先算法,二是无后继的顶点优先算法。换句话说,一种是“从前向后”的排序,一种是“从后向前”排。当然,后一种排序出来的结果是“逆拓扑有序”的。6.关键路径问题:这个问题是图一章的难点问题。理解关键路径的关键有三个方面:一是何谓关键路径,二是最早时间是什么意思、如何求,三是最晚时间是什么意思、如何求。简单地说,最早时间是通过“从前向后”的方法求的,而最晚时间是通过“从后向前”的方法求解的,并且,要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。这个问题拿来直接考算法源码的不多,一般是要求按照书上的算法描述求解的过程和步骤。在实际设计关键路径的算法时,还应该注意以下这一点:采用邻接表的存储结构,求最早时间和最晚时间要采用不同的处理方法,即:在算法初始时,应该首先将所有顶点的最早时间全部置为0。关键路径问题是工程进度控制的重要方法,具有很强的实用性。7.最短路径问题:与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的,关键是算法的理解。最短路径问题分为两种:一是求从某一点出发到其余各点的最短路径;二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色,一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法,解决第二个问题用FLOYD算法。注意区分。第七章查找在不少数据结构的教材中,是把查找与排序放入高级数据结构中的。应该说,查找和排序两章是前面我们所学的知识的综合运用,用到了树、也用到了链表等知识,对这些数据结构某一方面的运用就构成了查找和排序。现实生活中,search几乎无处不在,特别是现在的网络时代,万事离不开search,小到文档内文字的搜索,大到INTERNET上的搜索,search占据了我们上网的大部分时间。在
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号