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

中国科学院研究生院计算与通信工程学院2007年硕士生入学考试大纲

   2007-01-11 17:28 【 】【我要纠错

  一、考试内容

  数据结构

  1、绪论

  (1)数据结构的基本概念,数据的逻辑结构、存储结构。

  (2)算法的定义、算法的基本特性以及算法分析的基本概念。

  2、线性表

  (1)线性关系、线性表的定义,线性表的基本操作。

  (2)线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。济

  3、堆栈与队列

  (1)堆栈与队列的基本概念、基本操作。

  (2)堆栈与队列的顺序存储结构与链式存储结构的构造原理。

  (3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。

  4、串

  (1)串的基本概念、串的基本操作和存储结构。

  (2)串的模式匹配算法和改进的KMP算法

  5、数组和广义表

  (1)数组的概念、多维数组的实现

  (2)对称矩阵和稀疏矩阵的压缩存储

  (3)广义表的基本概念

  6、树与二叉树

  (1)树的定义和性质

  (2)二叉树的概念、性质和实现

  (3)遍历二叉树和线索二叉树

  (4)树和森林

  (5)赫夫曼树及其应用

  (6)树的计数

  7、图

  (1)图的定义,基本概念,图的分类,常用名词术语。

  (2)图的邻接矩阵存储方法、邻接表存储方法的构造原理。

  (3)图的遍历操作。

  (4)最小生成树,最短路径,AOV网与拓扑排序。

  8、文件及查找

  (1)数据文件的基本概念和基本术语,数据文件的基本操作。

  (2)顺序文件、索引文件、散列(Hash)文件。

  (3)顺序文件的顺序查找方法、排序连续顺序文件的折半查找方法以及其他文件的基本查找方法。

  9、内排序

  (1)排序的基本概念,排序方法的分类。

  (2)插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、堆积排序法、归并排序、基数排序。各种排序方法排序的原理、规律和特点,各种排序算法的时空复杂度简单分析。

  二、考试要求

  数据结构

  1、  建立有关数据结构最基本的概念,包括数据的逻辑结构、存储结构和算法,算法分析的基本概念与基本方法

  2、  掌握线性表的基本概念以及两种存储结构的构造原理,掌握在各种存储结构下对线性表进行的基本操作的算法设计。

  3、  掌握堆栈和队列的基本概念与特征,掌握在两种存储结构下如何对堆栈和队列进行插入和删除等操作,以及利用堆栈与队列解决实际问题的基本方法。

  4、  充分了解串的基本概念、掌握串的存储结构和相关的操作算法。

  5、  掌握数组、广义表和稀疏矩阵的基本概念,物理结构和基本操作的实现

  6、  充分了解树型结构的逻辑特征,掌握各种存储结构的构造原理,能够熟练地利用常用的三种遍历方法,掌握利用二叉树的遍历操作解决实际问题的方法,掌握二叉排序树的建立以及在二叉排序树中查找一个结点存在与否的过程。

  7、  充分了解图的逻辑结构的特点,掌握常用的两种存储方法,掌握最小生成树(Prim算法和Kruskal算法)、最短路径、拓扑排序的具体求解过程。

  8、  充分了解各种顺序文件的结构与相应的查找方法;了解各种查找算法之间时空效率的差异;从结构与操作上了解散列文件的建立、散列函数的选择(构造)原则、处理散列冲突的方法以及在散列文件中查找一个记录存在与否的过程。

  9、  充分了解各种排序方法的排序特点和排序过程,对于任意给出的数据元素序列,能够熟练地采用指定排序方法进行排序,并且能够对每一种排序方法排序过程中所进行的元素之间的比较次数、相应排序算法的时间、空间、排序的稳定性等性能进行简单分析。

  三、主要参考书目

  1、《数据结构》严蔚敏,清华大学出版社;

◇ 编辑推荐
·2016年考研调剂信息汇总(更新中)
·2016年考研国家线
·2017考研网上辅导招生简章
 考研教育网官方微信

微信公众账号cnedu_cn

 网上辅导课程特色
  • 即报即学
  • 名师团队
  • 反复看课
  • 在线答疑
  • 移动教学
  • 讲义下载
  • 课后练习
  • 模拟测试
 24小时报名咨询
考研网上辅导课程 精品班 实验班
学费 购买 学费 购买
公共课 政 治 1500元 购买 3500元 购买
英 语 1500元 购买 3500元 购买
数 学 1500元 购买 3500元 购买
专业课 考研名师编写,网校独创考研管理类、法律类、教育等专业课电子书正在热卖!