一、考试目的

兰州城市学院专升本招生《计算机科学与技术专业》专业综合课包括三部分内容：数据结构、算法设计 及数据库。考试目的是检查学生是否牢固掌握《数据结构》、《算法设计与问题求解》和《数据库技术》三门课程相关知识的一次水平测定，全面考核普通高校计算机专科（含高职）应届毕业生对这三门专业核心课程的掌握程度，要求学生比较系统地掌握其中的基本概念和基本理论并能应用这三门课程的基本理论去解决简单的实际问题。

二、考试重点

 

（数据结构部分）

 

（一）数据结构的概念

 1.理解数据结构中的一些基本概念；

 2. 掌握算法，算法特性、算法分析方法。

（二）线性表

1.掌握线性表的特点、顺序存储和链式存储的优缺点；

2.掌握线性表在顺序存储和链式存储（包括单循环链表、双链表、双循环链表）结构下的基本操作和一些简单算法的实现；

3.了解静态链表概念及存储表示。

（三） 栈和队列

1.掌握栈的特点、栈的基本操作、能够用栈的基本操作解决一些实际问题；

2.掌握队列的特点、队列的基本操作、链式队列的实现；

3.掌握循环队列基本操作的实现。

（四）数组和串

1.掌握高下标优先和低下标优先存储下多维数组中元素地址的计算方法；

2.掌握一些特殊矩阵的压缩存储；

3.掌握稀疏矩阵的表示法、掌握矩阵的加法和转置等运算；

4.掌握串的基本操作和朴素的模式匹配算法。

（五）树和二叉树

1.树和二叉树的概念；

2.树（林）与二叉树的相互转换；

3.二叉树的存储表示（1）二叉链表（2）完全二叉树的顺序存储；

4.二叉树与树的周游（遍历）的概念，各种周游方法实现；

5.二叉树遍历的算法及基于遍历算法的其它算法实现（结点统计等）；

6.Huffman树及应用。

（六）内部排序

1.排序的概念，内排序的分类、排序算法的分析；

2. 插入类、选择类、交换类排序中各种排序的基本思想，算法实现，稳定性，时空复杂度；

3.能综合分析比较各种排序方法的稳定性，及在各种情况下的时空复杂度。

（七）检索

1.顺序检索、二分检索、分块检索的概念，算法，时间复杂度；

2.散列法的基本概念，散列函数的构造方法；冲突的处理方法；

3. 二叉排序树的概念，插入，删除、创建及检索操作的实现。

（八）图

 1.图的概念和相关术语；

 2.图的存储表示方法：邻接矩阵，邻接表，邻接多重表；

 3.图的遍历： 深度优先遍历，广度优先遍历；

 4.最小生成树的概念，构造方法，算法；

 5.拓扑排序的概念，算法思想，算法；

 6.最短路径的概念，构造方法，算法。

 

（算法设计与问题求解部分）

 

（一）、考试重点：

本部分主要的考点是考生的应用编程能力，语种不限，要求选用适当语言设计出给定算法的程序。

（二）、考试形式：写程序。

（三）、分数：满分50分。

（四）、具体考试范围：

1.算法的基本概念及特点

2.算法的三种结构及其综合应用

3.掌握一门具体的语言，熟悉其基本语法规则

4.用户自定义函数的设计实现

5.递归算法

6.递推算法

7.回溯算法

8.枚举算法

9.常见查询算法（顺序查询、二分查询等）

10.常见排序算法

11.其它常见算法

 

（数据库技术部分）

 

（一）、考试重点：

了解关系型数据库系统基本原理，熟练掌握SQL语言的基本语句及常用函数。

（二）、考试形式：提供一部分原始数据库，按要求写出相应命令。

（三）、分数：满分50分。

（四）、具体考试范围：

1.关系数据库、SQL，了解关系数据库的物理和理论构成，SQL基本理论知识。

2.第二部分常用SQL语句的使用

SELECT、INSERT、DELETE、UPDATE

3.第三部分数据约束和排序

如何对数据进行约束;如何排序;SQL语句中支持的常用函数;第五部分显示多表数据;通过表连接和非表连接访问多个表中的数据;通过外连接访问数据表的自连接;分组函数;支持的分组函数及其使用;通过GROUPBY子句分组;在GROUPBY子句中使用HAVING子句;子查询;实现子查询的方法;定义子查询;定义单行和多行子查询;多列查询;定义多列子查询;当没有查询结果时，了解子查询的功能;在FROM子句中定义子查询.

三、试题难易度

较容易题                      约30%

中等难度题                    约50%

较难题                        约20%

四、说明

试卷满分为200分，《数据结构》100分,《算法设计与问题求解》和《数据库技术》各50分，考试时间为180分钟。