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

《数据结构复习重点归纳15761.pdf》由会员分享，可在线阅读，更多相关《数据结构复习重点归纳15761.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.一、数据构造的章节构造及重点构成 数据构造学科的章节划分根本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，排，外排，文件，动态存储分配。对于绝大多数的学校而言，外排，文件，动态存储分配三章根本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是根本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道根本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进展过考核的历史，则这局部朋友就要留意这三章了。按照以上我们给出的章节以及对后三章的介绍，数据构造的章节比重大致为：概论：容很少，概念简单，分数大多只有几分，有的学校甚至不考。线性表：根

2、底章节，必考容之一。考题多数为根本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节容相结合。栈和队列：根底章节，容易出根本概念题，必考容之一。而相联系进展考察。串：根底章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据 KMP 进展算法分析。多维数组及广义表：根底章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的可选单元或侯补单元。一般如果要出题，多数不会作为大题出。数组常与查找，排序等章节结合来作为大题考察。树和二叉树：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数

3、学校在本章都曾有过出大型算法设计题的历史。图：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。查找：重点难点章节，概念较多，联系较为严密，容易混淆。出题时可以作为分析型题目给出，在根本概念型题目中也较为常见。算法设计型题中可以数组结合来考察，也可以与树一章结合来考察。排序：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为严密，概念之间更容易混淆。在根本概念的考察中，尤爱考各种排序算法的优劣比拟此类的题。算法设计大题中，如果作为出题，则常与数组结合来考察。二、数据构造各章节重点勾划 第 0 章概述 本章主要起到总领作

4、用，为读者进展数据构造的学习进展了一些先期铺垫。大家主要注意以下几点：数据构造的根本概念，时间和空间复杂度的概念及度量方法，算法设计时的考前须知。本章考点不多，只要稍加注意理解即可。第一章 线性表 作为线性构造的开篇章节，线性表一章在线性构造的学习乃至整个数据构造学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据构造学科的重中之重，无论哪一章都涉及到了这个概念。总体来说，线性表一章可供考察的重要考点有以下几个方面：1.线性表的相关根本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。2.3.线性表的顺序存储方式及其在具体语言

5、环境下的两种不同实现：表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。.4.线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考察方式。此外，近年来在不少学校中还屡次出现要求用递归算法实现单链表输出可能是顺序也可能是倒序的问题。在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是不一样的，请大家注意。5.线性表的顺序存储及链式存储情况下，其不同的优缺点比拟，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾

6、指针而不设置头指针以及索引存储构造的各自好处。第二章 栈与队列 栈与队列，是很多学习 DS 的同学遇到第一只拦路虎，很多人从这一章开场坐晕车，一直晕到现在。所以，理解栈与队列，是走向 DS 高手的一条必由之路。学习此章前，你可以问一下自己是不是已经知道了以下几点：1.栈、队列的定义及其相关数据构造的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据请注意包括：存和取两局部的特点。2.递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib 数列问题，Hanoi 问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树

7、与图的问题，多半会在树与图的相关章节中进展考察。3.栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考察此为题目的算法设计题不多。4.循环队列中判队空、队满条件，循环队列中入队与出队算法。如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。第三章 串 经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。串，在概念上是比拟少的一个章节，也是最容易自学的章节之一，但正如每个过来人所了解的，KMP 算法是这一章的重要关隘，突破此关隘后，走过去又是一马平川的大好 DS 山河了，呵呵。串一章需要攻破的主要堡垒有：1.串的根本概

8、念，串与线性表的关系串是其元素均为字符型数据的特殊线性表，空串与空格串的区别，串相等的条件。2.串的根本操作，以及这些根本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的根本操作去完成特定的算法是很多学校在根本操作上的考察重点。3.顺序串与链串及块链串的区别和联系，实现方式。4.KMP 算法思想。KMP 中 ne*t 数组以及 ne*tval 数组的求法。明确传统模式匹配算法的缺乏，明确 ne*t 数组需要改良之外。其中，理解算法是核心，会求数组是得分点。不用我多说，这一节容是本章的重中之重。可能进展的考察方式是：求 ne*t 和 ne*tval 数组值，根据求得的 ne*t 或

9、 ne*tval 数组值给出运用 KMP 算法进展匹配的匹配过程。第四章 数组与广义表 学过程序语言的朋友，数组的概念我们已经不是第一次见到了，应该已经一回生，二回熟了，所以，在概念上，不会存在太大障碍。但作为考研课程来说，本章的考察重点可能与大学里的程序语言所关注的不太一样，下面会作介绍。广义表的概念，是数据构造里第一次出现的。它是线性表或表元素的有限序列，构成该构造的每个子表或元素也是线性构造的，所以，这一章也归入线性构造中。本章的考察重点有：1.多维数组中*数组元素的 position 求解。一般是给出数组元素的首元素地址和每个元.素占用的地址空间并组给出多维数组的维数，然后要求你求出该

10、数组中的*个元素所在的位置。2.明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解 1 中类型的题。3.将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩阵，具有*种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进展转换的算法。4.广义表的概念，特别应该明确表头与表尾的定义。这一点，是理解整个广义表一节算法的根底。近来，在一些学校中，出现了这样一种题目类型：给出对*个广义表 L 假设干个求了假设干次的取头和取尾操作后的串值，要求求出原广义表 L。大家要留意。5.

11、与广义表有关的递归算法。由于广义表的定义就是递归的，所以，与广义表有关的算法也常是递归形式的。比方：求表深度，复制广义表等。这种题目，可以根据不同角度广义表的表现形式运用两种不同的方式解答：一是把一个广义表看作是表头和表尾两局部，分别对表头和表尾进展操作；二是把一个广义表看作是假设干个子表，分别对每个子表进展操作。第五章 树与二叉树 从对线性构造的研究过度到对树形构造的研究，是数据构造课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这所有的一切，将最终影响你的专业课总分。所以，树这一章的重要性，已经不说自明了。总体来说，树一章的知识点包括：二叉树的概念、

12、性质和存储构造，二叉树遍历的三种算法递归与非递归，在三种根本遍历算法的根底上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。下面我们来看考试中对以上知识的主要考察方法：1.二叉树的概念、性质和存储构造考察方法可有：直接考察二叉树的定义，让你说明二叉树与普通双分支树的区别；，普通二叉树的五个性质：第 i 层的最多结点数，深度为 k 的二叉树的最多结点数，n0=n2+1 的性质，n 个结点的完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算关系

13、左为：2*i，右为：2*i+1。二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。2.二叉树的三种遍历算法这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来比方：求叶子个数，所以，掌握了三种遍历的非递归算法后，对付诸如：利用非递归算法求二叉树 叶 子 个 数 这 样 的 题

14、目 就 下 笔 如 有 神 了。我 会 在 另 一 篇 系 列 文 章bbs.kaoyan./ibbs.dllb.3&bp=2&bt=0里给出三种遍历的递归和非递归算法的背记版，到时请大家一定熟记。3.可在三种遍历算法的根底上改造完成的其它二叉树算法：求叶子个数，求二叉树结点总数，求度为 1 或度为 2 的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为 n 的*个指定结点，删除值为 n 的*个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，则解决以上问题就是小菜一碟了。4.线索二叉树：线索二叉树的引出，是为防止如二叉树遍历时的递归求解。众所周知，.递归虽然

15、形式上比拟好理解，但是消耗了大量的存资源，如果递归层次一多，势必带来资源耗尽的危险，为了防止此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，根本线索二叉树的其它算法问题如：查找*一类线索二叉树中指定结点的前驱或后继结点就是一类常考题。？5.：最优二叉树是为了解决特定问题引出的特殊二叉树构造，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考察算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题。6.二叉搜索树

16、(二叉排序树)B 树和 B+数同样掌握 B 树的构建,添加节点与删除节点等操作 8.树与森林：二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2 以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树我们认为是不一样的两棵二叉树。但是，对于普通的双分支树而言，不具有这种性质。树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根对于森林而言称作：先序与后序遍历。在难度比拟大的考试中，也有基于此二种算法的根底上再进展扩展要求你利用这两种算法设计其它算法的，但一般院校很少有这种考法

17、，最多只是要求你根据先根或后根写出他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。这一点成为很多学校的考点，考察的方式不一而足，有的直接考此句话，有的是先让你求解遍历序列然后答复这个问题。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟称孩子兄弟链表，而森林也是利用二叉链表存储孩子及兄弟。树一章，处处是重点，道道是考题，大家务必个个过关。第六章 图 如果说，从线性构造向树形构造研究的转变，是数据构造学科对数据组织形式研究的一次升

18、华，则从树形构造的研究转到图形构造的研究，则进一步让我们看到了数据构造对于解决实际问题的重大推动作用。图这一章的特点是：概念繁多，与离散数学中图的概念联系严密，算法复杂，极易被考到，且容易出大题，尤其是名校，作为考研课程，如果不考察树与图两章的知识，几乎是不可想像的。下面我们看一下列图这一章的主要考点以及这些考点的考察方式：1.考察有关图的根本概念问题：这些概念是进展图一章学习的根底，与这些概念相联系的相关计算题也应该掌握。2.考察图的几种存储形式：在考察时，有的学校是给出一种存储形式，要求考生用算法或手写出与给定的构造相对应的该图的另一种存储形式。3.考察图的两种遍历算法：深度遍历和广度遍历

19、深度遍历和广度遍历是图的两种根本的遍历算法，其中深度遍历相当于二叉树中的先序遍历,而广度遍历相当于二叉树中的层次遍历.这两个算法对图一章的重要性等同于先序、中序、后序遍历对于二叉树一章的重要性。在考察时，图一章的算法设计题常常是基于这两种根本的遍历算法而设计的，.比方：求最长的最短路径问题和判断两顶点间是否存在长为 K 的简单路径问题，就分别用到了广度遍历和深度遍历算法。4.考察时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。5.，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是从前向后的排序，一种是从后向前排。当然，

20、后一种排序出来的结果是逆拓扑有序的。6.：这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过从前向后的方法求的，而最晚时间是通过从后向前的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进展。这个问题拿来直接考算法源码的不多，一般是要求按照书上的算法描述求解的过程和步骤。在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储构造，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为0。关键路径问题是工

21、程进度控制的重要方法，具有很强的实用性。7.：与关键路径问题并称为图一章的两只拦路虎。概念理解是比拟容易的，关键是算法的理解。最短路径问题分为两种：一是求从*一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用 DIJSKTRA 算法，解决第二个问题用 FLOYD 算法。注意区分。*注意区分关键路径问题与最短路径问题*第七章 查找 在不少数据构造的教材中，是把查找与排序放入高级数据构造中的。应该说，查找和排序两章是前面我们所学的知识的综合运用，用到了树、也用到了链表等知识，对这些数据

22、构造*一方面的运用就构成了查找和排序。现实生活中，search 几乎无处不在，特别是现在的网络时代，万事离不开search，小到文档文字的搜索，大到INTERNET 上的搜索，search 占据了我们上网的大局部时间。在复习这一章的知识时，你需要先弄清楚以下几个概念：关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度 ASL 的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型构造的 ASL 值，应该记住。在 DS 的教材中，一般将 search 分为三类：1st，在顺序表上的查找；2nd，在树表上的查找；3rd，在哈希表上的查找。下面详细介绍其考察知识点及

23、考察方式：1.线性表上的查找：主要分为三种线性构造：顺序表，有序顺序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比拟。对于第三种索引构造，我们采用索引查找算法。考生需要注意这三种表下的ASL 值以及三种算法的实现。其中，二分查找还要特别注意适用条件以及其递归实现方法。2.树表上的查找：这是本章的重点和难点。由于这一节介绍的容是使用树表进展的查找，所以很容易与树一间的*些概念相混淆。本节容与树一章的容有联系，但也有很多不同，应注意规纳。树表主要分为以下几种：，键树。其中，尤以前两种构造为重，也有局部名校偏爱考 B 树的。由于二叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就

24、更为严密，二叉树一章学好了，这里也就不难了。二叉排序树，简言之，就是左小右大，它的中序遍历结果是一个递增的有序序列。平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的.深度有了限定：深度之差的绝对值不得大于 1。对于二叉排序树，判断*棵二叉树是否二叉排序树这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，所以应该掌握平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果一样。B 树是报考名校的同学应该关注的焦点之一。键树也称字符树，特别适用于查找英文单词的场合。一般

25、不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。3.：哈希一词，是外来词，译自hash一词，意为：散列或杂凑的意思。哈希表查找的根本思想是：根据当前待查找数据的特征，以记录关键字为自变量，设计一个function，该函数对关键字进展转换后，其解释结果为待查的地址。基于哈希表的考察点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。第八章 部排序 排是 DS 课程中最后一个重要的章节，建立在此章之上的考题可以有多种类型：填空，选择，判断乃至大型算法题。但是，归结到一点，就是考察你对书本上的各种排序算法及其思想以及其优缺点和性能指标时间复杂度能否了如指掌。这一章，

26、我们对重点的规纳将跟以上各章不同。我们将从以下几个侧面来对排序一章进展不同的规纳，以期能更全面的理解排序一章的总体构造及各种算法。从排序算法的种类来分，本章主要阐述了以下几种排序方法：其中，在插入排序中又可分为：直接插入、折半插入、2 路插入、希尔排序。这几种插入排序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。希尔排序，是通过控制每次参与排序的数的总围由小到大的增量来实现排序效率提高的目的。*，在交换排序的根底上改良又可以得到快速排序。快速排序的思想，一语以敝之：用中间数将待排数据组一分为二。快速排序，在处理的问题规模这个概念上，与希

27、尔有点相反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，最终到达排序的目的。，相对于前面几种排序算法来说，难度大一点。具体来说，它可以分为：简单项选择择、树选择、堆排。这三种方法的不同点是，根据什么规则选取最小的数。简单项选择择，是通过简单的数组遍历方案确定最小数；树选择，是通过锦标赛类似的思想，让两数相比，不断淘汰较大小者，最终选出最小大数；而堆排序，是利用堆这种数据构造的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。树选择排序，也曾经在一些学校中的大型算法题中出现，请大家注意。，故名思义，是通过归并这种操作完成排序的目的，既

28、然是归并就必须是两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是算法思想比拟简单，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比拟适合于一些特别的场合，比方扑克牌排序问题等。基数排序，又分为两种：多关键字的排序扑克牌排序，链式排序整数排序。基数排序的核心思想也是利用基数空间这个概念将问题规模规、变小，并且，在排序的过程中，只要按照基排的思想，是不用进.展关键字比拟的，这样得出的最终序列就是一个有序序列。本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的，学习时要多注意规纳、总结、比照。此外，对于教材中的 10.7 节，要求必须熟记，在理解的根底上记忆，这一节几乎成为很多学校每年的必考点。堆基于完全二叉树,又可分为大顶堆和小顶堆,掌握堆的构建,与删除节点操作,如删除顶点时先将最后一个叶子节点与顶点交换位置,然后进展再排序.