一、考试性质

数据结构是计算机专业的一门核心专业基础课程，在整个专业教学中占有十分重要的地位。主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种存储数据结构上执行操作的算法。课程教学应达到的目标是使学生掌握数据的逻辑结构、存储结构和数据运算的基本理论、基本知识和基本技能，并具有利用计算机解决实际应用问题的能力。数据结构课程既是对以往课程的深入和扩展，也是为将来更加深入地学习后续专业课程打下基础。

本考试是为在计算机专科毕业生中招收本科生，实施的具有选拔功能的水平考试，指导思想是既有利于国家对高层次人才的选拔，又利于促进高等学校课程教学质量的提高。

二、考试的基本要求

要求学生比较系统地掌握数据结构的基本知识和基本技能，初步具有在明确所要解决的问题的基础上，经过对问题的深入分析和抽象，为其在计算机中建立一个模型，然后确定恰当的数据结构表示该模型，再在此基础上设计合适的算法，最后根据设计的数据结构和算法进行相应的程序设计来模拟和解决实际问题，为后继专业课程学习提供基础。

三、考试方法和考试时间

考试方法为闭卷笔试，考试时间为90分钟，满分为100分。

四、考试内容和要求

第 1 章 数据结构基础 

1、     考试内容

数据结构的基本概念和基本术语，算法的描述和算法分析。

2、基本要求

1）数据、数据元素、数据对象、数据结构等基本概念。

2）数据的逻辑结构、存储结构、算法的概念。

3）数据类型、抽象数据类型的概念。

4）时间复杂度、空间复杂度的概念以及简单算法时间复杂度的计算。

5）数据结构二元组的概念，S=（D,R）

第 2 章 线性表

1、考试内容

线性表的定义、线性表的逻辑结构，顺序表、链表、双向链表、循环链表存储结构及其运算。

2、基本要求

1）线性表的定义和线性结构的特点。

2）顺序表存储结构及其运算的实现。

3）单链表存储结构及其运算的实现。

4）循环链表、双向链表存储结构及其运算的实现和的特点。

5）顺序表和链表的存储结构各自的优缺点。

第 3 章 栈和队列

1、考试内容

栈和队列的定义、特点，存储结构及其各种运算。

2、基本要求

1）栈的定义、特点。

2）顺序栈存储结构及其运算的实现。

3）链栈存储结构及其运算的实现。

4）队列的定义、特点。

5）链队列存储结构及其运算的实现。

6）循环队列存储结构及其运算的实现。

7）栈和队列的简单应用。

第 4 章 串

1、考试内容

串的定义及其基本操作。

2、基本要求

1）串的定义和相关术语。

2）串的基本存储结构。

3）串的基本操作。

第 5 章 数组和广义表

1、考试内容

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

2、基本要求

1）数组的定义及存储结构。

2）特殊矩阵（对称矩阵、三角矩阵）的压缩存储和矩阵元素的访问。

3）稀疏矩阵的存储和矩阵元素的访问。

4）广义表的定义和特点。

5）广义表的存储结构和基本运算。

第 6 章 树

1、考试内容

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

2、基本要求

1）树的定义及其基本术语。

2）二叉树的定义、性质和存储结构。

3）二叉树的遍历（先序遍历、中序遍历、后序遍历、层次遍历）算法。

4）建立二叉树、输出二叉树中的叶子节点、统计二叉树中叶子节点个数、计算二叉树的高度算法。

5）树的存储结构，树、森林与二叉树的转换。

6）哈夫曼树的基本概念、构造哈夫曼树算法以及哈夫曼编码。

第 7章 图

1、考试内容

图的定义和术语、图的存储结构及其各种操作。

2、基本要求

1）图的定义和基本术语。

2）图的存储结构（邻接矩阵、邻接表）。

3）图的遍历算法（深度优先遍历、广度优先遍历）。

4）图的最小生成树构造算法（prim 算法、kruskal 算法）。

第 8章 查找

1、考试内容

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

2、基本要求

1）查找的基本概念。

2）顺序表的查找（顺序查找、折半查找）。

3）树表的查找（二叉排序树的定义、二叉排序树的查找、二叉排序树的插入与创建）。

4）散列表的查找（散列表的基本概念、散列函数构造方法、处理冲突的方法）。

第9章 排序

1、考试内容

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

2、基本要求

1）排序的基本概念（关键字、内外排序、稳定性等） 

2）插入排序的方法（直接插入排序） 

3）交换排序的方法（冒泡排序） 

4）选择排序的方法（简单选择排序） 

五、命题要求

本课程命题范围应涵盖课程的所有章节，试题难易程度分为，较易占45％，中等难度占35％，较难占20％。题型范围无选择题、无判断题，主要为主观题。

六、主要参考书目

1、程海英，彭文艺．数据结构案例教程（C语言版）．北京：电子工业出版社，2022．

2、严蔚敏，李冬梅，吴伟民．数据结构（C语言版）.第2版.北京：人民邮电出版社，2016.