博文学院2021年专升本专业课数据结构考试大纲

计算机科学与技术、网络工程、物联网工程专业《数据结构》考试大纲

一、考试内容与要求

(一) 基本理论知识

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分)

四、参考教材

《数据结构》(C语言版)，严蔚敏、吴伟民编著，清华大学出版社，2011年