当前位置:评价网 > 考研加油绽 > 互助交流 > 互助交流 > 正文
1.2 考试知识点分析
来源:评价网
发布时间:2010-11-18 08:15
点击数:
分享到:

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)、基数排序的基本概念和方法。搞清楚这些排序方法的流程,以及它们之间的区别。

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

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

 

【中国科教评价网www.nseac.com
[发布者:yezi]
  相关阅读:  ·英语单词记忆技巧:分析单词词缀是法宝  ·研究生补贴仅二三百 生活拮据羞于向父母要钱  ·英语面试实战指南:如何自我介绍和回答问题  ·赴港读研 听听名校新生经验谈(组图)  ·考研分享:别让最后的压力压垮之前的努力
    网友评论:(只显示最新5条。评论内容只代表网友观点,与本站立场无关!)
文明上网,理性评论:
表情:
用户:密码: 验证码:点击我更换图片