上饶师范学院年专升本《数据结构》考试大纲
上饶师范学院普通高校专升本招生统一考试《数据结构》试题，以上饶师范学院计算机科学与技术专业《数据结构》教学大纲和我省相关专业专科考生的实际为依据，主要考查学生的基本类型数据结构和各种基于数据结构的算法，以及运用所学知识组织数据的能力和算法设计的能力。
本科考试时间为分钟，总分为分。
一、考试范围及要求
（一）绪论
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分。试卷总分分。
命题原则
试题力求覆盖教材主要内容，知识点分布均匀，保持稳定的难易程度。着重考查学生基本知识的掌握程度，是否具备一定的数据组织能力，对具体问题，能抽象思维，并建立数学模型，并能独立地设计算法，解决实际问题。
试题难易比例
试题不超出教材所学知识，难易度与教材相当。其中，较容易题约占40％，中等难度题约占50％，较难题约占10％。
三、样题示例
一、单项选择题（每小题4分，15小题共60分）
1．将两个各有n个元素的有序表归并成一个有序表，在最好情况下最少的比较次数是()。
A.nB.2n-1C.2nD.n-1
二、填空题（每小题3分，10小题共30分）
16.高度为h的完全二叉树中最少有________个结点，最多有________个结点。
三、判断题（每小题3分，5小题共15分，对的打“√”，错的打“×”）
26.拓朴排序方法可以判断出一个有向图是否有环。（）
四、应用题（每小题8分，2小题共16分）
31.设无向图G（如图1所示），请用prim算法算法图示求最生成树的过程，并计算最小生成树各边上的权值之和。
图1
五、算法分析题（每小题6分，2小题共12分）
33.以下算法是实现将一个不带头结点的单链表按逆序链接，将空白部分补充完整。
#defineNULL0
typedefintelemtype;
typedefstructnode
{elemtypedata;
Structnode*next;
}linklist;
Voidfunction(linklist*head)
{linklist*p,*q;
p=head;
;
while(p!=NULL)
{q=p;
;
q-next=head;
;
}
}
六、算法设计题（共17分）
35.（本题要求采用C/C++语言描述，写出以下相应类型定义及算法，不要求写完整程序。）请用二叉链表表示一棵二叉树的存储方式；
（1）写出二叉树的结点的类型定义。（5分）
（2）写出统计一棵二叉树中叶子结点个数的算法。(12分)
尤轩专升本：
预览时标签不可点收录于话题#个上一篇下一篇