2021吉首大学数据结构研究生考试大纲

发布时间：2020-12-07 编辑：考研派小莉推荐访问：

2021吉首大学数据结构研究生考试大纲内容如下，更多考研资讯请关注我们网站的更新！敬请收藏本站，或下载我们的考研派APP和考研派微信公众号（里面有非常多的免费考研资源可以领取，有各种考研问题，也可直接加我们网站上的研究生学姐微信，全程免费答疑，助各位考研一臂之力，争取早日考上理想中的研究生院校。）

+吉首大学研究生
微信,为你答疑,送资源

2021吉首大学市场营销学研究生考试大纲 2021吉首大学会计学原理研究生考试大纲 2021吉首大学产业经济学研究生考试大纲 2021吉首大学807管理学原理研究生考试大纲 2021吉首大学财务管理研究生考试大纲 2021吉首大学中级财务会计（MPAcc）研究生考试大纲 95%的同学还阅读了： 吉首大学研究生招生目录吉首大学研究生分数线吉首大学王牌专业排名吉首大学考研难吗吉首大学考研调剂信息吉首大学研究生导师名单吉首大学研究生学费吉首大学研究生奖学金

2021吉首大学数据结构研究生考试大纲正文

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

考试科目名称：数据结构

一、考试形式与试卷结构

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三、参考书目

[1] 严蔚敏、吴伟民编著，数据结构(C 语言版)，清华大学出版社，2012 年 7 月

吉首大学

添加吉首大学学姐微信，或微信搜索公众号“考研派小站”，关注[考研派小站]微信公众号，在考研派小站微信号输入[吉首大学考研分数线、吉首大学报录比、吉首大学考研群、吉首大学学姐微信、吉首大学考研真题、吉首大学专业目录、吉首大学排名、吉首大学保研、吉首大学公众号、吉首大学研究生招生）]即可在手机上查看相对应吉首大学考研信息或资源。