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

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

1、精品_精品资料_一、数据结构得章节结构及重点构成数据结构学科得章节划分基本上为 :概论 ,线性表 ,栈与队列 ,串,多维数组与广义表,树与二叉树, 图,查找, 内排,外排,文件,动态储备安排 .对于绝大多数得学校而言 ,“外排 ,文件, 动态储备安排” 三章基本上就是不考得 ,在大多数高校得运算机本科教学过程中 ,这三章也就是基本上不作讲授得.所以,大家在这三章上可以不必花费过多得精力,只要知道基本得概念即可.但就是,对于报考名校特殊就是该校又有在试卷中对这三章进行过考核得历史,那么这部分伴侣就要留意这三章了.依据以上我们给出得章节以及对后三章得介绍,数据结构得章节比重大致为： 概论： 内容很

2、少 ,概念简洁 ,分数大多只有几分,有得学校甚至不考.线性表: 基础章节,必考内容之一.考题多数为基本概念题,名校考题中,鲜有大型算法设计题.假如有,也就是与其它章节内容相结合 .栈与队列： 基础章节 ,简洁出基本概念题,必考内容之一.而相联系进行考查.串：基础章节 ,概念较为简洁 .特的针对于此章得大型算法设计题很少, 较常见得就是依据KM 进行算法分析.多维数组及广义表 :基础章节, 基于数组得算法题也就是常见得 ,分数比例波动较大, 就是出题得“可选单元”或“侯补单元” .一般假如要出题 ,多数不会作为大题出 .数组常与“查找,排序”等章节结合来作为大题考查.树与二叉树 :重点难点章节,

3、 各校必考章节. 各校在此章出题得不同之处在于 ,就是否在本章中出一到两道大得算法设计题.通过对多所学校得试卷分析,绝大多数学校在本章都曾有过出大型算法设计题得历史.图:重点难点章节,名校尤爱考.假如作为重点来考,就多显现于分析与设计题型当中, 可与树一章共同构成算法设计大题得题型设计.查找:重点难点章节 ,概念较多,联系较为紧密 ,简洁混淆.出题时可以作为分析型题目给出,在基本概念型题目中也较为常见.算法设计型题中可以数组结合来考查,也可以与树 一章结合来考查.排序:与查找一章类似 ,本章同属于重点难点章节,且概念更多,联系更为紧密,概念之间更简洁混淆.在基本概念得考查中,尤爱考各种排序算法

4、得优劣比较此类得题.算法设 计大题中,假如作为出题,那么常与数组结合来考查.二、数据结构各章节重点勾划第章概述本章主要起到总领作用 ,为读者进行数据结构得学习进行了一些先期铺垫.大家主要留意以下几点 :数据结构得基本概念, 时间与空间复杂度得概念及度量方法 ,算法设计时得留意事项.本章考点不多 ,只要稍加留意懂得即可.第一章 线性表作为线性结构得开篇章节 ,线性表一章在线性结构得学习乃至整个数据结构学科得学习中,其作用都就是不行低估得.在这一章,第一次系统性的引入链式储备得概念,链式存储概念将就是整个数据结构学科得重中之重,无论哪一章都涉及到了这个概念. 总体来说 ,线性表一章可供考查得重要考

5、点有以下几个方面：1、 线性表得相关基本概念,如：前驱、后继、表长、空表、首元结点,头结点,头指针等概念.2、3、 线性表得次序储备方式及其在具体语言环境下得 两种不同实现 ：表空间得静态安排与动态安排.静态链表与次序表得相像及不同之处.可编辑资料 - - - 欢迎下载精品_精品资料_4、 线性表得链式储备方式及以下几种常用链表得特点与运算：单链表、循环链表,双向链表,双向循环链表.其中 ,单链表得 归并算法、循环链表得归并算法、双向链表及双向循环链表得插入与删除算法 等都就是较为常见得考查方式.此外,近年来在不少学校中仍多次显现要求用递归算法实现单链表输出可能就是次序也可能就是倒序 得问题.

6、在链表得小题型中 ,常常考到一些诸如：判表空得题.在不同得链表中,其判表空得方式就是不一样得,请大家留意 .5、 线性表得次序储备及链式储备情形下,其不同得优缺点比较,即其各自适用得场合.单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引储备结构得各自 好处.其次章 栈与队列栈与队列,就是许多学习DS 得同学遇到第一只拦路虎,许多人从这一章开头坐晕车, 始终晕到现在.所以,懂得栈与队列 ,就是走向 DS 高手得一条必由之路.学习此章前 ,您可以问一下自己就是不就是已经知道了以下几点：1、 栈、队列得定义及其相关数据结构得概念,包括：次序栈,链栈,共享栈 ,循环队列, 链队等.栈与队

7、列存取数据（请留意包括：存与取两部分得特点.2、 递归算法. 栈与递归得关系 ,以及借助栈将递归转向于非递归得经典算法：n；阶乘问题,fib 数列问题 ,aoi 问题,背包问题 ,二叉树得递归与非递归遍历问题,图得深度遍历与栈得关系等 .其中,涉及到树与图得问题 ,多半会在树与图得相关章节中进行考查.3、 栈得应用：数值表达式得求解,括号得配对等得原理,只作原理性明白 ,具体要求考查此为题目得算法设计题不多 .4、 循环队列中判队空、队满条件,循环队列中入队与出队算法.假如您已经对上面得几点了如指掌,栈与队列一章可以不瞧书了.留意,我说得就是可以不瞧书,并不就是可以不作题哦.第三章 串经受了栈

8、一章得痛楚煎熬后 ,最终迎来了串一章得柳暗花明.串,在概念上就是比较少得一个章节 ,也就是最简洁自学得章节之一,但正如每个过来人所明白得,KM 算法就是这一章得重要关隘 ,突破此关隘后 ,走过去又就是一马平川得大好 DS 山河了,呵呵.串一章需要攻破得主要堡垒有：1、 串得基本概念 ,串与线性表得关系 串就是其元素均为字符型数据得特殊线性表） ,空串与空格串得区分,串相等得条件.2、 串得基本操作,以及这些基本函数得使用,包括：取子串,串连接 ,串替换,求串长等等.运用串得基本操作去完成特定得算法就是许多学校在基本操作上得考查重点.3、 次序串与链串及块链串得区分与联系,实现方式.4、 KP

9、算法思想.KMP 中 next 数组以及 nextvl 数组得求法. 明确传统模式匹配算法得不足 ,明确 net 数组需要改进之外 .其中,懂得算法就是核心 ,会求数组就是得分点.不用我多说 ,这一节内容就是本章得重中之重.可能进行得考查方式就是:求 ext 与 etv 数组值,依据求得得 nx或 nexval 数组值给出运用 KP 算法进行匹配得匹配过程.第四章 数组与广义表学过程序语言得伴侣 ,数组得概念我们已经不就是第一次见到了,应当已经“一回生,二回熟”了,所以,在概念上 ,不会存在太大障碍 .但作为考研课程来说 ,本章得考查重点可能与高校里得程序语言所关注得不太一样,下面会作介绍.

10、广义表得概念 ,就是数据结构里第一次显现得 .它就是线性表或表元素得有限序列,构成该结构得每个子表或元素也就是线性结构得,所以,这一章也归入线性结构中.本章得考查重点有：1、 多维数组中某数组元素得 poition 求解.一般就是给出数组元素得首元素的址与每个元素占用得的址空间并组给出多维数组得维数,然后要求您求出该数组中得某个元素可编辑资料 - - - 欢迎下载精品_精品资料_所在得位置.2、 明确按行储备与按列储备得区分与联系 ,并能够依据这两种不同得储备方式求解1 中类型得题 .3、 将特殊矩阵中得元素按相应得换算方式存入数组中.这些矩阵包括：对称矩阵,三角矩阵,具有某种特点得稀疏矩阵等

11、. 熟识稀疏矩阵得三种不同储备方式 :三元组, 带帮助行向量得二元组 ,十字链表储备.把握将稀疏矩阵得三元组或二元组向十字链表进行转换得算法.4、 广义表得概念,特殊应当明确表头与表尾得定义.这一点,就是懂得整个广义表一节算法得基础. 近来,在一些学校中, 显现了这样一种题目类型 :给出对某个广义表 L 如干个求了如干次得取头与取尾操作后得串值,要求求出原广义表L.大家要留意.5、 与广义表有关得递归算法.由于广义表得定义就就是递归得,所以,与广义表有关得算法也常就是递归形式得.比如：求表深度,复制广义表等.这种题目,可以依据不同角度广义表得表现形式运用两种不同得方式解答：一就是把一个广义表瞧

12、作就是表头与表尾两部分 ,分别对表头与表尾进行操作. 二就是把一个广义表瞧作就是如干个子表,分别对每个子表进行操作.第五章 树与二叉树从对线性结构得讨论过度到对树形结构得讨论,就是数据结构课程学习得一次跃变,此次跃变完成得好坏,将直接关系到您到实际得考试中就是否可以拿到高分,而这全部得一切,将最终影响您得专业课总分.所以,树这一章得重要性,已经不说自明白.总体来说 , 树一章得学问点包括 :二叉树得概念、 性质与储备结构 ,二叉树遍历得三种算法 （递归与非递归） ,在三种基本遍历算法得基础上实现二叉树得其它算法,线索二叉树得概念与线索化算法以及线索化后得查找算法, 最优二叉树得概念、 构成与应

13、用 ,树得概念与储备形式, 树与森林得遍历算法及其与二叉树遍历算法得联系,树与森林与二叉树得转换.下面我们来瞧考试中对以上学问得主要考查方法：1、 二叉树得概念、性质与储备结构考查方法可有：直接考查二叉树得定义,让您说明二叉树与一般双分支树得区分.,一般二叉树得五个性质：第 i 层得最多结点数,深度为 k 得二叉树得最多结点数, n0=2+1 得性质, n 个结点得完全二叉树得深度,次序储备二叉树时孩子结点与父结点之间得换算关系（左为: ,右为: i+1.二叉树得次序储备与二叉链表储备得各自优缺点及适用场合,二叉树得三叉链表表示方法 .2、 二叉树得三种遍历算法 这一学问点把握得好坏 ,将直接

14、关系到树一章得算法能否懂得,进而关系到树一章得算法设计题能否顺当完成.二叉树得遍历算法有三种: 先序,中序与后序.其划分得依据就是视其每个算法中对根结点数据得拜访次序而定.不仅要娴熟把握三种遍历得递归算法 ,懂得其执行得实际步骤,并且应当娴熟把握三种遍历得非递归算法.由于二叉树一章得许多算法,可以直接依据三种递归算法改造而来 （比如：求叶子个数）,所以,把握了三种遍历得非递归算法后,应付诸如：“利用非递归算法求二叉树叶子个数 这样得题目就下笔如有神了 .我会在另一篇系列文章（ : b s、 a a、 ibbs、ll ？、 =2&b 0里给出三种遍历得递归与非递归算法得背记版,到时请大家肯定熟记

15、.3、 可在三种遍历算法得基础上改造完成得其它二叉树算法：求叶子个数,求二叉树结点总数,求度为 1 或度为 2 得结点总数,复制二叉树,建立二叉树,交换左右子树,查找值为 n 得某个指定结点,删除值为 n 得某个指定结点 ,诸如此类等等等等.假如您可以娴熟把握二叉树得递归与非递归遍历算法 ,那么解决以上问题就就是小菜一碟了.4、 线索二叉树 :线索二叉树得引出 ,就是为防止如二叉树遍历时得递归求解.众所周知 , 递归虽然形式上比较好懂得,但就是消耗了大量得内存资源,假如递归层次一多 ,势必带来资源耗尽得危急,为了防止此类情形,线索二叉树便堂而皇之的显现了.对于线索二可编辑资料 - - - 欢迎

16、下载精品_精品资料_叉树,应当把握：线索化得实质 ,三种线索化得算法 ,线索化后二叉树 得遍历算法 ,基本线索二叉树得其它算法问题如:查找某一类线索二叉树中指定结点得前驱或后继结点就就 是一类常考题）.？、：最优二叉树就是为明白决特定问题引出得特殊二叉树结构,它得前提就是给二叉树得每条边给予了权值,这样形成得二叉树按权相加之与就是最小得.最优二叉树一节 ,直接考查算法源码得很少 ,一般就是给您一组数据 ,要求您建立基于这组数据得最优二叉树,并求出其最小权值之与,此类题目不难,属送分题.6、二叉搜寻树（二叉排序树 B 树与 +数同样把握 B 树得构建,添加节点与删除节点等操作8、 树与森林 :二

17、叉树就是一种特殊得树,这种特殊不仅仅在于其分支最多为以及其它特点,一个最重要得特殊之处就是在于： 二叉树就是有序得 . 即:二叉树得左右孩子就是不行交换得 ,假如交换了就成了另外一棵二叉树,这样交换之后得二叉树与原二叉树我们认为就是不相同得两棵二叉树.但就是,对于一般得双分支树而言,不具有这种性质.树与森林得遍历,不像二叉树那样丰富,她们只有两种遍历算法:先根与后根（对于森林而言称作：先序与后序遍历） .在难度比较大得考试中,也有基于此二种算法得基础上再进行扩展要求您利用这两种算法设计其它算法得,但一般院校很少有这种考法 ,最多只就是要求您依据先根或后根写出她们得遍历序列.此二者得先根与后根遍

18、历与二叉树中得遍历算法就是有对应关系得 :先根遍历对应二叉树得先序遍历,而后根遍历对应二叉树得中序遍历.这一点成为许多学校得考点 ,考查得方式不一而足, 有得直接考此句话, 有得就是先让您求解遍历序列然后回答这个问题. 二叉树、树与森林之所以能有以上得对应关系, 全拜二叉链表所赐.二叉树使用二叉链表分别存放她得左右孩子,树利用二叉链表储备孩子及兄弟（称孩子兄弟链表） ,而森林也就是利用二叉链表储备孩子及兄弟.树一章,处处就是重点 ,道道就是考题,大家务必个个过关 .第六章 图假如说,从线性结构向树形结构讨论得转变,就是数据结构学科对数据组织形式讨论得一次升华,那么从树形结构得讨论转到图形结构得

19、讨论,就进一步让我们瞧到了数据结构对于解决实际问题得重大推动作用.图这一章得特点就是:概念繁多,与离散数学中图得概念联系紧密 ,算法复杂 ,极易被考到,且简洁出大题 ,特殊就是名校 ,作为考研课程,假如不考查树与图两章得学问 ,几乎就是不行想像得 .下面我们瞧一下图这一章得主要考点以及这些考点得考查方式：1、 考查有关图得基本概念问题 :这些概念就是进行图一章学习得基础,与这些概念相联系得相关运算题也应当把握.2、 考查图得几种储备形式：在考查时,有得学校就是给出一种储备形式,要求考生用算法或手写出与给定得结构相对应得该图得另一种储备形式.3、 考查图得两种遍历算法： 深度遍历与广度遍历 深度

20、遍历与广度遍历就是图得两种基本得遍历算法 ,其中深度遍历相当于二叉树中得先序遍历,而广度遍历相当于二叉树中得层次遍历、 这两个算法对图一章得重要性等同于“先序、中序、后序遍历”对于二叉树一章得重要性.在考查时,图一章得算法设计题常常就是基于这两种基本得遍历算法而设计得,比如：“求最长得最短路径问题”与“判定两顶点间就是否存在长为K 得简洁路径问题” ,就分别用到了广度遍历与深度遍历算法 .、可编辑资料 - - - 欢迎下载精品_精品资料_考查时,一般不要求写出算法源码 ,而就是要求依据这两种最小生成树得算法思想写出其构造过程及最终生成得最小生成树 .、,一就是无前趋得顶点优先算法 ,二就是无后

21、继得顶点优先算法.换句话说,一种就是“从前向后”得排序 ,一种就是“从后向前”排.当然,后一种排序出来得结果就是“逆拓扑有序”得.6、：这个问题就是图一章得难点问题. 懂得关键路径得关键有三个方面： 一就是何谓关键路径 ,二就是最早时间就是什么意思、 如何求,三就是最晚时间就是什么意思、如何求.简洁的说 ,最早时间就是通过“从前向后”得方法求得 ,而最晚时间就是通过“从后向前”得方法求解得,并且,要想求最晚时间必需就是在全部得最早时间都已经求出来之后才能进行.这个问题拿来直接考算法源码得不多 ,一般就是要求依据书上得算法描述求解得过程与步骤.在实际设计关键路径得算法时,仍应当留意以下这一点：采

22、用邻接表得储备结构, 求最早时间与最晚时间要采纳不同得处理方法, 即:在算法初始时 , 应当第一将全部顶点得最早时间全部置为 0.关键路径问题就是工程进度掌握得重要方法 , 具有很强得有用性.、:与关键路径问题并称为图一章得两只拦路虎.概念懂得就是比较容易得,关键就是算法得懂得. 最短路径问题分为两种 :一就是求从某一点动身到其余各点得最短路径.二就是求图中每一对顶点之间得最短路径.这个问题也具有特别有用得背景 特色 , 一个典型得应当就就是旅行景点及旅行路线得挑选问题.解决第一个问题用DIJSKTRA 算法,解决其次个问题用 FLYD 算法.留意区分.* * 留意区分关键路径问题与最短路径问

23、题 * 第七章 查找在不少数据结构得教材中 ,就是把查找与排序放入高级数据结构中得.应当说,查找与排序两章就是前面我们所学得学问得综合运用,用到了树、也用到了链表等学问,对这些数据 结构某一方面得运用就构成了查找与排序.现实生活中,search几乎无处不在 ,特殊就是现在得网络时代 ,万事离不开 sarch,小到文档内文字得搜寻,大到 NTER 上得搜寻, a h 占据了我们上网得大部分时间 .在复习这一章得学问时,您需要先弄清晰 以下几个概念：关键字、主关键字、次关键字得含义.静态查找与动态查找得含义及区别;平均查找长度 A 得概念及在各种查找算法中得运算方法与运算结果,特殊就是一些典型结构

24、得 ASL 值,应当记住.在 DS 得教材中,一般将 searh 分为三类： 1t,在次序表上得查找 ;2nd,在树表上得查找 ;3 d,在哈希表上得查找. 下面具体介绍其考查学问点及考查方式：1、 线性表上得查找 :主要分为三种线性结构：次序表,有序次序表,索引次序表.对于第一种,我们采纳传统查找方法,逐个比较.对于第三种索引结构,我们采纳索引查找算法.考生需要留意这三种表下得ASL 值以及三种算法得实现.其中, 二分查找仍要特殊留意适用条件以及其递归实现方法.、 树表上得查找 :这就是本章得重点与难点.由于这一节介绍得内容就是使用树表进行得查找 ,所以很简洁与树一间得某些概念相混淆 .本节

25、内容与树一章得内容有联系 ,但也有许多不同,应留意规纳.树表主要分为以下几种：, ,键树.其中 ,尤以前两种结构为重,也有部分名校偏爱考树得.由于二叉排序树与平稳二叉树就是一种特殊得二叉树, 所以与二叉树得联系就更为紧密 ,二叉树一章学好了 ,这里也就不难了. 二叉排序树 ,简言之,就就是“左小右大” ,它得中序遍历结果就是一个递增得有序序列.平稳二叉树就是二叉排序树得优化,其本质也就是一种二叉排序树,只不过,平稳二叉树对左右子树得深度有了限定：深度之差得肯定值不得大于 1.对于二叉排序树,“判定某棵二叉树就是否二叉排序树” 这一算法常常被考到, 可用递归 ,也可以用非递归 .平稳二叉树得建立

26、也就是一个常考点,但该学问点归根结底仍就是关注得平稳二叉树得四种调整算法,所以应当把握平稳二叉树得四种调整算法, 调整得一个参照就是 :调整前后得中序遍可编辑资料 - - - 欢迎下载精品_精品资料_历结果相同 .B 树就是报考名校得同学应当关注得焦点之一.键树也称字符树,特殊适用于查找英文单词得场合.一般不要求能完整描述算 法源码,多就是依据算法思想建立键树及描述其大致查找过程.、:哈希一词,就是外来词 ,译自“ hash一词,意为 :散列或杂凑满意思.哈希表查找得基本思想就是：依据当前待查找数据得特征,以记录关键字为自变量,设计一个f ncion,该函数对关键字进行转换后 ,其说明结果为待

27、查得的址.基于哈希表得考查点有:哈希函数得设计,冲突解决方法得挑选及冲突 处理过程得描述.第八章内部排序内排就是 S 课程中最终一个重要得章节 ,建立在此章之上得考题可以有多种类型 :填空, 挑选,判定乃至大型算法题.但就是,归结到一点,就就是考查您对书本上得各种排序算法及其思想以及其优缺点与性能指标 时间复杂度） 能否了如指掌. 这一章,我们对重点得规纳将跟以上各章不同.我们将从以下几个侧面来对排序一章进行不同得规纳,以期能更全面得懂得排序一章得总体结构及各种算法.从排序算法得种类来分,本章主要阐述了以下几种排序方法：其中,在插入排序中又可分为：直接插入、折半插入、2 路插入、希尔排序.这几

28、种插入排序算法得最根本得不同点 ,说究竟就就是依据什么规章查找新元素得插入点.直接插入就是依次查找,折半插入就是折半查找.希尔排序,就是通过掌握每次参加排序得数得总范畴“由小到大”得增量来实现排序效率提高得目得.* *,在交换排序得基础上改进又可以得到快速排序.快速排序得 思想,一语以敝之：用中间数将待排数据组一分为二.快速排序 ,在处理得“问题规模”这个概念上, 与希尔有点相反, 快速排序 ,就是先处理一个较大规模 ,然后逐步把处理得规模降低,最终达到排序得目得 .,相对于前面几种排序算法来说,难度大一点.具体来说,它可以分为 :简洁挑选、树挑选、堆排.这三种方法得不同点就是 ,依据什么规章

29、选取最小得数.简洁挑选 ,就是通过简洁得数组遍历方案确定最小数.树挑选,就是通过“锦标赛”类似得思想,让两数相比,不断剔除较大（小 者,最终选出最小 大）数 ;而堆排序,就是利用堆这种数据结构得性质,通过堆元素得删除、调整等一系列操作将最小数选出放在堆顶.堆排序中得堆建立、堆调整就是重要考点.树挑选排序,也曾经在一些学校中得大型算法题中显现,请大家留意.,故名思义 ,就是通过“归并”这种操作完成排序得目得,既然就是归并就必需就是两者以上得数据集合才可能实现归并.所以,在归并排序中,关注最多得就就是算法思想比较简洁,就是一种很特殊得排序方法,也正就是由于它得特殊,所以,基数排序就比较适合于一些特

30、殊得场合 ,比如扑克牌排序问题等.基数排序,又分为两种：多关键字得排序扑克牌排序 ,链式排序（整数排序） .基数排序得核心思想也就是利用“基数空间” 这个概念将问题规模规范、变小 ,并且,在排序得过程中,只要依据基排得思想,就是不用进行关键字比较得,这样得出得最终序列就就是一个有序序列.本章各种排序算法得思想以及伪代码实现,及其时间复杂度都就是必需把握得,学习时要多留意规纳、总结、对比 .此外,对于教材中得、节,要求必需熟记,在懂得得基础上记忆 ,这一节几乎成为许多学校每年得必考点 .可编辑资料 - - - 欢迎下载精品_精品资料_堆基于完全二叉树 ,又可分为大顶堆与小顶堆,把握堆得构建,与删除节点操作,如删除顶点时先将最终一个叶子节点与顶点交换位置,然后进行再排序、可编辑资料 - - - 欢迎下载