Exam 版 (精华区)

发信人: fuxi (虽穷否不改其志), 信区: Exam
标  题: 数据结构复习重点归纳（清华严蔚敏教材）
发信站: 哈工大紫丁香 (Sat Jul 19 15:17:37 2003)


近来，被不少朋友问起关于各门学科的复习重点问题，我想这正在成为越来越多的同学共
同关注的一个焦点问题，所以，从数据结构学科开始，本版将陆续推出这一系列的复习重
点的归纳。 

既然作为某一门学科的重点归纳，不可避免地就要牵涉到我们归纳时所参照的教材。关于
这一点，作个说明。我们在作这些学科的归纳时，都会指明我们主要用的是哪本教材作为
参照的。比如，数据结构，由于严老师的教材在国内是最为常用的，所以我们采用严蔚敏
的教材。而如编译原理，我们可能会采用陈火旺的；操作系统则采用汤子灜的。总之，我
们采用是国内普遍采用的教材以及质量和内容都相对更好的教材。 

由于时间关系，这些复习重点，我们不可能一次全部给出，我们会陆续给出。现在下面的
各个系列回贴里给出数据结构的前面几个章节的复习重要知识点归纳。 

一、数据结构的章节结构及重点构成 

数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，
树和二叉树，图，查找，内排，外排，文件，动态存储分配。 

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

按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为： 
概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。 
线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法
设计题。如果有，也是与其它章节内容相结合。 
栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，
也常与递归等概念相联系进行考查。 
串 ：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据
KMP进行算法分析。 
多维数组及广义表 ：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出
题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“
查找，排序”等章节结合来作为大题考查。 
树和二叉树 ：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本
章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾
有过出大型算法设计题的历史。 
图 ：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，
可与树一章共同构成算法设计大题的题型设计。 
查找 ：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目
给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与
树一章结合来考查。 
排序 ：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之
间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设
计大题中，如果作为出题，那么常与数组结合来考查。 
二、数据结构各章节重点勾划： 
第0章　概述 
本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意
以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注
意事项。本章考点不多，只要稍加注意理解即可。 

第一章　线性表 
作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中
，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概
念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。 

总体来说，线性表一章可供考查的重要考点有以下几个方面： 

1.线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等
概念。 
2.线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和
只有一个后继。 
3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动
态分配。静态链表与顺序表的相似及不同之处。 
4.线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链
表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双向链表及双向循
环链表的插入和删除算法等都是较为常见的考查方式。此外，近年来在不少学校中还多次
出现要求用递归算法实现单链表输出（可能是顺序也可能是倒序）的问题。 
在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式
是不一样的，请大家注意。 
5.线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单
链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处
。 

第二章　栈与队列 
栈与队列，是很多学习DS的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕
到现在。所以，理解栈与队列，是走向DS高手的一条必由之路，。 

学习此章前，你可以问一下自己是不是已经知道了以下几点： 

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

3.栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查
此为题目的算法设计题不多。 
4.循环队列中判队空、队满条件，循环队列中入队与出队算法。 

如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不
看书，并不是可以不作题哦。 

第三章　串 
经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。 

串，在概念上是比较少的一个章节，也是最容易自学的章节之一，但正如每个过来人所了
解的，KMP算法是这一章的重要关隘，突破此关隘后，走过去又是一马平川的大好DS山河了
，呵呵。 

串一章需要攻破的主要堡垒有： 

1.串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串
与空格串的区别，串相等的条件 
2.串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等
等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。 
3.顺序串与链串及块链串的区别和联系，实现方式。 
4.KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足，
明确next数组需要改进之外。其中，理解算法是核心，会求数组是得分点。不用我多说，
这一节内容是本章的重中之重。可能进行的考查方式是：求next和nextval数组值，根据求
得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。 


第四章　数组与广义表 
学过程序语言的朋友，数组的概念我们已经不是第一次见到了，应该已经“一回生，二回
熟”了，所以，在概念上，不会存在太大障碍。但作为考研课程来说，本章的考查重点可
能与大学里的程序语言所关注的不太一样，下面会作介绍。 

广义表的概念，是数据结构里第一次出现的。它是线性表或表元素的有限序列，构成该结
构的每个子表或元素也是线性结构的，所以，这一章也归入线性结构中。 

本章的考查重点有： 
1.多维数组中某数组元素的position求解。一般是给出数组元素的首元素地址和每个元素
占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位
置。 
2.明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解1中类型
的题。 
3.将特殊矩阵中的元素按相应的换算方式存入数组中。这些矩阵包括：对称矩阵，三角矩
阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行
向量的二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的
算法。 
4.广义表的概念，特别应该明确表头与表尾的定义。这一点，是理解整个广义表一节算法
的基础。近来，在一些学校中，出现了这样一种题目类型：给出对某个广义表L若干个求了
若干次的取头和取尾操作后的串值，要求求出原广义表L。大家要留意。 
5.与广义表有关的递归算法。由于广义表的定义就是递归的，所以，与广义表有关的算法
也常是递归形式的。比如：求表深度，复制广义表等。这种题目，可以根据不同角度广义
表的表现形式运用两种不同的方式解答：一是把一个广义表看作是表头和表尾两部分，分
别对表头和表尾进行操作；二是把一个广义表看作是若干个子表，分别对每个子表进行操
作。 

第五章　树与二叉树 
从对线性结构的研究过度到对树形结构的研究，是数据结构课程学习的一次跃变，此次跃
变完成的好坏，将直接关系到你到实际的考试中是否可以拿到高分，而这所有的一切，将
最终影响你的专业课总分。所以，树这一章的重要性，已经不说自明了。 

总体来说，树一章的知识点包括： 
二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本
遍历算法的基础上实现二叉树的其它算法，线索二叉树的概念和线索化算法以及线索化后
的查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算
法及其与二叉树遍历算法的联系，树与森林和二叉树的转换。 

下面我们来看考试中对以上知识的主要考查方法： 
1.二叉树的概念、性质和存储结构 
考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树的区别；考查满
二叉树和完全二叉树的性质，普通二叉树的五个性质：第i层的最多结点数，深度为k的二
叉树的最多结点数，n0=n2+1的性质，n个结点的完全二叉树的深度，顺序存储二叉树时孩
子结点与父结点之间的换算关系（左为：2*i，右为：2*i+1）。 
二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合，二叉树的三叉链表表示方法
。 
2.二叉树的三种遍历算法 
这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法
设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视
其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解
其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算
法，可以直接根据三种递归算法改造而来（比如：求叶子个数），所以，掌握了三种遍历
的非递归算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就下笔如
有神了。我会在另一篇系列文章里给出三种遍历的递归和非递归算法的背记版，到时请大
家一定熟记。 
3.可在三种遍历算法的基础上改造完成的其它二叉树算法： 
求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树
，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等
等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小菜
一碟了。 
4.线索二叉树： 
线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比
较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险，
为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索
化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法
问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题）。 
5.最优二叉树（哈夫曼树）： 
最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋
予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源
码的很少，一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小
权值之和，此类题目不难，属送分题。 
6.树与森林： 
二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的
特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子是不可交换的，如果交换了就
成了另外一棵二叉树，这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树
。但是，对于普通的双分支树而言，不具有这种性质。 
树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后根（对于森林
而言称作：先序与后序遍历）。在难度比较大的考试中，也有基于此二种算法的基础上再
进行扩展要求你利用这两种算法设计其它算法的，但一般院校很少有这种考法，最多只是
要求你根据先根或后根写出他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍历
算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍
历。这一点成为很多学校的考点，考查的方式不一而足，有的直接考此句话，有的是先让
你求解遍历序列然后回答这个问题。二叉树、树与森林之所以能有以上的对应关系，全拜
二叉链表所赐。二叉树使用二叉链表分别存放他的左右孩子，树利用二叉链表存储孩子及
兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。 

树一章，处处是重点，道道是考题，大家务必个个过关。 

--
宁为玉碎，不为瓦全
低价转让工大教务处考研辅导班高数听课证---联系站内信箱
※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 210.46.79.63]