1.2 考试知识点分析

1.2 考试知识点分析

1.2 考试知识点分析

　　计算机考研专业综合课考试，涉及的面比较大，知识点多，相关的教材和书籍也很多，那么，考生是否需要把每本大学教材中的所有章节内容都要掌握呢？答案是“否”。在本节中，我们对考试大纲所规定的数据结构、计算机组成原理、操作系统、计算机网络4个学科的考点，进行详细分析，便于考生有的放矢，提高学习效率。

1.2.1 数据结构

　　在计算机考研专业课统考中，数据结构知识一共是45分，占整个考试比重的30%。对于数据结构课程的考查，基于以下目标：

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

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

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

　　下面，我们围绕以上目标，对数据结构学科的考试知识点进行深入分析。

　　1．线性表

　　线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作（包括计算长度、查找、插入、删除、逆序、集合运算等），以及线性表的实现。

　　在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构（包括单链表、双向链表、循环链表），这是考查的重点。另外，还要掌握线性表的基本应用。

　　2．栈、队列和数组

　　栈和队列是两种特殊的线性表，在这方面，考生要掌握栈和队列的基本概念，以及它们之间的区别。包括栈和队列的定义，栈和队列的表示和实现，栈和队列的应用，栈和队列的插入、删除元素等基本操作。

　　对于栈和队列的存储结构（包括顺序存储结构、链式存储结构）要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。

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

　　3．树与二叉树

　　树和二叉树是一类非常重要的数据结构。在这个部分，考生要掌握树的定义、二叉树的定义及主要特征（特殊的二叉树、二叉树的性质）；掌握二叉树的顺序存储结构和链式存储结构，特别是链式存储结构。因为很多应用都是建立在链式存储基础上的，例如，二叉树的遍历（前序遍历、中序遍历、后序遍历）就是一种典型的应用。

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

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

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

　　4．图

　　在数据结构中，图的结构是最复杂的，这里的概念也是最多的，考生要掌握图的基本概念（例如，有向图、无向图、连通、路径、子图、出度、入度、邻接表、邻接矩阵、生成树、最短路径、关键路径等）。

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

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

　　在数据结构课程中，图的基本应用是最多的，也是最复杂的，考生要掌握这些应用的复杂度分析。要掌握的具体应用主要包括最小（代价）生成树、最短路径、拓扑排序、关键路径。在给出的一个具体图中，考生要会利用已知条件，求出上述应用的结果。而且，要注意所有的算法都应牢牢掌握，且是在理解的基础上牢记。

　　5．查找

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

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

　　6．内部排序

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

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

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

1.2 考试知识点分析