文档介绍：《算法与数据结构》复****重点
一、第2章程序性能
1、给出一个程序段，会写出该程序段的时间复杂度；
二、第3章线性表
1、顺序存储结构的特点
表中元素可以随机访问；
非表尾的插入和删除操作需要移动元素；
表空间无法动态扩充，1个结点，至少有2h-i个结点
若非空二叉树有no个叶结点，气个度为2的结点，则气二『
具有n个结点的完全二叉树的高度为h= |log2n +1。
具有n个结点的二叉树的最小高度为Llog2n_| +1，最大高度为n。
若对具有n个结点的完全二叉树按照层次从上到下，每层从左到右的顺序进行编号，则编号为i的结点具有下列性质：
i如果i=1，则结点i是二叉树的根，无父结点；否则父结点是i/2
ii如果2i>n，则结点i无左孩子（结点i为叶结点）；否则左孩子编号为2i
iii如果2i+1>n，则结点i无右孩子；否则右孩子为结点2i+1
例题：（以下题均设仅含一个结点的二叉树的高度为1）
具有74个结点的完全二叉树，高度为 7 ，叶结点有37 个。（设
仅含一个结点的二叉树的高度为1）
已知二叉树中叶子数为40，仅一个孩子的结点数为20，则总结点数—__。
在含30个结点的完全二叉树中，对所有结点按层序从1开始编号（从上层到
下层，每层从左到右），则编号为10的结点的左子结点编号为20 ，右子结点编号为21 ，父结点编号为 5 。
高度为11的完全二叉树至多有2047个结点，至少有1024个结点。
具有70个结点的完全二叉树的高度为_1—。
具有43个结点的二叉树的最小高度为6 ，最大高度为 43 。
设在高度为h的二叉树（设仅有一个结点的二叉树高度为1）中只有叶结点和度为2的结点（没有度为1的结点），则该二叉树至多有2h-1个结点，至少有2h-1个结点。
8、二叉树的存储结构
在二叉树的链式存储结构中，含有n个结点的二叉链表有n+1个空链域，含有n个结点的三叉链表有n+2个空链域。
9、二叉树的前序、中序、后序遍历
给定一棵二叉树，能写出它的前序、中序、后序遍历序列；
给定一棵二叉树的前序和中序序列，能画出该二叉树并写出它的后序序列；或给定一棵二叉树的后序和中序序列，能画出该二叉树并写出它的前序序列；
10、线索二叉树
线索二叉树结点的Ichild、ltag、rchild、rtag各域的含义
如何利用中序线索链表进行二叉树的中序遍历？如何利用后序线索链表进行二叉树的后序遍历？如何利用前序线索链表进行二叉树的前序遍历？
11、树、二叉树、森林的相互转换中的几个结论
前序遍历树与前序遍历与该树对应的二叉树具有相同的遍历结果
后序遍历树与中序遍历与该树对应的二叉树具有相同的遍历结果
前序遍历森林与前序遍历与该森林对应的二叉树具有相同的遍历结果
后序遍历森林与中序遍历与该森林对应的二叉树具有相同的遍历结果
六、第7章优先队列
1、最大堆和最小堆的定义（理解）
2、初始建堆操作的建堆过程；堆的插入操作中堆的调整过程；删除堆顶元素后堆的调整过程
3、堆排序的时间复杂度为O（nlogn）
4、堆排序的方法；堆排序是一种不稳定的排序方法
5、左偏高树的左子树高度不一定大于右子树高度
6、具有m个结点的左偏高树和左偏重树的最右路