01章块对照
教材常按线性表、栈队列、串、数组、树、图、查找、排序写。本站把查找树与散列拆开，方便演示挂钩。
| 408 / 严蔚敏块 | 本站全书 | 笔记时盯什么 |
|---|---|---|
| 绪论 · 复杂度 | 01 overview | ADT 三要素；平均必须带前提 |
| 线性表 | 02 list | 单链表改链要前驱 |
| 栈与队列 | 03 stackq | 循环队列空满约定 |
| 串 | 04 string | 设 1≤m≤n，朴素最坏 Θ((n−m+1)m)；next[1]=0 |
| 树与二叉树 | 05 tree · 06 bst | 非空 n0=n2+1；B 树根可为叶 |
| 图 | 07 graph | Dijkstra 非负；BF 仅源点可达负环 |
| 查找 / 散列 | 08 search · 09 hash | 折半要顺序表；二次探查 h+i² |
| 内排序 | 10 sort | 直接插入稳；建堆 O(n) |
严蔚敏章序→全书十章→演示核对数
02易混口径
链表删除
教材例题有时先给前驱再改链，看起来像 O(1)。答题默认：单链表按位定位 O(n)；已定位到相关前驱后，改链才 O(1)。只握待删结点不能默认 O(1)。
KMP 下标
严口径常见 1 下标、next[1]=0。模式 abaabc 的 next 是 0 1 1 2 2 3。不要和 nextval 混成一张未声明的表。
B / B+
m 阶 B 树：根若非叶至少 2 叉，非根内部结点至少 ⌈m/2⌉ 叉；非空单结点树的根可为叶。B+ 记录/数据只存叶，内部只存索引关键字，分隔关键字可在上层重复。
易错：「插入排序都稳定」不对——直接插入稳定，希尔不稳。快排平均 O(n log n) 必须带随机输入/随机枢轴前提，最坏仍是 Θ(n²)。冒泡在相等不换的标准实现下是稳定的。
章末自测
不能逐字替换。本站把查找树与散列拆开，方便挂钩 AVL 与探查演示。知识块没有超出 408。
问有没有前驱、是单链还是双链。单链表默认不成立。
不要。红黑只考近似平衡概念。证明细节在 CLRS 笔记里标超纲。