2021年湖南专升本考试公告尚未发布。对于即将参加2021年湖南省大专生考试的考生，以下乐贞老师为考生编辑的2020年湖南省人文科学学院数据结构考试大纲，可供2021年考生参考。

湖南文理学院数据结构考试大纲

一、考试大纲描述

1、课程的性质、目的和任务

数据结构是计算机专业的必修专业基础课。这门课程的主要特点是实用性强。不仅要学习基础理论知识，还要注重计算机实践。通过计算机实践，验证了算法的正确性，掌握并巩固了所学的理论知识。开设本课程的目的是使学生学会分析和研究计算机处理的数据结构的特点，从而为应用中涉及的数据选择合适的逻辑结构、存储结构和相应的算法，初步了解算法的时间分析和空互分析技术。另一方面，通过本课程中算法设计和计算机实践的训练，也要培养学生的数据抽象和程序设计能力，为后续课程尤其是软件课程打下坚实的知识基础。要求学生掌握各种常用数据结构的逻辑结构、存储结构和运算算法。

2.考试目标和要求

通过本课程的学习，学生要从数据结构逻辑结构、存储结构、运算三个方面系统地掌握常用的数据结构如线性表、栈、队列、串、数组、树、图等；并了解在各种常用数据结构上实现的排序和搜索算法，有一定的分析空之间的时间和复杂度的能力；对于简单的应用问题，我们应该能够选择合适的数据结构，并设计有效的算法来解决它们。考试的目的是考察学生对上述问题的掌握程度，以及在具体算法实施中发现和纠正错误的能力。

3.相关事项

在试题中，不同能力水平要求的分数一般如下:死记硬背占20%，理解占30%，简单应用占30%，综合应用占20%。

试题合理安排的难度结构。试题难度可分为易、易、难、难四个等级。每张试卷中，不同难度题目的评分比例为2: 3: 3: 2、

本课程有填空、单项选择、真假题、简答题、算法应用题、算法填空六种题型。

4.教学参考书

[1]吴伟民严为民。数据结构(c语言版本)。北京:清华大学出版社. 2011，7

专升本考试大纲" alt="湖南专升本考试大纲" width="600" height="372" border="0" vspace="0" style="width: 600px; height: 372px;"/>

二、考试内容及具体要求

(a)导言

1、知识点的考核

(1)解决实际应用问题时，正确数据结构的关键；以及研究数据结构的意义。

(2)数据、数据元素、数据项、数据结构等基本概念。

(3)数据结构的四种逻辑结构和两种存储结构表示。

(4)抽象数据类型的表示和实现。

(5)算法的五个特点。

(6)算法的概念，算法的时间复杂度，空之间的复杂度，最坏和平均时间复杂度等。

(7)算法描述和算法分析方法，可以分析一般算法的时间复杂度。

2.评估要求

(1)记忆

1)数据结构的基本概念和术语。

2)正确的数据结构在解决实际应用问题中的关键和研究数据结构的意义。

3)数据结构的四种逻辑结构和两种存储结构表示。

(2)理解

算法描述和分析:时间复杂度和空之间的复杂度，算法最差和平均时间复杂度。

(2)线性表

1、知识点的考核

(1)线性表的类型定义。

(2)序列表的含义和特点，序列表上的插入和删除操作及其平均时间性能分析。

(3)链式表示和实现，以及单链表、双链表和循环链表的链接方式的区别。

(4)单链表的创建表、搜索、插入、删除等基本算法及其时间复杂度。

(5)尾部指针代替循环链表上的头部指针。

(6)单循环链表上的算法与单链表上对应算法的异同。

(7)双链表的定义。

(8)序列表和链表的比较，以及如何选择一个作为其存储结构来达到更好的time 空性能。

2.评估要求

(1)记忆

1)线性表的逻辑结构特征；

2)线性表上定义的基本运算，利用基本运算构造复杂运算。

(2)理解

1)序列表和链表的比较，各自的优缺点。

2)对于线性表上要执行的主要操作，需要知道是选择顺序表还是链表作为其存储结构，才能获得更好的time 空性能。

(3)综合应用

1)序列表的含义和特征，以及对序列表的插入和删除操作。

2)单链表和双链表的区别；

3)单链表创建表、搜索、插入、删除等基本算法。

4)尾部指针代替循环链表中的头部指针，

5)单循环链表上的算法与单链表上对应算法的异同。

(3)堆栈和队列

1、知识点的考核

(1)栈的抽象数据类型的定义

(2)栈的表示和实现

(3)栈的简单应用

(4)抽象数据类型队列的定义

(5)队列的链式表示和实现

(6)队列的顺序表示和实现

2.评估要求

(1)理解

堆栈和队列的特征，以及它们各自的用法。

(2)综合应用

1)栈的逻辑结构特征，栈与线性表的异同。

2)在序列栈和链栈上实现栈入口和栈出口等基本算法。

3)队列逻辑结构的特点，队列与线性表的异同。

4)在顺序队列(主要是循环队列)和链式队列上实现的入队、出队等基本算法。

(4)字符串

1、知识点的考核

(1)字符串的定义，空字符串，空点阵字符串，子字符串，主字符串，字符串相等。

(2)字符串的基本操作。

(3)字符串的顺序存储结构以及顺序存储结构下基本操作的实现。

2.评估要求

(1)理解

字符串的一些概念及其基本运算。

(2)简单应用

1)字符串的三种存储表示。

(5)数组和广义表

1、知识点的考核

(1)数组的顺序存储结构。

(2)二维数组按行、列存储，计算数组元素的地址计算公式。

2.评估要求

(1)理解

1)多维数组的逻辑结构特征。

2)多维数组的顺序存储结构及其地址计算方法。

3)特殊矩阵和稀疏矩阵的概念。

4)稀疏矩阵的压缩存储方式——三重表。

(6)树和二叉树

1、知识点的考核

(1)树的定义和术语。

(2)二叉树(完全二叉树和全二叉树)的定义和性质，二叉树的存储结构——顺序表示和链表表示。

(3)二叉树的三种遍历方法及相应的递归算法。

(4)树的存储表征——儿童表征、父母表征和儿童兄弟表征。

(5)树、林、二叉树的转换方法。

(6)树的路径长度，树的加权路径长度，Hoeffmann树(最优二叉树)的构造方法。

(7)霍夫曼编码方法。

2.评估要求

(1)理解

1)树的逻辑结构特征。

2)树的不同表示。

3)树的常用术语和含义。

4)树与林、二叉树的转换方法。

5)树木的各种贮藏结构及其特点。

6)树的遍历方法。

(2)简单应用

1)二叉树的定义以及树和二叉树的区别。

2)二叉树的性质

3)二叉树的两种存储结构和特点。

4)最优二叉树和前缀编码的概念和特点。

5)根据给定的叶节点及其权重，构造相应的最优二叉树。

6)根据最优二叉树构造相应的霍夫曼码。

(3)综合应用

1)二叉树的三种遍历算法，并了解其执行过程。

2)根据不同的遍历方式，应该得到相应的节点访问顺序。

(7)图

1、知识点的考核

(1)图的逻辑结构特征。

(2)图形的常用术语和含义。

(3)图的邻接矩阵表示的存储结构。

(4)图的邻接表表示。

(5)图的深度优先遍历。

(6)图的广度优先遍历。

(7)生成树和最小生成树。

(8)构造最小生成树的PRIM算法。

(9)构造最小生成树的Kruskal算法。

2.评估要求

(1)理解

1)图的逻辑结构和特征。

2)图形的常用术语和含义。

3)生成树和最小生成树的概念。

4)遍历给定的图，先画深度，先画宽度的生成树或森林。

Prim和Kruskal算法的基本思想。

6)对于给定的连通图，根据Prim和Kruskal算法构造最小生成树。

(2)简单应用

1)图的邻接矩阵表示和邻接表表示。

2)根据应用问题的特点选择合适的存储结构。

3)两种遍历算法:深度优先搜索和广度优先搜索。

4)确定两个遍历顶点访问序列。

(八)寻找

1、知识点的考核

(1)搜索定义关键词、搜索和平均搜索长度。

(2)静态查找表查找算法(顺序查找、二进制查找、块查找(索引顺序表查找))的效率(最差和平均长度)。

(3)散列法的特点。

(4)哈希函数和哈希地址。

(5)处理冲突的方法:开放地址法和链式地址法。开放地址法分为线性检测再散列、二次检测再散列和伪随机检测再散列。

2.评估要求

(1)记忆

1)数据处理中搜索的重要性。

2)找到成功或失败的意义。

(2)简单应用

1)顺序搜索、二分搜索法和块搜索的基本思想、算法实现和搜索效率分析。

2)二叉排序树的定义和特征

3)建立二叉排序树的过程是输入序列的排序过程，输入序列对建立的二叉排序树形状的影响

4)哈希表、哈希函数、哈希地址(哈希地址)、填充因子等相关概念

5)散列函数的构造方法和冲突解决方法

(9)内部排名

1、知识点的考核

(1)排序的目的、分类的定义和排序方法的稳定性。

(2)插入排序:直接插入排序算法、分裂插入排序算法、Hill排序思想。

(3)选择排序的思想

(5)气泡排序的思想。

2.评估要求

(1)记忆

排序方法稳定性的含义。

(2)理解

排序和其他排序方法的区别。

2021年湖南专升本考试政策还没有出台。准备参加考试的考生必须为考试做好准备。2021年，湖南专升本考试视频课程更新。考生可以提前登录乐贞教育学习，努力进入理想的大学。

部分内容来源于网络转载、学生投稿，如有侵权或对本站有任何意见、建议或者投诉，请联系邮箱（1296178999@qq.com）反馈。 未经本站授权，不得转载、摘编、复制或者建立镜像， 如有违反，本站将追究法律责任！