一、考试基本要求

数据结构是计算机专业的一门专业基础课。本课程主要研究如何组织各种数据在计算机中的存储、传递和转换。通过学习，要求学生比较系统地理解数据结构的基本概念和基本理论，掌握各种数据结构特点、存储表示和常用算法，初步具备综合运用所学知识分析问题和解决问题的能力。

二、考试方法和考试时间

数据结构为笔试，考试时间为1小时。

三、适用专业

数据结构考试试卷适用的专业为：计算机科学与技

四、考试内容及要求

(一)线性表

1.线性表的逻辑结构和顺序存储结构;

2.线性链表，循环链表的链式存储结构的特点。

(二)栈和队列

1.栈的定义、基本操作和实现算法;

2.队列的定义、基本操作和实现算法;

3.链式存储结构实现的链队列;

4.顺序存储结构实现的循环队列。

(三)串

1.串的定义、逻辑结构及基本操作;

2.串的存储结构;

3.模式匹配的定义及基本算法。

(四)数组和广义表

1.数组的定义和运算;

2.数组的顺序存储结构及特殊矩阵的压缩存储;

3.稀疏矩阵;

4.广义表的定义、存储结构。

(五)树和二叉树

1.树的结构定义及基本操作;

2.二叉树的结构定义及基本操作;

3.二叉树的性质;

4.前序，中序，后序遍历二叉树;

5.树与二叉树的相互转换、森林与二叉树的相互转换，树的遍历算法;

6.哈夫曼树及其应用。

(六)图

1.图的定义和术语;

2.图的邻接矩阵表示法;

3.图的深度优先搜索和广度优先搜索算法;

4.生成树，最小生成树的概念;

5.构造无向图的最小生成树的算法;

6.单源最短路径。

(七)查找

1.顺序查找算法、折半查找算法;

2.二叉排序树。

(八)内部排序

1.直接插入排序算法、希尔排序算法;

2.冒泡排序算法、快速排序算法。

五、试卷结构

(一)题型比例

填空题10%、选择题20%~30%、判断题10%、简答题10%~20%、综合题30%~50%。

(二)参考书目 (以下教材任何一种均可)

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

[2]《数据结构习题集》(C语言版)，严蔚敏、吴伟民编著，清华大学出版社