算法与数据结构-刷题日记
分类:
文章
•
2023-12-12 18:21:58
- 各种排序时间、空间复杂度、稳定性总结：
一般把快排的空间复杂度看作
O
(
l
o
g
n
)
O(logn)
O(logn)?
- n个顶点的无向图的邻接矩阵有n个表头节点，每个节点选作一个表头，即可建立邻接表。
- 二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 左、右子树也分别为二叉排序树；
- 没有键值相等的节点；
- 憨憨题：
- 若二叉树用二叉链表作存贮结构,则在 n 个结点的二叉树链表中只有 n—1 个非空指针域。n个节点的二叉树中，每个节点有两个链域，也就是2n个，除了根节点外，每个节点能且只能被指一次，所以有n-1个指针域非空，空指针域 =
2
n
−
(
n
−
1
)
=
n
+
1
2n-(n-1) = n+1
2n−(n−1)=n+1.
- 快排的挖坑法：快速排序之“挖坑法”
- 非空的二叉树一定满足:某结点若有左孩子,则其中序前驱一定没有右孩子。如果有右孩子，就会继续遍历它的右孩子而不会返回。
如下图所示：左图中前驱无右孩子中序为：BA 若前驱有右孩子中序为：BCA 因此A的前驱发生了变化，其前驱没有右孩子
- p个顶点p条边的连通图中至少有多少个生成树？
连通图中的生成树必须满足以下 2 个条件：
- 包含连通图中所有的顶点；
- 任意两顶点之间有且仅有一条通路；
因此，连通图的生成树具有这样的特征，即生成树中 边的数量 = 顶点数 - 1。
p个顶点p条边的连通图，则一定有环，最小的环为3条边组成，3条边随便去掉一条就是一棵生成树，所以为3个。
