考前看数据结构
+ kmp：
next 就是 nextval（注意nextval求法）
j 就是 next，在 408 基础上-1
- 迪杰斯特拉没有路径 pre 写-1，length 为 0
- 注意空树
- 折半查找仅限于有序表，顺序存储
- 顺序<分块<折半<哈希
- 折半查找次数：2–2；3–2；4–3
总结：往2n 靠3->2（1）；5/6/7->4（2）；8/9/…/15->8（3）；
然后次数=n+1；
- 度数和节点的关系：节点数目=所有节点度数之和+1
- 不稳定：快希选堆
- A[m][n][p]，m层n行p列
- 层次遍历用队列
- 递归树
排序比较
5.求前k个最大元素，选堆排序较好
6.在具有n个元素的集合中找第k个最小元素，应使用快速排序方法。
1.1局部或整体有序，插入与冒泡排序的速度较快；快速排序较慢
1.2分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是冒泡算法，
1.3冒泡算法，初始序列为反序时交换次数最多。
2.当n较小时，宜采用选择排序（不稳定）；选用插入或冒泡排序（稳定）
3.当n较大且关键字元素随机，对稳定性也无需求时采用快速排序
4.当n较大且关键字元素有序，对稳定性+空间允许时，使用归并排序，否则（对稳定性无要求）用堆排序。
与初始序列之间的关系：
1.选择排序、二路归并、二分排序与初始序列无关，
2.冒泡、插入、快速、希尔排序与原始序列有关
**1.**在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的这个说法是错误的
2.堆不一定是一颗平衡二叉树（平衡二叉树一定有序）
3.在内部排序方法中，一趟排序后只有简单选择排序和冒泡排序可以选出一个最大（或最小）元素，并加入到已有的有序子序列中，但要比较n-1次。选次大元素要再比较n-2次,其时间复杂度是O(n2)。从10000个元素中选10个元素不能使用这种方法。
而快速排序、插入排序、归并排序、基数排序等时间性能好的排序，都要等到最后才能确定各元素位置。
堆排序，在未结束全部排序前，可以有部分排序结果。凡要求在n个元素中选出k个最大（或最小）元素，一般均使用堆排序。
因为堆排序建堆比较次数至多不超过4n,对深度为k的堆，在调堆算法中进行的关键字的比较次数至多为2(k-1)次，且辅助空间为O(1)。
4.堆可以看作是n个结点的完全二叉树。而败者树是由参加比赛的n个元素作叶子结点而得到的完全二叉树。每个非叶（双亲）结点中存放的是两个子结点中的败者数据，而让胜者去参加更高一级的比赛。另外，还需增加一个结点，即结点0，存放比赛的全局获胜者。
5.冒泡排序结束的条件：当至多进行n-1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。
三元组：
存储非0元素（适用于稀疏矩阵）
数据构成
- 数据项构成了数据元素，数据元素是构成数据的基本单位
数据三要素：重点俩结构
- 逻辑结构：线性+非线性
- 存储结构：顺序存储+链式存储+索引存储+散列存储
- 数据运算包含两部分内容，即数据运算的定义和实现。
数据运算的定义是针对逻辑结构来讲的，指出了运算的功能。
数据运算的实现是针对存储结构来讲的，指出了运算的具体实现步骤。
- 算法的三要素：操作、控制结构和数据结构
- 顺序，选择（条件分支），循环
算法特性
