​2023年天水师范学院免试生专升本电子类考试大纲

一、适用专业

本大纲适用于报考天水师范学院2023年专升本免试入学专业能力测试计算机科学与技术专业的考生。

二、测试科目

考试科目为《数据结构》。

三、测试方式

形式以笔试、闭卷进行，满分150分,考试时间120分钟。

三、基本题型

考试题型主要有：选择题、填空题、判断题、简答题。

四、测试内容及要求

(一) 数据结构基本概念

1. 掌握数据结构（逻辑结构、存储结构）的含义及其相互关系；

2. 掌握算法特性、算法时间复杂度和空间复杂度的计算方法；

3. 掌握算法与程序的区别；

4. 掌握算法描述和算法分析的方法；

(二) 线性表

1. 掌握线性表的逻辑结构特性；

2. 掌握线性表的顺序存储结构特征；

3. 掌握顺序表的插入、删除、查找操作；

4. 掌握单链表的概念、特点；

5. 掌握单链表的插入、删除、查找操作及其平均时间性能分析；

5. 掌握单链表、双链表、循环链表逻辑结构的区别；

6. 理解链表中头指针和头结点的使用；

(三) 栈和队列

1. 掌握栈的逻辑结构的特点；

2. 掌握队列的逻辑结构的特点；

3. 掌握顺序栈上实现入栈、出栈的基本算法；

4. 掌握顺序队列上实现入队、出队的基本算法；

4. 掌握使用数组实现的循环队列取代普通顺序队列的原因；

5. 掌握队列中计算数据元素个数的方法。

(四) 树

1. 掌握树与二叉树的逻辑结构的特征；

2. 掌握树的常用术语及含义；

3. 掌握二叉树的性质，掌握二叉树中节点的计算方法；

4. 掌握二叉树的两种存储方法及特点；

5. 掌握解二叉树的三种遍历算法；

6. 掌握确定三种遍历所得到的相应的节点访问序列；

7. 掌握树和森林与二叉树之间的转换方法；

8. 掌握哈夫曼算法的思想；

9. 掌握二叉排序树的概念及插入、删除算法。

(五) 图

1. 掌握图的概念和相关术语；

2. 掌握图的存储表示方法：邻接矩阵、邻接表；

3. 掌握图的遍历算法：深度优先遍历、广度优先遍历；

4. 掌握最小生成树的概念和构造方法。

(六) 查找

1. 理解查找在数据处理中的重要性；

2. 掌握查找算法效率的评判标准；

3. 掌握顺序查找、二分查找的基本思想及实现算法。

(七) 排序

1. 理解排序在数据处理中的重要性；

2. 掌握排序方法的“稳定性”含义；

3. 掌握排序方法的分类及其稳定性；

4. 掌握冒泡排序的基本思想及算法实现；

5. 掌握快速排序的基本思想及算法实现；

6. 掌握堆排序的基本思想及算法实现。

五、参考书目

严蔚敏主编，《数据结构》（C语言版），清华大学出版社,2018年出版。