2018年沈阳大学809数据结构考研大纲

1
沈阳大学攻读硕士研究生入学考试大纲
（科目：809/数据结构）
一、 基本要求
1. 理解数据结构的基本概念、基本原理和基本方法；
2. 掌握数据的逻辑结构、存储结构及基本操作的实现；
3. 能够选择合适的数据结构对实际问题进行求解；
4. 具备采用 C（或 C++、JAVA）语言设计实现算法的能力。
二、考试形式与试卷结构
1．试卷成绩及考试时间
本试卷满分为 150 分，考试时间为 180 分钟。
2. 答题方式
答题方式为闭卷、笔试。
3. 参考教材
《数据结构（C 语言版）》，严蔚敏、吴伟民，清华大学出版社。
4. 题型结构
（1）选择题：10 小题，每小题 2 分，共 20 分。
（2）填空题：10 小题，每小题 2 分，共 20 分。
（3）问答题：6 小题，每小题 10 分，共 60 分。
（4）算法与程序设计题：5 小题，每题 10 分，共 50 分。
三、考试范围
1 基本概念和术语
1.1 数据元素、数据结构、抽象数据类型等概念；
2
1.2 算法设计的基本要求；
1.3 语句的频度，时间复杂度的估算。
2 线性表
2.1 线性表的定义和基本操作；
2.2 线性表的顺序存储结构、链式存储结构的实现；
2.3 线性表的应用。
3 栈与队列
3.1 栈和队列的基本概念；
3.2 栈和队列的顺序存储结构及链式存储结构的实现；
3.3 栈和队列的应用。
4 串、数组和广义表
4.1 串的存储结构，串的基本操作；
4.2 数组的定义，数组的顺序存储结构；
4.3 广义表的定义。
5 树与二叉树
5.1 树的概念，树的存储结构；
5.2 二叉树的定义及其主要特征，二叉树的顺序存储结构和链式存
储结构，二叉树的遍历，线索二叉树的构造，二叉排序树，平衡二叉树；
5.3 森林与二叉树的转换；
5.4 哈夫曼（Huffman）树和哈夫曼编码。
6 图
6.1 图的概念，图的存储结构（邻接矩阵、邻接表）及基本操作；
6.2 图的深度优先搜索和广度优先搜索；
6.3 最小生成树，拓扑排序，关键路径，最短路径。
3
7. 查找
7.1 查找的基本概念；
7.2 顺序查找法，折半查找法，散列（Hash）表及其查找；
7.3 查找算法的分析及应用。
8 内部排序
8.1 排序的基本概念；
8.2 直接插入排序，折半插入排序，冒泡排序，简单选择排序，希
尔排序，快速排序，堆排序；
8.3 各种内部排序算法的比较及应用。