根据上饶师范学院计算机科学与技术专业数据结构教学大纲和我省相关专业院校考生的实际情况，上饶师范学院专升本统考数据结构试题主要考查学生数据结构的基本类型和基于数据结构的各种算法，以及用自己的知识组织数据和设计算法的能力。

本科考试120分钟，总分150分。

一、考试范围和要求

(a)导言

1.数据结构的概念；数据的逻辑结构(线性结构、树形结构、网状结构、集合结构)和存储结构(顺序存储结构、链式存储结构、索引存储结构、哈希存储结构)；数据操作。

2.抽象数据类型的表示和实现。

3.算法描述；时间复杂度；空之间的复杂度；算法分析方法。

(2)线性表

1.线性表格的类型和定义。

2.线性序列表示及算法实现。

3.线性表的链式存储及算法实现:包括线性链表、循环链表和双向链表。

4.一元多项式的表示及数学运算的实现。

(3)堆栈和队列

1.堆栈的抽象数据类型定义；序列栈和链栈的表示与实现。

2.栈的应用实例:数制转换问题；迷宫问题；表情评价问题；递归算法的实现。

3.队列抽象数据类型定义；顺序存储队列、链式队列和循环队列的算法实现。(4)字符串

1.字符串的抽象类型定义和特征。

2.字符串的表示和实现(字符串的定长顺序存储表示；堆分配存储表示；字符串的区块链存储表示)。

3.字符串模式匹配算法(朴素模式匹配算法、KMP模式匹配算法)及其改进算法。

(5)阵列

1.数组的定义，抽象数据类型。

2.数组的顺序存储表示和实现。矩阵的压缩存储(特殊矩阵的概念；稀疏矩阵的三元表示:稀疏矩阵的链表表示:稀疏矩阵转置、加减等的实现。

(6)树和二叉树

1.树形结构的基本概念。

2.树的存储结构。

3.二叉树的定义、性质和存储结构。

4.二叉树与树和森林之间的转换；树操作的实现。

5.遍历二叉树。

6、线索二叉树(靠前线程树；中间穿线树；穿线树后)。

7.霍夫曼树及其应用，霍夫曼编码。

(7)图

1.图形的定义和术语；图的邻接矩阵存储结构和邻接表存储结构。

2.图的两种遍历策略:深度优先搜索和广度优先搜索。

3.图最小生成树的prim算法和Kruskal算法。

4.拓扑排序算法；单源最短路径问题的Dijstra算法。

(八)寻找

1、静态查找表、序列表搜索；有序表的搜索；索引顺序表的搜索。

2.动态查找表，二进制排序树，二进制平衡树。

3.哈希表的概念、哈希函数的构造方法及冲突的解决。

(9)内部排名

1.插入排序的基本思想、算法特点、排序过程及其时间复杂度分析(Hill排序不做测试)。

2.交换排序(冒泡排序、快速排序)的基本思想、算法特点、排序过程和时间复杂度分析。

3.选择性排序的基本思想、算法特点、排序过程及其时间复杂度分析。

4.合并排序的基本思想、算法特点、排序过程及其时间复杂度分析(基数排序不做测试)。

二、考试形式和试卷结构

(一)考试形式:闭卷笔试。

(二)试卷结构

试卷由靠前卷和第二卷两部分组成。靠前卷包括单项选择题、填空题空题和判断题三种题型。靠前道单项选择题，包括15道小题，每道4分，共60分；填写第二个大题空，包括10个小题，每题3分，共30分；第三个大题，真假，包含5个小题，每题3分，共15分。第二卷包括三类问题:应用问题、算法分析问题和算法设计问题。第四大应用题，包括2道小题，每道小题8分，共16分；第五大题算法分析题，包括2个小题，每个小题6分，共12分；第六大题，算法分析，一个小项目组成，每个项目17分，共17分。试卷总分150。

(三)命题原则

试题尽量覆盖教材的主要内容，知识点分布均匀，保持稳定的难易程度。重点是考察学生对基础知识的掌握情况，是否具备一定的数据组织能力，对具体问题进行抽象思维，建立数学模型，自主设计算法解决实际问题。

(4)试题难度比

试题不超过课本所学知识，难度与课本相当。其中，易题约占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算法举例说明寻找最大生成树的过程，并计算最小生成树每边的权重之和。

专升本数据结构考试大纲题型" alt="2020上饶师范学院专升本数据结构考试大纲题型" width="147" height="186" border="0" vspace="0" style="width: 147px; height: 186px;"/>

第五，算法分析题(每道小题6分，2道小题12分)

33.下面的算法是将没有前导节点的单个链表反向链接，完成空的白色部分。

#定义空0

typedef int elemtype

typedef结构节点

{ elemtype数据；

Struct节点* next

} linklist

作废功能(链表*表头)

{ linklist *p，* q；

p = head

while(p！=空)

{ q = p；

q-> next = head；

}

}

六、算法设计题(共17分)

35.(本题目要求用C/C++语言来描述，写出下面相应的类型定义和算法，不要求完整的程序。请用二进制链表来表示一个二叉树的存储方式；

(1)写出二叉树节点类型的定义。(5分)

(2)写一个计算二叉树叶节点数的算法。(12分)

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