吉首大学硕士研究生入学考试自命题考试大纲（同等学力加试科目）

考试科目名称：数据结构

一、考试形式与试卷结构

1) 试卷成绩及考试时间

本试卷满分为 100 分，考试时间为 120 分钟。

2) 答题方式：闭卷、笔试。

3) 试卷内容结构

数据结构基本概念、算法特点及分析 5%，常用数据结构（线性表、栈、队

列、串、数组、广义表、树、二叉树、图）的定义、表示、实现及应用 65%， 查

找和内部排序算法及分析 30%。

4) 题型结构

a: 单选题，10 小题，每小题 2 分，共 20 分。

b: 填空题，10 小题，每小题 2 空，每空 1 分，共 20 分。

c: 名词解释，3 小题，每小题 5 分，共 15 分。

d: 简答题，3 小题，每小题 5 分，共 15 分。

e: 综合应用题，2 小题，每小题 15 分，共 30 分。

二、考试内容与考试要求

1、数据结构基本概念、算法特点与分析

考试内容

数据和数据结构概念，数据结构分类，算法的定义及特性，算法效率的度量。

考试要求

（1）掌握数据结构的基本概念、相关术语

（2）掌握常用数据结构的分类。

（3）了解抽象数据类型的表示与实现方法。

1

（4）掌握算法的定义、特性和度量方法。

（5）掌握算法的时间效率和空间效率的分析方法。

2、线性表表示与实现

考试内容

线性表的概念，线性表的顺序表示和实现，线性表的链式表示及其实现方法。

考试要求

（1）掌握线性表的类型定义。

（2）掌握线性表的顺序表示及其实现方法。

（3）掌握线性表的链式表示及其实现方法。

（4）了解线性链表、循环链表、双向链表在表示、实现及应用方面的区别。

3、栈和队列的表示与实现

考试内容

栈和队列的概念，栈和队列的表示及实现，栈和队列的应用。

考试要求

（1）掌握栈的抽象数据类型定义。

（2）掌握栈的表示及其实现方法。

（3）了解栈在数制转换、表达式求值、递归实现等方面的应用。

（4）掌握队列的抽象数据类型定义。

（5）掌握队列的链式表示（链队列）及其实现方法。

（6）掌握队列的顺序表示（循环队列）及其实现方法。

（7）了解队列在事件模拟方面的应用。

4、串、数组与广义表的表示与实现

考试内容

串类型的定义，串的表示和实现，串的模式匹配算法，数组和广义表的定义，

数组的顺序表示与实现，矩阵的压缩存储，广义表的存储结构。

考试要求

（1）掌握串类型、数组和广义表的定义。

（2）掌握串的定长顺序存储、堆分配存储和块链存储的表示表示及其实现

方法。

2

（3）掌握串的模式匹配算法及其改进 KMP 算法。

（4）了解串操作在文本编辑、建立词索引表等方面的应用。

（5）掌握数组的顺序表示及其实现方法。

（6）了解特殊矩阵、稀疏矩阵的压缩存储方法。

（7）掌握广义表的存储结构建立方法。

（8）了解求广义表的深度、复制广义表等广义表的递归算法。

5、树和二叉树的表示与实现

考试内容

树与二叉树的定义，二叉树性质与存储结构，二叉树的遍历，树和森林存储

结构与遍历，赫夫曼树及其应用。

考试要求

（1）掌握树和二叉树的定义、基本术语和性质。

（2）掌握二叉树的存储结构。

（3）掌握二叉树遍历算法。

（4）了解线索二叉树的相关概念。

（5）了解树和森林的定义。

（6）了解树的存储结构。

（7）了解森林与二叉树的转换算法，树与二叉树的等价转换算法，树和森

林的遍历算法。

（8）掌握最优二叉树（赫夫曼树）的构造方法及其应用方法。

6、图的表示与实现

考试内容

图的定义与基本概念，图的存储结构，图的遍历方法，拓扑排序，关键路径。

考试要求

（1）掌握图的定义和相关术语。

（2）掌握图的数组存储结构和邻接表存储结构。

（3）掌握图的深度优先和广度优先搜索遍历算法。

（4）了解无向图的连通分量、生成树，以及有向图的强连通分量的概念。

（5）掌握最小生成树构造算法。

3

（6）掌握有向无环图在拓扑排序、关键路径获取方面的应用。

（7）掌握从某个源点到其余各顶点的最短路径求解算法。

（8）掌握每一对顶点之间的最短路径求解算法。

7、查找算法及分析

考试内容

静态表（顺序表、有序表）的查找，动态表（二叉排序树、平衡二叉树、B

－树）的查找，哈希表查找（哈希函数构造、冲突处理方法，哈希表查找分析）。

考试要求

（1）掌握顺序表查找算法和有序表查找算法。

（2）了解静态树表查找算法和索引顺序表查找算法

（3）掌握二叉排序树和平衡二叉树的相关概念。

（4）了解 B 树、B+树、键树的相关概念。

（5）掌握哈希函数的构造方法、冲突处理方法。

（6）掌握哈希表的查找算法及其效率分析方法。

8、内部排序算法及分析

考试内容

插入排序算法及分析，交换排序算法及分析，快速排序算法及分析，选择排

序算法及分析，归并排序算法及分析，各种排序算法的比较。

考试要求

（1）掌握以希尔排序算法为代表的插入排序类算法的基本思想、排序过程

及时间复杂度分析。

（2）掌握以快速排序算法为代表的交换排序类算法的基本思想、排序过程

及时间复杂度分析。

（3）掌握以堆排序算法为代表的选择排序类算法的基本思想、排序过程及

时间复杂度分析。

（4）掌握归并排序算法的基本思想、排序过程及时间复杂度分析。

（5）了解基数排序（多关键字的排序、链式基数排序）算法的基本思想、

排序过程及时间复杂度分析。

（6）了解上述各种内部排序算法在算法原理及时空效率方面的区别。

4