2018年江西理工大学622数据结构B考研大纲

1、 业务课（自命题）考试大纲、考试题型及分值分布
《数据结构》考试大纲:
一、考试内容
（一）绪论
1．数据结构基本概念、抽象数据类型的表示和实现
2．算法和算法设计、分析
（二）线性表
1．线性表的抽象数据类型定义、线性表的顺序存储结构、链式存储结构
2．单向链表、单向循环链表、双向链表、双向循环链表
3．线性链表的应用
4．串类型的定义、操作
（三）栈和队列
1．栈的定义、栈的表示与实现
2．栈的应用
3．队列的定义、队列的表示与实现
4．队列的应用
5．递归的定义及应用
（四） 数组和广义表
1．一维数组、多维数组的定义及地址计算
2．稀疏矩阵的存储存储表示
3．广义表的定义及基本操作
（五）树和二叉树
1．树的定义和基本术语
2．二叉树的定义、二叉树的性质、二叉树的存储结构
3．二叉树的遍历及建立算法
4．线索二叉树
5．树的存储结构、森林和二叉树的转换、树和森林的遍历
6．赫夫曼树及其应用
（六）图
1．图的定义和术语
2．图的四种存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）
3．图的遍历
4．最小生成树
5．拓扑排序
6．关键路径
7．最短路径
（七）查找
1．查找的基本概念
2．线性表的查找（顺序查找、折半查找、分块查找）
3．哈希查找（哈希函数、处理冲突的方法）
（八）排序
1．排序的基本概念
2．插入排序（直接插入排序、折半插入排序、希尔排序）
3．交换排序（冒泡排序、快速排序）
4．选择排序
5．归并排序
6．基数排序内容
二、考试要求
（一）绪论
1. 了解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念。
2. 了解数据结构的发展和地位。
3. 了解各种算法描述方法和算法设计的基本要求。
4．掌握对算法的评价标准和算法效率的度量方法。
（二）线性表
1．理解线性表的概念、定义、逻辑结构和存储结构。
2．熟练掌握线性表的顺序结构及其各种基本运算。
3．熟练掌握单链表、循环链表、双向链表的存储结构及其各种基本运
算。
4．理解链表的应用——稀疏多项式存储和运算。
5. 了解串的基本概念及顺序和链式存储结构。
6. 掌握串的各种基本运算。
7. 了解串的模式匹配算法。
（三）栈和队列
1．理解线性表的概念、定义、逻辑结构和存储结构。
2．熟练掌握线性表的顺序结构及其各种基本运算。
3．熟练掌握单链表、循环链表、双向链表的存储结构及其各种基本运
算。
4．理解链表的应用——稀疏多项式存储和运算。
（四） 数组和广义表
1．掌握数组的顺序存储结构。
2．理解稀疏数组的概念和压缩存储的方法。
3．理解稀疏矩阵的三元组存储结构和基本运算。
4．了解稀疏矩阵的十字链表存储结构。
5．理解广义表的基本概念，掌握广义表的存储结构。
（五）树和二叉树
1. 理解树的基本概念及其存储结构。
2. 熟练掌握二叉树的定义、性质以及各种存储结构和遍历算法。
3. 掌握线索二叉树的概念、存储结构及线索化算法。
4. 掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法。
5. 掌握哈夫曼树的概念、存储结构和应用。
（六）图
1. 理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构。
2. 了解十字链表，邻接多重表等存储结构。
3. 熟练掌握图的深度优先和广度优先遍历算法。
4. 理解图的连通性、最小生成树的概念。
5. 掌握求最小生成树算法。
6. 理解有向无环图的概念，掌握拓扑排序和关键路径算法。
7. 理解带权最短路径的概念，掌握求最短路径的算法。
（七）查找
1. 理解查找的概念及其效率的评价方法。
2. 理解静态查找表的概念，熟练掌握顺序、折半和分块查找算法。
3. 理解动态查找表和二叉排序树的概念。
4. 了解平衡二叉树的概念。
5. 理解哈希表的含义，掌握哈希函数的构造和处理冲突的基本方法。
（八）排序
1. 掌握插入类排序的算法：直接插入排序、希尔排序。
2. 掌握交换类排序的算法：冒泡排序、快速排序。
3. 掌握选择类排序的算法：简单选择排序、堆排序。
4. 了解归并排序、基数排序的思想，了解外排序的概念。
三、考试题型与分值分布
选择题（每题 2 分，共 40 分，）
简答题（大概 5-6 道题，共 30 分）
应用题（大概 5-8 道题，共 60 分）
算法设计题（每题 10 分，共 20 分）
四、考试形式及时间
考试形式为闭卷笔试，试卷总分值为 150 分。