您的位置:考研教育网>  > 考试大纲 > 考研专业课 正文

2017年计算机考研大纲详解(三)数据结构

正保考研教育网整理   2016-08-28 19:02 【 】【我要纠错

2017年考研计算机大纲详解(三)数据结构

----掌握基础,强调运用

一、数据结构考查目标

1. 掌握数据结构的基本概念、基本原理和基本方法。

2. 掌握数据的逻辑结构、存储结构及其基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析。

3. 能够运用数据结构的基本原理和方法进行问题的分析和求解,具备采用C或C++语言设计与实现算法的能力。

二、数据结构考点解析

今天我们首先来解析一下计算机统考大纲数据结构部分及其相关知识点。数据结构占了45分,和计算机组成原理部分同一个比重,在以往各年计算机专业的研究生入学考试中,几乎没有学校不考查数据结构的内容,而且绝大部分考试中,数据结构这一门都占据了重要的地位,这足以体现计算机专业研究生选拔对数据结构课程的要求之重。

2017年的统考大纲对数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法;掌握数据的逻辑结构、存储结构及其基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析;能够综合运用数据结构的基本原理和方法进行问题的分析和求解,具备采用C或C++语言设计与实现算法的能力。要求运用数据结构的基本原理和方法进行分析问题,要求学生能够活学活用,事实上,可以看出研究生入学考试对知识实际应用能力的加强。大纲仍要求学生具备采用C或C++语言设计与实现算法的能力,但是考生不必因此而专门复习一遍C或C++程序设计,毕竟复习时间有限,而且数据结构要求的重点在于算法设计的能力,而不是编写代码的能力,因此,只要能用类似伪代码的形式把思路表达清楚就行,不用强求写出一个没有任何语法错误的程序。

下面我们来解析一下知识点。

线性表这一章里面的知识点不多,但要做到深刻理解,能够应用相关知识点解决实际问题。链表插入、删除节点时的指针操作是选择题的一个常考点,诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。

栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的,是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点,进栈出栈序列的问题常出现在选择题中。其次,是栈和队列的顺序和链式存储结构,这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作,特别是循环队列判满和判空的2种判断方法。再次,是特殊矩阵的压缩存储,这个考点复习的重点可以放在二维矩阵与一维数组相互转换时,下标的计算方法,比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后,各个数据点相应的下标的计算。这一章可能的大题点,在于利用堆栈或队列的特性,将它们作为基础的数据结构,支持实际问题求解算法的设计,例如用栈解决递归问题,用队列解决图的遍历问题等等。

树和二叉树。这一章中我们从顺序式的数据结构,转向层次式的数据结构,要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树),重点要熟练掌握的,是森林、树以及二叉树的前中后三种遍历方式,要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点,复习时要特别关注。一些常见的选择题考点包括:满二叉树、完全二叉树节点数的计算,由树、二叉树的示意图给出相应的遍历序列,依据二叉树的遍历序列还原二叉树,线索化的实质,计算采用不同的方法线索化后二叉树剩余空指针域的个数,平衡二叉树的定义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括:二叉树的遍历算法,遍历基础上针对二叉树的一些统计和操作(比如结点数统计、左右子树对换等等),判断某棵二叉树是否二叉排序树,以上这些都要求能用递归的和非递归的算法解决,特别要重视非递归的算法,线索化后二叉树的遍历算法,如查找某结点线索化后的前驱或后继结点的算法以及给出Huffman编码等等。

图。在这一章中需要识记的是图以及基于图的各种定义,存储方式。本章重点:要熟练掌握图的深度遍历和广度遍历算法,这是用图来解决应用问题时常用的算法基础。需要掌握基于图的多个算法,能够以手工计算的方式在一个给定的图上执行特定的算法求解问题。常见的应用问题直接给出或经过抽象,会成为下列问题:最小生成树求解(PRIM算法和KRUSKAL算法,两种方法思想都很简单,但要注意不要混淆这两种方法),拓扑排序问题(这里会用到数组实现的链表,可以注意一下),关键路径问题(数据结构的较大难点,要把概念理解透,能做出表格找出关键路径),最短路径问题(有重要的应用背景,也是贪心法不多的能给出最优解的典型问题之一)

查找。这一章,需要识记关键字、主关键字、次关键字的含义;本章重点:静态查找与动态查找的含义及区别;平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果,特别是一些典型结构的ASL值,B树的概念和基本操作冲突解决方法的选择和冲突处理过程的描述,B+树的概念,特别要注意B树和B+树概念的对比,以及Hash表相关的概念。要熟练掌握顺序表、链表、二叉树上的查找方法,特别要注意顺序查找、二分查找的适用条件(比如链表上用二分查找就不合适)和算法复杂度。

排序。既包括内部排序,又包括外部排序,排序既是重点,又是难点。排序算法众多,光大纲上列出的内部排序就有9种,还要再加上外部排序,各种不同算法还有相应的一些概念定义需要记住。选择题常见的问题包括:不同排序算法的复杂度,给定数列要求给出某种特定排序方法运行一轮后的排序结果,或者给出初始数列和一轮排序结果要求选择采用的排序算法,给定时间、空间复杂度要求以及数列特征要求选择合适的排序算法等等。如果排序这一考点出现在综合应用题中则常与数组结合来考查。

◇ 编辑推荐
·2020年医学硕士辅导
·2019年考研真题解析
·2020考研公共课网上辅导课程
·2020考研管理类联考网上辅导热招!!
·2020考研英语全程班620元
·2020考研政治全程班580元
 考研教育网官方微信

微信公众账号cnedu_cn

 网上辅导课程特色
  • 即报即学
  • 名师团队
  • 反复看课
  • 在线答疑
  • 移动教学
  • 讲义下载
  • 课后练习
  • 模拟测试
 24小时报名咨询
辅导课程
辅导体系 授课教师 招生方案 课时 价格 购买
考研政治
导学、基础、强化、冲刺、点题班赠19年导学、基础班 米 鹏 方案 109 580元 购买
考研英语
导学、基础、强化、冲刺、点题班赠19全程班 夏徛荣 方案 159 620元 购买
考研数学一
包含基础、强化、冲刺 赠19年特色班课程 李永乐团队 方案 210 919元 购买
考研数学二
包含基础、强化、冲刺 赠19年特色班课程 李永乐团队 方案 210 739元 购买
考研数学三
包含基础、强化、冲刺 赠19年特色班课程 李永乐团队 方案 210 919元 购买

医学硕士

基础班强化班冲刺班全程班
方案价格购买 方案价格购买方案价格购买方案价格购买
中医综合
方案 420元 购买 方案 360元 购买 方案 300元 购买 方案 880元 购买
西医综合
方案 420元 购买 方案 360元 购买 方案 300元 购买 方案 880元 购买
辅导课程
辅导体系 授课教师 招生方案 课时 价格 购买
英语二
含导学、基础、强化、冲刺班 乔老师 方案 108 1600元 购买
数学(全程班)
含导学、基础、强化、真题、冲刺班 官老师 方案 120 1600元 购买
逻辑(全程班)
导学、基础、强化、冲刺 真题班 丁老师 方案 120 1600元 购买
写作(全程班)
含导学、基础、强化、冲刺班 胡元奎 方案 30 1200元 购买
管综(全程班)
含数学、逻辑、写作三部分的基础、强化、冲刺班 名师团 方案 270 4500元 购买
管综+英语二
英语二全程班+管综全程班 比单报优惠600元 名师团 方案 386 5800元 购买