上饶师范学院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分)

推荐阅读

上饶师范学院2020年专升本《C语言程序设计》考试大纲