技术工程学院2020年专升本计算机科学与技术、软件工程专业课考试大纲

一、考试目的

兰州理工大学技术工程学院专升本招生计算机科学与技术专业课为《数据结构》。考试目的是检查学生是否牢固掌握《数据结构》课程相关知识的一次水平测定，全面考核普通高校计算机类专业专科(含高职)应届毕业生对专业核心课程《数据结构》的掌握程度，要求学生比较系统的理解数据结构的基本概念和基本理论。

二、考试内容

(一)基本概念

1.数据结构的基本概念和术语(数据元素、数据对象、逻辑结构、存储结构);

2.算法的特性和算法分析。

(二)顺序表

1.线性表的定义;

2.线性表的顺序存储结构(顺序表的查找、插入、删除操作);

3.线性表的链式存储结构(单链表的插入、删除操作)。

(三)栈和队列

1.栈和队列的定义;

2.顺序栈的入栈和出栈操作;

3.链队列的入队和出队操作。

(四)数组和广义表

1.数组的定义;

2.数组的顺序存储结构(分别以行序和列序为主，计算一维数组和二维数组元素的地址);

3.广义表的定义(计算广义表的长度)。

(五)树和二叉树

1.树和二叉树的定义;

2.二叉树的性质和存储结构(顺序、链式);

3.二叉树的遍历(先序、中序和后序)，线索二叉树的构造;

4.树、森林与二叉树的相互转换;

5.树的遍历(先根、后根)，森林的遍历(先序、中序);

6.最优二叉树(WPL值的计算)，应用赫夫曼树构造赫夫曼编码。

(六)图

1.图的定义和基本术语;

2.图的存储结构：邻接矩阵和邻接表;

3.图的遍历：深度优先搜索和广度优先搜索;

4.最小生成树的构造(普里姆算法和克鲁斯卡尔算法);

5.Dijkstra算法求解最短路径的过程。

(七)查找

1.顺序查找、折半查找和分块查找的过程、算法实现和算法分析;

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

(八)内部排序

1.直接插入排序、希尔排序、快速排序、简单选择排序等;

2.各种排序的算法实现和性能分析。

三、试题难易程度

1.较容易题：约40%;

2.中等难度题：约50%;

3.较难题：约10%。

四、考试形式及试卷结构

考试形式为闭卷笔试，时间为120分钟，试卷满分200分，试卷长度为A4纸8-10版。

试卷结构如下：

1.选择题 约20%;

2.填空题 约20%;

3.简答题 约40%;

4.算法设计题 约20%。

五、参考书目

《数据结构》(C语言版).严蔚敏编著.清华大学出版社,2011年。