2021湖南第一师范学院专升本《数据结构》考试大纲

湖南第一师范学院2021年的专升本招生专业的计算机科学与技术专业的考试科目包含数据结构，校带大家看一下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%。