2018年辽宁科技大学数据结构考研大纲

辽宁科技大学 2018 年全国硕士研究生入学考试
《数据结构》考试大纲
本考试大纲由电信学院教授委员会于 2015 年 7 月 7 日通过。
科目代码：812
I.考试性质
数据结构考试是为辽宁科技大学电信学院控制科学与工程和电力电子与电力传动学科招收硕士研
究生而设置的具有选拔性质的全国统一入学考试科目，其目的是科学、公平、有效地测试学生掌握大
学本科阶段数据结构课程的基本知识、基本理论，以及运用数据结构学科的基础理论和方法分析和解
决问题的能力，评价的标准是高等学校本科毕业生能达到的及格或及格以上水平，以保证被录取者具
有数据表示和操作及问题求解的素质，并有利于其他高等院校和科研院所相关专业上的择优选拔。
II.考查目标
数据结构科考试涵盖数据结构的基本概念、算法及算法性能分析、线性表顺序和链式存储及其上
的操作、栈和队列的性质，存储和操作、二维数组及特殊矩阵的存储和元素地址求解、树和二叉树的
定义，性质，存储表示，二叉树的遍历，树与二叉树及森林的转换，哈夫曼树及哈夫曼编码、图的定
义及重要术语，图的存储及深度和广度遍历，图的应用（最小生成树，最短路径，拓扑排序，关键路
径）、查找的定义和查找方法，二叉排序树，平衡二叉树的创建，散列应用、排序的定义及排序方法尤
其是快速排序和堆排序。要求考生：
（1）掌握数据结构的里线性表，树和图，查找，排序的相关概念及性质、各种逻辑结构在计算机
内部的表示，在各种结构上实现重要操作的算法及算法性能的分析。
（2）能熟练运用链表，栈和队列，树的遍历，哈夫曼树，图的遍历，最小生成树，拓扑排序，最
短路径，查找，排序求解问题。
Ⅲ.考试形式和试卷结构
1、试卷满分及考试时间
本试卷满分为 150 分，考试时间为 180 分钟
2、答题方式
答题方式为闭卷，笔试。
3、试卷内容结构
数据结构概念、性质，算法及算法性能分析约 30%
数据结构应用链表，栈和队列，树的遍历，哈夫曼树，图的遍历，最小生成树，拓扑排序，最短
路径，查找，排序约 50%
算法及程序设计约 20%
Ⅳ.试卷题型结构
题型包括选择题、填空题、判断题、应用题和程序题（分程序阅读写结果和程序设计两类）。
Ⅴ.考查内容
（一）绪论
21
辽宁科技大学硕士研究生自命题大纲
了解和掌握数据结构的基本概念，这些概念包括:数据、数据元素、数据类型、抽象数
据类型、数据逻辑结构、数据存储结构、数据结构上的操作集合、算法及算法特点等。了
解和掌握算法效率分析的目的和方法。
考点：数据结构的定义，数据逻辑结构和存储结构以及二者之间的关系、算法效率分析
（时间复杂度求解）。
（二）线性表
了解线性表的逻辑结构和基本操作；理解线性表的顺序存储结构和实现方法；理解线性
表的链式存储结构和实现方法；了解单循环链表和双向链表的概念和基本设计方法。
考点：单链表的存储结构设计及操作实现算法，利用单链表完成差或等比及判断双链表
是否对称的应用。
（三）栈和队列
理解栈的概念、顺序栈和链式栈的设计方法；理解队列的概念、顺序循环队列和链式队
列的设计方法；了解优先级队列以及优先级队列和一般队列的差别；了解堆栈和队列的应用
方法。
考点：栈和队列的操作特性，双栈共享空和满的条件，循环队列空，满的条件及队列中
元素个数的求解。
（四）字符串和多维
理解串的概念；了解串基本操作的实现方法；了解串的 BF 模式匹配方法，掌握 KMP
模式匹配方法。熟练掌握二维数组的概念，了解特殊矩阵和稀疏矩阵的压缩存储方法；及稀
疏矩阵的三元组表的概念。
考点：串的基本操作应用，KMP 模式匹配的 NEXT 求解；数组中元素地址的求解，特
殊矩阵的存储。
（五）树与二叉树
了解树的定义、表示方法及其典型存储结构；理解二叉树的定义、性质、存储结构和操作
的实现方法；掌握二叉树的遍历算法及其应用实现；理解哈夫曼树的概念及其应用；了解树与二
叉树的关系。
考点：二叉树的性质；二叉树的遍历算法及应用；哈夫曼树的构建和编码的应用方法。
并能利用树的遍历实现如统计二叉树深度或宽度的算法，会实现树、二叉树和森林的相互转
换。
（六）图
了解图的基本概念和术语；掌握图的邻接矩阵和邻接表存储结构以及图操作的实现方法；
理解图的深度和广度优先遍历方法和算法设计方法；理解最小生成树的概念以及普里姆算法
和单源最短路径的狄杰斯特拉算法，拓扑排序和关键路径。
考点：图的邻接矩阵和图的邻接表存储结构；图的深度和广度遍历算法；最小生成树
的求解，单源点最短路径的求解，拓扑排序。
（七）查找
了解查找的基本概念和查找方法的评判标准；理解顺序查找，掌握折半（二分）查找的
算法设计方法；掌握二叉排序树和平衡二叉树树的基本结构和插入、删除方法；掌握散列函
数、散列冲突函数和散列表的构造方法。
考点：二叉排序树和平衡二叉树的构造；散列函数、散列冲突函数和散列表（开散列和
闭散列）的构造方法。
（八）排序
了解排序的基本概念和排序算法的评判标准；掌握直接插入排序、希尔排序、直接选择
排序、堆排序、快速排序、二路归并排序、基数排序的算法思想和算法设计方法；理解各种
排序方法的性能特点。
考点：希尔排序、堆排序、快速排序的实现，各种排序方法的时间复杂度分析。
VI 参考文献
《数据结构（C++版）》（第二版），王红梅编著，清华大学出版社，2011 年。