计算机统考网校（www.cstongkao.com）由清华、北大、北航等学校的专家教授团队与国内最早专门从事专业课辅导的凯程专业课辅导中心发起设立，是国内第一家专门、专业、专注于考研计算机辅导及服务的教学机构。网校秉承了凯程一贯的应试风格与高质量服务理念，旨在为广大国内计算机考研学子提供最权威、最专业、最高性价比的计算机应试辅导课程和资料服务。

 

网校特聘高级顾问：

王教授，任职于清华大学，博士生导师。王教授是多个国家863计划组织者，着重研究计算机网络，对我国80年代以来计算机网络化做出了重大贡献，并多次被国家部级单位授予自然科学奖章。

李教授，中国科学院计算所高级研究员，博士生导师。李教授曾经承担国家863计划等多个国家级大型科研项目，在计算机基础研究方面功底深厚。多年来在国内外权威杂志发表论文数十篇，并数次获得国家级科研奖项。

 

下面是计算机统考网校针对09计算机考研中数据结构部分的详细解析，如需转载，请务必说明：

在计算机考研专业基础课统考科目中，一共考查数据结构、操作系统、计算机组成原理、计算机网络四门课程，满分为150分，其中数据结构占45分（占33%）。数据结构是计算机考研专业课中最为重要的一门， 它所占的分值比例大，也是最容易拉开差距的一门课程，可以说数据结构复习的好坏对就算机考研专业课得分的高低起着决定性的作用。

 

一、考纲分析

09年的统考大纲对数据结构的考查目标分为了三个层次：理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现；在掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析；能够选择合适的数据结构和方法进行问题求解。从这个考查目标上来看和往年各个学校的考研大纲的考查目标并没有什么实质性的区别，这说明数据结构科目考查的指导思想并没有发生变化，同学们可以在不影响已有复习成果的基础上继续进行复习计划。

大纲上给出的数据结构的考点也没有什么大的变化，大纲上罗列出来的这6个部分和往年各高校的考点基本一致，只是第一章绪论没有出现，但是建议各位考生在复习的时候也简单的复习一下这一章，因为把握了这章有助于对整个课程知识的理解。

根据大纲的要求试卷题型结构为单项选择题 80分(40小题，每小题2分)，综合应用题 70分。根据这个试题结构数据结构将有2～3道综合应用题，而且还有可能会出现数据结构和其它科目结合的综合应用题。单项选择题主要考查基本概念、基本原理和方法。综合应用题主要考查考生运用基本原理和基本方法分析、判断和解决有关理论问题和实际问题的能力。在数据结构的复习过程中，考生一定要注意理解和运用，因为数据结构考题中靠死记的很少，即使是选择题也很少会出现靠死记就能完成的题目。

 

二、知识点解析

1、线性表

线性表是一种最简单的数据结构，但是本章在整个数据结构学科的学习中占着非常重要的地位，在这一章中，首次引入了链式存储的概念，链式存储是整个数据结构的重中之重，后面的章节都将涉及到这个概念，所以一定能搞透彻。

本章主要考查线性表的定义和基本操作、线性表的实现。（1）首先本章需要记住一些线性表的相关概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等，其中一定要注意首元结点、头结点和头指针三者的区别和联系，这在数据结构的考研题中经常出现。另外线性表的结构特点也要记住，有可能会出现在选择题中；（2）然后就是要掌握线性表的两种存储方式的实现方法，要清楚静态链表与顺序表的相似及不同之处，并掌握几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表，（3）理解线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合，（4）理解单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处，（5）掌握对于线性表的各种实现方式能够实现指定的操作，尤其是各种线性链表的插入、删除（删除自己，还是删除后继结点）、判表空等。

 

2、栈、队列和数组

栈和队列是两种特殊的线性表，属于线性结构的拓展，其中栈和队列是两种操作受限的线性表，数组是数据元素为非原子类型的线性表。本章是考试中的重点，各位考生在复习这章的时候一定要注意栈和队列的应用，数组这一节要特别注意特殊矩阵压缩方面的题目，还有就是数组寻址的计算题目。

本章的重点在栈和队列部分，如果本章出大题的话应该是关于栈和队列的，数组部分的重要性相对而言要低一些，对于栈和队列：（1）首先要弄清楚栈和队列各自的特点以及它们的区别，记住一些有关栈和队列的相关概念，包括：顺序栈，链栈，共享栈，循环队列，链队等；（2）对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解。（3）在此基本上要掌握栈和队列插入、删除等基本操作的特点和算法描述，包括栈的出栈、入栈，单链队列的入队和出队，还有循环队列中判断空、队满条件的条件，判循环队列是空还是满的两种处理方法及其入队和出队的算法描述；（4）掌握递归算法，在弄清楚递归算法和栈的关系的基础上，要能把递归算法转换为用栈实现的非递归算法。（5）对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。

数组部分为一维数组和多维数组，其中一维数组属于线性表范畴，但多维数组不属于线性表，这一部分重点要掌握多维数组中某数组元素的寻址求解（不管是按行存储和按列存储）：一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置，其次要理解稀疏矩阵的三种不同实现方式：三元组，带辅助行向量的二元组，十字链表存储和稀疏矩阵各种实现方式的转置和相乘运算的操作及复杂性分析。

 

3、树与二叉树

树和二叉树历来都是考试的重点章节，同时也是难点，在数据结构考试中本章所占的分值比例很大，本章学习的好坏直接关系到数据结构考试中的得分高低，所以考生在复习本章的时候一定要力求吃透，不能只是浮在表面上，同时要注意算法设计题目。

复习本章的时候（1）首先必须要弄清楚二叉树和树是两种不同的概念，比如可以考判断二叉树是否为度为2的有序树这样的题目，同时弄清楚这一点也是学好本章的基础。（2）然后掌握二叉树的五个性质，尤其是性质3和性质4，都有可能在选择题中出现。（3）本章的一个重点中重点就是二叉树的三种遍历算法：先序、中序以及后序，要求熟练的掌握这三种遍历的递归算法和非递归算法，理解其执行的实际步骤，同时还要掌握在三种遍历算法的基础上改造完成的其它二叉树算法，比如求叶子节点个数，求二叉树结点总数，复制二叉树、交换二叉树左右子树等等诸如此类的综合应用题，这方面的题目考试一定要自己实实在在地自己解决一两个，找到解这种题目方法和思想。

本章还有特殊的二叉树，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造，以及三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题（如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题），会计算针对某个二叉树在采用不同的线索化方法后剩余空链域的个数二叉排序树，平衡二叉树的基本概念和应用，特别是二叉排序树的基本性质和特点要能很好地理解。

本章还有一个很重要的点就是哈夫曼树，也叫最优二叉树。什么样的编码是哈夫曼编码。一般很少考哈夫曼编码的算法，能够利用算法构造哈夫曼树并求出最小带权路径长度即可。还有一个树的应用：等价类问题，通常会作为综合应用类试题出现，

最后对是树和森林，多棵独立的树就组成了森林，考生对树的三种存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要有了解，在选择题中可能会出现。

 

4、图

   图是最复杂的一种数据结构类型，图这一章也是数据结构考试中必考的一章，而且本章中处处都是重点。

图这一章的概念很多，这些概念也很重要，考生在复习的时候（1）首先要记住一些的定义和术语：有向图、无向图、连通、路径、子图、出度、入度、生成树、最短路径、关键路径等。（2）然后是要掌握图的存储结构，重点要放在邻接矩阵和邻接表这两种存储方式上，弄清楚图的连通和存储方法之间的关系。例如，一个顶点的出度和临界矩阵中1的个数有什么关系，等等。（3）图的两种遍历算法：深度遍历和广度遍历是本章的一个重点，考生不但要熟练掌握这两种遍历算法的算法实现，同时对于给定的一个图，要能知道它的各种遍历次序。在考查时，图一章的算法设计题常常是基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。（4）最后是图的应用，图的应用很多也很难，但是考试中却是必考的内容，所以这一部分令很多考试很头疼，我们要掌握的图的应用包括：最小生成树、拓扑排序、关键路径、最短路径。

最小生成树的构造：普里姆算法和克鲁卡尔算法，要掌握这两个算法的基本思想。这两个算法考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其构造过程及最终生成的最小生成树。

拓扑排序问题：拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句话说，一种是“从前向后”的排序，一种是“从后向前”排。当然，后一种排序出来的结果是“逆拓扑有序”的。

关键路径问题：这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。这个问题拿来直接考算法源码的不多，一般是要求按照书上的算法描述求解的过程和步骤；最短路径问题：与关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理解。

最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二个问题用FLOYD算法。这个算法的要求就是要会用算法求解最短路径。

 

5、查找

查找一章是考试的重点难点章节，概念较多，联系较为紧密，容易混淆。大家在复习这一章要学会分类和对比相结合来进行复习。查找这一章用到的数据结构是查找表，查找表分为静态查找表和动态查找表，所谓静态查找表是指在查找过程中对查找表只做“查找”操作；动态查找表是指在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。

静态查找表的查找，主要分为三种线性结构：顺序表，有序表，索引顺序表。对于第一种，我们采用传统查找方法，逐个比较，顺序表的查找一般考得不多，考得也不会很难。对于有序表的查找主要掌握折半查找算法，对于折半查找算法考试要掌握算法的基本思想、查找过程，平均查找长度的计算以及其递归实现方法。对于索引顺序表的查找采用的是索引查找算法，考试需要掌握索引表的建立，以及对查找表和索引表分别是如何进行查找的，另外同样需要掌握其平均查找长度（ASL）的计算。

动态查找表的查找，用到的主要是两种非线性数据结构：树和哈希表。对于树上的查找是本章的重点和难点，这一节的内容和树一章的内容有联系，但也有不同，所以考生复习的时候要主要归纳比较。树上的查找算法主要有：二叉排序树，平衡二叉树，B树，键树。其中，前两种结构是考试中的重点，有时候也会考查Ｂ树，但是以选择为主，很少会考大题。由于二叉排序树与平衡二叉树是一种特殊的二叉树，所以与二叉树的联系就更为紧密，二叉树一章学好了，这里也就不难了。对于二叉排序树主要要掌握二叉排序树的插入和删除过程。平衡二叉树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二叉排序树，“判断某棵二叉树是否二叉排序树”这一算法经常被考到，可用递归，也可以用非递归。平衡二叉树的建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，所以应该掌握平衡二叉树的四种调整算法。B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉....排序树。除B树的查找算法外，应该特别注意一下B树的插入和删除算法。因为这两种算法涉及到B树结点的分裂和合并，是一个难点，考试中占的分数也不会很多，所以如果没有时间可以不看。键树也称字符树，特别适用于查找英文单词的场合，考试时多是根据算法思想建立键树及描述其大致查找过程。

哈希表的查找算法是本章的一个重点，首先要弄清楚什么是哈希表，掌握哈希表查找的基本思想以及哈希函数。对于哈希表的查找主要掌握：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。

 

6、内部排序

09年的大纲明确规定只考查内部排序，外部排序不考，所以考试的时候只需要复习内部排序就可以了。内部排序在考试中也很重要，所谓内部排序，就是在内存中进行排序。在这一部分中，主要要掌握直接插入排序、折半插入排序、冒泡排序(bubble sort)、简单选择排序、希尔排序(shell sort)、快速排序、堆排序、二路归并排序(merge sort)、基数排序的基本概念和方法。

插入排序包括直接插入、折半插入、2路插入、希尔排序。这几种插入排序算法的最根本的不同点是根据什么规则寻找新元素的插入点。直接插入是依次寻找，折半插入是折半寻找。希尔排序，是通过控制每次参与排序的数的总范围“由小到大”的增量来实现排序效率提高的目的。在插入排序中重点要掌握的是直接插入排序和希尔排序，特别是希尔排序。

快速排序可以说是内部排序中最重要也是最常考的一种算法，首先要掌握快速排序的基本思想，快速排序的过程，比如可以给定一组关键字，要求选择某一趟的排序后的结果等。其次也要注意一下快速算法的实现，在在考试中也是可能会出现的。还有就是考试中常常出现的一个就是关于快速排序的最坏情况，考生也要主要一下。

选择排序的难度相对而言比较难，它可以分为：简单选择、树选择、堆排。这三种方法的不同点是，根据什么规则选取最小的数。简单选择，是通过简单的数组遍历方案确定最小数；树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大（小）者，最终选出最小（大）数；而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最小数选出放在堆顶。这一部分的考试重点是堆排序中的堆建立、堆调整。