数据结构复习重点归纳
（适于清华严版教材）
一、数据结构的章节结构及重点构成
数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查，内排，外排，文件，动态存储分配。
对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特殊是该校又有在试卷中对这三章进行过考核的历史，那末这部份朋友就要留意这三章了。
按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：
概论：内容很少，概念简单，分数大多惟独几分，有的学校甚至不考。
线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节内容相结合。
数据结构与算法考研真题
栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。
串：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据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.二叉树的三种遍历算法
这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算法设计题能否
顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视其每一个算法中对根结点
数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练
掌握三种遍历的非递归算法。由于二叉树一章的不少算法，可以直接根据三种递归算法改造而来（比
如：求叶子个数），所以，掌握了三种遍历的非递归算法后，对付诸如：“利用非递归算法求二叉树叶
子个数”这样的题目就下笔如有神了。我会在另一篇系列文章（bbs.kaoyan/ibbs.dll?bbsdisp?t_id=301583&bp=2&bt=0）里给出三种遍历的递归和非递
归算法的背记版，到时请大家一定熟记。
3.可在三种遍历算法的基础上改造完成的其它二叉树算法：
求叶子个数，求二叉树结点总数，求度为1或者度为2的结点总数，复制二叉树，建立二叉树，交换左
右子树，查值为n的某个指定结点，删除值为n的某个指定结点，诸如此类等等等等。如果你可以
熟练掌握二叉树的递归和非递归遍历算法，那末解决以上问题就是小菜一碟了。
4.线索二叉树：
线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上比较好理解，
但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危（wei）险，为了避免此类情况，线索二叉树便堂而皇之地浮现了。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线
索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查某一类线索二叉树中指定结点
的前驱或者后继结点就是一类常考题）。
5.最优二叉树（哈夫曼树）：
最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，
这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源码的很少，普通是给你
一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和，此类题目不难，属送分
题。
6.树与森林：
二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处
是在于：二叉树是有序的！即：二叉树的摆布孩子是不可交换的，如果交换了就成为了此外一棵二叉树，
这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是，对于普通的双分支树而言，
不具有这种性质。
树与森林的遍历，不像二叉树那样丰富，他们惟独两种遍历算法：先根与后根（对于森林而言称作：
先序与后序遍历）。在难度比较大的考试中，也有基于此二种算法的基础上再进行扩展要求你利用这两
种算法设计其它算法的，但普通院校很少有这种考法，最多只是要求你根据先根或者后根写出他们的遍
历序列。此二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。这一点成为不少学校的考点，考查的方式不一而足，有的直接考此句话，有的是先让你求解遍历序列然后回答这个问题。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉链表分别存放他的摆布孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也是利用二叉链表存储孩子及兄弟。
树一章，处处是重点，道道是考题，大家务必个个过关。
第六章 图
如果说，从线性结构向树形结构研究的转变，是数据结构学科对数据组织形式研究的一次升华，那末从树形结构的研究转到图形结构的研究，则进一步让我们看到了数据结构对于解决实际问题的重大推动作用。
图这一章的特点是：概念繁多，与离散数学中图的概念联系密切，算法复杂，极易被考到，且容易出大题，特别是名校，作为考研课程，如果不考查树与图两章的知识，几乎是不可想像的。
下面我们看一下图这一章的主要考点以及这些考点的考查方式：
1.考查有关图的基本概念问题：
这些概念是进行图一章学习的基础，这一章的概念包括：图的定义和特点，无向图，有向图，入度，出度，彻底图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。与这些概念相联系的相关计算题也应该掌握。
2.考查图的几种存储形式：
图的存储形式包括：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。在考查时，有的学校是给出一种存储形式，要求考生用算法或者手写出与给定的结构相对应的该图的另一种存储形式。
3.考查图的两种遍历算法：深度遍历和广度遍历
深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题往往是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。
4.生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法。
考查时，普通不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最平生成的最小生成树。
5.拓扑排序问题：
拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。固然，后一种排序出来的结果是“逆拓扑有序”的。
6.关键路径问题：
这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才干进行。这个问题拿来直接考算法源码的不多，普通是要求按照书上的算法描述求解的过程和步骤。
在实际设计关键路径的算法时，还应该注意以下这一点：采用邻接表的存储结构，求最早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早时间全部置为0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。