2014年硕士研究生入学考试大纲

考试科目名称：数据结构    考试科目代码：801
 
一、        考试要求
考生要对算法设计中相关的数据结构有明确的认识，全面系统地掌握数据结构的基本概念、基本方法以及必要的基础理论知识，要具备较强的分析问题、算法设计能力，要求对给定的问题能够选择适当的数据结构，使用类C语言或者标准C语言或者标准C++语言比较规范的表达问题求解的算法。

二、        考试内容
1） 绪论
数据结构等术语的定义，抽象数据类型的定义和表示，算法和算法设计的基本要求，算法分析的基本方法。
2） 线性表
线性表的类型定义，线性表的两种存储结构（顺序和链式）的表示和实现，线性链表包括单向、双向和循环链表；一元多项式的表示及相加操作的实现。
3） 栈和队列
栈和队列的结构特性，两种存储结构上栈和队列的实现及其应用
4） 数组
数组的定义和表示方式，特殊矩阵和稀疏矩阵的压缩存储方法和运算的实现。
5） 树和二叉树
二叉树的定义、性质和存储结构，二叉树的遍历和线索化，树和森林，哈夫曼树及其应用。
6） 图
图的定义和相关术语，图的存储结构，图的遍历，图的连通性问题，有向无环图及其应用，最短路径
7） 查找
查找表的定义，静态查找表，动态查找表（二叉排序树，平衡二叉树，B-树），哈希表
8） 内部排序
排序的概念，插入排序的几种方法，快速排序，选择排序的几种方法，归并排序，基数排序
9） 外部排序
外部排序的概念和基本方法
10）            文件
文件的概念，顺序文件和索引文件

三、        试卷结构
考试时间180分钟、满分150分
1）题型结构
·单项选择题（10分）
 判断正误题（10分）
·填空题（20分）
·简答题（20分）
·应用题（60分）
·算法设计题（30分）
2） 内容结构
·绪论 （5分）
·线性表（20分）
·栈和队列（15分）
·数组（10分）
·树和二叉树（30分）
·图（25分）
·查找（20分）
·内部排序（15分）
·外部排序（5分）
·文件（5分）