809数据结构

1、报考条件

需要学生系统地学会数据结构的基本定义和基本理论，学会各种数据结构的特征和基本办法，着重考察考生综合运用所学常识剖析问题和解决问题的能力。需要考生可以拥有使用C++语言设计与达成算法的能力。

2、考试内容

绪论

1)数据结构的基本定义，数据的逻辑结构、存储结构;

2)算法的概念和应具备的特质，算法设计的需要，算法的时间复杂度剖析和算法的空间复杂度剖析。

线性表

1)线性表的基本定义、特征、概念和基本操作;

2)线性表的顺序存储结构，对其进行检索、插入和删除等操作;线性表的链式存储结构，单链表、双向链表、循环链表和静态链表这四种链表形式的存储结构和特征与基本操作;

3)线性表的应用。

扩展线性表

1)栈、队列、多维数组、串的基本定义;

2)栈的顺序存储结构、链式存储结构、基本操作和应用;

3)队列的顺序存储结构、链式存储结构、基本操作和应用;

4)多维数组的存储、稀疏矩阵的三元组表示和有关运算;

5)串的存储结构、模式匹配算法;

6)经典算法应用：贪心、穷举、分治、回溯和动态规划。

树与二叉树

1)树、二叉树和森林的基本定义，树、二叉树和森林的遍历操作，树、森林与二叉树的转换;

2)完全二叉树与满二叉树的基本定义，二叉树的基本性质;

3)树和二叉树的存储结构;

4)二叉链表存储结构的架构、二叉树的前序遍历、中序遍历、后序遍历与层次遍历，与在二叉链表基础上各种有关算法的设计、达成与应用;

5)哈夫曼树和哈夫曼编码的基本定义、达成和应用。

图

1)图的基本定义、名词术语;

2)邻接矩阵、邻接表、邻接多重表、十字链表、边集数组的存储办法;

3)图的深度优先搜索与广度优先搜索的算法过程;

4)最小生成树、最短路径、拓扑排序和重点路径算法的原理与应用求解过程;

5)图的基本应用，譬如图的连通性、染色问题等。

查找

1)查找的基本定义，平均查找长度的计算等;

2)顺序查找法、折半查找法、索引查找算法;

3)二叉排序树、平衡二叉树的基本定义、打造、插入、删除、查找算法;

4) B-树的基本定义，B-树的查找、插入和删除算法;

5) 散列技术基本定义、散列函数的架构，冲突处置的办法和应用。

排序

1)直接插入排序、折半插入排序、希尔排序、简单选择排序、起泡排序、迅速排序、堆排序和归并排序算法的排序原理、规律、特征和达成;

2)计数排序、桶排序和基数排序的原理、规律、特征和达成;

3)各种内部排序算法的比较;

4)排序算法的应用。

3、试题结构

试题：填空题、选择题、简答卷、画图综合题、编程题