天水师范学院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年出版。