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

最近准备期末考试,熬了好多个夜,事情比较多也没有太多时间准备数据结构的考试了(都怪我平时没有好好学)。明天就是数据结构的考试了,这里记录一下复习的一些总结,还有一些题目,便于以后需要的时候翻阅。
前提与规定:二叉树从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时间复杂度是N(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},请用筛选法建立最小堆。

发表评论

电子邮件地址不会被公开。 必填项已用*标注