2020上饶师范学院专升本数据结构考试大纲题型
上饶师范学院普通高校专升本招生统一考试《数据结构》试题，以上饶师范学院计算机科学与技术专业《数据结构》教学大纲和我省相关专业专科考生的实际为依据，主要考查学生的基本类型数据结构和各种基于数据结构的算法，以及运用所学知识组织数据的能力和算法设计的能力。
本科考试时间为120分钟，总分为150分。
一、考试范围及要求
(一)绪论
1、数据结构概念;数据的逻辑结构(线性结构，树型结构，网状结构，集合结构)，存储结构(顺序存储结构，链式存储结构，索引存储结构，散列存储结构);数据的运算。
2、抽象数据类型的表示与实现。
3、算法描述;时间复杂性;空间复杂性;算法分析方法。
(二)线性表
1、线性表的类型和定义。
2、线性的顺序表示和算法实现。
3、线性表的链式存储和算法实现;包括线性链表、循环链表、双向链表。
4、一元多项式的表示及数学运算的实现。
(三)栈和队列
1、栈的抽象数据类型定义;顺序栈、链栈的表示和实现。
2、栈的应用举例：数制转换问题;迷宫问题;表达式求值问题;递归算法的实现问题。
3、队列抽象数据类型定义;顺序存储队列、链队列、循环队列的算法实现。(四)串
1、串的抽象类型定义及特性。
2、串的表示和实现(串的定长顺序存储表示;堆分配存储表示;串的块链存储表示)。
3、串的模式匹配算法(朴素的模式匹配算法，KMP模式匹配算法)及其改进的算法。
(五) 数组
1、数组的定义，抽象数据类型。
2、数组的顺序存储表示和实现。矩阵的压缩存储(特殊矩阵的概念;稀疏矩阵的三元组表示法;稀疏矩阵的十字链表表示法;稀疏矩阵转置、加减法等运算的实现)。
(六)、树和二叉树
1、树型结构的基本概念。
2、树的存储结构。
3、二叉树的定义、性质及存储结构。
4、二叉树与树、森林之间的转换;树的运算的实现。
5、遍历二叉树。
6、线索二叉树(先序穿线树;中序穿线树;后序穿线树)。
7、哈夫曼树及其应用，哈夫曼编码。
(七)图
1、图的定义和术语;图的邻接矩阵存储结构、邻接表存储结构。
2、图的两种遍历策略：深度优先搜索和广度优先搜索。
3、图的最小生成树prim算法、Kruskal 算法。
4、拓扑排序算法;单源最短路径问题的Dijstra 算法。
(八)查找
1、静态查找表，顺序表的查找;有序表的查找;索引顺序表的查找。
2、动态查找表，二叉排序树和二叉平衡树。
3、哈希表的概念，哈希函数的构造方法，冲突的解决方法。
(九)内部排序
1、插入排序(希尔排序不考)的基本思想、算法特点、排序过程以及它们的时间复杂度分析。
2、交换排序(冒泡排序、快速排序)的基本思想、算法特点、排序过程以及它们的时间复杂度分析。
3、选择排序的基本思想、算法特点、排序过程以及它们的时间复杂度分析。
4、归并排序(基数排序不考)的基本思想、算法特点、排序过程以及它们的时间复杂度分析。
二、考试形式与试卷结构
(一) 考试形式：闭卷笔试。
(二) 试卷结构
试卷为第 I 卷、第 II 卷两大部分。第 I 卷包括单项选择题、填空题和判断题三种题型。第一大题单项选择题，含15个小题，每小题4分，共60分;第二大题填空题，含10个小题，每小题3分，共30分; 第三大题判断题，含有5小题，每小题3分，共15分。第 II 卷包括应用题、算法分析题和算法设计题三种题型。第四大题应用题，含2个小题，每小题8分，共16分;第五大题算法分析题，含2个小题，每小题6分，共12分;第六大题算法分析题，含1个小题，每题17分，共17分。试卷总分150分。
(三)命题原则
试题力求覆盖教材主要内容，知识点分布均匀，保持稳定的难易程度。着重考查学生基本知识的掌握程度，是否具备一定的数据组织能力，对具体问题，能抽象思维，并建立数学模型，并能独立地设计算法，解决实际问题。
(四)试题难易比例
试题不超出教材所学知识，难易度与教材相当。其中，较容易题约占 40%，中等难度题约占 50%，较难题约占 10%。
三、样题示例
一、单项选择题(每小题4分，15小题共60分)
1.将两个各有n个元素的有序表归并成一个有序表，在最好情况下最少的比较次数是( )。
A.n B.2n-1 C.2n D.n-1
二、填空题(每小题3分，10小题共30分)
16.高度为h的完全二叉树中最少有________个结点，最多有________个结点。
三、判断题(每小题3分，5小题共15分，对的打“√”，错的打“×”)
26.拓朴排序方法可以判断出一个有向图是否有环。 ( )
四、应用题(每小题8分，2小题共16分)
31.设无向图G(如图1所示)，请用prim算法算法图示求最生成树的过程，并计算最小生成树各边上的权值之和。
五、算法分析题(每小题6分，2小题共12分)
33.以下算法是实现将一个不带头结点的单链表按逆序链接，将空白部分补充完整。
#define NULL 0
typedef int elemtype;
typedef struct node
{ elemtype data;
Struct node *next;
}linklist;
Void function( linklist *head)
{ linklist *p,*q;
p=head;
;
while(p!=NULL)
{ q=p;
;
q->next=head;
;
}
}
六、算法设计题(共17分)
35.(本题要求采用C/C++语言描述，写出以下相应类型定义及算法，不要求写完整程序。)请用二叉链表表示一棵二叉树的存储方式;
(1)写出二叉树的结点的类型定义。(5分)
(2)写出统计一棵二叉树中叶子结点个数的算法。(12分)
