沈阳建筑大学2005级硕士研究生复试《数据结构》考试大纲
一、适用专业
计算机应用技术
二、题目类型
选择题
填空题
计算分析算法题
三、参考书目
1.《数据结构》（C语言版） 严蔚敏、吴伟民编著 清华大学出版社
2.《数据结构题集》（C语言版）严蔚敏、吴伟民编著 清华大学出版社
四、基本内容
（一）绪论
1 掌握数据、数据元素、数据对象、数据结构、存储结构和数据类型的概念和术语的含义；
2 理解算法五要素的确切含义；
3 掌握算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。
（二）线性表
1 掌握线性表的逻辑结构特性是数据元素之间存在着的线性关系；
2 熟练掌握线性表的顺序存储结构和链式存储结构的描述方法及循环链表, 双向链表的特点；
3 熟练掌握线性表在顺序存储结构和各种链表结构上的查找、插入和删除的算法；
4 能够从时间和空间复杂度的角度综合比较两种存储结构的不同特点及其适用的场合。
（三）栈和队列
1 熟练掌握栈和队列的结构特性----操作受限的线性表；
2 熟练掌握栈类型在两种存储结构表示时的基本操作实现方法；
3 熟练掌握循环队列和链队列的基本操作实现算法；
4 熟练掌握栈和队列的满和空的条件和它们的描述方法；
5 熟悉栈和队列的典型应用，如：数制转换、表达式求值等。
（四）串
1 掌握串的结构特性----数据元素为字符的线性表；
2 熟悉串的七种基本操作;
3 掌握串匹配的KMP算法, 熟悉next函数的定义,学会手工计算next函数值。
（五）数组
1 掌握高维数组存在一维数组中的两种存储表示方法及以行为主(低下标优先)的存储结构中的地址计算, 特别注意下标是从0开始或从1开始；
2 掌握对特殊矩阵(对称矩阵,下三角矩阵等) 进行压缩存储时的下标变换公式；
3 了解稀疏矩阵的三元组压缩存储表示方法及适用范围。
（六） 树和二叉树
1 熟悉树的基本定义及其相关的术语的含义（如孩子、兄弟,深度、度等概念）；
2 熟练掌握二叉树的结构特性，了解相应的证明方法, 理解常见的二叉树（如满二叉树，完全二叉树，Huffman树，平衡二叉树，排序二叉树和判定树）有关理论结论；
3 熟悉二叉树的二叉链和线索二叉树存储结构特点及适用范围；
4 熟悉三种遍历二叉树的递归算法（先序, 中序和后序）；
5 掌握二叉树线索化的实质及线索化的过程；
6 掌握树和森林与二叉树的转换, 及其各自遍历的对应关系；
7 了解实现树的各种操作的算法；
8 掌握最优树的特性，掌握Huffman树及其应用。
（七） 图
1 掌握图的定义和术语（如顶点，边，度及其相互之间的数量关系,连通性与生成树等）；
2 掌握图的两种存储结构：数组表示法（邻接矩阵）、邻接表，了解实际问题的求解效率与采取何种存储结构和算法有密切关系；
3 掌握图的两种遍历策略：深度优先搜索和广度优先搜索；图的遍历和树的遍历之间的类似与差异；
4 熟悉图的最小生成树的生成方法（Prim方法和Kruskal方法）；
5 AOE有向无环网的关键路径, 关键活动的计算思路；
6 掌握网络顶点之间的最短距离的计算思想(Dijkstra方法和Floyed方法)。
（八）查找
1 熟练掌握顺序表和有序表的查找方法（顺序查找和二分查找）；
2 掌握查找效率的计算方法-----平均查找长度；
3 熟练掌握二叉排序树的构造和查找方法；
4 掌握平衡二叉树的维护平衡的方法。
（九）内部排序
1 掌握排序的定义和各种排序方法的基本思想及其特点；
2 了解各种排序方法的排序过程及其依据的原则，基于“关键字间的比较”进行排序的方法可以分为插入排序、交换排序、选择排序、归并排序和基数排序；
3 熟练掌握快速排序和堆排序等方法的实例排序过程；
4 能够进行各种排序方法的时间复杂性(平均情况与最坏情况)估计或分析；
5 一般了解排序方法“稳定”的含义。
一、适用专业
计算机应用技术
二、题目类型
选择题
填空题
计算分析算法题
三、参考书目
1.《数据结构》（C语言版） 严蔚敏、吴伟民编著 清华大学出版社
2.《数据结构题集》（C语言版）严蔚敏、吴伟民编著 清华大学出版社
四、基本内容
（一）绪论
1 掌握数据、数据元素、数据对象、数据结构、存储结构和数据类型的概念和术语的含义；
2 理解算法五要素的确切含义；
3 掌握算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。
（二）线性表
1 掌握线性表的逻辑结构特性是数据元素之间存在着的线性关系；
2 熟练掌握线性表的顺序存储结构和链式存储结构的描述方法及循环链表, 双向链表的特点；
3 熟练掌握线性表在顺序存储结构和各种链表结构上的查找、插入和删除的算法；
4 能够从时间和空间复杂度的角度综合比较两种存储结构的不同特点及其适用的场合。
（三）栈和队列
1 熟练掌握栈和队列的结构特性----操作受限的线性表；
2 熟练掌握栈类型在两种存储结构表示时的基本操作实现方法；
3 熟练掌握循环队列和链队列的基本操作实现算法；
4 熟练掌握栈和队列的满和空的条件和它们的描述方法；
5 熟悉栈和队列的典型应用，如：数制转换、表达式求值等。
（四）串
1 掌握串的结构特性----数据元素为字符的线性表；
2 熟悉串的七种基本操作;
3 掌握串匹配的KMP算法, 熟悉next函数的定义,学会手工计算next函数值。
（五）数组
1 掌握高维数组存在一维数组中的两种存储表示方法及以行为主(低下标优先)的存储结构中的地址计算, 特别注意下标是从0开始或从1开始；
2 掌握对特殊矩阵(对称矩阵,下三角矩阵等) 进行压缩存储时的下标变换公式；
3 了解稀疏矩阵的三元组压缩存储表示方法及适用范围。
（六） 树和二叉树
1 熟悉树的基本定义及其相关的术语的含义（如孩子、兄弟,深度、度等概念）；
2 熟练掌握二叉树的结构特性，了解相应的证明方法, 理解常见的二叉树（如满二叉树，完全二叉树，Huffman树，平衡二叉树，排序二叉树和判定树）有关理论结论；
3 熟悉二叉树的二叉链和线索二叉树存储结构特点及适用范围；
4 熟悉三种遍历二叉树的递归算法（先序, 中序和后序）；
5 掌握二叉树线索化的实质及线索化的过程；
6 掌握树和森林与二叉树的转换, 及其各自遍历的对应关系；
7 了解实现树的各种操作的算法；
8 掌握最优树的特性，掌握Huffman树及其应用。
（七） 图
1 掌握图的定义和术语（如顶点，边，度及其相互之间的数量关系,连通性与生成树等）；
2 掌握图的两种存储结构：数组表示法（邻接矩阵）、邻接表，了解实际问题的求解效率与采取何种存储结构和算法有密切关系；
3 掌握图的两种遍历策略：深度优先搜索和广度优先搜索；图的遍历和树的遍历之间的类似与差异；
4 熟悉图的最小生成树的生成方法（Prim方法和Kruskal方法）；
5 AOE有向无环网的关键路径, 关键活动的计算思路；
6 掌握网络顶点之间的最短距离的计算思想(Dijkstra方法和Floyed方法)。
（八）查找
1 熟练掌握顺序表和有序表的查找方法（顺序查找和二分查找）；
2 掌握查找效率的计算方法-----平均查找长度；
3 熟练掌握二叉排序树的构造和查找方法；
4 掌握平衡二叉树的维护平衡的方法。
（九）内部排序
1 掌握排序的定义和各种排序方法的基本思想及其特点；
2 了解各种排序方法的排序过程及其依据的原则，基于“关键字间的比较”进行排序的方法可以分为插入排序、交换排序、选择排序、归并排序和基数排序；
3 熟练掌握快速排序和堆排序等方法的实例排序过程；
4 能够进行各种排序方法的时间复杂性(平均情况与最坏情况)估计或分析；
5 一般了解排序方法“稳定”的含义。