初试《数据结构》科目考试大纲

一、考查目标

考查学生对数据结构及算法分析相关基础知识及技能的掌握水平，并对学生利用有关基础知识和技能分析研究计算机加工的数据结构特性，进一步为实际应用涉及的数据选择及设计适当的逻辑结构、存储结构及其相应的算法能力进行考核。

二、考试形式与试卷结构

（一）试卷满分及考试时间
满分为150分，考试时间为3小时。
（二）答题方式
答题方式为闭卷、笔试。
（三）试卷内容结构
内容结构为各部分知识点在试卷中所占的比例。
（四）试卷题型结构
选择题10分、简答题20分、解答题80分、算法设计题40分，合计150分。

三、考查内容及要求

（一）数据结构概述
1、基本概念及术语
数据结构、逻辑结构、物理结构、抽象数据类型的概念；数据结构的分类、两种物理结构的特点。
2、ADT的表示与实现
ADT的定义、作用及类C语言实现方法。
3、算法和算法分析
算法的概念、特性和评判标准、算法时间复杂度的概念、简单的算法时间复杂度分析。
（二）线性表
1、线性表的类型定义
线性表的抽象数据类型定义、线性结构的特点。
2、线性表的顺序表示和实现
顺序表的含义、特点和相关算法。
3、线性表的链式表示和实现
链表的含义、特点和相关算法。
4、一元多项式表示与相加
一元多项式表示与相加的方法、顺序结构和链式结构的区别和选择。
（三）栈与队列
1、栈
栈结构的抽象数据类型定义、特点、存储结构和相关算法。
2、栈的应用举例
栈的应用及相关算法。
3、队列
队列结构的抽象数据类型定义、特点、存储结构和相关算法。
（四）串
1、串类型的定义、表示和实现
串的定义、串的三种主要表示和实现方式。
2、串的模式匹配
串的常见模式匹配算法。
（五）数组与广义表
1、数组的定义
数组概念、特点。
2、数组的顺序表示和实现
数组顺序存储结构表示和实现。
3、数组的压缩存储
特殊矩阵的压缩存储、稀疏矩阵的压缩存储的实现方法。
4、广义表的定义和实现
广义表的定义及运算、广义表的存储结构。
（六）树和二叉树
1、树的定义和基本术语
树的定义、常用术语。
2、二叉树
二叉树的定义、二叉树的性质、存储结构。
3、数组的压缩存储
特殊矩阵的压缩存储、稀疏矩阵的压缩存储的实现方法。
4、遍历二叉树和线索二叉树
二叉树遍历及线索化的概念、方法和算法。
5、树和森林
树的存储结构，树、森林、二叉树间相互转换方法、树和森林遍历方法。
6、赫夫曼树及其应用
赫夫曼树和赫夫曼编码构造方法。
（七）图
1、图的定义和术语
图的定义和术语。
2、图的存储结构
图的邻接矩阵表示法、邻接表表示法、十字链表表示法。
3、图的遍历
图的深度优先及广度优先遍历方法和算法。
4、图的连通性问题
连通子图、生成树、最小生成树的定义和构造方法。
5、拓扑排序
拓扑排序方法、算法及应用。
6、最短路径
最短路径问题求解方法、算法及应用。
7、关键路径
关键路径问题求解方法、算法及应用。
（八）查找
1、静态查找表
查找的概念、顺序查找和折半查找的方法和算法。
2、动态查找表
二叉查找树和二叉平衡概念及作用、二叉查找树和二叉平衡树相关算法。
3、哈希表
哈希表的概念、冲突的概念、常见哈希函数构造方法、哈希表的处理冲突的常用方法。
（九）排序
1、排序的概念
排序的有关概念、排序的类型。
2、排序方法及算法
掌握插入排序、快速排序、选择排序、归并排序、基数排序的方法、算法及相关算法时间、空间复杂度分析过程。

四、考试用具说明

考试使用黑色笔作答,考试时需要携带计算器、直尺、笔。