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

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

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

2、据结构的章节比重大致为： 概论：容很少，概念简洁，分数大多只有儿分，有的学校甚至不考。线性表 : 基础章节，必考容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如 果有，也是与其它章节容相结合。栈和队列：基础章节, 简洁出基本概念题, 必考容之一。而號 2 其它章 牛瓦令老至也常与递归轰达 式的求值等概 念相联 系进行考查。串：基础章节，概念较为简洁。特的针对于此章的大型算法设计题很少，较常见的是根据 KMP 进行算法分析。多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可 选单元”或 侯补单元”。一般假如要出题，多数不会作为大题出。数组常与“

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

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

5、一章都涉及到了这个概念。总体来说,线性表一章可供考查的重要 考点有以下儿个方面：1. 线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。2. 线性表的结构特点夕兰要是指 除第一及最终一入元素外？每人结点都只有一个前趋和只有一个 后继。3. 线性表的次序储备方式及其在具体语言环境下的两种不同实现: 表空间的静态安排和动态安排。贞脚.可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总

6、结归纳 - - - - - - - - - - - -静态链表与次序表的相像及不同之处。4. 线性表的链式储备方式及以下儿种常用链表的特点和运算：单链表、循环链表，双向链表，双向 循环链表。 其中， 单链表的归并算法. 循环链表的归并算法、双向链表及双向循环链表的插入和删除 算法等都是较为常见的考查方式。此外，近年来在不少学校中仍多次显现要求用递归算法实现单链 表输出（可能是次序也可能是倒序）的问题。 在链 表的小题型中， 常常考到一些诸如：判表空的题。 在不同的链表中，其判表空的方式是不一样的，请大家留意。5. 线性表的次序储备及链式储备情形下，其不同的优缺点比较，即其各自适用的场合。单链表

7、中设 置头指针、循环链表中设置尾指针而不设置头指针以及索引储备结构的各自好处。其次章栈与队列栈与队列， 是许多学习DS 的同学遇到第一只拦路虎，许多人从这一章开头坐晕车，一 直晕到现在。所以，懂得栈与队列，是走向DS 高手的一条必山之路。学习此章前，你可以问一下自己是不是已 经知道了以下儿点：1.栈、队列的定义及其相关数据结构的概念，包括：次序栈, 链栈，共享栈 , 循环队列 ,链队等。栈 与队列存取数据（请留意包括：存和取两部分）的特点。2-递归算法 - 栈与递归的关系以及借助栈将递归转向TTF.递归的经典算法; . 阶乘问题, fib 数列回趣 , Hanoi 问題丄背包问题丄二义树的递归

8、和非递归遍历问题丄图的深度遍历与栈的关系等其 中，涉及到树与图的问题, 多丫会在树与图的相关章节中进行考查。3. 栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性明白，具体要求考查此为题目 的算法设计题不多。4. 循环队列中判队空、队满条件，循环队列中入队与出队算法。假如你已经对上面的儿点了如指掌，栈与队列一章可以不看书了。留意，我说的是可以不看书，并不是可以不作题哦。第三章串经石了栈一章的痛楚煎熬后，最终迎来了串一章的柳暗花明。串，在概念上是比较少的一个章 节，也是最简洁自学的章节之一，但正如每个过来人所明白的，KMP 算法是这一章的重要关隘， 突破此关隘后，走过去乂是一马平川的大

9、好DS 山河了，呵呵。串一章需要攻破的主要堡垒有：1. 串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区分，串相等的条件。2. 串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是许多学校在基本操作上的考查重点。3.次序串与链串及块链串的区分和联系，实现方式。4. KMP 算法思想。 KMP 中 next 数组以及 nextval 数组的求法。明确传统模式匹配算法的 不足， 明确 next 数组需要改进之外。其中，懂得算法是核心，会求数组是得分点。不用 我多说，这一节容是本章的重中之重。可能进

10、行的考查方式是：求 next 和 nextval 数组值 , 依据求得的 next 或nextval 数组值给出运用KMP 算法进行匹配的匹配过程。第四章数组与广义表学过程序语言的伴侣，数组的概念我们已经不是第一次见到了，应当已经“一回生，二回熟” 了，所以，在概念上，不会存在太大障碍。但作为考研课程来说，本章的考查重点可能与高校里 的程序语言所关注的不太一样，下面会作介绍。广义表的概念，是数据结构里第一次显现的。它 是线性表或表元素的有限序列，构成该结构的每个子表或元素也是线性结构的，所以，这一章也 归入线性结构中。本章的考查重点有：1.多维数组中某数组元素的position 求解。一般是给

11、出数组元素的首元素的址和每个元素占用的的址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。2.明确按行储备和按列储备的区分和联系，并能够依据这两种不同的储备方式求解1 中类型的题。贞脚.学习资料 名师精选 - - - - - - - - - -第 2 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -3. 将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩阵，具有 某种特点的稀疏矩阵等。熟识稀疏矩阵的三种不同储备方式：三

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

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

14、联系，树 与森林和二义树的转换。下面我们来看考试中对以上学问的主要考查方法：1. 二义树的概念、 性质和储备结构考查方法可有：直接考查二叉树的定义，让你说明二叉树与一般 双分支树的区分。考查满二叉树和完全二叉树的性质，一般二叉树的五个性质: 第 i层的最多结点 数，深度为k 的一.叉树的最多结点数, nO 二 n2+l 的性质， n 个结点的完全二义树的透厦川谕値飞 右为： 2 賢+1）。二义树的次序储备和二义链表储备的各自优缺点及适用场合, 二叉树的三叉链表表 示方法。2. 二叉树的三种遍历算法这一学问点把握的好坏, 将直接关系到树一章的算法能否理解，进而关系 到树一章的算法设计题能否顺当完

15、成。二义树的遍历算法有三种：先序，中序和后序。其划分的依 据是视其每个算法中对根结点数据的拜访次序而定。不仅要熟练把握三种遍历的递归算法，懂得其执行的实际步骤，并且应当娴熟把握三种遍历的非递归算法。山于二叉树一章的许多算法，可 U直接依据三种递归算法改造而来比呃 .求叶子个数），所以，把握了三种遍历的非递归算法 后，应付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。我会在另一篇 系列文章 （ http: /bbs.kaoyan./ibbs.dll.b.3&bp=2&bt=0 ）里给出三种遍历的递归和非递归算法的背记版，到时请大家肯定熟记。3. 可在三种遍历算法的基础上改造完

16、成的其它二义树算法：求叶子个数 - 求二义树结点 总数， 求度为 1 或度为 2 的结点 总数，复制一 .义树，建立一 .义树，交换左右子树 , 查找 值为 n 的某个指定结点，删除值为卫的某个指定结点，诸如此类等等等等假如你可以 娴熟寧握二义 W 的递归和非递归遍历算法一那么解决以上问题就是小菜二碟了。4. 线索二叉树：线索二义树的引出，是为防止如二义树遍历时的递归求解。众所周知，递归虽然形式上比较好懂得，但是消耗了大量的存资源，假如递归层次一多，势必带来资源耗尽的危急， 为了防止此类情形，线索二叉树便堂而皇之的显现了。对于线索二义树，应当把握：线索化的实质，三种线索化的算法，线索化后二义树

17、的遍历算法.基本线索二义树的其它算法问题（如：查找 某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。？ ？5. :* 优二叉树（哈夫曼树）：最优二叉树是为明白决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边给予了权值，这样形成的二义树按权相加之和是最小的。最优二义树一节， 直接考查算法源码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二义树，并求出其最小权值之和，此类题目不难，属送分题。贞脚.可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 6 页 - - - - - - - - - -可编

18、辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -6 .二义搜寻树（二义排序树）娴熟把握二叉搜寻树的构造 以及 节点芥 班除炎 作例 如删除其根节点时关键应找出右子树中最小的节点来替代其帳节点然后进行后续操作 ZB 树和 B+ 数同样把握 B 树的构建 , 添加节点与删除节点等操作8.树与森林：二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2 以及其它特征，一个最 重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不行交换的，假如交换了就成 了另外一棵二叉树，这样交换之后的二义树与原二叉树我们认为是不相同的两棵

19、二义树。但是，对 于一般的双分支树而言，不具有这种性质。树与森林的遍历，不像二叉树那样丰富，他们只有两种 遍历算法：先根与后根（对于森林而言称作：先序与后序遍历）。在难度比较大的考试中，也有基于此二种算法的基础上再进行扩展要求你利用这两种算法设讣其它算法的，但一般院校很少有这种 考法，最多只是要求你依据先根或后根写岀他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的： 先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。这一点成为许多学校的考点，考查的方式不一而足，有的直接考此句话，有的是先让你求解遍历序 列然后回答这个问题。 .二义树、树与森林之所以能有以上的

20、对应关系，全拜二义链表所赐。二义树 使用二叉链表分别存放他的左右孩子，树利用二义链表储备孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表储备孩子及兄弟。树一章，处处是重点，道道是考题，大家务必个个过关。第六章图假如说，从线性结构向树形结构硏究的转变，是数据结构学科对数据组织形式讨论的一次升华，那么从树形结构的讨论转到图形结构的讨论，就进一步让我们看到了数据结构对于解决实际问题 的重大推动作用。图这一章的特点是：概念繁多，与离散数学中图的概念联系紧密，算法复杂， 极易被考到，且简洁出大题，特殊是名校，作为考研课程，假如不考查树与图两章的学问，儿乎 是不行想像的。下面我们看一下图这一章的主要考

21、点以及这些考点的考查方式：1. 考查有关图的基本概念问题：这些概念是进行图一章学习的基础，这一童的概念包招图的定义 和特点 $无向妙 有向酸入度出度？完全釦生成子图2 路径乞度 回路 2（强）连通图 $（强连通重量等概念。与这些概念相联系的相关运算题也应当把握。2. 考查图的几种储备形式：图的储备形式包括，邻接矩阵. （逆）邻接表 / 十字链表及邻妾多玄表。 在考查时，有的学校是给出一种储备形式，要求考生用算法或手写岀与给定的结构相对应的该图的 另一种储备形式。3. 考查图的两种逊历算法: 深度遍历和广度遍历深度遍丿力和广度遍历是图的两种丛本的迪历算法, I 你度遍为相m：。 义树川 的先庁

22、遍刃.而厂度遍力机 、丫 r 1 义树 I】的层次逊为 .这两个算法对图二章的里要性等同于：先疗: 、中序 、JS 序遍历：对于二义树二章的重要性。在考 查时，图章的算法设计题常常是基于这两种基本的遍历算法而设讣的,比如：“求最长的最短路径 问题 : 和“判定两顶点间是否存在长为K 的简洁路径问题笃就分别用到了广度遍历和深度遍历算法。4. 生成树 . 最小生成树的概念以及毘小生成树的构造X 算法和 KRUSKAL算法。 考 查时，一般不要求写出算法源码，而是要求依据这两种最小生成树的算法思想写岀其构造过程及最终生成的 最小生成树。5. 拓扑井序问题：拓扑排序有两种方法，一是无前趋的顶点优先算法

23、，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”Wo 当然，后一种排序出来的 结果是“逆拓扑有序”的。6. 关键路径问融：这个问题是图一章的难点问题。懂得关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简洁的说，最 早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且， 要想求最晚时间必需是在全部的最早时间都已经求出来之后才能进行。这个问题拿来直接考算法贞脚.可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4

24、页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -源码的不多，一般是要求依据书上的算法描述求解的过程和步骤。在实际设计关键路径的算法 时，仍应当留意以下这一点：采纳邻接表的储备结构，求最早时间和最晚时间要采纳不同的处理方法， B|J： 在算法初始时，应当首先将全部顶点的最早时间全部置为0。关键路径问题是丄程进度掌握的重要方法，具有很强的有用性。7. 扇短洛径 问鬆： 与关键路径问题并称为图一章的两只拦路虎。概念懂得是比较简洁的,关键是算法的懂得。最短路径问题分为两种：一

25、是求从某一点动身到其余各点的最短路径。二是求图中每一 对顶点之间的最短路径。这个问题也具有特别有用的背景特色，一个典型的应当就是旅行景点及旅 游路线的挑选问题。解决第一个问题用DIJSKTRA算法 ,解决其次个问题用FLOYD算法。留意区 分。枠* 林留意区分关键路径问题与最短路径问题*第七章査找在不少数据结构的教材中，是把查找与排序放入高级数据结构中的。应当说，查找和排序两章是前 面我们所学的学问的综合运用，用到了树、也用到了链表等学问，对这些数据结构某一方面的运用 就构成了查找和排序。 现实生活中， search儿乎无处不在， 特殊 是现在的网络时代， 万事离不开search, 小到文档文

26、字的搜寻，大到INTERNET 的搜 索， search占据了我们上网的大部分时间。在复习这一章的学问时，你需要先弄清晰以下儿个概念：关键字、主关键字、次关键字的含义。静态查找与 动态查找的含义及区分;平均查找长度ASL 的概念及在各种查找算法中的讣算方法和运算结果，特别是一些典型结构的 ASL 值，应当记住。在DS 的教材中，一般将search分为三类 : 1st,在次序表上 的查找。 2nd,在树表上的查找。 3rd,在哈希表上的查找。下面具体介绍其考查学问点及考查方式：1. 线性表上的查找：主要分为三种线性结构：次序表，有序次序表，索引次序表。对于 第一种，我们采纳传统查找方法，逐个比较

27、。 对于既有序次序表我们采纳二分査找法。 对于第三种索引结构， 我们采纳索引查找算法。 考生需要留意这三种表下的 ASL 值以及 三种算法的实现。 其中， 二分查找仍要特殊留意适用条件以及其递归实现方法。2. 树表上的查找：这是本章的重点和难点。山于这一节介绍的容是使用树表进行的查找,所以很简洁与树一间的某些概念相混淆。本节容与树一章的容有联系，但也有许多不同,应留意规纳。 树表主要分为以下儿种: 二叉排序树， 平術二姻3 務 键树。其中 ,尤以前两种结构为重，也有部分名校偏 爱考 B 树的。由于二义排序树与平稳二义树是一种特殊的二叉树， 所以与二叉树的联系就更为紧密， 二叉树一章学好了，这里

28、也就不难To 二义排序树，简言之，就是“左小右大S 它的中序遍历结果是一个递增的有序序列。平稳二义树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定：深度之差的肯定值不得大于1。对于二义排序树，“判定某 棵 二义树是否二叉排序树”这一算法常常被考到，可用递归，也可以用非递归。平稳二义树的建立也是一个常考点，但该学问点归根结底仍是关注的平稳二叉树的四种调整算法，所以应当把握平稳 二义树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。 B 树是二叉排序树的进一步改进亍也可以把必树懂得为三叉四叉.排序树。除 B 树的査找算法外，应当特殊注 意一下

29、 E 珂的插入和删除算法。 由于这两种算法涉及到胚树结点的分裂和合并 是一个难点。 B 树是报考名校的同学应当关注的焦点之一。键树也称字符树，特殊适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是依据算法思想建立键树及描述其大致查找过程。X 基本哈希表的査找算法（应把握哈希表的用法）：哈希一词，是外来词，译自“ hash一”词 ，意为：散列或杂凑的意思。哈希表查找的基本思想是：依据当前待查找数据的特征，以记录关键字为自变量，设计一个function, 该函数对关键字进行转换后，其说明结果为待查的的址。基于哈希 表的考查点有：哈希函数的设计，冲突解决方法的挑选及冲突处理过程的描述。第八

30、章部排序排是 DS 课程中最终一个重要的章节，建立在此章之上的考题可以有多种类型：填空，挑选，判定 乃至大型算法题。但是，归结到一点，就是考查你对书本上的各种排序算法及其思想以及其优缺 点和性能指标（时间复杂度）能否了如指掌。这一章，我们对重点的规纳将跟以上各章不同。我 们将从以下儿个侧面来对排序一章进行不同的规纳，以期能更全面的懂得排序一章的总体结构及贞脚.可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结

31、归纳 - - - - - - - - - - - -各种算法。从排序算法的种类来分，本章主要阐述了以下儿种排序方法：插入 . （冒泡 I 挑选 希尔 .归并、快速 等五种排序方法。其中，在插入排序中乂可分为：直接插入、折半插入、2 路插入、希尔排序。这儿种插入排序算法的最根本的不同点，说究竟就是依据什么规章查找新元素的插入点。直接插入是依次查找，折半插 入是折半查找。希尔排序，是通过掌握每次参加排序的数的总围“山小到大”的增量来实现排序效 率提高的目的。*S待排序序列基本有序或规模很小时挑选插入排序法交拱 拧序，戈參 言汽玄 序， 在交换排序的基础上改址乂可以得鈔快速挑序思想，一语以敝之1 用

32、中间数将待排数据组一分为二快速排序，在处理的：问题规模”这个概念上，与希尔有点相反， 快速排怡是先处理一个较大规模, 撚后逐步把处理的规模降低，最终达到排序的U 的。选径排序， 相对于前面儿种排序算法来说，难度大一点。具体来说，它可以分为：简洁挑选、树选择、堆排。这三种方法的不同点是，依据什么规章选取最小的数。简洁挑选，是通过简洁的数组遍 历方案确定最小数。树挑选， 是通过“锦标赛”类似的思想，让两 数相比， 不断剔除较大 （小） 者，最终选出最小（大）数。而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。树挑选排

33、序，也曾经在 一些学校中的大型算法题中出现，请大家留意。右并排 序， 故名思义，是通过“归并”这种操作完成排序的 H 的，既然是归并就必需是 两者以上的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是 2 路归并。 算法思想比较简洁， 有一点，要铭远在归并滸序是稳固芍序。基数排序， 是一种很特殊的排序方法，也正是山于它的特殊，所以，基数排序就比较适合于一些特殊的场合，比如扑克牌排序问题等。基数排序，乂分为两种：多关键字的排序（扑克牌排序），链式排序（整数排序）。基数排序的核心思想也是利用“基数空间”这个概念将问题规模 规、变小，并且，在排序的过程中，只要依据基排的思想，是不用进行关键

34、字比较的，这样得出 的最终序列就是一个有序序列。本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必需把握的，学习时要 多留意规纳、总结、对比。此外，对于教材中的 10.7 节，要求必需熟记，在懂得的基础 上记忆，这一节儿乎成为许多学校每年的必考点。堆排序堆基于完全二义树，乂可分为大顶堆和小顶堆，把握堆的构建，与删除节点操作，如删除顶点时先将最终二个叶子节点与顶点交换位置, 然后进行再排序.贞脚.可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载