兰州信息科技学院2022年普通专升本免试生“电子类”专业能力测试大纲（二）

（计算机科学与技术、软件工程、物联网工程、数据科学与大数据技术）专业

为了做好2022年专升本免试招录工作，根据《2022年甘肃省普通高校高职（专科）升本科免试生招生工作实施方案》文件精神，制定电子类专业能力测试大纲，旨在考查学生对算法相关知识的理解和掌握程度。

要求考生掌握数据结构的基本概念，理解线性结构、树结构、图、内排序等相关算法，了解算法的设计分析和编程实现方法。

一、适用对象

2022年普通专升本招生，报考电子类计算机科学与技术、软件工程、物联网工程、数据科学与大数据技术等专业的免试生。

二、专业能力测试内容

报考以上专业的免试生，专业能力测试采用面试形式进行，测试满分为100分。通过考查以下内容，综合评价学生专业素质与知识：

（一）主要专业课程（60%）

考查考生对专业基础课《数据结构》理论与知识的掌握：

1.绪论

（1）掌握数据结构的概念；

（2）理解C语言、数据结构、算法以及程序之间的关系；

（3）掌握逻辑结构与存储结构两个层次的含义及相互关系；

（4）理解算法的特性和评价算法优劣的标准。

2.线性表 

（1）掌握线性表的定义；

（2）理解线性表的顺序存储结构（顺序表的查找、插入、删除操作）；

（3）了解线性表的链式存储结构（单链表的插入、删除操作）；

（4）理解数组与链表的区别。

3.栈和队列

（1）掌握栈和队列的定义；

（2）理解栈和队列分别在逻辑结构、存储结构和运算规则三方面的比较。 

4.树和二叉树

（1）掌握树和二叉树的定义；

（2）理解遍历二叉树算法（先序、中序和后序）及根据遍历序列确定二叉树；

（3）了解树、森林与二叉树的相互转换；

（4）了解最优二叉树（WPL值的计算），应用赫夫曼树构造赫夫曼编码。

5.图

（1）理解图的定义和基本概念；

（2）理解邻接矩阵表示法和邻接表表示法的优缺点；

（3）了解图的遍历和树的遍历的区别；

（4）理解最小生成树的构造及各自特点（Prim算法和Kruskal算法）；

（5）了解Dijkstra算法求解最短路径的过程。

6.查找

（1）理解顺序查找、折半查找和分块查找的过程和算法实现；

（2）了解二叉排序树的查找、插入和删除操作算法。

7.内部排序

（1）理解直接插入排序、希尔排序、快速排序、冒泡排序、简单选择排序的思想过程；

（2）了解各种排序的算法实现和性能分析。

（二）思辨能力与人文素养（25%）

考查考生表达能力、分析与解决问题的能力，以及行为举止、礼仪等。

（三）实践与创新能力（15%）

考查考生本专业以外的学习、社会实践（校园文化、实习实践）、创新创业能力等。

三、专业课推荐学习书目

《数据结构(第3版微课版)》（高职高专立体化教材计算机系列）李筠,姜学军主编.清华大学出版社，2021年。