数据结构大纲

《数据结构》考试大纲

一、考试基本要求

数据结构是计算机专业的一门专业基础课。本课程主要研究如何组织各种数据在计算

机中的存储、传递和转换。通过学习，要求学生比较系统地理解数据结构的基本概念和基本理论，掌握各种数据结构特点、存储表示和常用算法，初步具备综合运用所学知识分析问题和解决问题的能力。

二、考试方法和考试时间

数据结构为笔试，考试时间为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语言版），严蔚敏、吴伟民编著，清华大学出版社