技术与工程学院

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

一、考试的目的:

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

二、考试内容:

(一)基本概念

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

2.算法的特点及分析。

(2)顺序表

1.线性表的定义；

2.线性表的顺序存储结构(顺序表的搜索、插入和删除操作)；

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

(3)堆栈和队列

1.堆栈和队列的定义；

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

3.加入和离开链式队列。

(4)数组和广义表

1.数组的定义；

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

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

(5)树和二叉树

1.树和二叉树的定义；

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

3.二叉树的遍历(一阶、中阶、末阶)，线索二叉树的构造；

4.树木、森林、二叉树的转换；

5.树的遍历(先根，后根)，林的遍历(一阶，中阶)；

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

(6)图

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

2.图的存储结构:邻接矩阵和邻接表；

3.图的遍历:深度优先搜索和广度优先搜索；

4.最小生成树的构造(prim算法和Kruskar算法)；

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

(七)寻找

1.顺序搜索、二分搜索法搜索和块搜索的过程、算法实现和算法分析；

2.二叉排序树的搜索、插入和删除算法。

(8)内部排序

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

2.各种算法实现及性能分析。

三、试题的难度

1.比较容易的问题:40%左右；

2.中等难度问题:50%左右；

3.难度:10%左右。

四.考试形式和试卷结构

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

试卷结构如下:

1.选择题20%左右；

2.填写空题20%左右；

3.简答题40%左右；

4.算法设计20%左右。

动词 （verb的缩写）书目

1.数据结构(c语言版本)。严为民编辑。清华大学出版社，2011、

部分内容来源于网络转载、学生投稿，如有侵权或对本站有任何意见、建议或者投诉，请联系邮箱（1296178999@qq.com）反馈。 未经本站授权，不得转载、摘编、复制或者建立镜像， 如有违反，本站将追究法律责任！