数据结构考研复习总结

记录数据结构中的常见计算题与易忘知识点

计算

汉诺塔问题中移动次数：
出栈序列个数（某先序序列确定的二叉树个数）：卡特兰数

结点数 = 分支数 + 1
二叉树中
完全二叉树中

从 1 开始编号的完全二叉树的规则：
- 双亲结点的编号为：
- 左孩子结点的编号为：2i ，右孩子结点的编号为：2i+1
- 若，则结点 i 为分支结点

m 叉树第 i 层最多共有结点数：
二叉树第 i 层最多共有结点数：
高为 h 的 m 叉树最多共有结点数：
高为 h 的二叉树最多共有结点数：
具有 n 个结点的 m 叉树的最小高度为：
具有 n 个结点的二叉树的最小高度为：

平衡二叉树中含有 h 层的最少结点数（含有 n 个结点的最大深度）计算方法：
- 显然 $，，$
- 有

二叉树链式存储中空链域：n+1
线索二叉树中空指针：n+1
折半查找判定树失败结点：n+1
哈夫曼树中分支结点：n-1，共有 2n-1 个结点

对于 n 个顶点的图 G
- G 是无向图
  - 连通：最少 n-1 条边
  - 非连通：最多条边
- G 是有向图
  - 强连通：最少 n 条边（形成回路）

折半查找判定树高：
B 树高取值范围：

严格 k 叉树空归并段数：
- 当时取
- 当时无需添加空段

概念

结点的度：该结点孩子的个数
树的度：树中结点的最大度数
路径：两个结点之间所经过的结点序列
路径长度：路径上经过边的个数
树的路径长度：根到每个结点的路径长度的总和
二叉树中若先序序列为 XY，后序为 YX，则 X 为 Y 的祖先
完全图：任意两个顶点间有边（有向图要保证从 a 到 b 和从 b 到 a 都有边）
连通图：任意两个顶点间有路径（有向图要保证从 a 到 b 和从 b 到 a 都有路径）
无向图的全部顶点的度之和 = 2 * 边数
有向图的全部顶点的入度之和 = 出度之和 = 边数

二叉树 vs 度为 2 的有序树
- 前者可以为空，而后者至少有 3 个结点
- 前者中某结点无论是否有 2 个孩子，均需确定其孩子左右次序；而后者中若某结点只有 1 个孩子，就无需区分其孩子左右次序

遍历序列的对应

树	森林	对应二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

排序算法的比较

	空间复杂度	稳定性	特点	备注
直接插入		√		首（尾）有序
折半插入		√	仅顺	首（尾）有序
希尔排序		×	仅顺
冒泡排序		√	终位	首（尾）有序且全局最大（小）
快速排序	最坏	×	终位
简单选择		×	终位	首（尾）有序且全局最大（小）
堆排序		×	终位
二路归并		√
基数排序		√		r进制，d位数

补充：

一般排序方法中 耗时 =（比较次数+移动次数）* 趟数，而对于基数排序一趟分配耗时收集耗时，共 d 趟，所以时间复杂度为

排序趟数 与序列初始状态无关：直插、简单选择、基数排序
关键字比较次数 与序列初始状态无关：折半插入排序
元素移动次数 与序列初始状态无关：基数排序

堆排序的时间复杂度为：，而建堆的时间复杂度为：

基本有序序列 ——–> 利于直接插入排序，利于冒泡排序，不利于快速排序
（枢轴使左右分段长度相等时利于快速排序）