【精品】【考研计算机专业课】厦门大学 《数据结构》期末复习（可编辑.ppt

《【精品】【考研计算机专业课】厦门大学 《数据结构》期末复习（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】厦门大学 《数据结构》期末复习（可编辑.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【考研计算机专业课】厦门大学 数据结构期末复习l l期末考试题型：与期中样卷类似，题目主要是选择题、期末考试题型：与期中样卷类似，题目主要是选择题、填空题、判断题、简答题、设计题（数据结构填空题、判断题、简答题、设计题（数据结构/算法设算法设计）、应用题（数据结构计）、应用题（数据结构/算法的实际运用）和证明题算法的实际运用）和证明题等等。等等。l l考试范围：第一章到第十二章（考试范围：第一章到第十二章（第八、十一和十二章第八、十一和十二章此次不作要求；其它章节具体要求以此次不作要求；其它章节具体要求以数据结构复习数据结构复习大纲大纲.doc.doc为准。为准。）l l设计题：面向问题，解决

2、问题。作答最好是先给出算设计题：面向问题，解决问题。作答最好是先给出算法描述，再给出具体的程序（可以利用书上的典型数法描述，再给出具体的程序（可以利用书上的典型数据结构和基本操作）。据结构和基本操作）。l l应用题：数据结构应用题：数据结构/算法的运用实例，比如哈曼树，折算法的运用实例，比如哈曼树，折半查找，半查找，HASHHASH表，二叉排序树，表，二叉排序树，B B树等等（主要集中树等等（主要集中在第在第410410章，尤其是章，尤其是610610章的典型问题和算法）；章的典型问题和算法）；l l期末成绩：期末成绩：l l理论部分：期末成绩为主，再参考平时成绩；理论部分：期末成绩为主，再参

3、考平时成绩；l l实验部分：以平时的各个大实验的成绩为主。实验部分：以平时的各个大实验的成绩为主。l l以下复习资料转自转自免费考研网，略作修改补充l l数据结构复习重点归纳笔记清华严蔚敏版l l数据结构的章节结构及重点构成数据结构的章节结构及重点构成l l数据结构学科的章节划分基本上为：概论，线数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动和二叉树，图，查找，内排，外排，文件，动态存储分配。态存储分配。l l对于绝大多数的学校而言，对于绝大多数的学校而言，“外排，文件，动外排，文

4、件，动态存储分配态存储分配”三章基本上是不考的，在大多数三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。朋友就要留意这三章了。l l对于每一章，要清楚对于每一章，要清楚1 1想解决的问题想解决的问题

5、2 2基本的数据结构基本的数据结构3 3基本的操作基本的操作4 4算法（特别是经典算法）的解决思路，程序算法（特别是经典算法）的解决思路，程序实现及时间复杂性实现及时间复杂性经典算法比如：有序表的归并，经典算法比如：有序表的归并，KMPKMP算法，矩阵算法，矩阵的快速转置，二叉树（递归或非递归）的遍历，的快速转置，二叉树（递归或非递归）的遍历，图的（广度优先和深度优先）遍历，最小生成图的（广度优先和深度优先）遍历，最小生成树，最短路径，折半查找，冒泡排序，快速排树，最短路径，折半查找，冒泡排序，快速排序等等序等等l l概述l l本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。

6、大家主要注意以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注意事项。本章考点不多，只要稍加注意理解即可。l l主要考时间复杂性的计算，时间复杂性的比较l l线性表线性表l l作为线性结构的开篇章节，线性表一章在线性结构的作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这

7、个概念。之重，无论哪一章都涉及到了这个概念。l l总体来说，线性表一章可供考查的重要考点有以下几总体来说，线性表一章可供考查的重要考点有以下几个方面：个方面：1.1.线性表的相关基本概念，如：前驱、后继、表长、空表、线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。首元结点，头结点，头指针等概念。2.2.线性表的结构特点，主要是指：除第一及最后一个元素线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。外，每个结点都只有一个前趋和只有一个后继。3.3.线性表的顺序存储方式及其在具体语言环境下的两种不线性表的顺序存储方式及其在

8、具体语言环境下的两种不同实现：表空间的静态分配和动态分配。静态链表与同实现：表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。顺序表的相似及不同之处。4.4.线性表的链式存储方式及以下几种常用链表的特点和运线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除算法等都是较为向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。此外，近年来在不少学校中还多次常见的考查方

9、式。此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出（可能是顺序也出现要求用递归算法实现单链表输出（可能是顺序也可能是倒序）的问题。可能是倒序）的问题。在链表的小题型中，经常考到一些诸如：判表空的题。在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是不一样的，请大在不同的链表中，其判表空的方式是不一样的，请大家注意。家注意。5.5.线性表的顺序存储及链式存储情况下，其不同的优缺点线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针

10、的各自好处。循环链表中设置尾指针而不设置头指针的各自好处。l l栈与队列栈与队列l l栈与队列，是很多学习栈与队列，是很多学习DSDS的同学遇到第一只拦路虎，很多人从这一的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向DSDS高高手的一条必由之路，。手的一条必由之路，。l l学习此章前，你可以问一下自己是不是已经知道了以下几点：学习此章前，你可以问一下自己是不是已经知道了以下几点：l l1.1.栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，栈、队列的定义及其相关数据结构的概念，包括：顺序

11、栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。取两部分）的特点。l l2.2.递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：典算法：n!n!阶乘问题，阶乘问题，fibfib数列问题，数列问题，hanoihanoi问题，背包问题，二叉树问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进

12、行考查。到树与图的问题，多半会在树与图的相关章节中进行考查。l l3.3.栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。了解，具体要求考查此为题目的算法设计题不多。l l4.4.循环队列中判队空、队满条件，循环队列中入队与出队算法。循环队列中判队空、队满条件，循环队列中入队与出队算法。l l5.5.栈的栈的InitStack,Push,Pop,StackEmptyInitStack,Push,Pop,StackEmpty等基本操作，队列的等基本操作，队列的InitQueue,Que

13、ueEmpty,EnQueue,DeQueueInitQueue,QueueEmpty,EnQueue,DeQueue等基本操作等基本操作l l如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。意，我说的是可以不看书，并不是可以不作题哦。l l串串l l经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。l l串，在概念上是比较少的一个章节，也是最容易自学的章节之一，串，在概念上是比较少的一个章节，也是最容易自学的章节之一，但

14、正如每个过来人所了解的，但正如每个过来人所了解的，KMPKMP算法是这一章的重要关隘，突算法是这一章的重要关隘，突破此关隘后，走过去又是一马平川的大好破此关隘后，走过去又是一马平川的大好DSDS山河了，呵呵。山河了，呵呵。l l串一章需要攻破的主要堡垒有：串一章需要攻破的主要堡垒有：l l1.1.串的基本概念，串与线性表的关系（串是其元素均为字符型数串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区别，串相等的条件据的特殊线性表），空串与空格串的区别，串相等的条件l l2.2.串的基本操作，以及这些基本函数的使用，包括：取子串，串串的基本操作，以及这些基本

15、函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。法是很多学校在基本操作上的考查重点。l l3.3.顺序串与链串及块链串的区别和联系，实现方式。顺序串与链串及块链串的区别和联系，实现方式。l l4.KMP4.KMP算法思想。算法思想。KMPKMP中中nextnext数组以及数组以及nextvalnextval数组的求法。明确数组的求法。明确传统模式匹配算法的不足，明确传统模式匹配算法的不足，明确nextnext数组需要改进之外。其中，数组需要改进之外。其中，理解算法是核

16、心，会求数组是得分点。不用我多说，这一节内容理解算法是核心，会求数组是得分点。不用我多说，这一节内容是本章的重中之重。可能进行的考查方式是：求是本章的重中之重。可能进行的考查方式是：求nextnext和和nextvalnextval数数组值，根据求得的组值，根据求得的nextnext或或nextvalnextval数组值给出运用数组值给出运用KMPKMP算法进行匹算法进行匹配的匹配过程。配的匹配过程。l l数组与广义表数组与广义表l l学过程序语言的朋友，数组的概念我们已经不是第一次见到了，学过程序语言的朋友，数组的概念我们已经不是第一次见到了，应该已经应该已经“一回生，二回熟一回生，二回熟”

17、了，所以，在概念上，不会存在太了，所以，在概念上，不会存在太大障碍。但作为考研课程来说，本章的考查重点可能与大学里的大障碍。但作为考研课程来说，本章的考查重点可能与大学里的程序语言所关注的不太一样，下面会作介绍。程序语言所关注的不太一样，下面会作介绍。l l广义表的概念，是数据结构里第一次出现的。它是线性表或表元广义表的概念，是数据结构里第一次出现的。它是线性表或表元素的有限序列，构成该结构的每个子表或元素也是线性结构的，素的有限序列，构成该结构的每个子表或元素也是线性结构的，l l本章的考查重点有：本章的考查重点有：l l1.1.多维数组中某数组元素的多维数组中某数组元素的positionp

18、osition求解。一般是给出数组元素的求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。然后要求你求出该数组中的某个元素所在的位置。l l2.2.明确按行存储和按列存储的区别和联系，并能够按照这两种不明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解同的存储方式求解1 1中类型的题。中类型的题。l l3.3.将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩阵

19、，具有某种特点的稀疏矩阵等。熟悉包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的三元组，稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的三元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。行转换的算法。l l4.4.广义表的概念，特别应该明确表头与表尾的定义。这一广义表的概念，特别应该明确表头与表尾的定义。这一点，是理解整个广义表一节算法的基础。传统经常给出某点，是理解整个广义表一节算法的基础。传统经常给出某个广义表，要求给出对应的广义表存储结构，注意两

20、种存个广义表，要求给出对应的广义表存储结构，注意两种存储结构不要混淆。近来，在一些学校中，出现了这样一种储结构不要混淆。近来，在一些学校中，出现了这样一种题目类型：给出对某个广义表题目类型：给出对某个广义表L L若干个求了若干次的取头若干个求了若干次的取头和取尾操作后的串值，要求求出原广义表和取尾操作后的串值，要求求出原广义表L L。大家要留意。大家要留意。l l5.5.与广义表有关的递归算法。由于广义表的定义就是递归与广义表有关的递归算法。由于广义表的定义就是递归的，所以，与广义表有关的算法也常是递归形式的。比如：的，所以，与广义表有关的算法也常是递归形式的。比如：求表深度，复制广义表等。这

21、种题目，可以根据不同角度求表深度，复制广义表等。这种题目，可以根据不同角度广义表的表现形式运用两种不同的方式解答：一是把一个广义表的表现形式运用两种不同的方式解答：一是把一个广义表看作是表头和表尾两部分，分别对表头和表尾进行广义表看作是表头和表尾两部分，分别对表头和表尾进行操作；二是把一个广义表看作是若干个子表，分别对每个操作；二是把一个广义表看作是若干个子表，分别对每个子表进行操作。子表进行操作。l l树与二叉树树与二叉树l l从对线性结构的研究过度到对树形结构的研究，是数据结构课程学习从对线性结构的研究过度到对树形结构的研究，是数据结构课程学习的一次跃变，此次跃变完成的好坏，将直接关系到你

22、到实际的考试中的一次跃变，此次跃变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这所有的一切，将最终影响你的专业课总分。是否可以拿到高分，而这所有的一切，将最终影响你的专业课总分。所以，树这一章的重要性，已经不说自明了。所以，树这一章的重要性，已经不说自明了。l l总体来说，树一章的知识点包括：总体来说，树一章的知识点包括：l l二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本遍历算法的基础上实现二叉树的其它算法，线索递归），在三种基本遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和

23、线索化算法以及线索化后的查找算法，最优二叉树的二叉树的概念和线索化算法以及线索化后的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。与二叉树遍历算法的联系，树与森林和二叉树的转换。l l下面我们来看考试中对以上知识的主要考查方法：下面我们来看考试中对以上知识的主要考查方法：l l1.1.二叉树的概念、性质和存储结构二叉树的概念、性质和存储结构l l考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分考查方法可有：直接考查二叉树的定义，让你说明二叉

24、树与普通双分支树的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个支树的区别；考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：第性质：第i i层的最多结点数，深度为层的最多结点数，深度为k k的二叉树的最多结点数，的二叉树的最多结点数，n0=n2+1n0=n2+1的性质，的性质，n n个结点的完全二叉树的深度，顺序存储二叉树时个结点的完全二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算关系（左为：孩子结点与父结点之间的换算关系（左为：2*i2*i，右为：，右为：2*i+12*i+1）。）。l l二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树二叉树的顺序存储和二

25、叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法。的三叉链表表示方法。l l2.2.二叉树的三种遍历算法二叉树的三种遍历算法l l这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，到树一章的算法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且定。不仅要熟

26、练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法，可以直接根据三种递归算法改造而来（比如：求叶子个数），所以，掌握了三直接根据三种递归算法改造而来（比如：求叶子个数），所以，掌握了三种遍历的非递归算法后，对付诸如：种遍历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。我会在另一篇系列文章这样的题目就下笔如有神了。我会在另一篇系列文章（http:/ l3.3.可在三种遍历算法的基础上改造完成的其它二叉树算

27、法：可在三种遍历算法的基础上改造完成的其它二叉树算法：l l求叶子个数，求二叉树结点总数，求度为求叶子个数，求二叉树结点总数，求度为1 1或度为或度为2 2的结点总数，复制二叉的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为树，建立二叉树，交换左右子树，查找值为n n的某个指定结点，删除值为的某个指定结点，删除值为n n的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜一碟了。和非递归遍历算法，那么解决以上问题就是小菜一碟了。l l4.4.线索二叉树：线索二叉树：l

28、 l线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的之地出现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：算法，线索化后二叉

29、树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。l l5.5.最优二叉树（哈夫曼树）：最优二叉树（哈夫曼树）：l l最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据，要求你优二叉树一节，直接考查算法源码的很少

30、，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分题。另外，还有考叶子结点与结点总数的关系。属送分题。另外，还有考叶子结点与结点总数的关系。l l6.6.树与森林：树与森林：l l二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2 2以及其它特以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉

31、树，这样交换之后的孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是，对于普通的双二叉树与原二叉树我们认为是不相同的两棵二叉树。但是，对于普通的双分支树而言，不具有这种性质。分支树而言，不具有这种性质。l l树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根（对于森林而言称作：先序与后序遍历）。在难度比较大的考试中，后根（对于森林而言称作：先序与后序遍历）。在难度比较大的考试中，也有基于此二种算法的基础上再进行扩展要求你利用这两种算法设计其它也有基于

32、此二种算法的基础上再进行扩展要求你利用这两种算法设计其它算法的，但一般院校很少有这种考法，最多只是要求你根据先根或后根写算法的，但一般院校很少有这种考法，最多只是要求你根据先根或后根写出他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍历算法是有出他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。这一点成为很多学校的考点，考查的方式不一而足，有的直接中序遍历。这一点成为很多学校的考点，考查的方式不一而足，有的直接考此句话，有的是先让你求解遍历序

33、列然后回答这个问题。二叉树、树与考此句话，有的是先让你求解遍历序列然后回答这个问题。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。链表），而森林也是利用二叉链表存储孩子及兄弟。l l树一章，处处是重点，道道是考题，大家务必个个过关。树一章，处处是重点，道道是考题，大家务必个个过关。l l图图l l如果说，从线性结构向树形结构研究的

34、转变，是数据结构学科对数据如果说，从线性结构向树形结构研究的转变，是数据结构学科对数据组织形式研究的一次升华，那么从树形结构的研究转到图形结构的研组织形式研究的一次升华，那么从树形结构的研究转到图形结构的研究，则进一步让我们看到了数据结构对于解决实际问题的重大推动作究，则进一步让我们看到了数据结构对于解决实际问题的重大推动作用。用。l l图这一章的特点是：概念繁多，与离散数学中图的概念联系紧密，算图这一章的特点是：概念繁多，与离散数学中图的概念联系紧密，算法复杂，极易被考到，且容易出大题，尤其是名校，作为考研课程，法复杂，极易被考到，且容易出大题，尤其是名校，作为考研课程，如果不考查树与图两章

35、的知识，几乎是不可想像的。如果不考查树与图两章的知识，几乎是不可想像的。l l下面我们看一下图这一章的主要考点以及这些考点的考查方式：下面我们看一下图这一章的主要考点以及这些考点的考查方式：l l1.1.考查有关图的基本概念问题：考查有关图的基本概念问题：l l这些概念是进行图一章学习的基础，这一章的概念包括：图的定义和这些概念是进行图一章学习的基础，这一章的概念包括：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，特点，无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。与这些概念相联系的回路，（强）连通图，（强）连通分量

36、等概念。与这些概念相联系的相关计算题也应该掌握。相关计算题也应该掌握。l l2.2.考查图的几种存储形式：考查图的几种存储形式：l l图的存储形式包括：邻接矩阵，（逆）邻接表，十字链表及邻接多重图的存储形式包括：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。在考查时，有的学校是给出一种存储形式，要求考生用算法或手表。在考查时，有的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另一种存储形式。写出与给定的结构相对应的该图的另一种存储形式。l l3.3.考查图的两种遍历算法：深度遍历和广度遍历考查图的两种遍历算法：深度遍历和广度遍历l l深度遍历和广度遍历是图的两种基本的

37、遍历算法，这两个算法对图一深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于章的重要性等同于“先序、中序、后序遍历先序、中序、后序遍历”对于二叉树一章的重要对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算性。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：法而设计的，比如：“求最长的最短路径问题求最长的最短路径问题”和和“判断两顶点间是判断两顶点间是否存在长为否存在长为K K的简单路径问题的简单路径问题”，就分别用到了广度遍历和深度遍历，就分别用到了广度遍历和深度遍历算法。算法。l l4.4.生成树、最小生成树

38、的概念以及最小生成树的构造：生成树、最小生成树的概念以及最小生成树的构造：PRIMPRIM算法和算法和KRUSKALKRUSKAL算法。算法。l l考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。另外，也经常的算法思想写出其构造过程及最终生成的最小生成树。另外，也经常考考MSTMST性质、性质、PRIMPRIM算法和算法和KRUSKALKRUSKAL算法可靠性的证明。算法可靠性的证明。l l5.5.拓扑排序问题：拓扑排序问题：l l拓扑排序有两种方法，一是无前趋的顶点优先算法

39、，二是无后继的顶拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是点优先算法。换句话说，一种是“从前向后从前向后”的排序，一种是的排序，一种是“从后从后向前向前”排。当然，后一种排序出来的结果是排。当然，后一种排序出来的结果是“逆拓扑有序逆拓扑有序”的。的。l l另外，值得注意的是，也可利用拓扑排序算法来确定有向图是否有环。另外，值得注意的是，也可利用拓扑排序算法来确定有向图是否有环。l l6.6.关键路径问题：关键路径问题：l l这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓

40、关键路径，二是最早时间是什么意思、如何求，三是最晚时间是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过是什么意思、如何求。简单地说，最早时间是通过“从前向后从前向后”的方的方法求的，而最晚时间是通过法求的，而最晚时间是通过“从后向前从后向前”的方法求解的，并且，要想的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。这求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。这个问题拿来直接考算法源码的不多，一般是要求按照书上的算法描述个问题拿来直接考算法源码的不多，一般是要求按照书上的算法描述求解的过程和步

41、骤。求解的过程和步骤。l l在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为算法初始时，应该首先将所有顶点的最早时间全部置为0 0。关键路径。关键路径问题是工程进度控制的重要方法，具有很强的实用性。问题是工程进度控制的重要方法，具有很强的实用性。l l7.7.最短路径问题：最短路径问题：l l与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，与关

42、键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到关键是算法的理解。最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用游路线的选择问题。解决第一个问题用DIJSKTRADIJSKTRA算法，解决第二个算法，解决第二个问题用问题用FLOYDFLOYD算法。注意区分。算

43、法。注意区分。l l查找查找l l在不少数据结构的教材中，是把查找与排序放入高级数据在不少数据结构的教材中，是把查找与排序放入高级数据结构中的。应该说，查找和排序两章是前面我们所学的知结构中的。应该说，查找和排序两章是前面我们所学的知识的综合运用，用到了树、也用到了链表等知识，对这些识的综合运用，用到了树、也用到了链表等知识，对这些数据结构某一方面的运用就构成了查找和排序。数据结构某一方面的运用就构成了查找和排序。l l现实生活中，现实生活中，searchsearch几乎无处不在，特别是现在的网络时几乎无处不在，特别是现在的网络时代，万事离不开代，万事离不开searchsearch，小到文档内

44、文字的搜索，大到，小到文档内文字的搜索，大到INTERNETINTERNET上的搜索，上的搜索，searchsearch占据了我们上网的大部分时占据了我们上网的大部分时间。间。l l在复习这一章的知识时，你需要先弄清楚以下几个概念：在复习这一章的知识时，你需要先弄清楚以下几个概念：l l关键字、主关键字、次关键字的含义；静态查找与动态查关键字、主关键字、次关键字的含义；静态查找与动态查找的含义及区别；平均查找长度找的含义及区别；平均查找长度ASLASL的概念及在各种查找的概念及在各种查找算法中的计算方法和计算结果，特别是一些典型结构的算法中的计算方法和计算结果，特别是一些典型结构的ASLASL

45、值，应该记住。值，应该记住。l l在在DSDS的教材中，一般将的教材中，一般将searchsearch分为三类：分为三类：1st1st，在顺序表，在顺序表上的查找；上的查找；2nd2nd，在树表上的查找；，在树表上的查找；3rd3rd，在哈希表上的查，在哈希表上的查找。下面详细介绍其考查知识点及考查方式：找。下面详细介绍其考查知识点及考查方式：l l1.1.线性表上的查找：线性表上的查找：l l主要分为三种线性结构：顺序表，有序顺序表，索引顺序主要分为三种线性结构：顺序表，有序顺序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比较。对表。对于第一种，我们采用传统查找方法，逐个比较。对于

46、及有序顺序表我们采用二分查找法。对于第三种索引结于及有序顺序表我们采用二分查找法。对于第三种索引结构，我们采用索引查找算法。考生需要注意这三种表下的构，我们采用索引查找算法。考生需要注意这三种表下的ASLASL值以及三种算法的实现。其中，二分查找还要特别注值以及三种算法的实现。其中，二分查找还要特别注意适用条件以及其递归实现方法。意适用条件以及其递归实现方法。l l2.2.树表上的查找：树表上的查找：l l这是本章的重点和难点。由于这一节介绍的内容是使用树这是本章的重点和难点。由于这一节介绍的内容是使用树表进行的查找，所以很容易与树一间的某些概念相混淆。表进行的查找，所以很容易与树一间的某些概

47、念相混淆。本节内容与树一章的内容有联系，但也有很多不同，应注本节内容与树一章的内容有联系，但也有很多不同，应注意归纳。树表主要分为以下几种：二叉排序树，平衡二叉意归纳。树表主要分为以下几种：二叉排序树，平衡二叉树，树，B B树，键树。其中，尤以前两种结构为重，也有部分树，键树。其中，尤以前两种结构为重，也有部分名校偏爱考名校偏爱考B B树的。由于二叉排序树与平衡二叉树是一种树的。由于二叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就更为紧密，二叉树特殊的二叉树，所以与二叉树的联系就更为紧密，二叉树一章学好了，这里也就不难了。一章学好了，这里也就不难了。l l二叉排序树，简言之，就是

48、二叉排序树，简言之，就是“左小右大左小右大”，它的中序遍历结果是一个，它的中序遍历结果是一个递增的有序序列。常考给定记录序列，建立相应的二叉排序树及其查递增的有序序列。常考给定记录序列，建立相应的二叉排序树及其查找长度分析。平衡二叉树是二叉排序树的优化，其本质也是一种二叉找长度分析。平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定：深度之差排序树，只不过，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于的绝对值不得大于1 1。对于二叉排序树，。对于二叉排序树，“判断某棵二叉树是否二叉判断某棵二叉树是否二叉排序树排序树”这一算法经常被

49、考到，可用递归，也可以用非递归。平衡二这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，所以应该掌握平衡二叉树的四种调整算法，调叉树的四种调整算法，所以应该掌握平衡二叉树的四种调整算法，调整的一个参照是：调整前后的中序遍历结果相同。整的一个参照是：调整前后的中序遍历结果相同。l lB B树是二叉排序树的进一步改进，也可以把树是二叉排序树的进一步改进，也可以把B B树理解为三叉、四叉树理解为三叉、四叉.排序树，主要用于文件系统，减少外存读次数。除排序树，主

50、要用于文件系统，减少外存读次数。除B B树的查找算法外，树的查找算法外，应该特别注意一下应该特别注意一下B B树的插入和删除算法。因为这两种算法涉及到树的插入和删除算法。因为这两种算法涉及到B B树树结点的分裂和合并，是一个难点。另外，也有考结点的分裂和合并，是一个难点。另外，也有考B B树的结点数与高度树的结点数与高度相关关系的题目。相关关系的题目。B B树是报考名校的同学应该关注的焦点之一。树是报考名校的同学应该关注的焦点之一。l l键树也称字符树，特别适用于查找英文单词的场合。一般不要求能完键树也称字符树，特别适用于查找英文单词的场合。一般不要求能完整描述算法源码，多是根据算法思想建立键