【408 冲刺】数据结构核心高频考点必杀技：树、KMP与内部排序解题圣经

Levi-Jac71

193人浏览 · 2026-06-13 23:33:40

Levi-Jac71 · 2026-06-13 23:33:40 发布

摘要：本文为 408 计算机考研数据结构学科的深度复习笔记，内容全量斩落平衡二叉树（AVL）递推边界、B/B+树核心指标区分、KMP子串计数陷阱、以及内部排序算法（希尔、堆排、快排）的底层宏观特征。重点收录了针对“快排第 $n$ 趟结果判断”和“初始堆分治精筛”的独家高效率秒杀方法，助力考研学子在选择题中快速破局。

文章目录

📚 本篇小结（05后备战考研备忘录）

一、树与二叉树（AVL 树的极限与 B/B+ 树的边界）

1. 平衡二叉树 (AVL 树) 核心定理

平衡二叉树作为 408 考研选择题的常客，其高度与结点数的关系是必考的数理考点。

最小高度公式：当平衡二叉树完全饱和（接近满二叉树）时，其高度最小：

$h_{\min} = \log_2(n+1)$

最少结点数递推公式：高度为 $h$ 的 AVL 树至少包含的结点数 $N (h)$ 满足斐波那契式的递推关系（红字强调：高度为 $h$ 的 AVL 树至少有 $N (h)$ 个结点）：

$N (h) = N (h - 1) + N (h - 2) + 1$

📌 核心边界值速查表（打牢数理地基）

根据上述递推公式，从高度 0 开始的边界结点数序列必须做到“肌肉记忆”：

树的高度 $h$	递推计算式	最少结点数 $N (h)$
$h = 0$	边界基础值	0
$h = 1$	边界基础值	1
$h = 2$	$N (1) + N (0) + 1 = 1 + 0 + 1$	2
$h = 3$	$N (2) + N (1) + 1 = 2 + 1 + 1$	4
$h = 4$	$N (3) + N (2) + 1 = 4 + 2 + 1$	7
$h = 5$	$N (4) + N (3) + 1 = 7 + 4 + 1$	12
$h = 6$	$N (5) + N (4) + 1 = 12 + 7 + 1$	20
$h = 7$	$N (6) + N (5) + 1 = 20 + 12 + 1$	33

💡 方法总结（平衡树调整的本质）：
平衡树调整的本质是在保持平衡因子 $\le 1$ 处的线索，即契合 AVL 树删除/插入结点的线索，做结构调整。在面对复杂的旋转题目时，宏观把握“平衡因子不破 1”的原则是快速排除错误选项的终极线索。

2. B 树与 B+ 树的核心边界对比

408 大纲中对 B 树和 B+ 树的定义有极其严苛的数值边界限定，选择题常利用其分支与关键字的对应关系设坑：

⚖️ B 树（多路平衡查找树）

子树与关键字约束：除根结点外，非叶结点至少有 $\lceil m/2 \rceil$ 棵子树；每个结点至多有 $m$ 个关键字。
最大深度公式（含失败叶子结点层）：

$H_{\max} = \lfloor \log_{\lceil m/2 \rceil} \frac{n+1}{2} \rfloor + 1$

⚖️ B+ 树（常见于操作系统的文件系统和数据库索引）

核心特征：每个非叶结点拥有 $m$ 个关键字，对应 $m$ 棵子树（关键字个数与子树个数严格相等）。

二、字符串与 KMP 算法的基础延伸

1. KMP 算法的概念本质

术语定义： $t$ 代表 target substring（目标子串 / 模式串）， $r$ 代表 result（匹配结果）。
next 数组核心指针：在进行前缀指针回溯时，其底层逻辑永远锚定在寻找 “既是真前缀又是真后缀的子串” 的最长长度。

2. 主串中的子串数量统计

对于一个长度为 $n$ 的任意主串，其包含的子串总数计算公式为：

$\text{子串总数} = \frac{n(n+1)}{2} + 1$

⚠️ 408 避坑警示： Formula 中的 $+ 1$ 绝对不能漏掉，它代表算入了“空串”。考研真题中经常在此处挖坑，务必审清题目问的是“非空子串”还是“所有子串”。

三、内部排序大战场（稳定性、希尔分组与快/堆排杀招）

1. 排序算法的基本属性定理

稳定性（Stability）的本质：特指关键字相同的记录，其相对顺序在排序前后保持绝对不变。
直接插入排序的极限开销：对 $n$ 个完全不同的元素进行直接插入排序，在最坏情况下（即原序列完全逆序），累计最多需要的比较次数为：

$\text{Max Compare Count} = \frac{n(n-1)}{2}$

2. 希尔排序（Shell Sort）的步长分组逻辑

希尔排序的本质是“缩小增量排序”，其核心在于依据当前步长 $d$ 进行物理分组。

规则提炼：所谓分组，具体指的就是索引之间的差值等于步长 $d$ 。

📝 原理图解：以步长 $d = 4$ 为例

假设存在一个索引为 0 ~ 8 的待排序列，当步长设定为 $4$ 时，元素的分组情况如下：

 索引下标:  [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]
             │    │    │    │    │    │    │    │    │
 分组一(d=4): ⭕───────────────────⭕───────────────────⭕  --> (索引 0, 4, 8 是一组)
 分组二(d=4):      🔺───────────────────🔺             --> (索引 1, 5 是一组)
 分组三(d=4):           🟩───────────────────🟩        --> (索引 2, 6 是一组)
 分组四(d=4):                ⭐───────────────────⭐   --> (索引 3, 7 是一组)

3. 堆排序的初始化机制

💡 方法总结（分治精筛法）：
堆的初始化过程在底层采用的是**“分治精筛”的思想。具体表现为：建堆调整必须从 第 1 个非叶子结点 开始向前倒序筛选，即从最后（非叶子结点）** 向前执行下沉调整（SiftDown）。

补充数学线索：对于规模为 $n$ 的完全二叉树，第一个非叶子结点的物理编号为 $\lfloor n/2 \rfloor$ 。

4. 快速排序：第 $n$ 趟排序结果判断题型的“秒杀圣经”

❓ 经典真题型再现

典型题干：“以下四个序列中，不可能是快速排序第 $n$ 趟之后的排序结果的是？”

🚀 我的方法总结（整体筛选秒杀法）

快速排序（Quick Sort）每经历一趟划分，必定会有一个枢轴（Pivot）元素到达它在最终有序序列中的绝对绝对位置。因此，不需要盲目、机械地去模拟每一步划分，应当从整体宏观逻辑进行逆向排除：

$\text{若某一选项中：} \Big( \text{处于最终绝对位置的元素个数} \Big) < n \implies \text{该选项绝对不可能/错误}$

🛠️ 规范化作答解题 3 步走

第一步（列出终态）：拿到题目后，花 5 秒钟直接将原序列按从小到大排好序，得出最终标准序列。
第二步（位移对齐）：将 4 个选项逐一与最终标准序列进行垂直上下对齐，数出每个选项里有哪些元素的位置和最终序列是完全重合的。
第三步（卡死阈值）：如果题目问的是第 $n$ 趟的结果，那么选项中固定在最终位置上的元素数量必须 $\ge n$ 。如果对齐后发现数量 $< n$ ，说明该选项还没产生足够数量的枢轴，直接判定其为不可能的结果，一秒锁定制胜选项！