首页 学院概况 IT动态 学院动态 组织机构 师资队伍 本科教育 研究生教育 科研工作 党建工作 通知公告 学生之家 招生就业
招生就业
   就业前景与行业形式
   招生信息
计算机专业硕士研究生入学考试专业课大纲(数据结构)
2006年08月27日 12:00 来源: 作者:   阅读次 上传:管理员 组别:管理组
  
 

《数据结构》考试大纲

第一章、绪论
[1] 熟悉各名词,术语的含义,掌握基本概念。
[2] 掌握数据结构中逻辑结构和存储结构之间的关系。
[3] 了解抽象数据类型的定义,表示和实现方法。
[4] 掌握计算语句频度和估算算法时间复杂度的方法。

第二章、线性结构——线性表、栈、队列和串
[1] 理解线性表的逻辑结构定义。
[2] 熟悉抽象数据类型定义方式。
[3] 熟练掌握各种存储结构的描述方法。
[4] 掌握线性表、栈和队列之间的关系。
[5] 熟悉串的逻辑特征和存储方式,理解串的主要运算。。
[6] 熟练掌握在顺序和链式存储结构上实现相关基本操作。

第三章、数组和广义表
[1] 掌握数组的逻辑特征与存储方式。
[2] 掌握矩阵的压缩存储方式及其特点。
[3] 理解广义表的逻辑特征和存储方式。
[4] 掌握广义表的基本操作。

第四章、树和二叉树
[1] 熟练掌握二叉树的结构特性,了解相应的证明方法。
[2] 熟练二叉树的各种存储结构的特点及适用范围。
[3] 熟练掌握各种遍历策略的递归算法。
[4] 掌握在遍历过程中实现二叉树操作的思想。
[5] 了解最优树的特性,掌握建立最优树和哈夫曼编码的方法。
[6] 了解线索二叉树的定义及其存储;

第五章、图
[1] 掌握图的定义及其它基本概念。
[2] 掌握图的存储结构——数组、邻接表、十字链表、邻接多重表。
[3] 掌握图的遍历方法——深度优先搜索、广度优先搜索。
[4] 掌握最小生成树生成方法。
[5] 了解拓扑排序概念,了解关键路径算法。
[6] 掌握图的最短路径算法。

第六章、排序
[1] 掌握插入排序、快速排序、选择排序、归并排序、基数排序等内部排序算法的思想及实现方法;理解算法复杂性的分析过程;熟悉算法特点。
[2] 理解外部排序的思想和方法。

第七章、查找(检索)
[1] 掌握静态查找表——顺序表、有序表、静态树表、索引表的查找算法;理解算法复杂性的分析过程;熟悉算法特点。
[2] 掌握动态查找表——二叉排序树和平衡二叉树的概念、基本操作及其实现。
[3] 理解B树和B+树概念和特点。
[4] 掌握哈希查找思想,各种典型的哈希函数形式及冲突解决方法。

第八章、文件
[1] 了解与文件有关的基本概念;
[2] 理解文件结构及其组织方式——顺序、索引、散列文件(HASH)。

参考教材:
1.《数据结构:C语言版》严蔚敏,吴伟民编著,清华大学出版社
2. Robert L. Kruse, Alexander J. Ryba著,Data Structures and Program Design in C++,高等教育出版社,Pearson Education 出版集团,2001。