2020-05-29 来源： 库课网校
一、考试目的
兰州理工大学技术工程学院专升本招生计算机科学与技术专业课为《数据结构》。考试目的是检查学生是否牢固掌握《数据结构》课程相关知识的一次水平测定，全面考核普通高校计算机类专业专科(含高职)应届毕业生对专业核心课程《数据结构》的掌握程度，要求学生比较系统的理解数据结构的基本概念和基本理论。
二、考试内容
(一)基本概念
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年。
