数据结构考研复习重点归纳

1、计算机吧，为计算机考研学生提供一站式的计算机考研服务。我们专注，所以我们更值得信任!II计算机吧【vwwz jsj8 ccrr专注于计算机考研为计算机考研提供一个免费的交流平台有丰富的计算机考研资料、考研视频、复试机试资料供大家免费下载欢迎大家访问：vwwv jsJ8 ccm彌结构复习重点归第数据结构学科的章节划分基本上为:概论，线性表，栈和队列，串,多维数组和广义农,树和二叉树, 图,査找,内排，外排，文件,动态存储分配.対绝人多数的学校而誌，“外拌，文件，动态存储分配”三章基本上是不考的，在大裳数高校的计算 机本科教学过程中，这三章也是基本上不作讲授的.所以.人家在这三章上可以不必花既过多

2、的桔力， 只要知道基木的概念即可但是，对于报考名校特别是该校又冇在试卷中对这三貳进行过考核的历史, 那么这部分朋友就要留意这三章了.按照以上我们给出的臣节以及对百三蔬的介绍，数抑:结构的帝节比匝人致为：林：内容很少，概念简的，分数大寒只冇儿分，冇的学校体至不考.41性表：基础章节.必考内容Z-.考题多数为基本概念题，名校考题中，鲜有大些算法设计題。如 果何，也足与其它章节内容和结合。枚和M：基础廉节，容易出基本概念題，必彩内容Z匕而找常与英它章节配介考査，也常与递归 等概念相联系进行考球.* :基础章节，概念絞为简单。专门针对于此章的大世算法设计题很少，较常见的是根据KMP进行 算法分析。MA

3、fiXTX* :基础章节，基数组的算法理也是估见的，分数比例波动较大，是出懸的“可选 取元”或“侯补单元”。一般如果要出题，多数不会作为大理出。数组常与“荻找，排序”等章节结介 来作为大题考査.tMimit ：重点难点章节,各校必考贞伉各校在此章出题的不同z处在于,迪否在本章中出 到 两道人的舜法设计懸.通过对多所7校的试卷分析，绝人多数学校在本帝都曾仃过出人型算法设汁题 的历史.:直点难点章节，名校尤爱考。如果作为取点來考，则多出现于分析卩设计题型肖中，可与树一章 共同构成算法设计人题的题型设计。査找:重点难点章节，櫃念较多，联系较为紧密，容易混汛出懸时可以作为分析型題H给出，在基 本概念科

4、题忖中也较为常见.算法设计科题中可以数组结介來考金，也町以与树-踊结介来考代.井序:与査找一章类似，本章同屈F重点难点章节，4概念更多，联系更为紧密，概念Z间更容易混 淆。在基本概念的舟査中.尤爱考外种拥序算法的优劣比较此类的题。算法设计人题中，如果作为出 题，那么谢与数组结介來有査.本章卞要起到总领作用.为或者进行数据结构的学习进行了一些先期铺堆。大家左要注怠以下儿点： 数据结构的基本概念，时何和空间复杂度的概念及度城力法，第法设计时的注盘事项。本帝考点不矢 只嬰稍加注盘理解即可。作为线件结构的开篇章节.线性衣一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低佔的。在这一章，

5、第次系统性地引入链式存储的概念，链式存储槪念将是整个数据结构学 科的重中之重，无论哪一章都涉及到了这个概念。总体来说，线件表一章可供考代的乖要考点冇以下几个方而：1线性衰的相关基本:,如：询驱、后继、税长、空表、首元结点,头结点,头指针筲概念。2. 线性农的结构特点，主要是指：除第-及垠后-个兀索外，毎个结点都只冇-个询趋和只冇-个后 继.3. 线件衣的顺序储方式及体诅冷坯境卜的两种不同实现：衣空何的静态分配和动态分配。静 态链农与顺序农的和似及不同Z处。4銭性表的链式存储方式及以下几种希用链表的特点和运算：单链表、循环链农，双向链农，双向循 环链表其中单链表的归并算法、循环链表的归并算法、双

6、向链表及双向循环链表的插入和删除算 法等都是较为常见的考査方式。此外，近年來在不少学校中还多次出现要求用递归算法实现单链衣输 出（可能足顺序也可能址倒序）的问题。在链农的小題醴中.经常考到一些诸如：判农空的题.在不同的链农中.其判农空的方式是不-样的, 请大家注意.5线性表的砒存储及链式存储情况下，其不同的优缺点比较,即其各自适用的场合.单链衣中设置 头指针、循环链农中设蜀址指针而不设蜀头指针以及索引存储结构的外门好处。第二章桟与队列栈与队列，是很等学习DS的同学遇到第-只拦路虎，很参人从这一章开始坐旱车，-总晕到规在。所以，理解栈少队列，是走向DS高F的一条必山Z路.©-学习此章询

7、，你可以问一卞fl（2址不址C经知逍了以卜儿点：1. 找、队列的定义及英相关数据结构的概念.包括：顺序栈，链找，共宁找，循环队列，链队等栈 与队列存取数据（请注意包括：存和取两部分）的特点.2. 递川算法。栈与递0的关系，以及借助栈将递归转向的经典算法：n!阶乘问题，fib数列问 题，hanoi问题，背包问题,二叉树的递归和非递归遍历问题,图的深度遍历与栈的关系等。其中, 涉及到树与图的问趙，多半会在树与图的相关章节中进行考査.3栈的应用：数值农达式的求解，挤号的配对等的脈理，只作凍理性了解，具体要求考査此为题H的 算法设计题不多。4. 循环队列中判队空、队満条件，循环队列中入队9出队知法.如

8、果你已经对上面的几点了如指掌,栈与队列一章可以不看15T»注意,我说的是可以不看书,并不宦可以不作题哦。©第三章串 经历了栈一章的痛苦煎熬后,终F迎来了串一章的柳暗花明.串，在概念上是比较少的一个章节，也是址帘易fl学的章节Z-,但止如毎个过來人所了解的，KMP 算法是这一章的重娶关隘，突破此关隘版，走过去乂是一马平川的人好DS di河呵呵.“ 帝需要攻破的主耍堡垒冇：1. 串的基本槪念，串与线性农的关系（串是其元索均为丫符世数据的特殊线性农），空串与空格串的区 别，申相等的条件2. 审的基本操作,以及这些基本函数的使用,包挤：取子串,小连接，申瞽换，求申长等等。运用串 的

9、荃本操作去完成特定的算法是很多学校在基本操作上的考査乖点.3. 顺用串与链串及块链串的区别和联系，实现方式.4. KMP毎法思想.KMP«!' next数组以及nextval数组的求法明确传统模式匹配算法的不足，明确next 敷组需要改进之外.梵中，理解知法是核心.会求数纽楚御分点.不用我务说，这节内容肚本章的 取中之取可能进行的考金方式是：求next和nextval数组值.根据求得的next或nextval数组值给 出运用KMP算法进行匹配的匹配过程。第四章数组与广义表学过程序语書的朋友，数组的概念我们C经不是第-次见到了，应该C经“一凹生，加熟” 了，所 以，在概念上，不

10、会"在太人障碍。但作为舟研课程來说，本章的考直重点可能9大学里的程序语盲 所关注的不太一样，下而会作介绍.广义衣的槪念，采数据结构里第-次出现的。它址线性衣或衣尤索的有限乍列，构成该结构的每个f 农或元索也是线性结构的，所以.这-章也归入线性结构中.本章的考代重点育：1. 多维数组中某数组九索的position求解。一般是给出数组元素的i'f尤索地址和毎个兀索山川的地址 空间并组给出女维数组的维数.然后要求你求出该数组中的某个元素所庄的位膛。2. 明确按行存储和按列存储的区别和联系并能够按照这两种不同的存储方式求解1中类些的题"3. 将特殊矩阵中的兀索按相咸的换算方

11、式存入数组中。这吐矩阵包括：対称矩阵，二角知阵，典令某 种特:点的稀疏矩阵等。熟悉稀筑矩阵的三种不同存储方式：三元组，帯辅助行向罐的元组，卜7链 衣存储.拿握将稀疏矩阵的三元组或二元组向十字链农进行转换的算法。4. 广义表的概念，特别应该明确表头与表尾的定义.这一点.是理解整个广义表一节算法的基础。近 來，在一些学校中，出现了这样一种题II类型：给出对某个广义农L若F个求了若干次的取头和収尾 染作后的小值，耍求求出原广义衣L。人家要留盘。5.9广义农冇关的递归算法.山丁广义农的定义就是递归的，所以，丐广义衣冇关的算法也術是递归 形式的.比如：求表深度.复制广义表等.这种懸H，可以根据不同角度广

12、义表的表现形式运用两种 不同的方式解答：一是把一个广义衣右作是& 1和k部分.分别対衣头和軽进彳J：操作：圧把 一个广义农看作是”干个子农，分别对毎个子农进行操作。第五章树与二叉树从对线件结构的研究过度到对树形结构的研究，是数据鉛构课用学习的一次跃变，此次跃变完成的好 坏，将直接关系到你到实际的考试中址否可以拿到高分，而这所仃的切，将址终彤响你的"业课总 分.所以，树这一晰的朿要性，己经不说fl明了.总体來说.树一章的知讲点包捕:义树的概念、性质和存储结构，义树遍历的三种算法（递归与非递归），在三种慕本遍历算法的基 础上实现叉树的其它算法，线索：叉树的概念和线索化算法以及线索

13、化后的査找算法，域优义树 的概念、构成和应用，树的概念和心储形式.树与森林的遍历算法及氏号二叉树遍历算法的联系，树 与森林和二叉树的转换.下面我们來看考试中对以上知识的主要考査方法:1 二叉树的概念、性质和存储结构考金方法可冇：血接考金二叉树的定义.计你说明二叉树与普通双分支树的区别；考賁满二义树和完 全：义树的性质，普通义树的五个性质：第i层的故多结点数.深度为k的二义树的绘多结点数， nO初2+1的性质，n个纟占点的完全.叉树的深度顺序储収树时孩子结点打父结点之.间的换算关 系（左为：2*i.右为:2*i+l）.二义树的顺序存储和艾链表存储的乞H优缺点及适用场介二艾树的三义链表表示方法。2

14、. 二叉树的三种遍历算法这知识点卑握的好坏，将血接关系到树-章的算法能否理解，进而关系到树章的算法设il懸能否 顾利完成.二叉树的遍历算法冇三种：先序.中序和后序.英划分的依据是视其侮个算法中对根结点 数据的访问顺序而定.不仅要熟练学握三种遍历的递归算法，理解英执行的实际步骤，并H.应该熟练 堂握三种遍历的非递归算法。山汶树-章的很女算法，町以世接根据三种递归算法改造而來（比 如：求叶子个数）,所以，掌握了三种遍历的非递归算法后,对付诸如：“利用非递归算法求:叉树叶 子个数”这样的题目就下笔如冇神了.我会在另一篇系列文章（ 归算法的背记版，到时请大家一定熟记。3. 可在三种遍历算法的基础上改适

15、完成的梵它叉树知汕：求叶子个数，求二叉树结点总数.求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左 右子树，代找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。如果你可以 熟练堂握二义树的递归和IE递归遍历算法，那么解决以上问题就是小菜-碟了。4. 线索:叉树:线玄二叉树的引出是为避免如叉树遍历时的递归求解.众所周知，递归虽然形式上比较好理解， 但是消耗r大磧的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为r避免此类惜况，线 索：义树便堂而呈z地出现了。対线索.义树，应该窣握：线索化的实质，二种线索化的算法，线 索化肓叉树的遍历知法.基本线索.叉树的其它知法

16、问题（如：査找某-类线索二叉树中指定结点 的前驱或麻继结点就足一类常考题）.5. 绘优二叉树（哈夫曼树）：蚁优义树采为了解决特圧问题引出的特殊.义树结构，它的询捉是给：义树的毎条边賦卩了权值， 这样形成的叉树按权相加之和是最小的.最优叉树节,直接考金算法源码的很少,般是给你 一组数据，要求你建立基于这组数据的垠优：叉树.并求出其最小权值之和，此类建h不难，屈送分 题。6. 树与森林:二叉树是种特殊的树这种特殊不仅仅在丁贞分支城多为2以及氏它特征，-个胶贡要的特殊之处 是在于：二叉树是有序的！即：二叉树的耳右孩子足不可交换的.如果交换了就成了另外-棵二叉树, 这样交换Z后的:叉树与原二叉树我们认

17、为是不相同的两棵:叉树。但是，对F普通的双分支树而言, 不具有这种性质.树与森林的遍历,不像叉树那样E富.他们只有两种遍历算法:先根与后根（对于森林而言称作: 先序勺赣序遍历。在难度比枚大的考试中，也仃基于此种笄法的呈础匕冉进仃扩脱要求你利用这两 种算法设il其它算法的，但-般院校很少仃这种考法，赧篡只是耍求你根振先根或肩根耳出他们的遍 历序列。此者的先根与百根遍历与艾树屮的遍历算法是右对应关系的：先根遍历对应-义树的先 序迟历,而后根遍历对应二叉树的中序遍历.这点成为很多学校的考点，考査的方式不 而足,有 的血接考此句话，冇的是先让你求解遍历序列然后I叫答这个问题。二叉树、树与森林之所以能冇

18、以上 的对应关系，全拜二叉链表所賜.二艾树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储 孩子及兄弟（称孩子兄弟链丧），而森林也是利用二义链农存储孩子及兄弟。树-偉，处处是贡点，道道是考懸大家务必个个过关.第六章图如果说，从线性结构向树形结构研究的转变是数抑;給构学科对数抓组织形式研究的次升华，那么 从树形结构的研究转到图形结构的研究则进步il我们看到了数抑;給构对解决实际问题的垂大推 动作用.图这-诡的特占是：概念緊炙仃离散数学屮图的概念联系紧密，算法父杂，极易彼考到，II容易出 大題，尤英是名校.作为考研课程，如果不考査树与图两章的知识，几乎足不可想像的.下仙我们看-下图这-章的上炊

19、考点以及这些考点的考査方式：1. 考査有关图的基木概念问题：这些概念是进行图-帝学习的忒础.这-章的概念包拆：图的定义和特点，无向图，冇向图，入度， 出度，完金图，牛成子图.路轻长度，阿路，（强）连通图，（强）连通分航等概念。与这些概念相联 系的相关计算邀也应该掌握。2 .考査图的几种存储形式:图的存储形式包括：邻接矩阵，（逆）邻接农，十字链农及邻接多录表.在考茂时，冇的学校是给出一 种存储形式，熨求考牛用算法或手写出与给定的结构柑対应的该图的另一种存储形式。3. 考査图的两种遍历算法：除度遍丿和广度遍历深度遍历和广度追历是图的两种基本的遍历毎法.这两个毎法对图帝的重耍性等同丁"先序

20、、中序、 肓序遍历”对于一叉树一章的雨要件在考金时，图一章的算法设计题常常是基于这两种基本的遍历 算法而设计的，比如：“求垠长的垠短路径问题”和“判晰两顶点间是古存在长为K的简单路径问建”, 就分别用到了广度遍历和深度遍历算法。4. 生成树、最小生成树的概念以及加小生成树的构造：PRIM算法和KRUSKAL算法。考金时，-般不要求写出算法源码.而是要求根拯这两稍最小牛成树的算法思想写出其构造过程及绘 终生成的最小生成树。5. 拓扑排序问题:拓扑排序冇两种方法，兄无前遁的顶点优先知法，足无后继的顶点优先算法。换句话说，种楚 “从前向后”的排序,一种是“从后向前”排.当然,后一种排序出来的结果是“

21、逆拓扑有序”的。6. 关键路径问题：这个何题是图偉的娅点问懸。理解关键路径的关键仃三个方1仏 是何谓关键路径，是购4时间 是什么意思、如何求,三是最晚时间是什么意思、如何求.简单地说,最早时间是通过“从前向后” 的方法求的，而最晚时间是通过“从晴向询”的方法求解的，并区要想求最晚时间必须是在所有的 蚁早时何都己经求出來Z垢才能进行。这个问题拿來1接考算法源码的不多，一般是耍求按照£上的 算法描述求解的过程和步骤。在实际设计关键路径的知法时.还应该注帝以下这点：采用邻接农的存储结构，求域早时间和胶晚 时间要采用不冋的处理方法，即：在算法初始时.应该洎先将所们顶点的垠早时间全部代为0.关

22、愷 路径问题是工程进度控制的重姿方法，具有很强的实用性。7. 最短路径问聽:与关键路径问題并称为图-章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。瑕短路径 问越分为两种：-是求从荣点出发到其余乂点的啟短路径：是求图中毎-对顶点之间的Id短路径. 这个问越也II冇非常实用的背就特色.一个典弋的应该就是旅游就点及旅游路线的选择问題.解决第 一个问题用DUSKTRA算法，解决第个问题用FLOYD算法。注总区分。第七章査找在不少数据结构的教材中，是把金找与排序放入高级数抵结构中的。应该说，金找和排序两章是谕ihi 我们所学的知i只的综合运用，川到树、也川到了链农筹知识，对这些数抿结构某-7/

23、lftl的运用就构 成了査找和排序。现实生活中，search儿卩无处不在，特别是现在的网络时代.万节离不开search.小到文档内文字的 捜索，人到INTERNET上的搜索，search .V据了我们上网的人部分时间。在复习这帝的知识时.你需要先弄消楚以下几个概念：关键7、主关键字、次关键字的含义：静态代找与动态伟找的介义及区别：半均代找长度ASL的概念 及在各种査找算法中的计算方法和计算结果.特别是一些典型结构的ASL值，应该记住。在DS的教材中，-般将search分为三类：1st.在顺序农上的茂找：2nd.在树农上的金找：3rd.在 哈希表上的責找.下面详细介绍其考査知识点及考査方式：1.

24、 线性农上的査找：主要分为三种线性结构:顾序表.有序顾序表.索引顺序表.对于第-种，我们采用传统査找方法, 逐个比较。对于及令序顺序农我们釆用.分金找法。对于第三种索引结构，我们采用索引金找算法。考生盅嘤注盘这三种衣卜的ASL值以及二种算法的实现。其屮，分仓找还耍持别注总适用条件以及 其递01实现方法。2. 树表上的資找：这是本章的重点和难点.山于这一节介绍的内容是使用树农进行的査找，所以很容易与树一间的某些 概念相混淆.冷节内容与树一章的内容有联系,但也有很多不同，应注总规纳。树表主要分为以下儿 种：叉押序树.平衡二叉树.B树，键树苴中，尤以询两种结构为3L也冇部分名校偏爱考B树 的.山于二

25、叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就更为紧密，二叉树一 章学好了，这里也就不难了.二叉排序树,简言之,就是“左小右大”，它的中序遍历结果雄一个递增的有序序列。平衡:叉树是二 叉拮：序树的优化.其木质也是-种二叉拥序树，只不过，平衡二叉树对左右子树的深度冇了限定：深 度之差的绝对值不得大于i对于二叉排序树，“判断某棵二叉树是否：叉排序树”这一算法经常被考 到，可用递归，也可以用非递归.半衡.义树的建立也是一个常考点，但该知识点归根结底还是关注 的平術二叉树的四种调整算法，所以应该生握平衡义树的四种调整算法，调整的 个参陳址：调整 询厉的中序追历结果相同.B树是二叉排序树的

26、进一步改进,也可以把B树理解为三叉、卩q叉.排序树。除B树的査找算法外, 应该持别注盘一下B树的插入和删除算法。因为这两种算法涉及到B树结点的分裂和合并，是-个难 点。B树是报考名校的同学应该关注的焦点Z 。礎树也称了符树.特别适用丁诜找英文m词的场介.般不耍求能完整描述算法源码，务是根据算法 思、想建立键树及描述其大致査找过程.3. 基本哈希表的査找算法：哈希一词,是外来词,译自“hash” 诃，总为：散列或杂凑的意恩哈希表査找的基本思想是:根 据卅询待査找数据的特征，以记录关键了为nu!.设il 个function,该函数对关键了辺行转换几 雄解释结果为待介的地址.基丁哈卅农的考充点冇：哈

27、希函数的设计，冲突解决方法的选择及冲突处 理过程的描述.第八章内部排序内卄是DS课程中垠后个匝耍的章节，建立在此章之上的考题可以冇筋种类樂：填空，选择，判断 乃至大熨算法趙.但足，归结到一点，就是考金你对甘木匕的各种排序算法及其思想以及其优缺点和 性能指标（时间复杂度）能否了如指掌。这 偉，我们对贡点的规纳将珮以上并章不同.我们将从以下几个侧而來对排序-章进行不同的规纳. 以期能更全面的理解排序一章的总体结构及各种算法.从排序算法的种类来分,本章主要阐述了以下几种排序方法:播入、选择、交换、归并、计数尊五种 排序方法.其中,在插入排序中又可分为:直接插入、折半插入、2路插入、希尔排序。这儿种插

28、入排序算法的 蚁根本的不同点说到底就是根据什么规则、/找莎尤索的播入点。门接插入址依次J找，折半插入是 折半寻找.希尔持序，是通过拎制毎次参号排序的数的总范用“山小到大”的増晟來实现排序效率提 高的目的.交换排序.又称R泡押序.在交换扑序的基础上改进又可以得到快速扌IT序。快速拮序的思想，语以 敝之：用中间数将待押数据组一分为二快速排序,在处理的“问题規模”这个權念上，与希尔有点 郴反，快速排序，是先处理一个较大规模，然后逐渐把处理的规模降低，绘终达到排序的II的。选择押序，相对于前面几种|排序算法来说,难度大一点具体来说,它可以分为：简单选择、树选择、 堆排.这三种方法的不同点是.根据什么规

29、则选取呆小的数.简单选择是通过简单的数组遍历方案 确定垠小数：树选择.是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大（小）者，绘终选 出鼓小（人）数：而堆排序,处利用堆这种数据结构的性质,通过堆元素的删除、调整等一系列操作 将加小数选出放在堆顶.堆排序中的堆建匕 堆调整是贡要考点。树选择拮序，也曾经在些学校中 的大型算法题中出现.请大家注总.01并排序，故名思义.込通过“归并”这种操作完成搏学的口的，既然址0并就必须是两者以上的数 据集合才可能实现归并.所以.止归并排序中.关注垠多的就足2路归并。算法思想比较简也 冇 点，要铭记在心：归并排序足稳定排序.基数排序,是种很特别的排序方法,也

30、正丛山于它的特殊,所以，基数排序就比较适合于-些特别 的场合,比如扑克牌排序问题等.基数排序,又分为两种：多关键字的排序（扑克牌排序）,链式排序 （整数旅序）。基数排序的核心思想也是利用“基数空间”这个概念将问题规模规范、变小，并仕，在 排序的过程中，只嬰按照基排的思想.是不川进行关键7比较的，这样得出的址终序列就是一个宵序 序列。本章各种押序算法的思想以及伪代码实现，及貝:时间复杂度都足必须举握的，学习时要多注意规纳、 总结、対比。此外，对F教材中的10.7节，要求必須熟记,在理解的基础上记忆，这一节几乎成为很多学校每年的必考点。二叉树三种遍历的非递归算法（背诵版）本贴给出:叉树先序、中序、

31、后序三种遍历的非递归算法.此三个算法可视为标准算法直接用于考研答 题。1. 先序遍历非递归算法#define maxsize 100typedef structBitree Elemmaxsize;int top;SqStack;void PreOrder U nrec (Bi tree t) Sq Stack s;Stacklnit(s);P=t； while (p!=null | !StackEmpty(s)while (p!=null)遍历左子树 visite(p->data); push(szp); p=p->lchild;/endwhileif (!StackEmpty(

32、s)通过下次循环中的内I茨while实现右子树遍历p=pop(s); p=p->rchild;/endif/endwhile/PreOrderUnrec2. 中序遷历非递归算法#define maxsize 100typedef structBitree Elemmaxsize;int top;SqStack;void InOrderUnrec( Bitree t) Sq Stack s;Stacklnit(s);P=t；while (p!=null | !StackEmpty(s)while (p!=null)遍历左子树push(s,p);p=p->lchild;/end whi

33、le if (!StackEmpty(s)访问根结点通过卜一次循环实现右了树遍历p=pop(s); visite(p->data); p=p->rchild;/endif/endwhile/InOrderUnr &3鮎序遍丿4递归算法#define maxsize 100typedef enu mL,R tag type; typedef structBitree ptr;tagtype tag;stacknode;typedef structstack node Elem maxsize; int top;SqStack;void PostOrderUnrec(Bitre

34、e t)Sq Stack s; stacknode x;Stacklnit(s);dowhile (p!=null) x.tag = L; push(s,x); p=p->lchild;遍历左子树标记为兀子树while (IStackEmpty(s) && s.Elems.top.tag=R)X = pop(s);p = x.ptr;visite(p->data); /tag为R.衣示右了树访问完毕，故访间根结点 if (SStackEmpty(s)s.Elems.top.tag =R;遍历右了树p=s. Elems.top ptr- > rc hild;wh

35、ile (!StackEmpty(s);/PostOrderU nrec重庆大学2000一、填空1、-个连通图的是-个极小连通子图。2、在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为3、法构造的哈希函数肯定不会发生冲突.4、设止文串长度为N,模式串长度为则串匹配的KMP算法的时间复杂度为5、广义农的定义为广义衣中拆弧的重数据。6、排序不需要进行记录关键字间的比较.7、又称作先进先出表。8、具河N个结点的义树，采川二义链衣存储，共有 个空链域。9、利用树的孩子兄弟农示法存储可以将一棵树转换为。10表达式求值圧应用的一个典型例子。二、简答题1、稀疏矩阵的三元组表存储结构中，记录的域MU、NU、TU和DATA分别存放什么内容？2、已知-棵义树的后序遍历序列为EICBGAHDF同时知道该叉树的中用遍历序列为CEIFGBADH. 试画出该二叉树。3、己知两个各包仟N和M个记录的It好序的文件能在O (N+NI)时间内合并为个包倉N+M个记录的 排好序的文件.当有多于两个排好序的文件要被合并在一起时，只需币:圮成对地合并便可完成。合并 的步骤不同,所需花费的记录移动次数也不同现有文件Fl, F2, F3, F4, F5.各有记录数为20, 30, 10, 5和30.试找出记录移动次数敲少的合并步驟。4、对二叉fll序树的金找都是从根