辽宁工程技术大学硕士研究生入学考试考试大纲
科目名称：810数据结构
一、试卷满分及考试时间
试卷满分为150分，考试时间为180分钟。
二、答题方式
答题方式为闭卷、笔试。
三、考试用具说明
考试使用黑色笔作答,考试时需要携带笔。
四、参考书目
《数据结构》(C语言版 第2版)，严蔚敏、李冬梅、吴伟民
编著，人民邮电出版社。
五、考查内容
(一)绪论
1.数据结构的逻辑结构和存储结构表示方法及关系;
2.算法五个要素的确切含义;
3.算法设计的时间复杂度计算方法。
(二)线性表
1.理解线性结构的特点以及线性表的概念;
2.掌握线性表在顺序存储结构和链式存储结构上的基本操作的
算法;
3.理解顺序表与链表的优缺点。
(三)栈和队列
1.理解栈和队列的定义、特点及与线性表的异同;
2.掌握顺序栈和链栈的存储结构及基本操作;
3.掌握循环队列和链队列的存储结构及基本操作。
(四)串
1.理解串的有关概念和术语、串的逻辑结构和特点;
2.掌握串的存储结构和基本操作。
(五)数组和广义表
1.掌握多维数组存在一维数组中存储的地址计算方法;
2.理解稀疏矩阵的三元组压缩存储表示方法;
3.理解并掌握广义表的定义、存储结构。
(六)树和二叉树
1.理解树的概念并熟悉有关术语的含义;
2.掌握二叉树的定义和性质;
3.掌握二叉树的顺序存储和链式存储结构;
4.掌握二叉树的各种遍历算法;
5.掌握二叉树线索化的实质及线索化的过程;
6.理解树和森林的定义、树的存储结构、树的遍历、掌握树、森
林与二叉树之间的相互转换方法;
7.掌握赫夫曼(Huffman)树的概念及构造赫夫曼树和赫夫曼编
码的方法。
(七)图
1.理解图的概念并掌握有关术语;
2.熟练掌握邻接矩阵表示法和邻接表表示法;
3.掌握连通图遍历的基本思想和算法(深度优先和广度优先)，
能够给出两种遍历的顶点访问序列;
4.掌握最小生成树的概念及普里姆(Prim)算法和克鲁斯卡尔算
法(Kruskal),并能用图示法表示出给定网的一棵最小生成树的过程;
5.理解AOE有向无环网的关键路径,关键活动的计算方法;
6.掌握最短路径的概念以及使用迪杰斯特拉算法和弗洛伊德算
法求最短路径的方法;
7.掌握拓扑排序的基本思想，对给定的有向图能够写出所有拓扑
序列。
(八)查找
1.掌握顺序查找算法、折半查找算法;
2.掌握二叉排序树的构造和查找算法;
3.掌握哈希表、哈希函数的构造方法及处理冲突的方法和平均查
找长度。
(九)内部排序
1.理解内部排序的定义和各种排序算法基本思想及其特点;
2.掌握插入，希尔，快速，堆等方法的排序过程;
3.理解各种内部排序算法的优缺点、各种排序算法的时间效率分
析。