2020年兰州交通大学博文学院专升本数据结构考试大纲

兰州交通大学博文学院是2020年甘肃专升本招生院校之一。数据结构是2020年兰州交通大学博文学院计算机科学与技术专业必考科目。数据结构考试参考教材：《数据结构》(C语言版)，严蔚敏、吴伟民编著，清华大学出版社，2011年。具体考试大纲如下

一、考试内容与要求

(一) 基本理论知识

1.数据结构的基本概念和基本术语，算法的描述，算法的时间复杂度和空间复杂度分析。

2.线性表的定义，在线性表上常进行的基本操作，这些操作在顺序和链式存储结构下的实现及复杂度分析。

3.栈和队列的定义、特点、表示方法和实现。

4.串的定义及其基本操作。

5.数组的定义、运算和存储、稀疏矩阵的压缩存储、广义表的定义和基本操作。

6.树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，Huffman和Huffman编码。

7.图的定义和常用术语、图的存储结构及其遍历操作，求最小生成树、最短路径的算法，拓扑排序。

8.各种查找方法的算法、适用范围及时间复杂度的分析。

9.各种内排序算法的基本思想和算法的时间复杂度分析，不同排序方法比较。

(二) 基本技能

1.能阅读用类C语言编写的算法。

2.能分析算法所实现的功能、运行结果和时间、空间复杂度。

3.能根据要求用类C语言编写一些经典、常用算法。

(三)各章节学习目的要求和主要学习内容

第一章 绪论

学习目的要求：掌握数据结构的定义、内容和方法，掌握算法的定义、描述和评价。

主要学习内容：

1. 数据结构的概念和术语

2. 基本数据类型

3. 抽象数据类型的表示与实现

4. 算法描述与分析

第二章 线性表

学习目的要求：掌握线性表的抽象数据类型定义和两种存储方式，以及在相应存储结构上的线性表运算。

主要学习内容：

1. 线性数据结构的特点

2. 线性表的逻辑结构

3. 线性表的顺序存储和实现

4. 线性表的链式存储和实现

5. 应用举例

第三章 栈和队列

学习目的要求：掌握栈和队列的结构特征以及操作实现特点。

主要学习内容:

1. 栈的抽象数据类型

2. 栈的表示和实现

3.栈的应用举例

4. 队列的抽象数据类型及定义

5. 循环队列和链队列

6. 队列的应用

第四章 串

学习目的要求：掌握串的定义、基本存储结构和基本操作以及串的应用。

主要学习内容：

1. 串的逻辑结构和意义

2. 串的表示和实现

3. 串的模式匹配算法

4. 串的应用

第五章 数组和广义表

学习目的要求：掌握数组和广义表的定义和实现，加深对这两种特殊的线性结构的理解。

主要学习内容：

1. 数组的定义和运算

2. 数组的顺序存储和实现

3.特殊矩阵的压缩存储

4. 广义表的定义

5. 广义表的存储结构

第六章 树和二叉树

学习目的要求：掌握树型特征、存储及其操作实现。

主要学习内容：

1.树的定义和基本术语

2.二叉树

3.二叉树的遍历和线索二叉树

4.树和森林

5.哈夫曼树及其应用

6.树的应用举例

第七章 图

学习目的要求：掌握图在计算机中的存储和实现，并且利用图来解决实际问题

主要学习内容

1.了解图的定义和术语。

2.图的存储结构

3. 图的遍历

4. 图的连通性

5. 最短路径

6. 应用举例

第九章 查 找

学习目的要求：掌握数据的查找技术和表示和实现方法。

主要学习内容：

1.顺序查找，有序表的查找

2.索引顺序查找，二分查找法

3.哈希表

4.应用举例

第十章 内部排序

学习目的要求：掌握数据结构中排序的基本概念和五类重要的排序方法。

主要学习内容：

1.插入排序

2.交换排序

3.选择排序

4.归并排序

5.基数排序

6.各种排序方法的比较

第十一章 外部排序

学习目的要求: 了解对外存信息进行存取的特点，掌握外部排序的方法及实现。

主要学习内容

1.外存信息的存取

2.外部排序的方法

二、考试形式与及时间

1. 答题方式为闭卷笔试

2.答卷时间为120分钟，满分200分

三、试题类型

1.单选题 (40分)

2.填空题 (40分)

3.判断题(20分)

4.应用题(100分)