2016年沈阳理工大学812数据结构考试大纲

　　一、考试基本内容
　　（一）绪论
　　（1）数据结构的基本概念和相关术语。
　　（2）数据的逻辑结构、存储结构。
　　（3）算法、算法的基本特性以及算法分析。
　　（二）线性表
　　（1）线性结构、线性表的定义，线性表的基本操作。
　　（2）线性表的顺序存储结构与链式存储结构(单链表、循环链表和双向链表)。在两种存储结构上主要的操作算法(包括建立、插入和删除等)的实现。
　　（3）线性表的应用。
　　（三）栈与队列
　　（1）栈与队列的基本概念、基本操作。
　　（2）栈和队列的两种存储结构及基本操作算法的实现。
　　（3）栈和队列的应用。
　　（四）串
　　（1）串的基本概念、串的基本操作和存储结构。
　　（2）串的模式匹配算法的实现。
　　（五）数组和广义表
　　（1）数组的概念、多维数组的实现。
　　（2）特殊矩阵和稀疏矩阵的压缩存储
　　（3）广义表的基本概念
　　（六）树与二叉树
　　（1）树的概念、术语，树的存储结构。
　　（2）二叉树的概念、性质，二叉树的存储结构。
　　（3）遍历二叉树和线索二叉树。
　　（4）树和森林。
　　（5）赫夫曼树及其应用。
　　（七）图
　　（1）图的定义，图的分类，常用概念术语。
　　（2）图的存储结构。
　　（3）图的遍历操作。
　　（4）最小生成树，最短路径，关键路径，拓扑排序。
　　（八）查找
　　（1）查找的概念和术语。
　　（2）静态查找表。
　　（3）动态查找表。
　　（4）哈希表。
　　（九）内排序
　　（1）排序的基本概念，排序方法的分类。
　　（2）插入排序法、选择排序法、交换排序法、归并排序、基数排序。各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度简单分析。

　　二、考试要求
　　（一）掌握数据结构的相关术语，建立有关数据结构的基本概念，掌握数据的逻辑结构、存储结构和算法，掌握算法分析的基本概念与基本方法。
　　（二）掌握线性表的基本概念，了解线性表在两种存储结构上实现的不同特点，掌握线性表的两种存储结构及其操作算法实现，掌握利用线性表实现不同问题的设计方法。
　　（三）掌握栈和队列的基本概念与特征，掌握在两种存储结构下栈和队列进行插入和删除等操作的实现，掌握栈和队列的应用问题。
　　（四）了解串的基本概念、掌握串的存储结构和相关的操作算法。
　　（五）掌握数组、广义表和稀疏矩阵的基本概念，掌握数组的物理结构和基本操作的实现，掌握特殊矩阵的压缩存储及操作实现。
　　（六）了解树与二叉树的逻辑特征，掌握二叉树的性质，掌握树与二叉树的存储结构，掌握树与二叉树的相互转换，能够熟练地利用常用的三种遍历方法及线索树的一般操作方法，掌握哈夫曼编码的设计与实现。
　　（七）了解图的逻辑结构的特点，掌握常用的两种存储方法，掌握最小生成树、最短路径、拓扑排序、关键路径的求解过程及算法实现，能运用上述算法解决一般问题。
　　（八）掌握顺序查找、折半查找方法，掌握二叉排序树的基本算法实现，掌握平衡二叉排序树及插入、删除时的方法，掌握哈希表的构造方法及处理冲突的方法，了解B树和B+树的操作过程，了解查找成功及失败的平均查找长度，了解各种查找算法之间时空效率的差异。
　　（九）掌握各种排序方法的排序特点和排序过程，对于任意给出的数据元素序列，能够熟练地采用指定排序方法进行排序，并且能够对每一种排序方法排序过程中所进行的元素之间的比较次数、相应排序算法的时间、空间、排序的稳定性等性能进行分析。

　　三、题型
　　（一）选择或判断或填空，20分
　　（二）简答题，40分
　　（三）综合应用，60分
　　（四）算法设计题，30分

　　（实习编辑：魏明瑞）