数据结构复习大纲第一章基本概念：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.二叉树的遍历①先序：②中序：③后序：④层次：先序、中序遍历二叉树的非递归算法：先序：中序：