2023年数据结构复习重点归纳严蔚敏版-格式修改-方便打印

一、数据构造的章节构造及重点构成数据构造学科的章节划分基本上为概论，线性表，栈和队列，串，多维数组和广义表,树和二叉树，图，查找，内排，外排，文件，动态存储分派对于绝大多数的学校而言,“外排，文件，动态存储分派”三章基本上是不考的，在大多数高校的I计算机本科教学过程中，这三章也是基本上不作讲授欧I因此，大家在这三章上可以不必花费过多的精力，只要懂得基本的I概念即可不过，对于报考名校尤其是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留心这三章了按照以上我们给出的章节以及对后三章的简介，数据构造的章节比重大体为:概论:内容很少，概念简朴，分数大多只有几分，有日勺学校甚至不考线性表基础章节，必考内容之一考题多数为基本概念题，名校考题中，鲜有大型算法设计题假如有，也是与其他章节内容相结合栈和队列基础章节，轻易出基本概念题，必考内容之一而栈常与其他章节配合考察,也常与递归等概念相联络进行考察串基础章节，概念较为简朴专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析多维数组及广义表基础章节，基于数组的算法题也是常见时，分数比例波动较大，是出题时“可选单元”或“侯补单元”一般假如要出题，多数不会作为大题出数组常与“查找，排序”等章节结合来作为大题考察树和二叉树重点难点章节，各校必考章节各校在此章出题的I不一样之处在于，与否在本章中出一到两道大的算法设计题通过对多所学校的|试卷分析，绝大多数学校在本章都曾有过出大型算法设计题日勺历史存储构造，求最早时间和最晚时间要采用不一样的J处理措施，即在算法初始时，应该首先将所有顶点的最早时间全部置为0关键途径问题是工程进度控制的重要措施，具有很强的实用性

7.最短途径问题与关键途径问题并称为图一章的I两只拦路虎概念理解是比较轻易的I,关键是算法的理解最短途径问题分为两种一是求从某一点出发到其他各点的最短途径；二是求图中每一对顶点之间的最短途径这个问题也具有非常实用的背景特色，一种经典时应该就是旅游景点及旅游路线aI选择问题处理第一种问题用DIJSKTRA算法,处理第二个问题用FLOYD算法注意辨别第七章查找在不少数据构造的教材中，是把查找与排序放入高级数据构造中的应该说，查找和排序两章是前面我们所学的知识的综合运用，用到了树、也用到了链表等知识，对这些数据构造某首先的I运用就构成了查找和排序现实生活中，search几乎无处不在，尤其是目前的I网络时代，万事离不开search,小到文档内文字的搜索，大到INTERNET上的搜索，search占据了我们上网的大部分时间在复习这一章的知识时，你需要先弄清晰如下几种概念关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别;平均查找长度ASL的概念及在多种查找算法中的计算措施和计算成果，尤其是某些经典构造的IASL值，应该记住在DS肚|教材中，一般将search分为三类1st,在次序表上日勺查找；2nd,在树表上日勺查找；3rd,在哈希表上的查找下面详细简介其考察知识点及考察方式

1.线性表上的查找重要分为三种线性构造次序表，有序次序表，索引次序表对于第一种，我们采用老式查找措施，逐一比较对于及有序次序表我们采用二分查找法对于第三种索引构造，我们采用索引查找算法考生需要注意这三种表下的ASL值以及三种算法的实现其中，二分查找还要尤其注意合用条件以及其递归实现措施

2.树表上的查找这是本章的重点和难点由于这一节简介的内容是使用树表进行的查找，因此很轻易与树一间的某些概念相混淆本节内容与树一章的内容有联络，但也有诸多不一样，应注意规纳树表重要分为如下几种二叉排序树，平衡二叉树，B树，键树其中，尤此前两种构造为重，也有部分名校偏爱考B树的I由于二叉排序树与平衡二叉树是一种特殊的二叉树，因此与二叉树的联络就更为紧密，二叉树一章学好了，这里也就不难了二叉排序树，简言之，就是“左小右大”，它的中序遍历成果是一种递增的有序序列平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过,平衡二叉树对左右子树的深度有了限定深度之差的绝对值不得不小于lo对于二叉排序树，“判断某棵二叉树与否二叉排序树”这一算法常常被考到，可用递归，也可以用非递归平衡二叉树的建立也是一种常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，因此应该掌握平衡二叉树的四种调整算法，调整的一种参照是调整前后的中序遍历成果相似B树是二叉排序树的进一步改善，也可以把B树理解为三叉、四叉….排序树除B树的查找算法外，应该尤其注意一下B树的插入和删除算法因为这两种算法波及到B树结点区|分裂和合并，是一种难点B树是报考名校的同学应该关注的焦点之一键树也称字符树，尤其合用于查找英文单词的场所一般不规定能完整描述算法源码，多是根据算法思想建立键树及描述其大体查找过程

3.基本哈希表日勺查找算法哈希一词，是外来词，译自“hash”一词，意为散列或杂凑的意思哈希表查找的基本思想是根据目前待查找数据的特性，以记录关键字为自变量，设计一种function,该函数对关键字进行转换后，其解释成果为待查的地址基于哈希表欧I考察点有哈希函数欧I设计，冲突处理措施的选择及冲突处理过程的描述第八章内部排序内排是DS课程中最终一种重要的章节，建立在此章之上的考题可以有多种类型填空,选择，判断乃至大型算法题不过，归结到一点，就是考察你对书本上的多种排序算法及其思想以及其优缺陷和性能指标（时间复杂度）能否了如指掌这一章，我们对重点时规纳将跟以上各章不一样我们将从如下几种侧面来对排序一章进行不一样的规纳，以期能更全面的理解排序一章的总体构造及多种算法从排序算法的种类来分，本章重要论述了如下几种排序措施插入、选择、互换、归并、计数等五种排序措施其中，在插入排序中又可分为直接插入、折半插入、2路插入、希尔排序这几种插入排序算法的最根本的不一样点，说究竟就是根据什么规则寻找新元素的插入点直接插入是依次寻找，折半插入是折半寻找希尔排序，是通过控制每次参与排序时数的总范围“由小到大”的增量来实现排序效率提高欧I目的互换排序，又称冒泡排序，在互换排序及I基础上改善又可以得到迅速排序迅速排序的思想，一语以敝之用中间数将待排数据组一分为二迅速排序，在处理的“问题规模”这个概念上，与希尔有点相反，迅速排序，是先处理一种较大规模，然后逐渐把处理的规模降低，最终到达排序的目的选择排序，相对于前面几种排序算法来说，难度大一点详细来说，它可以分为简朴选择、树选择、堆排这三种措施的不一样点是，根据什么规则选用最小时数简朴选择，是通过简朴日勺数组遍历方案确定最小数；树选择，是通过“锦标赛”类似的思想，让两数相比，不停淘汰较大（小）者，最终选出最小（大）数；而堆排序，是运用堆这种数据构造的性质，通过堆元素及J删除、调整等一系列操作将最小数选出放在堆顶堆排序中的堆建立、堆调整是重要考点树选择排序，也曾经在某些学校中的大型算法题中出现，请大家注意归并排序，故名思义，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上的数据集合才可能实现归并因此，在归并排序中，关注最多的就是2路归并算法思想比较简朴，有一点，要铭记在心归并排序是稳定排序基数排序，是一种很尤其的排序措施，也正是由于它的特殊，因此，基数排序就比较适合于某些尤其的场所，例如扑克牌排序问题等基数排序，又分为两种多关键字的排序（扑克牌排序），链式排序（整数排序）基数排序的关键思想也是运用“基数空间”这个概念将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字比较的，这样得出的最终序列就是一种有序序列本章多种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的I,学习时要多注意规纳、总结、对比此外，对于教材中的

10.7节，规定必须熟记，在理解日勺基础上记忆，这一节几乎成为诸多学校每年的必考点图重点难点章节，名校尤爱考假如作为重点来考，则多出现于分析与设计题型当中,可与树一章共同构成算法设计大题的J题型设计查找重点难点章节，概念较多，联络较为紧密，轻易混淆出题时可以作为分析型题目给出，在基本概念型题目中也较为常见算法设计型题中可以数组结合来考察，也可以与树一章结合来考察排序与查找一章类似，本章同属于重点难点章节，且概念更多，联络更为紧密，概念之间更轻易混淆在基本概念的考察中，尤爱考多种排序算法的优劣比较此类的题算法设计大题中，假如作为出题，那么常与数组结合来考察

二、数据构造各章节重点勾划第0章概述本章重要起到总领作用，为读者进行数据构造的学习进行了某些先期铺垫大家重要注意如下几点数据构造欧I基本概念，时间和空间复杂度欧I概念及度量措施，算法设计时的注意事项本章考点不多，只要稍加注意理解即可第一章线性表作为线性构造的开篇章节，线性表一章在线性构造的学习乃至整个数据构造学科的学习中，其作用都是不可低估时在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据构造学科的重中之重，无论哪一章都波及到了这个概念总体来说,线性表一章可供考察KJ重要考点有如下几种方面

1.线性表的有关基本概念，如前驱、后继、表长、空表、首元结点，头结点，头指针等概念

2.线性表的构造特点，重要是指除第一及最终一种元素外，每个结点都只有一种前趋和只有一种后继

3.线性表的次序存储方式及其在详细语言环境下的两种不一样实现表空间的静态分派和动态分派静态链表与次序表的相似及不一样之处

4.线性表的链式存储方式及如下几种常用链表的特点和运算单链表、循环链表，双向链表，双向循环链表其中，单链表日勺归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为常见的考察方式止匕外，近年来在不少学校中还多次出现规定用递归算法实现单链表输出（可能是次序也可能是倒序）日勺问题在链表的小题型中，常常考到某些诸如判表空的题在不一样的链表中，其判表空的方式是不一样的I,请大家注意

5.线性表的次序存储及链式存储状况下，其不一样的优缺陷比较，即其各自合用的场所单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储构造的各自好处第二章栈与队列栈与队列，是诸多学习DS的同学碰到第一只拦路虎，诸多人从这一章开始坐晕车，一直晕到目前因此，理解栈与队列，是走向DS高手的一条必由之路学习此章前，你可以问一下自己是不是已经懂得了如下几点

1.栈、队列的定义及其有关数据构造的I概念，包括次序栈，链栈，共享栈，循环队列,链队等栈与队列存取数据（请注意包括存和取两部分）的特点

2.递归算法栈与递归欧I关系，以及借助栈将递归转向于非递归日勺经典算法n!阶乘问题，fib数列问题，Hanoi问题，背包问题，二叉树日勺递归和非递归遍历问题，图日勺深度遍历与栈的关系等其中，波及到树与图的问题，多半会在树与图的有关章节中进行考察

3.栈的应用数值体现式的求解，括号的配对等的原理，只作原理性了解，详细规定考察此为题目的算法设计题不多

4.循环队列中判队空、队满条件，循环队列中入队与出队算法假如你已经对上面的几点了如指掌，栈与队列一章可以不看书了注意，我说的是可以不看书，并不是可以不作题哦第三章串经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明串，在概念上是比较少的一种章节，也是最轻易自学的章节之一，但正如每个过来人所了解的，KMP算法是这一章的重要关隘，突破此关隘后，走过去又是一马平川的大好DS山河了，呵呵串一章需要攻破的I重要堡垒有

1.串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区别，串相等的条件

2.串的基本操作，以及这些基本函数的使用，包括取子串，串连接，串替代，求串长等等运用串的基本操作去完成特定的算法是诸多学校在基本操作上的考察重点

3.次序串与链串及块链串的区别和联络，实现方式

4.KMP算法思想KMP中next数组以及nextval数组的求法明确老式模式匹配算法日勺局限性，明确next数组需要改善之外其中，理解算法是关键，会求数组是得分点不用我多说，这一节内容是本章日勺重中之重可能进行欧I考察方式是求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的|匹配过程第四章数组与广义表学过程序语言的朋友，数组的I概念我们已经不是第一次见到了，应该已经“一回生，二回熟”了，因此，在概念上，不会存在太大障碍但作为考研课程来说，本章的考察重点可能与大学里的I程序语言所关注的不太一样，下面会作简介广义表的I概念，是数据构造里第一次出现日勺它是线性表或表元素的有限序列，构成该构造的I每个子表或元素也是线性构造的，因此，这一章也归入线性构造中本章的考察重点有

1.多维数组中某数组元素的position求解一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后规定你求出该数组中的某个元素所在日勺位置

2.明确按行存储和按列存储的J区别和联络，并可以按照这两种不一样的存储方式求解1中类型的I题

3.将特殊矩阵中的元素按对应的换算方式存入数组中这些矩阵包括对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等熟悉稀疏矩阵的三种不一样存储方式三元组，带辅助行向量的二元组，十字链表存储掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法

4.广义表的概念，尤其应该明确表头与表尾的定义这一点，是理解整个广义表一节算法的基础近来，在某些学校中，出现了这样一种题目类型给出对某个广义表L若干个求了若干次的取头和取尾操作后的串值，规定求出原广义表L大家要留心

5.与广义表有关的递归算法由于广义表的I定义就是递归的，因此，与广义表有关的算法也常是递归形式欧I例如求表深度，复制广义表等这种题目，可以根据不一样角度广义表的体现形式运用两种不一样日勺方式解答一是把一种广义表看作是表头和表尾两部分，分别对表头和表尾进行操作；二是把一种广义表看作是若干个子表，分别对每个子表进行操作第五章树与二叉树从对线性构造的研究过度到对树形构造的研究，是数据构造课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中与否可以拿到高分，而这所有的一切,将最终影响你的专业课总分因此，树这一章的重要性，已经不说自明了总体来说，树一章的知识点包括二叉树的J概念、性质和存储构造，二叉树遍历的J三种算法（递归与非递归），在三种基本遍历算法的基础上实现二叉树的其他算法，线索二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联络，树与森林和二叉树的转换下面我们来看考试中对以上知识的重要考察措施

1.二叉树的概念、性质和存储构造考察措施可有直接考察二叉树的定义，让你阐明二叉树与一般双分支树的区别；考察满二叉树和完全二叉树的性质，一般二叉树的五个性质第i层的最多结点数，深度为k时二叉树的最多结点数，n0=n2+l的性质，n个结点的完全二叉树的深度，次序存储二叉树时孩子结点与父结点之间的换算关系（左为2*i,右为2*i+l）二叉树口勺次序存储和二叉链表存储的各自优缺陷及合用场所，二叉树的三叉链表表达措施

2.二叉树的三种遍历算法这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成二叉树的I遍历算法有三种先序，中序和后序其划分的根据是视其每个算法中对根结点数据的访问次序而定不仅要纯熟掌握三种遍历日勺递归算法，理解其执行的实际步骤，并且应该纯熟掌握三种遍历的非递归算法由于二叉树一章的诸多算法，可以直接根据三种递归算法改造而来（例如求叶子个数），因此，掌握了三种遍历的非递归算法后，对付诸如“运用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了我会在另一篇系列文章（）里给出三种遍历的递归和非递归算法的I背记版，到时请大家一定熟记

3.可在三种遍历算法的基础上改造完成的其他二叉树算法求叶子个数，求二叉树结点总数，求度为1或度为2时结点总数，复制二叉树，建立二叉树，互换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等假如你可以纯熟掌握二叉树的递归和非递归遍历算法，那么处理以上问题就是小菜一碟了

4.线索二叉树线索二叉树的引出，是为防止如二叉树遍历时的递归求解众所周知，递归虽然形式上比很好理解，不过消耗了大量的内存资源，假如递归层次一多，势必带来资源耗尽的危险，为了防止此类状况，线索二叉树便堂而皇之地出现了对于线索二叉树，应该掌握线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其他算法问题（如查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）

5.最优二叉树（哈夫曼树）最优二叉树是为了处理特定问题引出的特殊二叉树构造，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小时最优二叉树一节，直接考察算法源码的很少，一般是给你一组数据，规定你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题

6.树与森林二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其他特性，一种最重要日勺特殊之处是在于二叉树是有序日勺！即二叉树的I左右孩子是不可互换的I,假如互换了就成了此外一棵二叉树，这样互换之后的二叉树与原二叉树我们认为是不相似的两棵二叉树不过，对于一般的双分支树而言，不具有这种性质树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法先根与后根（对于森林而言称作先序与后序遍历）在难度比较大的考试中，也有基于此二种算法的基础上再进行扩展规定你运用这两种算法设计其他算法的，但一般院校很少有这种考法，最多只是规定你根据先根或后根写出他们的遍历序列此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系日勺先根遍历对应二叉树聆I先序遍历，而后根遍历对应二叉树的I中序遍历这一点成为诸多学校的考点，考察欧I方式不一而足，有时直接考此句话，有的是先让你求解遍历序列然后回答这个问题二叉树、树与森林之因此能有以上的对应关系，全拜二叉链表所赐二叉树使用二叉链表分别寄存他的左右孩子，树运用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是运用二叉链表存储孩子及兄弟树一章，到处是重点，道道是考题，大家务必个个过关第六章图假如说，从线性构造向树形构造研究的转变，是数据构造学科对数据组织形式研究的一次升华，那么从树形构造的研究转到图形构造的研究，则进一步让我们看到了数据构造对于处理实际问题的重大推动作用图这一章的特点是概念繁多，与离散数学中图的概念联络紧密，算法复杂，极易被考到，且轻易出大题，尤其是名校，作为考研课程，假如不考察树与图两章的知识，几乎是不可想像的I下面我们看一下图这一章的重要考点以及这些考点的I考察方式

1.考察有关图日勺基本概念问题这些概念是进行图一章学习的基础，这一章的概念包括:图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，途径长度，回路,（强）连通图，（强）连通分量等概念与这些概念相联络日勺有关计算题也应该掌握

2.考察图的几种存储形式图的存储形式包括邻接矩阵，（逆）邻接表，十字链表及邻接多重表在考察时，有的学校是给出一种存储形式，规定考生用算法或手写出与给定的构造相对应的该图日勺另一种存储形式

3.考察图的两种遍历算法深度遍历和广度遍历深度遍历和广度遍历是图日勺两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性在考察时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计欧I,例如“求最长的最短途径问题”和“判断两顶点间与否存在长为K日勺简朴途径问题”，就分别用到了广度遍历和深度遍历算法

4.生成树、最小生成树的概念以及最小生成树的构造RIM算法和KRUSKAL算法考察时，一般不规定写出算法源码，而是规定根据这两种最小生成树的I算法思想写出其构造过程及最终身成的I最小生成树

5.拓扑排序问题拓扑排序有两种措施，一是无前趋的顶点优先算法，二是无后继欧I顶点优先算法换句话说，一种是“从前向后”的排序，一种是“从后向前”排当然，后一种排序出来的成果是“逆拓扑有序”的

6.关键途径问题这个问题是图一章的难点问题理解关键途径的关键有三个方面一是何谓关键途径，二是最早时间是什么意思、怎样求，三是最晚时间是什么意思、怎样求简朴地说，最早时间是通过“从前向后”的措施求欧I,而最晚时间是通过“从后向前”欧I措施求解的，并且，要想求最晚时间必须是在所有日勺最早时间都已经求出来之后才能进行这个问题拿来直接考算法源码时不多，一般是规定按照书上欧I算法描述求解欧I过程和步骤在实际设计关键途径的算法时，还应该注意如下这一点采用邻接表的I。