算法应该是问题求解步骤的描述
Xmind下载
线性表
顺序存储方式适用于图、树、线性表
定义一个顺序表需要包含的数据成员为：数组指针*data、表中元素个数n、表的大小MaxSize2 xde
kmp算法中，next数组看next[j],j，nextval数组中看next[i]（i为本位、j为上一位）
树
- 出现树的题要考虑树是一颗空树
- 树中结点数等于所有结点的度数之和加1
- 高度为n个结点的m叉树至多有$\frac{(m^k-1)}{m-1}$个结点
- 具有n个结点的m叉树最小高度为$\lceil\log_m(n(m-1)+1)\rceil$（向上取整）
- 非空二叉树上的叶子结点数等于度为2的结点数加1（$n_0=n_2+1$）
- 具有n个结点的完全二叉树的高度为$\lceil\log_2(n+1)\rceil$或$\lfloor\log_2n\rfloor+1$
- 非空二叉树上第k层至多有$2^{k-1}$个结点
- 高度为h的二叉树至多有$2^k-1$个结点
- 完全二叉树中按层次编号，则结点i的双亲为$\lfloor\frac{i}{2}\rfloor$，左孩子为$2i$，右孩子为$2i+1$，所在层次（深度）为$\lfloor\log_2i\rfloor+1$
- 红黑树黑高为h时，内部结点数最少的情况$2^k-1$，内部结点数最多的情况$2^{2k}-1$
- 红黑树上任一查找路径的红结点数量不可能超过一半，但整棵树的红结点总数有可能过半
- 哈夫曼树的WPL计算过程中：路径长度比结点在树中的高度少1
图
当带权连通图的任意一个环中包含的边的权值均不同时，其MST是唯一的
非连通的情况下边最多的情况：n-1个结点构成一个完全图，再任意加一条边变成连通图
一个有n条边n个结点的无向图是有环的
连通无向图边数至少是n-1条
有向图强连通情况下边最少的情况：至少需要n条边构成一个环路
在无向图中常讨论连通性，有向图中讨论强连通性
有向图的邻接表存储中，顶点v在边表中出现的次数是顶点v的入度
AOE图中只有关键路径上的活动同时减少时，才能缩短工期
增加任一关键活动的时间都会延长工程的工期
邻接表在更新边的操作时效率优于邻接矩阵（需要搜索所有结点）
广搜、深搜、拓扑排序、prime算法需要更新结点的边，因此选择邻接表表示图更好
一个单独的顶点也可以构成一个强连通分量
查找
- 折半查找判定树即在根据折半查找的过程构造的二叉树，其中mid的选择可以是向上取整、或是向下取整。但是需要在整个查找过程中保持一个取整方向
- B+树适用于关系数据库系统的索引
- 折半查找的平均查找长度为$\log_2(n+1)+1$。对折半查找进一步优化，可以使用索引顺序查找（将查找元素分块，为每块建立一个索引项，对索引项和块使用折半查找）
- 索引块的最佳大小是$\sqrt{n}$
- 折半查找的判定树高度为$h=\lceil\log_2(n+1)\rceil$（查找不存在的元素进行的关键字比较次数、查找存在元素的最多比较次数）
B树与B+树内部结点的子树个数$[\lceil m/2\rceil,m]$只是结点所含关键字不同（B树中结点的关键字要比子树少1）
装填因子$\alpha=\frac{n}{m}$（n：表中记录数，m：散列表长度）
选择排序和归并排序时间性能与初始状态无关
$\alpha<1$不表示可以避免碰撞（与散列函数有关）
求散列表的平均查找失败次数时，可能的取值是散列函数的取值范围（mod 7，表示散列只能取0-6，因此分母就是7，与散列表长度无关）
排序
向具有n个关键字的堆中插入一个新元素的时间复杂度为$O(\log_2n)$，删除一个元素的时间复杂度为$O(\log_2n)$
堆排序适用于关键字较多的情况，建一个大小为n的小（大）根堆，遍历一遍 数据，即可得到最大（小）的n个数（建立小根堆，，而后依次读入余下的数，小于堆顶则舍弃，否则用该数取代堆顶并重新调整堆）
小根堆堆最大关键字一定在叶子结点上，二叉树最后一个非叶子结点存储在$\lceil n/2\rceil$，最大关键字存储范围$\lceil n/2\rceil+1$～$n$
构建堆从n/2出开始调整，递减处理其他子堆（n/2为最后一个非叶子结点）
将两个各有N个元素的有序表合并为一个有序表，最少比较次数N次，最多比较次数2N-1次
有序顺序表、二叉排序树、堆、平衡二叉树相比，堆的查找效率最低（查找时是无序的）
排序趟数与原始状态无关的有：插入排序、选择排序、基数排序
就地算法要求空间复杂度为O(1),即所用空间大小为常数
元素规模较小时，使用直接插入、冒泡、简单选择排序
元素规模中等时，使用希尔排序
元素规模较大时，使用快排、堆排序、或基数排序；
快速排序算法中，不产生有序子序列，但每趟排序后会将枢轴元素放到最终位置上
外部排序进行多路归并时，能选取的最大归并段数取决于用于归并的内存大小。内存大小为一个输出缓存区+n个输入缓冲区（n即为归并段数）
