天水师范学院2022年专升本“计算机科学与技术”专业免试入学专业能力测试大纲

一、测试科目

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

二、测试方式

形式以笔试、闭卷进行,满分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语言版)严蔚敏编著,清华大学出版社。


甘肃专升本