2017年辽宁工程技术大学数据结构（C语言）考研大纲

- 1 -
初试《数据结构（C 语言）》科目考试大纲
一、考查目标
理解数据结构和算法的基本概念及如何利用抽象数据类型进
行程序设计；掌握线性表、栈和队列、串、数组和广义表、树、
图等典型数据结构及相关算法，以及排序、查找等重要算法；掌
握算法的时间分析和空间分析的技术。具备分析和解决现实世界
问题在计算机中如何表示和处理的能力，具有软件开发的基本能
力。
二、考试形式与试卷结构
（一）试卷满分及考试时间
满分为 150 分，考试时间为 3 小时。
（二）答题方式
闭卷、笔试。
（三）试卷内容结构
算法及其分析(5%)、线性表及其应用(10%)、栈和队列及应用
(20%)、树及应用(20%)、图及应用(20%)、查找排序(20%)、其他内容
(10%)。
（四）试卷题型结构
作图题、计算题（150 分）。
三、考查内容
（一）算法及分析
掌握算法的时间复杂度及空间复杂度计算方法,从而分析算
法优劣。
- 2 -
（二）线性表及其应用
主要内容为：
（1）线性表的逻辑结构定义及 ADT。
（2）线性表的顺序存储结构及操作的实现。
（3）线性表的链式存储结构及操作的实现。
（4）线性表的基本应用。
（三）栈和队列及其应用
主要内容为：
（1）栈的逻辑结构及特点。
（2）栈的顺序存储结构及其基本操作的实现。
（3）栈的应用。
（4）队列的逻辑结构及特点。
（5）队列的链式存储及其基本操作的实现。
（6）循环队列的特点及操作的实现。
（7）队列的应用。
（四）树及应用
主要内容为：
（1）树的基本概念及术语。
（2）二叉树的定义、特性及二叉树存储。
（3）二叉树遍历的递归算法及非递归算法。
（4）树的存储。
（5）最优二叉树——赫夫曼树。
（五）图及应用
主要内容为：
（1）图的基本概念。
- 3 -
（2）图的存储——邻接矩阵和邻接表。
（3）图的遍历算法——深度优先算法，广度优先算法。
（4）图的应用——拓扑排序，关键路径，最小生成树，最短
路径。
（六）查找排序
主要内容为：
（1）静态查找表——顺序表的查找及折半查找。
（2）动态查找表——二叉排序树和平衡二叉树的构造、插入、
删除及查找过程。
（3）哈希表——哈希表的构造和查找，并计算平均查找长度。
（4）常见的内部排序过程及算法——直接插入排序、希尔排
序、快速排序、队排序、归并排序。分析各算法优劣。
（七）其他内容
根据具体应用，能够选择合适的逻辑结构及存储结构，并
实现算法。
四、考试用具说明
考试使用黑色笔作答,允许在考试中使用直尺、三角板、计算
器。