数据结构考试大纲-九游会j9官方登录

总要求：

1．熟悉信息的逻辑结构及其基本操作并在计算机中表示和实现；

2．掌握各种数据结构（线性表、堆栈与队列、树、图）的特性，具有数据抽象的能力；

3．熟练掌握各种数据结构的基本操作并能灵活应用，掌握应用问题的算法设计；

4．掌握主要的查找与排序的思想与算法，并初步掌握各类算法的时间分析和空间分析的技术。

内容：

（一）绪论
1．掌握数据、数据元素、数据对象、数据结构、存储结构和数据类型的概念和术语的含义；

2．理解算法五要素的确切含义；

3．掌握算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法；

（二）线性表
1．掌握线性表的逻辑结构特性是数据元素之间存在着的线性关系；

2．熟练掌握线性表的顺序存储结构和链式存储结构的描述方法, 头结点, 头指针, 和首元结点的区别及循环链表, 双向链表的特点；

3．熟练掌握线性表在顺序存储结构和各种链表结构上的查找、插入和删除的算法；

4．能够从时间和空间复杂度的角度综合比较两种存储结构的不同特点及其适用的场合。

（三）栈和队列

1． 熟练掌握栈和队列的结构特性；

2． 熟练掌握栈类型在两种存储结构表示时的基本操作实现方法；

3． 熟练掌握循环队列和链队列的基本操作实现算法；

4． 熟练掌握栈和队列的满和空的条件和它们的描述方法；

5． 熟悉栈和队列的典型应用。

（四）串

1．掌握串的结构特性----数据元素为字符的线性表；

2．熟悉串的七种基本操作；

3．掌握串匹配的kmp算法, 熟悉next函数的定义,学会手工计算next函数值。

（五）数组

1．掌握高维数组存在一维数组中的两种存储表示方法及以行为主的存储结构中的地址计算；

2．掌握对特殊矩阵进行压缩存储时的下标变换公式；

3．了解稀疏矩阵的三元组压缩存储表示方法及适用范围；

（六） 树和二叉树

1．熟悉树的基本定义及其相关的术语的含义；

2．熟练掌握二叉树的结构特性，了解相应的证明方法, 理解常见的二叉树有关理论结论；

3．熟悉二叉树的二叉链和线索二叉树存储结构特点及适用范围；

4．熟悉三种遍历二叉树的递归算法；

5．掌握二叉树线索化的实质及线索化的过程；

6．掌握树和森林与二叉树的转换, 及其各自遍历的对应关系；

7．了解实现树的各种操作的算法；

8． 掌握最优树的特性，掌握huffman树及其应用。

（七） 图

1．掌握图的定义和术语；

2．掌握图的两种存储结构：数组表示法、邻接表，了解实际问题的求解效率与采取何种存储结构和算法有密切关系；

3．掌握图的两种遍历策略；图的遍历和树的遍历之间的类似与差异；

4．熟悉图的最小生成树的生成方法；

5．aoe有向无环网的关键路径, 关键活动的计算思路；

6．掌握网络顶点之间的最短距离的计算思想。

（八）查找

1. 熟练掌握顺序表和有序表的查找方法；

2. 掌握查找效率的计算方法；

3. 熟练掌握二叉排序树的构造和查找方法；

4. 掌握平衡二叉树的维护平衡的方法。

（九）内部排序
1． 掌握排序的定义和各种排序方法的基本思想及其特点；

2． 了解各种排序方法的排序过程及其依据的原则，基于“关键字间的比较”进行排序的方法；

3． 熟练掌握快速排序和堆排序等方法的实例排序过程；

4． 能够进行各种排序方法的时间复杂性(平均情况与最坏情况)估计或分析；

5． 一般了解排序方法“稳定”的含义。