09计算机考研专业课考试知识点分析：数据结构

　　作者：张友生

　　编者按：2009年是计算机专业考研专业基础课首次实行全国统考，面对今年的改变，想报考计算机专业的考生可能对复习的准备有很多的疑问。为了帮助考生正确的做好准备工作，学赛网研究生院特访问了我国著名的计算机教育专家、湖南师范大学计算机软件与理论/计算机应用技术硕士点专业课试题命题人张友生博士，请张博士对考试大纲进行全面的解析。本文为大纲解析的第二篇：数据结构知识点分析。

　　访问本系列文章第一篇：2009年计算机专业考研专业课大纲解析

　　在计算机考研专业基础课统考科目中，一共考查数据结构、操作系统、计算机组成原理、计算机网络四门课程，满分为150分，其中数据结构占45分。

　　一、考查目标

　　(1)理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

　　(2)掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。

　　(3)能够选择合适的数据结构和方法进行问题求解。

　　二、知识点解析

　　1.线性表

　　线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。

　　2.栈、队列和数组

　　栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。

　　一维数组属于线性表范畴，但多维数组不属于线性表。在这方面，主要掌握数组的存储结构，例如按行优先、按列优先等，某个元素存在的地址是什么。对于特殊矩阵(二维数组)的压缩存储原理也要搞清楚。

　　3、树与二叉树

　　二叉树和树是两种不同的概念，这一点是必须要搞清楚的。在这个部分，我们要掌握树的定义、二叉树的定义及主要特征(特殊的二叉树、二叉树的性质)。在二叉树的顺序存储结构和链式存储结构方面，特别是链式存储结构，因为很多应用都是建立在链式存储基础上，例如，二叉树的遍历(前序遍历、中序遍历、后序遍历)就是一种典型的应用。

　　在特殊的二叉树中，完全二叉树的概念是必须要搞清楚的，其次，线索二叉树的基本概念和构造、二叉排序树、平衡二叉树的基本概念和应用，特别是二叉排序树的基本性质和特点要能很好地理解。

　　多棵独立的树就组成了森林，树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二叉树的转换等知识，也要有了了解。

　　最后就是树的应用，通常会作为综合应用类试题出现，包括等价类问题、哈夫曼(Huffman)树和哈夫曼编码等。

　　4、图

　　在数据结构中，图的结构是最复杂的，这里的概念也是最多的。我们要掌握图的基本概念(有向图、无向图、连通、路径、子图、出度、入度、生成树、最短路径、关键路径等)。

　　图的存储及基本操作主要有邻接矩阵法和邻接表法，我们要掌握这有向图和无向图的这2种存储方法，要清楚图的连通和存储方法之间的关系。例如，一个顶点的出度和临界矩阵中1的个数有什么关系，等等。

　　图的遍历方法有深度优先搜索和广度优先搜索，我们要掌握这2种遍历方法的算法实现。给出一个具体的图，要能知道它的遍历次序。

　　在数据结构课程中，图的基本应用是最多的，也是最复杂的，我们要掌握这些应用的复杂度分析。要掌握的具体应用主要包括最小(代价)生成树、最短路径、拓扑排序、关键路径。在给出的一个具体的图中，我们要会利用已知条件，求出上述应用的结果。

　　5、查找

　　在给定的数据集合中查找某个关键值就是查找，查找的基本方法主要有顺序查找法、折半查找法、B-树、散列(Hash)表及其查找。考的比较多的是折半查找和散列表，我们要掌握它们的基本概念和方法，例如散列表的碰撞如何解决，装载因子的概念等。

　　另外，我们要掌握各种查找算法的分析及应用，最好能把各种查找在查找成功、查找失败的情况下的最好、平均、最坏的平均查找次数的计算方法搞清楚。

　　6、内部排序

　　根据考试大纲，只考查内部排序。所谓内部排序，就是在内存中进行排序。在这一部分中，主要要掌握直接插入排序、折半插入排序、冒泡排序(bubble sort)、简单选择排序、希尔排序(shell sort)、快速排序、堆排序、二路归并排序(merge sort)、基数排序的基本概念和方法。搞清楚这些排序方法的流程，以及它们之间的区别。

　　在这个知识点，一个很重要的考查点就是各种内部排序算法的比较，一般的书上都会有这样的一个表格，列出了所有排序在各种情况下(最好、最坏、平均)的时间复杂度和空间复杂度，这个表是需要我们记下来的。当然，如果我们能掌握复杂度的计算方法，自己能推算出来，那就更好了。

　　最后，就是要掌握内部排序算法的基本应用，以及算法的实现。

　　三、复习方法

　　1、教材的选择

　　从考试大纲来看，所要求的知识在一般的大学数据结构教材中都已经包含，所以，选择哪本书并不是最重要的事情。不过，根据希赛教育推荐，对于数据结构的复习，可以选择清华大学出版社的《数据结构(第二版)》(严蔚敏主编)。这本书有多种语言的版本，建议选择C语言的版本，在复习的过程中，还可以配以相应的习题集。

　　2、学习方法

　　对于数据结构的学习，难在其中的算法及实现。有条件的考生，可以在计算机上编写程序，自己实现教材上的算法(要注意，书上的算法通常都采用伪代码编写，需要我们自己用某种程序设计语言去具体实现)。如果没有条件，那就只有在心里进行推导了，可以使用实际的例子，手工“实现”算法。 

    更多信息请访问：新浪考研频道 考研论坛 考研博客圈

　　特别说明：由于各方面情况的不断调整与变化，新浪网所提供的所有考试信息仅供参考，敬请考生以权威部门公布的正式信息为准。