科目代码：843

科目名称：数据结构

一、考试的总体要求

主要考查学生对数据结构的基本理论与应用的掌握情况，以便为应用所涉及的数据结构选择适当的逻辑结构、存储结构及其相应的操作算法。考试时用C语言及C++语言描述算法均可。　

二、考试的内容

第1章 数据结构基础知识（1.2 与数据结构相关的概念；1.3.3 算法效率的衡量方法和准则）；

第2章 线性表（2.1 线性表的类型定义；2.2 线性表的顺序表示和实现；2.3 线性表的链式表示和实现(其中，2.3.5 双向链表不作要求)； 2.5 顺序表和链表的综合比较）

第3章 排序(3.1 排序的基本概念；3.2 简单排序方法；3.3 先进排序方法；3.4 基数排序；3.5 各种排序方法的综合比较)

第4章 栈和队列(4.1 栈； 4.2 栈的应用举；4.3 队列；4.4 队列应用举例)

第5章 串和数组(5.1 串的定义和操作；5.2 串的表示和实现；5.3 正文模式匹配)

第6章 二叉树和树(6.1 二叉树；6.2 二叉树遍历(其中，6.2.4 线索二叉树不作要求)；6.3 树和森林；6.4 树的应用)

第7章 图和广义表（7.1 图的定义和术语；7.2 图的存储结构； 7.3 图的遍历；7.4 连通网的最小生成树；7.5 单源最短路径；7.6 拓扑排序；7.7 关键路径）

第8章 查找表（8.1 静态查找表；8.2 动态查找表（其中，键树不作要求）；8.3 哈希表及其查找）

三、试卷类型及比例

（1）填空题 ，约占10％。

（2）选择题，约占30％。

（3）简答题、综合题、设计题，约占60％。

四、考试形式及时间

考试形式为笔试，考试时间为3小时，满分150分。

五、参考书目

（1）严蔚敏，陈文博 编著.《数据结构及应用算法教程》. 清华大学出版社，2011年5月第1版。