数据结构的复习笔记和一点点总结

最近准备期末考试，熬了好多个夜，事情比较多也没有太多时间准备数据结构的考试了(都怪我平时没有好好学)。明天就是数据结构的考试了，这里记录一下复习的一些总结，还有一些题目，便于以后需要的时候翻阅。
前提与规定：二叉树从0开始编号，空树高度为-1，根节点深度0，叶子节点高度为0。
1.关于树与二叉树
任意数 总结点数=分支数+1
三叉树 n3+n2+n1+n0= 3n3+2n2+n1+1
二叉树 n0=n2+1
二叉树的第i层(深度为i的层)上最多有2^i个节点
完全二叉树 2^k<=n<=2^(k+1)-1，k是高度，n是可能的节点数量，2^k<=n<2^(k+1)
任意二叉树 k+1<=n<=2^(k+1)-1，k是高度，n是可能的节点数量，k<n<2^(k+1)，单链-满二叉树
完全二叉树的高度k=[log2(n)]向下取整，k为高度 n为节点数量
完全二叉树下标为i的节点左右孩子是2i+1和2i+2，父亲是[(i-1)/2]向下取整，或者ceil(i/2)-1向上取整
二叉搜索树的充要条件(当且仅当)是其中序遍历序列单调非降
2.关于m阶B树(m路平衡搜索树)
m=2^k，k为合并的层数，二叉树的第i层(深度为i的层)上最多有2^i个节点
内部节点即非根节点非叶子节点，也可以叫中间节点
性质a:树中每个内部结点最多连有m个孩子节点(或叫做分支,m>=2)，存有不超过m-1个关键码.根节点关键字最少1个，分支数最少2个–满二叉树最下层节点个数为2^k，除最下层外2^k-1个(这里不同于编号)
性质b:每个内部节点至少连有ceil(m/2)个子节点(5阶B-树最小度数为3)–即减去一层是上限了
性质c:关键字key的数量ceil(m/2)-1<=n<=m-1，关键字按递增排序
性质总结:ceil(m/2)-1≤关键字≤m-1，ceil(m / 2) ≤子节点≤m，上下限：关键字=子节点-1
3.各种复杂度总结
稳定性快速记忆:冒泡、直接插入、桶、归并、基数排序是稳定的，快速、选择、希尔、堆排序是不稳定的。
图表总结(图片源自网络):桶排序:O(n+M),M是元素可能的上限[0,M)，n是关键码数量，稳定
基数排序:O(t*(n+M))，t为关键码的字段数(整数的位数)，稳定
DFS:O(n+e),BFS:O(n+e),PFS:O(n^2)
最小支撑树:Prim算法,O(n^2)
最短路径树:Dijkstra算法,O(n^2)
建堆:上滤(插入)、下滤(删除),O(log n)
自上而下的上滤(蛮力):O(n log n)，自下而上的下滤(Floyd):O(n)
4.排序数量相关总结
总排序趟数与初始状态有关的只有:快速排序，优化的冒泡 (快速排序的排序次数（递归深度）与关键字选择（初始状态）有关，还有一个优化后的冒泡排序和后序是否有序有关)
算法复杂度与初始状态无关的有:堆排序、归并排序、选择排序、基数排序
元素总比较次数与初始状态无关的有:选择排序、基数排序 (基数排序中并不发生任何元素之间的比较)
元素总移动次数与初始状态无关的有:归并排序、基数排序
5.关于图
一个有向图G是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次
有n个顶点的强连通图最多有n（n-1）条边，最少有n条边
在邻接表中，删除一个顶点需要先删除其在顶点数组中的存储，再删除在其他结点中与被删除节点相关的边—O(E)，判断一条边是否存在要遍历顶点的邻居-O(n),一般e>>n,e=O(n2)
BFS、DFS时间复杂度是O(n+e)，PFS、Prim、Dijkstra时间复杂度是O(n^2)
6.一些相关的题目
a.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数目有____14___。
b.在一棵高为2 的5阶B-树中，所含关键字的个数最少是____5____。
c.在快速排序、堆排序、归并排序中，__归并__排序是稳定的。
d.在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ D ）。
A.希尔排序 B.冒泡排序 C.直接插入排序 D.直接选择排序
e.有n个顶点的有向强连通图最少有__n___条弧。
f.在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ A ）
A.直接插入排序 B.冒泡排序 C.简单选择排序 D.快速排序
g.序列的关键码为{80,70,33,65,24,56,48}，请用筛选法建立最小堆。

相关内容：
数据结构复习笔记与一些总结：https://4r7.com/archives/907
基于比较、渐进最优的排序算法(插入、希尔、选择、堆、冒泡、快速、归并排序实现)：https://4r7.com/archives/1152
不基于比较、线性时间运行的排序算法(计数、基数、桶排序分析)和顺序、对分查找实现：https://4r7.com/archives/1165
各种算法特性与复杂度总结：https://4r7.com/archives/1174