2022年数据结构复习重点归纳 .pdf

一、数据结构得章节结构及重点构成数据结构学科得章节划分基本上为:概论 ,线性表 ,栈与队列 ,串，多维数组与广义表，树与二叉树，图，查找，内排,外排,文件,动态存储分配 .对于绝大多数得学校而言 ,“外排 ,文件,动态存储分配” 三章基本上就是不考得 ,在大多数高校得计算机本科教学过程中,这三章也就是基本上不作讲授得。所以，大家在这三章上可以不必花费过多得精力,只要知道基本得概念即可。但就是，对于报考名校特别就是该校又有在试卷中对这三章进行过考核得历史，那么这部分朋友就要留意这三章了。按照以上我们给出得章节以及对后三章得介绍，数据结构得章节比重大致为：概论： 内容很少 ,概念简单 ,分数大多只有几分，有得学校甚至不考. 线性表 :基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题 .如果有，也就是与其它章节内容相结合. 栈与队列： 基础章节 ,容易出基本概念题，必考内容之一。而相联系进行考查。串：基础章节 ,概念较为简单 .专门针对于此章得大型算法设计题很少，较常见得就是根据KM 进行算法分析。多维数组及广义表 :基础章节， 基于数组得算法题也就是常见得,分数比例波动较大， 就是出题得“可选单元”或“侯补单元” .一般如果要出题 ,多数不会作为大题出 .数组常与“查找,排序”等章节结合来作为大题考查。树与二叉树 :重点难点章节， 各校必考章节。 各校在此章出题得不同之处在于,就是否在本章中出一到两道大得算法设计题。通过对多所学校得试卷分析,绝大多数学校在本章都曾有过出大型算法设计题得历史。图:重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题得题型设计。查找:重点难点章节 ,概念较多，联系较为紧密,容易混淆。出题时可以作为分析型题目给出,在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。排序:与查找一章类似 ,本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念得考查中，尤爱考各种排序算法得优劣比较此类得题。算法设计大题中，如果作为出题，那么常与数组结合来考查. 二、数据结构各章节重点勾划第章概述本章主要起到总领作用 ,为读者进行数据结构得学习进行了一些先期铺垫。大家主要注意以下几点 :数据结构得基本概念， 时间与空间复杂度得概念及度量方法,算法设计时得注意事项。本章考点不多 ,只要稍加注意理解即可。第一章 线性表作为线性结构得开篇章节,线性表一章在线性结构得学习乃至整个数据结构学科得学习中，其作用都就是不可低估得。在这一章,第一次系统性地引入链式存储得概念，链式存储概念将就是整个数据结构学科得重中之重,无论哪一章都涉及到了这个概念。总体来说 ,线性表一章可供考查得重要考点有以下几个方面：1、 线性表得相关基本概念，如：前驱、后继、表长、空表、首元结点,头结点，头指针等概念。2、3、线性表得顺序存储方式及其在具体语言环境下得两种不同实现 ：表空间得静态分配与动态分配。静态链表与顺序表得相似及不同之处。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 4、线性表得链式存储方式及以下几种常用链表得特点与运算：单链表、循环链表，双向链表，双向循环链表。其中,单链表得 归并算法、循环链表得归并算法、双向链表及双向循环链表得插入与删除算法等都就是较为常见得考查方式。此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出(可能就是顺序也可能就是倒序)得问题。在链表得小题型中 ,经常考到一些诸如：判表空得题。在不同得链表中，其判表空得方式就是不一样得，请大家注意. 5、 线性表得顺序存储及链式存储情况下，其不同得优缺点比较，即其各自适用得场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构得各自好处。第二章 栈与队列栈与队列，就是很多学习DS 得同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列,就是走向 DS 高手得一条必由之路。学习此章前,您可以问一下自己就是不就是已经知道了以下几点：1、 栈、队列得定义及其相关数据结构得概念，包括：顺序栈,链栈，共享栈 ,循环队列，链队等。栈与队列存取数据（请注意包括：存与取两部分)得特点。2、 递归算法。 栈与递归得关系 ，以及借助栈将递归转向于非递归得经典算法：n！阶乘问题,fib 数列问题 ,aoi 问题,背包问题 ,二叉树得递归与非递归遍历问题，图得深度遍历与栈得关系等 .其中，涉及到树与图得问题,多半会在树与图得相关章节中进行考查。3、栈得应用：数值表达式得求解，括号得配对等得原理,只作原理性了解 ,具体要求考查此为题目得算法设计题不多. 4、 循环队列中判队空、队满条件，循环队列中入队与出队算法。如果您已经对上面得几点了如指掌，栈与队列一章可以不瞧书了。注意，我说得就是可以不瞧书，并不就是可以不作题哦。第三章 串经历了栈一章得痛苦煎熬后,终于迎来了串一章得柳暗花明。串，在概念上就是比较少得一个章节 ,也就是最容易自学得章节之一，但正如每个过来人所了解得,KM 算法就是这一章得重要关隘 ,突破此关隘后 ,走过去又就是一马平川得大好DS 山河了，呵呵。串一章需要攻破得主要堡垒有：1、 串得基本概念 ,串与线性表得关系 (串就是其元素均为字符型数据得特殊线性表），空串与空格串得区别，串相等得条件。2、 串得基本操作，以及这些基本函数得使用，包括：取子串,串连接 ,串替换，求串长等等。运用串得基本操作去完成特定得算法就是很多学校在基本操作上得考查重点。3、 顺序串与链串及块链串得区别与联系，实现方式. 4、KP 算法思想。KMP 中 next 数组以及 nextvl 数组得求法。 明确传统模式匹配算法得不足 ,明确 net 数组需要改进之外 .其中,理解算法就是核心 ,会求数组就是得分点。不用我多说 ,这一节内容就是本章得重中之重。可能进行得考查方式就是:求ext 与etv数组值，根据求得得nx或 nexval 数组值给出运用 KP 算法进行匹配得匹配过程。第四章 数组与广义表学过程序语言得朋友 ,数组得概念我们已经不就是第一次见到了，应该已经“一回生，二回熟”了，所以，在概念上 ,不会存在太大障碍 .但作为考研课程来说 ,本章得考查重点可能与大学里得程序语言所关注得不太一样,下面会作介绍。 广义表得概念 ,就是数据结构里第一次出现得 .它就是线性表或表元素得有限序列，构成该结构得每个子表或元素也就是线性结构得，所以，这一章也归入线性结构中。本章得考查重点有：1、 多维数组中某数组元素得poition 求解。一般就是给出数组元素得首元素地址与每个元素占用得地址空间并组给出多维数组得维数，然后要求您求出该数组中得某个元素名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 所在得位置。2、 明确按行存储与按列存储得区别与联系,并能够按照这两种不同得存储方式求解1 中类型得题 . 3、 将特殊矩阵中得元素按相应得换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩阵 ,具有某种特点得稀疏矩阵等。 熟悉稀疏矩阵得三种不同存储方式:三元组，带辅助行向量得二元组 ,十字链表存储。掌握将稀疏矩阵得三元组或二元组向十字链表进行转换得算法。4、 广义表得概念，特别应该明确表头与表尾得定义。这一点，就是理解整个广义表一节算法得基础。 近来,在一些学校中， 出现了这样一种题目类型:给出对某个广义表L 若干个求了若干次得取头与取尾操作后得串值，要求求出原广义表L。大家要留意。5、 与广义表有关得递归算法。由于广义表得定义就就是递归得，所以，与广义表有关得算法也常就是递归形式得。比如：求表深度,复制广义表等。这种题目，可以根据不同角度广义表得表现形式运用两种不同得方式解答：一就是把一个广义表瞧作就是表头与表尾两部分 ,分别对表头与表尾进行操作； 二就是把一个广义表瞧作就是若干个子表,分别对每个子表进行操作。第五章 树与二叉树从对线性结构得研究过度到对树形结构得研究，就是数据结构课程学习得一次跃变,此次跃变完成得好坏，将直接关系到您到实际得考试中就是否可以拿到高分，而这所有得一切,将最终影响您得专业课总分。所以，树这一章得重要性，已经不说自明了.总体来说 ,树一章得知识点包括 :二叉树得概念、 性质与存储结构 ,二叉树遍历得三种算法 （递归与非递归） ,在三种基本遍历算法得基础上实现二叉树得其它算法，线索二叉树得概念与线索化算法以及线索化后得查找算法，最优二叉树得概念、 构成与应用 ,树得概念与存储形式，树与森林得遍历算法及其与二叉树遍历算法得联系,树与森林与二叉树得转换。下面我们来瞧考试中对以上知识得主要考查方法：1、二叉树得概念、性质与存储结构考查方法可有：直接考查二叉树得定义，让您说明二叉树与普通双分支树得区别；，普通二叉树得五个性质：第 i 层得最多结点数，深度为k 得二叉树得最多结点数， n0=2+1 得性质， n 个结点得完全二叉树得深度，顺序存储二叉树时孩子结点与父结点之间得换算关系（左为: ,右为:i+1)。二叉树得顺序存储与二叉链表存储得各自优缺点及适用场合，二叉树得三叉链表表示方法. 2、二叉树得三种遍历算法这一知识点掌握得好坏 ,将直接关系到树一章得算法能否理解,进而关系到树一章得算法设计题能否顺利完成。二叉树得遍历算法有三种:先序,中序与后序。其划分得依据就是视其每个算法中对根结点数据得访问顺序而定。不仅要熟练掌握三种遍历得递归算法,理解其执行得实际步骤，并且应该熟练掌握三种遍历得非递归算法。由于二叉树一章得很多算法，可以直接根据三种递归算法改造而来（比如：求叶子个数）,所以，掌握了三种遍历得非递归算法后，对付诸如： “利用非递归算法求二叉树叶子个数 这样得题目就下笔如有神了.我会在另一篇系列文章（:bs、aa、ibbs、ll？、 、 、 =2&b0)里给出三种遍历得递归与非递归算法得背记版,到时请大家一定熟记。3、 可在三种遍历算法得基础上改造完成得其它二叉树算法：求叶子个数,求二叉树结点总数，求度为 1 或度为 2 得结点总数，复制二叉树，建立二叉树，交换左右子树,查找值为 n 得某个指定结点，删除值为n 得某个指定结点 ,诸如此类等等等等。如果您可以熟练掌握二叉树得递归与非递归遍历算法,那么解决以上问题就就是小菜一碟了。4、 线索二叉树 :线索二叉树得引出 ,就是为避免如二叉树遍历时得递归求解。众所周知,递归虽然形式上比较好理解，但就是消耗了大量得内存资源，如果递归层次一多,势必带来资源耗尽得危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 叉树,应该掌握：线索化得实质,三种线索化得算法 ,线索化后二叉树 得遍历算法 ，基本线索二叉树得其它算法问题(如:查找某一类线索二叉树中指定结点得前驱或后继结点就就是一类常考题）。？、：最优二叉树就是为了解决特定问题引出得特殊二叉树结构，它得前提就是给二叉树得每条边赋予了权值，这样形成得二叉树按权相加之与就是最小得 .最优二叉树一节 ,直接考查算法源码得很少,一般就是给您一组数据 ,要求您建立基于这组数据得最优二叉树，并求出其最小权值之与，此类题目不难，属送分题。6、二叉搜索树（二叉排序树) B 树与 +数同样掌握 B 树得构建，添加节点与删除节点等操作8、树与森林 :二叉树就是一种特殊得树，这种特殊不仅仅在于其分支最多为以及其它特征，一个最重要得特殊之处就是在于：二叉树就是有序得 !即:二叉树得左右孩子就是不可交换得 ,如果交换了就成了另外一棵二叉树,这样交换之后得二叉树与原二叉树我们认为就是不相同得两棵二叉树。但就是,对于普通得双分支树而言，不具有这种性质。树与森林得遍历，不像二叉树那样丰富，她们只有两种遍历算法:先根与后根（对于森林而言称作：先序与后序遍历） 。在难度比较大得考试中，也有基于此二种算法得基础上再进行扩展要求您利用这两种算法设计其它算法得,但一般院校很少有这种考法,最多只就是要求您根据先根或后根写出她们得遍历序列。此二者得先根与后根遍历与二叉树中得遍历算法就是有对应关系得:先根遍历对应二叉树得先序遍历，而后根遍历对应二叉树得中序遍历 .这一点成为很多学校得考点,考查得方式不一而足， 有得直接考此句话， 有得就是先让您求解遍历序列然后回答这个问题。二叉树、树与森林之所以能有以上得对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放她得左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表）,而森林也就是利用二叉链表存储孩子及兄弟.树一章，处处就是重点 ,道道就是考题，大家务必个个过关. 第六章 图如果说，从线性结构向树形结构研究得转变，就是数据结构学科对数据组织形式研究得一次升华，那么从树形结构得研究转到图形结构得研究，则进一步让我们瞧到了数据结构对于解决实际问题得重大推动作用。图这一章得特点就是:概念繁多，与离散数学中图得概念联系紧密 ,算法复杂 ,极易被考到，且容易出大题,尤其就是名校 ,作为考研课程，如果不考查树与图两章得知识,几乎就是不可想像得.下面我们瞧一下图这一章得主要考点以及这些考点得考查方式：1、考查有关图得基本概念问题:这些概念就是进行图一章学习得基础，与这些概念相联系得相关计算题也应该掌握。2、 考查图得几种存储形式：在考查时，有得学校就是给出一种存储形式，要求考生用算法或手写出与给定得结构相对应得该图得另一种存储形式。3、 考查图得两种遍历算法：深度遍历与广度遍历 深度遍历与广度遍历就是图得两种基本得遍历算法 ,其中深度遍历相当于二叉树中得先序遍历,而广度遍历相当于二叉树中得层次遍历、 这两个算法对图一章得重要性等同于“先序、中序、后序遍历”对于二叉树一章得重要性。在考查时，图一章得算法设计题常常就是基于这两种基本得遍历算法而设计得 ,比如： “求最长得最短路径问题”与“判断两顶点间就是否存在长为K 得简单路径问题” ,就分别用到了广度遍历与深度遍历算法. 、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 考查时，一般不要求写出算法源码,而就是要求根据这两种最小生成树得算法思想写出其构造过程及最终生成得最小生成树. 、，一就是无前趋得顶点优先算法,二就是无后继得顶点优先算法。换句话说，一种就是“从前向后”得排序,一种就是“从后向前”排。当然，后一种排序出来得结果就是“逆拓扑有序”得。6、：这个问题就是图一章得难点问题。 理解关键路径得关键有三个方面：一就是何谓关键路径 ,二就是最早时间就是什么意思、如何求,三就是最晚时间就是什么意思、如何求。简单地说 ,最早时间就是通过“从前向后”得方法求得,而最晚时间就是通过“从后向前”得方法求解得，并且，要想求最晚时间必须就是在所有得最早时间都已经求出来之后才能进行。这个问题拿来直接考算法源码得不多,一般就是要求按照书上得算法描述求解得过程与步骤。在实际设计关键路径得算法时，还应该注意以下这一点：采用邻接表得存储结构， 求最早时间与最晚时间要采用不同得处理方法，即:在算法初始时 ,应该首先将所有顶点得最早时间全部置为0.关键路径问题就是工程进度控制得重要方法,具有很强得实用性。、:与关键路径问题并称为图一章得两只拦路虎。概念理解就是比较容易得,关键就是算法得理解。 最短路径问题分为两种 :一就是求从某一点出发到其余各点得最短路径；二就是求图中每一对顶点之间得最短路径。这个问题也具有非常实用得背景特色 ,一个典型得应该就就是旅游景点及旅游路线得选择问题。解决第一个问题用DIJSKTRA 算法，解决第二个问题用FLYD 算法。注意区分。* *注意区分关键路径问题与最短路径问题* 第七章 查找在不少数据结构得教材中,就是把查找与排序放入高级数据结构中得.应该说,查找与排序两章就是前面我们所学得知识得综合运用,用到了树、也用到了链表等知识，对这些数据结构某一方面得运用就构成了查找与排序。现实生活中,search几乎无处不在 ,特别就是现在得网络时代 ,万事离不开 sarch，小到文档内文字得搜索，大到NTER上得搜索，ah 占据了我们上网得大部分时间.在复习这一章得知识时，您需要先弄清楚以下几个概念：关键字、主关键字、次关键字得含义；静态查找与动态查找得含义及区别;平均查找长度A得概念及在各种查找算法中得计算方法与计算结果,特别就是一些典型结构得 ASL 值，应该记住。在DS 得教材中，一般将searh 分为三类： 1t,在顺序表上得查找 ;2nd,在树表上得查找 ;3d,在哈希表上得查找。 下面详细介绍其考查知识点及考查方式：1、 线性表上得查找 :主要分为三种线性结构：顺序表,有序顺序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比较。对于第三种索引结构，我们采用索引查找算法。考生需要注意这三种表下得ASL 值以及三种算法得实现。其中， 二分查找还要特别注意适用条件以及其递归实现方法。、 树表上得查找 :这就是本章得重点与难点。由于这一节介绍得内容就是使用树表进行得查找 ,所以很容易与树一间得某些概念相混淆.本节内容与树一章得内容有联系,但也有很多不同，应注意规纳。树表主要分为以下几种：，,键树。其中 ,尤以前两种结构为重，也有部分名校偏爱考树得。由于二叉排序树与平衡二叉树就是一种特殊得二叉树， 所以与二叉树得联系就更为紧密,二叉树一章学好了 ,这里也就不难了。 二叉排序树 ,简言之，就就是“左小右大” ,它得中序遍历结果就是一个递增得有序序列。平衡二叉树就是二叉排序树得优化，其本质也就是一种二叉排序树，只不过，平衡二叉树对左右子树得深度有了限定：深度之差得绝对值不得大于1。对于二叉排序树，“判断某棵二叉树就是否二叉排序树” 这一算法经常被考到， 可用递归 ,也可以用非递归 .平衡二叉树得建立也就是一个常考点，但该知识点归根结底还就是关注得平衡二叉树得四种调整算法,所以应该掌握平衡二叉树得四种调整算法，调整得一个参照就是 :调整前后得中序遍名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 历结果相同 .B 树就是报考名校得同学应该关注得焦点之一。键树也称字符树，特别适用于查找英文单词得场合。一般不要求能完整描述算法源码，多就是根据算法思想建立键树及描述其大致查找过程. 、:哈希一词，就是外来词 ,译自“hash一词，意为 :散列或杂凑得意思。哈希表查找得基本思想就是：根据当前待查找数据得特征,以记录关键字为自变量，设计一个fncion，该函数对关键字进行转换后,其解释结果为待查得地址。基于哈希表得考查点有:哈希函数得设计，冲突解决方法得选择及冲突处理过程得描述。第八章内部排序内排就是 S课程中最后一个重要得章节,建立在此章之上得考题可以有多种类型:填空，选择,判断乃至大型算法题。但就是，归结到一点，就就是考查您对书本上得各种排序算法及其思想以及其优缺点与性能指标(时间复杂度）能否了如指掌。 这一章 ,我们对重点得规纳将跟以上各章不同。我们将从以下几个侧面来对排序一章进行不同得规纳,以期能更全面得理解排序一章得总体结构及各种算法。从排序算法得种类来分，本章主要阐述了以下几种排序方法：其中,在插入排序中又可分为：直接插入、折半插入、2 路插入、希尔排序。这几种插入排序算法得最根本得不同点,说到底就就是根据什么规则寻找新元素得插入点。直接插入就是依次寻找，折半插入就是折半寻找.希尔排序，就是通过控制每次参与排序得数得总范围“由小到大”得增量来实现排序效率提高得目得。* * ，在交换排序得基础上改进又可以得到快速排序。快速排序得思想，一语以敝之：用中间数将待排数据组一分为二.快速排序 ,在处理得“问题规模”这个概念上， 与希尔有点相反， 快速排序 ,就是先处理一个较大规模 ,然后逐渐把处理得规模降低，最终达到排序得目得. ,相对于前面几种排序算法来说，难度大一点.具体来说，它可以分为 :简单选择、树选择、堆排。这三种方法得不同点就是,根据什么规则选取最小得数。简单选择,就是通过简单得数组遍历方案确定最小数；树选择，就是通过“锦标赛”类似得思想,让两数相比,不断淘汰较大（小 )者，最终选出最小 (大）数 ;而堆排序，就是利用堆这种数据结构得性质,通过堆元素得删除、调整等一系列操作将最小数选出放在堆顶.堆排序中得堆建立、堆调整就是重要考点。树选择排序，也曾经在一些学校中得大型算法题中出现，请大家注意。，故名思义 ,就是通过“归并”这种操作完成排序得目得，既然就是归并就必须就是两者以上得数据集合才可能实现归并。所以，在归并排序中,关注最多得就就是算法思想比较简单，就是一种很特别得排序方法，也正就是由于它得特殊,所以，基数排序就比较适合于一些特别得场合 ,比如扑克牌排序问题等。基数排序，又分为两种：多关键字得排序(扑克牌排序 )，链式排序（整数排序） 。基数排序得核心思想也就是利用“基数空间”这个概念将问题规模规范、变小,并且，在排序得过程中，只要按照基排得思想,就是不用进行关键字比较得，这样得出得最终序列就就是一个有序序列。本章各种排序算法得思想以及伪代码实现，及其时间复杂度都就是必须掌握得，学习时要多注意规纳、总结、对比 .此外，对于教材中得、节，要求必须熟记,在理解得基础上记忆 ,这一节几乎成为很多学校每年得必考点. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 堆基于完全二叉树 ,又可分为大顶堆与小顶堆，掌握堆得构建，与删除节点操作，如删除顶点时先将最后一个叶子节点与顶点交换位置,然后进行再排序、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -