2021年湖南第一师范学院专升本《数据结构》科目考试大纲
《数据结构》考试大纲
(满分 100 分，时限 90 分钟)
一、选用教材
李刚、刘万辉，数据结构(C 语言版)，高等教育出版社，2017 年。
二、考试范围和内容
第一章 绪论及C语言介绍
识记：
(1)数据、数据元素、数据项的基本概念;
(2)算法的概念、性质和目标。
领会：
(1)数据结构的三种逻辑结构和两种存储结构表示方法;
(2)数据结构和抽象数据类型的概念。
运用：
(1)算法的时间复杂度和空间复杂度分析。
第二章 线性表的结构分析与应用
识记：
(1)线性表的定义和抽象数据类型。
领会：
(1)顺序表的定义和存储结构;
(2) 单链表上实现的建表、查找、插入和删除等基本算法;
(3) 顺序表、单链表的优缺点。
运用：
(1)线性表的顺序表示和实现。线性表的链式表示和实现;
(2) 单链表、循环单链表、双向链表的存储结构和操作实现;
(3) 顺序表上的插入、删除等操作及其平均时间性能分析。
第三章 栈和队列的结构分析与应用
识记：
(1)栈的定义和特点。栈顶和栈底相关术语;
(2)队列的概念和特点。队首和队尾相关术语。
领会：
(1)顺序堆栈的存储结构和操作实现;
(2) 链式栈的存储结构和操作实现;
(3) 顺序队列的存储结构、顺序循环队列的表示和实现;
(4) 链式队列的存储结构和实现。
运用：
(1)栈和队列的应用。
第四章 字符串的结构分析与应用
识记：
(1)串的定义、空串、空格串、子串、主串、串相等。
领会：
(1)串的基本操作。
运用：
(1)模式匹配的原理及其 Brute-Force 算法
第五章 二维数组及广义表的结构分析与应用
识记：
(1)数组的定义;
(2)广义表的定义。
领会：
(1)特殊矩阵和稀疏矩阵的概念及其压缩存储;
(2)广义表的存储结构与操作实现。
运用：
(1)数组的实现机制。计算数组元素的地址计算公式。
第六章 树和二叉树的结构分析与应用
识记：
(1)树的定义、相关术语、表示方法和存储结构;
(2)二叉树的路径、路径长度、带权路径长度、哈夫曼树的概念。
领会：
(1)二叉树的存储结构——顺序表示法和链表表示法;
(2)二叉树的操作实现。
运用：
(1)二叉树、完全二叉树、满二叉树的定义和性质;
(2) 二叉树的三种遍历方法及相应的递归算法;
(3) 哈夫曼树的构造，哈夫曼编码方法;
(4) 树与二叉树的转换、树的遍历。
第七章 图的结构分析与应用
识记：
(1)图的定义和常用术语;
(2) 生成树和最小生成树的概念;
(3) 最短路径及相关概念;
(4) AOE 网、关键路径、关键活动的概念。
领会：
(1)邻接矩阵存储结构下图操作的实现;
(2)图的深度和广度优先遍历算法。
运用：
(1)图的邻接矩阵存储结构和邻接表存储结构;
(2) 构造最小生成树的普里姆算法和克鲁斯卡尔算法;
(3) 求最短路径的狄克斯特拉算法。
第八章 查找的分析与应用
识记：
(1)查找的基本概念、分类、平均查找长度。
领会：
(1)顺序查找、二分查找、分块查找的基本思想与实现方法;
(2)二叉排序树的查找、插入和删除算法。
运用：
(1)散列表的基本概念、构造方法和冲突解决方法;
(2) 散列表的查找算法;
(3) 各种查找算法的性能分析及比较。
第九章 排序的分析与应用
识记：
(1)排序的概念、分类;
(2)排序算法好坏的评判标准、排序方法的稳定性。
领会：
(1)直接选择排序的基本思想;
(2) 直接插入排序的基本思想;
(3) 冒泡排序的基本思想;
(4) 希尔排序的基本思想;
(5) 快速排序的基本思想。
运用：
(1)直接插入排序、冒泡排序、直接选择排序算法的实现;
(2) 各种内部排序方法的比较;
(3) 各种排序算法的性能分析和评价。
三、考核方式
1. 采取笔试，闭卷的形式进行考核。
2. 题型结构：选择题、填空题、判断题、程序分析填空题、算法设计题、综合应用题等。
3. 试题难易度：难度适中。基础题、中等难度题和难题比例分别大致控制在50%、30%、20%。
