数据结构复习大纲.doc

数据结构复习大纲
第一章
基本概念：
1.数据结构的概念：
（1）逻辑结构：数据之间的结构关系，是现实中具体关系的抽象。
（2）存储结构：数据结构在计算机内存中的表示。
（3）算法：算法是求解问题的操作序列。
抽象数据类型：抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
3.算法的5个特征：
1）输入：0个或多个输入；2）输出：1个或多个输出；3）有穷性：算法必须在有限步内结束；4）确定性：组成算法的操作必须清晰无二义性；5）可行性：组成算法的操作必须能够在计算机上实现。
4.时间复杂度：
一般来说，设算法中基本操作的执行次数是问题规模n的某个函数f(n)，算法的时间复杂度记作：T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率与f(n)的增长率相同。
5.空间复杂度：
在本课程中，用执行算法所需的辅助空间的大小作为算法所需空间的度量。设执行算法所需的辅助空间是问题规模n的某个函数g(n),则算法空间复杂度记作：
S(n)=O(g(n))
注：要求会计算时间复杂度和空间复杂度！

第六章树与二叉树
1.二叉树的基本性质：
性质1在二叉树的第i层上最多有2i-1个结点
性质2深度为k的二叉树最多有2k-1个结点
性质3设二叉树叶子结点数为n0，度为2的结点n2，则n0=n2+1
二叉树的存储：
①顺序：（满二叉树或完全二叉树的顺序存储）

（非完全二叉树的顺序结构）

②二叉链表：

③三叉链表：

3.二叉树的遍历
①先序：

②中序：

③后序：

④层次：

先序、中序遍历二叉树的非递归算法：
先序：

中序：