石家庄铁道大学

硕士研究生招生初试科目考试大纲

——————————————————————————————————

科目名称：       数据结构         

编制单位：   信息科学与技术学院 

——————————————————————————————————

一、总体要求

本课程要求考生理解数据结构的基本术语、基本知识，掌握线性结构（线性表、栈和队列、数组、广义表、串等）、树、图等几种基本数据结构的特点、存储表示、基本运算方法以及应用；掌握常用的排序与查找算法；初步掌握算法的时间复杂度分析和空间复杂度分析技术。能够针对具体问题，选择并运用合适的数据结构解决问题。

二、考试形式

试卷一般采用客观题型和主观题型相结合的形式，主要包括选择题、填空题、解答题、算法设计题等，具体以实际考试为准。考试时间和总分以招生简章发布为准。

三、考试内容

1、绪论

（1）掌握数据结构的基本概念，数据的逻辑结构、存储结构以及二者之间的关系。

（2）掌握计算语句频度和估算算法时间复杂度的方法。

（3）理解算法五个要素的确切含义。

（4）了解抽象数据类型的定义、表示和实现方法。

2、线性结构

（1）掌握线性表的顺序存储结构和链式存储结构定义及其各种基本运算。

（2）掌握栈的顺序存储结构和链式存储结构以及基本操作的实现。

（3）掌握队列的顺序存储结构和链式存储结构及其基本操作的实现。

（4）了解串的基本概念及其存储结构。

（5）理解稀疏矩阵和特殊矩阵的压缩方法。

（6）理解广义表的基本概念，掌握广义表的特点及基本操作；

（7）掌握数组的存储表示方法和地址计算方法。

3、树与二叉树

（1）掌握二叉树的基本概念、性质和存储结构。

（2）掌握二叉树的先序、中序、后序和层序遍历方法、算法实现及算法思想的应用。

（3）掌握已知二叉树遍历序列，求解二叉树的方法。

（4）掌握线索二叉树的概念、存储结构及线索化方法。

（5）掌握二叉树、树和森林的转换方法；掌握树和森林的遍历方法。

（6）掌握哈夫曼树的构造和求解哈夫曼编码的方法。

4、图

（1）掌握图的基本概念、性质、邻接矩阵和邻接表存储结构。

（2）掌握图的深度优先搜索和广度优先搜索方法。

（3）掌握图的最小生成树生成方法。

（4）掌握图的最短路径求解方法。

（5）掌握图的拓扑排序和求解关键路径的方法。

5、查找

（1）掌握顺序查找、折半查找与分块查找算法，能对其性能进行分析。

（2）掌握二叉排序树的定义、二叉排序树的构造方法和查找方法。

（3）掌握平衡二叉树的定义、平衡二叉树的构造方法和查找方法。

（3）理解解决冲突的开放地址法与链地址法；掌握哈希表的构造方法；掌握哈希表的查找方法。

6、排序

（1）掌握插入类排序算法：直接插入排序，折半插入排序、希尔排序。

（2）掌握交换类排序算法：冒泡排序，快速排序。

（3）掌握选择类排序算法：简单选择排序，堆排序。

（4）理解归并排序算法和基数排序算法。

（5）掌握各种排序方法的特点，能够对各种排序算法进行评价，并能加以灵活应用。