95 个考点按讲次编排，含 S/A/B 分级与老师原话证据
考点总表
课程：NUAA-ADS2026（Advanced Data Structures and Algorithm Analysis）
生成依据：4 份 PPT 文本（ads 八讲）+ 4 份纪要 + 4 份逐字稿（304 KB）
证据标注约定：[PPT:文件名:行号] = PPT 文本行号；[纪要:n] = n-conclusion.md；[稿:文件:行号] = 逐字稿行号
重要度定义
| 级别 |
含义 |
判据 |
| S |
必考 / 课堂明确强调 / 正答率极低处 |
逐字稿有"经常会考""考试"等原话，或正答率<30% |
| A |
高概率考（PPT 有 Definition/Theorem/Lemma 或完整 Example） |
PPT 有正式定义/定理/证明 |
| B |
理解性考点（背景、动机、工程取舍） |
仅出现在 PPT 正文或项目要求中 |
一、按讲次的考点清单
第 1 讲（上）— AVL Trees, Splay Trees, and Amortized Analysis
证据：PPT_文本/ADS/第一讲（上）AVL Trees, Splay Trees, and Amortized Analysis.txt（640 行）
| 编号 |
考点 |
级 |
证据 |
预测题型 |
| 1.1.1 |
BST 退化问题：Tp=O(height)，height 可退化到 O(N) |
B |
[PPT:1上:20] 正文；[稿:1-逐字稿:122] 好学生陷阱 |
选择/简答 |
| 1.1.2 |
AVL 定义与平衡因子 BF=hL−hR∈{−1,0,1} |
S |
[PPT:1上:49,57] 【Definition】×2 |
判断/选择 |
| 1.1.3 |
AVL 高度上界 h ≤ 1.44 log₂N，最少节点 N(h)=N(h−1)+N(h−2)+1 |
A |
[PPT:1上:49-60] 斐波那契递推 |
计算/证明 |
| 1.1.4 |
四种旋转 LL/RR/LR/RL 的判定与执行顺序 |
S |
[PPT:1上:66] 【Example】Mar/May/Nov RR |
画树大题 必考 |
| 1.1.5 |
插入/删除后的旋转修复；删除可能需多次旋转 |
A |
[PPT:1上] 正文 |
画树 |
| 1.1.6 |
Splay Tree：访问即旋转至根 |
A |
[PPT:1上:581] |
画树/简答 |
| 1.1.7 |
zig / zig-zig / zig-zag 三种情形 |
S |
[PPT:1上:581] |
画树 必考 |
| 1.1.8 |
为何必须双旋：单旋退化为 O(N) |
S |
[纪要:1-conclusion] 双旋优化；[稿:2-逐字稿:119] |
简答/证明 |
| 1.1.9 |
摊还分析三法：聚合分析 / 记账法 / 势能法 |
S |
[PPT:1上:514,560] MultiPop 例 |
证明题 |
| 1.1.10 |
势能法 Φ=Σlog(size)，splay 摊还 O(log N) |
A |
[PPT:1上:581] |
证明 |
| 1.1.11 |
MultiPop 栈：单次 O(N) 但摊还 O(1) |
A |
[PPT:1上:514,560] 两次【Example】 |
计算/证明 |
| 1.1.12 |
摊还复杂度 ≠ 每次最坏复杂度 |
S |
[纪要:1-conclusion] 明示区分 |
判断（高频陷阱） |
第 1 讲（下）— Red-Black Trees and B+ Trees
证据：PPT_文本/ADS/第一讲（下）Red-Black Trees and B+ Trees.txt（299 行）
| 编号 |
考点 |
级 |
证据 |
预测题型 |
| 1.2.1 |
红黑树五条性质（根黑/NIL黑/红子必黑/黑高相等/节点非红即黑） |
S |
[PPT:1下:15] 【Definition】 |
判断/选择 必考 |
| 1.2.2 |
black-height bh(x) 定义与计算 |
A |
[PPT:1下:31] 【Definition】 |
填空/计算 |
| 1.2.3 |
引理：size(x) ≥ 2^bh(x)−1，归纳证明 |
A |
[PPT:1下:36] 【Lemma】 |
证明 |
| 1.2.4 |
树高 h ≤ 2 log₂(N+1) 的完整证明链 |
S |
[PPT:1下:36] 证明分两步 |
证明题 高频 |
| 1.2.5 |
插入：默认染红 + Case 1/2/3（叔红变色 / 叔黑旋转） |
S |
[PPT:1下:50+] Case 1/2 |
画树 必考 |
| 1.2.6 |
插入口诀 "swap colors and rotate" |
S |
[稿:1-逐字稿:437] 老师原话"记住一个口诀" |
简答 |
| 1.2.7 |
删除修复：最多 3 次旋转 |
S |
[PPT:1下] 对比表 O(logN)/≤3 |
选择/简答 |
| 1.2.8 |
红黑树 vs AVL：旋转次数、parent 指针开销、随机数据实测更快 |
S |
[稿:1-逐字稿:470] 老师大段论述 |
简答 高频 |
| 1.2.9 |
大型系统不做删除 → 红黑树的绝对优势消失 |
B |
[稿:1-逐字稿:470] |
简答 |
| 1.2.10 |
B+ 树 M 阶结构：内部只存索引、数据全在叶子、叶子链表 |
S |
[PPT:1下] For a general B+ tree of order M |
判断/选择 |
| 1.2.11 |
键值数上下界 ⌈M/2⌉−1 ~ M−1（与 M 的换算） |
S |
[PPT:1下] |
计算 高频易错 |
| 1.2.12 |
插入分裂：溢出→分裂→可能上传致树高 +1 |
A |
[PPT:1下] |
画树 |
| 1.2.13 |
B+ 树的磁盘 I/O 优势与分裂开销权衡 |
B |
[纪要:1-conclusion] 三、 |
简答 |
| 1.2.14 |
为何 NIL 是黑的（内部叶子可以是红的） |
A |
[稿:1-逐字稿:422] 课堂问答 |
判断 |
第 2 讲（上）— Backtracking
证据：PPT_文本/ADS/第二讲（上）Backtracking.txt（312 行）
| 编号 |
考点 |
级 |
证据 |
预测题型 |
| 2.1.1 |
回溯 = 解空间树 + DFS + 剪枝函数 |
A |
[PPT:2上] Rationale |
简答 |
| 2.1.2 |
解空间树构造（子集树 / 排列树） |
A |
[PPT:2上] Eight Queens |
画图 |
| 2.1.3 |
约束函数 vs 限界函数 |
A |
[PPT:2上] Constrains |
选择 |
| 2.1.4 |
N 皇后（4 皇后为例）完整求解 |
A |
[PPT:2上] Step 1 |
画树 |
| 2.1.5 |
搜索顺序优化：最大距离优先（端点确定→砍半棵树） |
S |
[纪要:2-conclusion] 一、1 |
简答 偏理论 |
| 2.1.6 |
Minimax + 博弈树 |
A |
[PPT:2上] Tic-tac-toe |
画图 |
| 2.1.7 |
Alpha-Beta 剪枝：规则与剪枝条件 α≥β |
S |
[稿:2-逐字稿:98] "考试的时候经常会考" |
计算/画树 必考 |
| 2.1.8 |
评估函数必须廉价 |
A |
[纪要:2-conclusion] 一、2 |
简答 |
| 2.1.9 |
剪枝不改变最坏复杂度，只改实际运行时间 |
S |
[纪要:2-conclusion] 一、2 |
判断 |
| 2.1.10 |
Turnpike Reconstruction / 重构问题 |
B |
[PPT:2上] |
了解 |
| 2.1.11 |
AlphaGo 与剪枝的关系 |
B |
[PPT:2上] Games |
背景 |
第 2 讲（下）— Divide and Conquer
证据：PPT_文本/ADS/第二讲（下）Divide and Conquer.txt（348 行）
| 编号 |
考点 |
级 |
证据 |
预测题型 |
| 2.2.1 |
三步 Divide/Conquer/Combine |
A |
[纪要:2-conclusion] 二、1 |
简答 |
| 2.2.2 |
子问题必须独立 + 可合并；否则不能用分治 |
S |
[稿:2-逐字稿:170] 老师留的讨论题 |
判断/简答 |
| 2.2.3 |
归并排序偏 Combine，快排偏 Divide |
A |
[稿:2-逐字稿:140] 老师原话 |
简答 |
| 2.2.4 |
分治不必然 O(N log N)（tree traversal 为 O(N)） |
S |
[稿:2-逐字稿:140] "不要一看到分治就想到 N log N" |
判断 |
| 2.2.5 |
代入法：先猜后用数学归纳法证明 |
A |
[PPT:2下:126,151] 【Example】 |
证明 |
| 2.2.6 |
T(N)=T(N/3)+T(2N/3)+cN 非完美递归树 → 猜 O(N log N) |
S |
[PPT:2下:205] 【Example】完整证明 |
证明 高频 |
| 2.2.7 |
主定理三种情况 + 正则条件 |
S |
[PPT:2下:226,296] 【Master Theorem】×2 |
计算 必考 |
| 2.2.8 |
主定理另一形式（N^p log^k N） |
A |
[PPT:2下:313] 【Theorem】 |
计算 |
| 2.2.9 |
主定理适用形状限制（必须 N^p log^k N 形） |
S |
[稿:2-逐字稿:167] "形状太特殊了" |
判断 |
| 2.2.10 |
K 路归并：K 为常数 vs K 为变量 |
S |
[纪要:2-conclusion] 三、；[稿:3-逐字稿:23] 正答率最低题 |
计算/简答 必考 |
| 2.2.11 |
堆优化 K 路归并 O(N log K)，总 O(N log N) 与 K 无关 |
S |
[纪要:2-conclusion] 三、2 |
计算 |
| 2.2.12 |
K=N 退化为选择排序（无堆）/ 堆排序（有堆） |
S |
[纪要:2-conclusion] 三、2 |
选择 易错 |
| 2.2.13 |
最近点对：Combine 步若 O(N²) 则整体退化 |
A |
[稿:2-逐字稿:140] 整例为此 |
简答 |
| 2.2.14 |
分治的重点是"复杂度分析"而非实现 |
B |
[稿:2-逐字稿:170] |
策略 |
第 3 讲（上）— Dynamic Programming
证据：PPT_文本/ADS/第三讲（上）Dynamic Programming.txt（387 行）
| 编号 |
考点 |
级 |
证据 |
预测题型 |
| 3.1.1 |
DP 本质："用表代替递归"，消除重叠子问题 |
S |
[纪要:3-conclusion] 二、1 |
简答 必考 |
| 3.1.2 |
最优子结构 + 重叠子问题（对比分治） |
S |
[纪要:3-conclusion] 二、1 |
判断/简答 |
| 3.1.3 |
矩阵链乘：枚举切分点、填表顺序 |
A |
[PPT:3上:50] 【Example】4 矩阵 |
填表计算 |
| 3.1.4 |
最优二叉搜索树 OBST：Tij/rij 递推 |
A |
[PPT:3上:132] 【Example】 |
填表 |
| 3.1.5 |
Floyd 三层循环：k 必须在最外层 |
S |
[纪要:3-conclusion] 二、2；[稿:3-逐字稿:119] 正答率 2x% |
判断/反例 必考 |
| 3.1.6 |
为何 k 不能在内层：反例构造 |
S |
[纪要:3-conclusion] 二、2 反例举证 |
反例构造 必考 |
| 3.1.7 |
前驱矩阵恢复路径同样要求 k 在外层 |
A |
[纪要:3-conclusion] 二、2 工程补充 |
简答 |
| 3.1.8 |
0-1 背包 DP（整数重量限制） |
S |
PTA HW3 题 03；[纪要:3-conclusion] 四 |
编程/填表 |
| 3.1.9 |
DP 的复杂度与"数值大小"成正比 → 非多项式（参数陷阱） |
S |
[纪要:4-conclusion] 二、2 |
判断 易错 |
| 3.1.10 |
加权活动安排只能 DP，贪心失效 |
S |
[稿:3-逐字稿:275] "这是个坑，这个公式其实是错的" |
判断 |
第 3 讲（下）— Greedy
证据：PPT_文本/ADS/第三讲（下）Greedy.txt（409 行）
| 编号 |
考点 |
级 |
证据 |
预测题型 |
| 3.2.1 |
贪心 = 局部最优 → 需证明可达全局最优 |
A |
[纪要:3-conclusion] 三、1 |
简答 |
| 3.2.2 |
交换论证 / 安全选择的证明框架 |
S |
[纪要:3-conclusion] 三、1 |
证明 必考 |
| 3.2.3 |
活动安排（区间调度）：按结束时间贪心 |
S |
[PPT:3下:150] 【Theorem】 |
计算/证明 |
| 3.2.4 |
最少教室问题：教室数 = 最大重叠数 |
S |
[纪要:3-conclusion] 三、2 |
计算/简答 必考 |
| 3.2.5 |
反例：先排满一间教室的"复用轮子"策略非最优 |
S |
[纪要:3-conclusion] 三、2 策略一 |
反例构造 |
| 3.2.6 |
Huffman：频率最高的两个字符在最底层 |
A |
[PPT:3下:363,383] 【Lemma】×2 |
证明 |
| 3.2.7 |
Huffman 交换论证证明 |
A |
[稿:3-逐字稿:284] "难在证明上" |
证明 |
| 3.2.8 |
Huffman 编码构造与 WPL 计算 |
A |
[PPT:3下:203] 【Example】1000 字符 |
计算 |
| 3.2.9 |
贪心 vs DP 的边界（可否加权） |
S |
[稿:3-逐字稿:275] |
判断 |
第 4 讲（上）— NP-Completeness
证据：PPT_文本/ADS/第四讲（上）NP-Completeness.txt（424 行）
| 编号 |
考点 |
级 |
证据 |
预测题型 |
| 4.1.1 |
P / NP / NPC / NP-hard 四个类的定义与包含关系 |
S |
[纪要:4-conclusion] 一、1 |
选择/判断 必考 |
| 4.1.2 |
NP-hard 不一定在 NP 内 |
S |
[纪要:4-conclusion] 一、1 |
判断 易错 |
| 4.1.3 |
归约方向：A ≤p B ⇒ B 不比 A 易 |
S |
[纪要:4-conclusion] 一、1 |
选择 历年高频错点 |
| 4.1.4 |
多项式时间归约的形式定义 |
A |
[PPT:4上:325] For SAT |
简答 |
| 4.1.5 |
优化问题 → 判定问题（引入 K） |
S |
[纪要:4-conclusion] 一、2 |
简答 必考 |
| 4.1.6 |
归约比较必须在判定问题层面进行 |
S |
[纪要:4-conclusion] 一、2 |
判断 |
| 4.1.7 |
停机问题不可判定 |
B |
[PPT:4上:48] 【Example】 |
选择 |
| 4.1.8 |
哈密顿回路问题 |
A |
[PPT:4上:157,217] 【Example】×2 |
简答 |
| 4.1.9 |
SAT → 3-SAT 归约 |
A |
[PPT:4上:325] |
简答 |
| 4.1.10 |
团问题（clique）归约 |
A |
[PPT:4上:377] 【Example】 |
简答 |
| 4.1.11 |
最短路径 vs 最长路径：为何前者在 P 内 |
A |
[PPT:4上:263] For SHORTEST-PATH |
简答 |
| 4.1.12 |
证明某问题为 NPC 的标准三步法 |
S |
综合 |
证明 必考 |
第 4 讲（下）— Approximation
证据：PPT_文本/ADS/第四讲（下）Approximation.txt（487 行）
| 编号 |
考点 |
级 |
证据 |
预测题型 |
| 4.2.1 |
近似比 ρ(n) 的定义：max(C/C, C/C) ≤ ρ(n) |
S |
[PPT:4下:29] 【Definition】 |
填空/简答 必考 |
| 4.2.2 |
近似算法 vs 启发式（能否证明上界） |
S |
[纪要:4-conclusion] 二、1；[稿:3-逐字稿:248] |
判断 易错 |
| 4.2.3 |
PTAS vs FPTAS 的复杂度差异 |
S |
[PPT:4下:38] O(n²/ε) vs O((1/ε)²n³) |
选择 必考 |
| 4.2.4 |
参数陷阱：复杂度与数值成正比即指数级 |
S |
[纪要:4-conclusion] 二、2 |
判断 易错 |
| 4.2.5 |
装箱问题：Next Fit ≤ 2M−1 及紧例 |
S |
[PPT:4下:82] 【Theorem】+ 证明 |
证明 必考 |
| 4.2.6 |
Next Fit 在 Si<1/2 时近似比 1/(1−α) |
S |
[纪要:4-conclusion] 三、1 A 选项证明 |
证明 低频正答率 |
| 4.2.7 |
α=1/2 是 1/(1−α) 与常数 2 的分界点 |
S |
[纪要:4-conclusion] 三、1 |
选择 必考 |
| 4.2.8 |
FFD 近似比 = 3/2 及其证明 |
S |
[PPT:4下:128] 【Theorem】；[纪要:4-conclusion] 三、2 |
证明 必考 |
| 4.2.9 |
1.5 的最优性：反证 + P=NP |
S |
[纪要:4-conclusion] 三、2 反证法 |
证明 必考 |
| 4.2.10 |
First Fit 近似比 17/10 |
A |
[PPT:4下] 正文 |
记忆 |
| 4.2.11 |
K-center 问题及 2-近似 |
A |
[PPT:4下:395,434] 【Theorem】×2 |
简答 |
| 4.2.12 |
除非 P=NP，不存在 ρ<... 的近似（下界定理） |
A |
[PPT:4下:443] 【Theorem】 |
简答 |
| 4.2.13 |
算法设计三目标：全实例最优 / 特殊实例最优 / 全实例快速有保证 |
S |
[纪要:4-conclusion] 四、1 |
简答 课程总结题 |
二、统计
| 讲次 |
考点数 |
S |
A |
B |
| 1上 AVL/Splay/摊还 |
12 |
6 |
5 |
1 |
| 1下 红黑树/B+树 |
14 |
8 |
4 |
2 |
| 2上 回溯 |
11 |
3 |
6 |
2 |
| 2下 分治 |
14 |
8 |
5 |
1 |
| 3上 DP |
10 |
7 |
3 |
0 |
| 3下 贪心 |
9 |
5 |
4 |
0 |
| 4上 NPC |
12 |
6 |
5 |
1 |
| 4下 近似 |
13 |
10 |
3 |
0 |
| 合计 |
95 |
53 |
35 |
7 |
S 级 53 个 → 按"每 S 级 ≥5 题"要求，题库至少需 265 题。
A 级 35 个 × 3 = 105，B 级 7 个 × 2 = 14 ⟹ 全量三档下限 384 题。
三、老师原话级 S 级证据（最高优先级，必须命中）
| 原话 |
出处 |
对应考点 |
| "考试的时候经常会考，但是记也挺好记的" |
[稿:2-逐字稿:98] 讲 Alpha-Beta |
2.1.7 |
| "正答率最低的那道题…k 路归并，k 到底怎么样会影响时间复杂度" |
[稿:3-逐字稿:23] |
2.2.10 / 2.2.12 |
| "正答率非常低…动态规划的计算顺序，kij 这个三重顺序是不能打乱的，打乱以后就会全错" |
[稿:3-逐字稿:119] |
3.1.5 / 3.1.6 |
| "红黑树所有操作，记住一个口诀 swap colors and rotate" |
[稿:1-逐字稿:437] |
1.2.6 |
| "红黑树的绝对优势是在 deletion，最多三次旋转；AVL 是 O(log N) 次" |
[稿:1-逐字稿:470] |
1.2.7 / 1.2.8 |
| "这是个坑，这个公式其实是错的，这个地方得是权重" |
[稿:3-逐字稿:275] |
3.1.10 |
| "不要一看到分治，马上就想到一定 N log N" |
[稿:2-逐字稿:140] |
2.2.4 |
| "主定理…它和函数的形状太特殊了，一定要是这种形式才能套结论" |
[稿:2-逐字稿:167] |
2.2.9 |
| "期末卷面 40 分是潜在的斩杀线" |
[稿:1-逐字稿:26,29] |
复习策略 |
| "至少 30% 有效注释，否则 0 分" |
[稿:1-逐字稿:77] |
Project |
十道送命题、易混概念对照、必背公式
高频易错清单
全部条目均来自课堂实证信号：老师原话、正答率数据、PPT 正式定理。
标注 ★ = 老师在课上明确说会考 / 或实测正答率 <30%（最低一档）。
一、十道"送命题"（老师亲口 / 正答率最低）
| # |
问题 |
正确答案要点 |
为什么错 |
| 1 ★ |
Floyd 三层循环，k 能放内层吗？ |
不能。k 必须在最外层。 若 k 内层，d[i][j] 可能未经 k−1 阶段优化就被"用掉"，反例可构造；且前驱矩阵更新失效 |
老师原话："kij 三重顺序不能打乱，打乱以后就会全错"。考试实测正答率 ~20% |
| 2 ★ |
K 路归并，K 变大时间复杂度变吗？ |
取决于 K 是常数还是变量。 K 为常数：O(N log N) 不变（log_k N 与 log₂N 差常数因子）。K 为变量且线性扫描找最小：O(KN log_k N)；用堆优化：O(N log N)，K 被抵消 |
课堂实测正答率最低。K=N 无堆 → 选择排序 O(N²)；有堆 → 堆排序 O(N log N) |
| 3 ★ |
Alpha-Beta 剪枝发生在什么条件？ |
Min 层：当前值 ≤ α → 剪（父 Max 已能拿到更好）；Max 层：当前值 ≥ β → 剪。等价说法：α ≥ β 时剪枝。剪枝不改最坏复杂度 |
老师说"考试的时候经常会考"，规则易记但方向常配反 |
| 4 ★ |
红黑树的绝对优势在哪？ |
在删除（deletion）。AVL 删除最坏需 O(log N) 次旋转；红黑树删除最多 3 次旋转。插入方面优势不大（都要 ≤2 次旋转），且红黑树多了 parent 指针开销 |
多数人误答"插入更快"。老师原话："它的绝对优势是在 deletion 方面" |
| 5 ★ |
摊还复杂度是平均复杂度吗？ |
不是。 摊还 = 最坏情况操作序列的总代价 ÷ 操作次数上限，是保证；平均复杂度需对输入分布做概率假设。Splay 单次可 O(N)，但 M 次操作总代价 O(M log N) |
PPT 用"摊还"专指 amortized，与 average-case 严格区分。判断题陷阱 |
| 6 |
红黑树是 AVL 树的特例吗？ |
不是。 二者是并列的不同平衡策略：AVL 严格平衡（ |
BF |
| 7 |
NP-hard 一定属于 NP 吗？ |
不一定。 NP-hard 只要求"所有 NP 问题都能归约到它"，它本身可以不可判定（如停机问题） |
老师说"NP-hard 难度不低于 NPC，但可能根本不在 NP 内" |
| 8 ★ |
若 A 可归约到 B（A ≤p B），谁更难？ |
B 更难（或至少一样难）。 解决 B 就能解决 A |
归约方向是历年高频错点，极易说反 |
| 9 ★ |
复杂度与"数值大小"成正比，是多项式算法吗？ |
不是。 如 O(n·Pmax)，Pmax 是数值不是输入规模 → 实际是指数级（二进制编码下）。这就是背包 DP 是伪多项式的根本原因 |
老师说"参数非多项式常数"。判断题必设陷阱 |
| 10 ★ |
α = 1/2 在装箱 Next Fit 分析里是什么？ |
分界点。 Si < 1/2 时近似比上界 1/(1−α)；α=1/2 时 1/(1−α)=2，与常数界 2 重合。若假设 ρ=2α，当 α<0.5 会得 ρ<1（近似解优于最优解），逻辑不可能 |
课堂讨论原题；选项 D 的经典错误 |
二、易混概念对照表（判断题高危区）
| 易混对 |
区别 |
记忆钩子 |
| 摊还 amortized / 平均 average |
摊还是最坏序列的均摊保证；平均依赖输入分布 |
摊还 = "最坏情况下的平均" |
| AVL / 红黑树 |
严格 vs 弱平衡；旋转次数 vs 树高 |
AVL h≤1.44log n；RB h≤2log(n+1) |
| B 树 / B+ 树 |
B 树每个节点都存数据；B+ 树数据全在叶子、内部只存索引、叶子有链 |
"+"= 多一条叶子链 |
| PTAS / FPTAS |
PTAS 对 n 多项式、对 1/ε 可指数；FPTAS 对 n 和 1/ε 都多项式 |
F = Fully = 连 1/ε 也管住 |
| P / NP / NPC / NP-hard |
P⊆NP；NPC = NP∩NP-hard；NP-hard 可不在 NP |
归约是"从易到难"画箭头 |
| 判定问题 / 优化问题 |
归约与难度比较必须在判定层面做 |
先改"是否≤K"，再谈难度 |
| 近似算法 / 启发式 |
近似算法能证明 ρ 上界；启发式不能 |
不能证明 = 只是"随便试试" |
| 剪枝 / 降低复杂度 |
剪枝只降实际运行时间，不改最坏复杂度 |
"剪枝不改 Big-O" |
| 分治 / DP |
子问题独立 vs 子问题重叠 |
重叠就得存表 |
| 贪心 / DP |
贪心需证贪心选择性质；加权后通常只能 DP |
有权重 → 想 DP |
| 树高 h / 黑高 bh |
黑高只数黑节点，且不含起点 |
bh ≤ h/2 |
| Splay 单旋 / 双旋 |
单旋逐层上提遇长链退化 O(N)；双旋（zig-zig/zag）使路径深度减半 |
"必须双旋" |
三、必须能手算/手画的动作（考试大题主力）
| 动作 |
出处考点 |
易错点 |
| 给插入序列 → 画 AVL 树并标平衡因子 |
1.1.4 |
LR/RL 的方向顺序：先转子节点，再转失衡点 |
| 给访问序列 → 画 Splay 每步形态 |
1.1.7 |
zig-zig 是先转祖父、再转父（不是连续两次单旋） |
| 给插入序列 → 画红黑树并标色 |
1.2.5 |
新节点先染红；叔红 → 变色上推（可能传到根，根强制黑） |
| 算红黑树某节点 black-height |
1.2.2 |
bh 不含起点自身；NIL 算黑且计入 |
| 给 M 阶 B+ 树插入 → 画分裂过程 |
1.2.11 |
键数上限 M−1、下限 ⌈M/2⌉−1；分裂中间键上移 |
| 给博弈树 → 标 Alpha-Beta 剪枝点 |
2.1.7 |
剪枝后不计算被剪子树的值 |
| 递归式 → 主定理判情况 |
2.2.7 |
先算 log_b a，再与 f(n) 比较；case 3 需查正则条件 af(n/b) ≤ cf(n) |
| 矩阵链 / OBST / 背包 → 填 DP 表 |
3.1.3/3.1.4/3.1.8 |
填表顺序必须按子问题规模递增 |
| Floyd → 逐轮更新 D 矩阵 |
3.1.5 |
k 外层；每轮 k 只允许经过节点集 {1..k} |
| 区间 → 求最少教室数 |
3.2.4 |
= 时间轴上最大重叠数（扫描线） |
| Huffman → 建树并算 WPL |
3.2.8 |
每次取两个最小合并，新节点回插 |
| 装箱 → Next Fit / FFD 装填并算近似比 |
4.2.5/4.2.8 |
Next Fit 只回看当前箱；FFD 先降序再 First Fit |
四、必背公式与界限
| 结论 |
公式 |
| AVL 高度上界 |
h ≤ 1.44 log₂ N |
| AVL 最少节点数 |
N(h) = N(h−1) + N(h−2) + 1，N(0)=1, N(1)=2 |
| 红黑树树高 |
h ≤ 2 log₂(N+1) |
| 红黑树子树规模 |
size(x) ≥ 2^bh(x) − 1 |
| 主定理 Case1/2/3 |
比较 f(N) 与 N^(log_b a)：小→Θ(N^log_b a)；等→Θ(N^log_b a · log N)；大→Θ(f(N)) |
| splay 摊还 |
单次 O(log N) 摊还；M 次共 O(M log N) |
| Next Fit |
≤ 2M − 1；Si<1/2 时 ≤ 1/(1−α)·M* |
| First Fit |
≤ 17/10 · M* |
| FFD |
≤ 3/2 · M* |
| 近似比定义 |
max(C/C, C/C) ≤ ρ(n) |
| PTAS / FPTAS |
PTAS: O(n^{f(1/ε)})；FPTAS: poly(n, 1/ε) |
五、Project / 平时分相关的"非知识"要点
- 期末卷面 必须 ≥40 分，否则总评直接不及格（平时满分也救不了）
- 平时分 50% = 分组讨论 10% + 作业 5% + Research Project 25%；期末 50%
- Project 代码 有效注释 ≥30%，否则 0 分
- 复杂度分析必须给推导过程，不能只写结论
- 禁止把源码直接贴进报告，须用伪代码 / 流程图 + 文字说明
- 提交后要下载回来验证文件完整性