Appearance
附录 B · 高频考点 · 易错点 · 速查总表
本附录把七级五章的「考点总结表」聚合为一张总表，并补充跨章易错点与考前速查卡。 星级说明：⭐⭐⭐⭐⭐ 必考压轴；⭐⭐⭐⭐ 高频；⭐⭐⭐ 中频；⭐⭐ 了解。
一、五星考点 TOP 榜（必看必背）
| # | 考点 | 出处 | 一句话记忆 |
|---|---|---|---|
| 1 | 三角函数参数是弧度，不是角度 | 第 2 章 | sin(30) ≠ 0.5，要写 sin(30 * PI / 180) |
| 2 | log() 是自然对数 ln | 第 2 章 | 以 10 为底用 log10，以 2 为底用 log2 |
| 3 | pow() 返回 double | 第 2 章 | 不能当数组下标，需要 (int) 转换 |
| 4 | 浮点数比较必须用 eps | 第 2 章 | fabs(a - b) < 1e-9，不能 == |
| 5 | LIS 答案是 max(dp)，不是 dp[n-1] | 第 3 章 | 和最大子段和同理 |
| 6 | LCS 的 dp 下标与字符串下标差 1 | 第 3 章 | dp[i][j] 对应 A[i-1]、B[j-1] |
| 7 | 区间 DP 枚举顺序：先长度，后起点 | 第 3 章 | len 在外层，保证子区间已算好 |
| 8 | 滚动数组倒序覆盖 | 第 3 章 | 01 背包一维必须倒序，否则覆盖上一行数据 |
| 9 | 无向图邻接表每条边存两次，总和 = 2m | 第 4 章 | 空间 O(n + 2m) |
| 10 | 完全图边数 n(n−1)/2 | 第 4 章 | 有向完全图才是 n(n−1) |
| 11 | BFS 求最短路只对无权图成立 | 第 4 章 | 带权图要 Dijkstra（📚 超纲） |
| 12 | Flood Fill 的 visited 要入队时标记 | 第 5 章 | 出队时标记会重复入队 |
| 13 | 哈希冲突不可避免（鸽巢原理） | 第 6 章 | 只能"解决"不能"消除" |
| 14 | map 有序（红黑树），unordered_map 无序（哈希表） | 第 6 章 | 选择题最爱考这一对 |
二、逐章考点 · 易错点总表
1. 第 2 章 数学库函数
| 考点 | 星级 | 出题形式 | 易错点 |
|---|---|---|---|
| 三角函数用弧度制 | ⭐⭐⭐⭐⭐ | 判断/选择 | 参数是弧度不是角度 |
log() 是自然对数 | ⭐⭐⭐⭐⭐ | 判断/选择 | 底是 e 不是 10；log10 才以 10 为底 |
pow() 返回 double | ⭐⭐⭐⭐⭐ | 判断/选择 | 不是 int，不能直接当数组下标 |
sqrt() 开平方 | ⭐⭐⭐⭐ | 选择/编程 | 参数 ≥ 0；返回 double |
exp() = e 的 x 次方 | ⭐⭐⭐⭐ | 选择 | exp(1) = e ≈ 2.718 |
ceil / floor 取整 | ⭐⭐⭐⭐ | 选择 | 负数容易搞反方向 |
| 浮点数比较用 eps | ⭐⭐⭐⭐ | 判断 | 不能直接用 == |
abs vs fabs | ⭐⭐⭐ | 选择 | abs 用于 int，fabs 用于 double |
M_PI 常量 | ⭐⭐⭐ | 选择/编程 | 可能需要定义 _USE_MATH_DEFINES |
log2(x) 以 2 为底 | ⭐⭐⭐ | 选择 | 和 log(x) 区分开 |
2. 第 3 章 复杂动态规划
| 考点 | 星级 | 出题形式 | 易错点 |
|---|---|---|---|
| 二维 DP（网格路径） | ⭐⭐⭐⭐⭐ | 选择/编程 | 边界初始化、转移方程 |
| LIS 最长上升子序列 | ⭐⭐⭐⭐⭐ | 编程题/选择 | 答案是 max(dp) 不是 dp[n−1] |
| LCS 最长公共子序列 | ⭐⭐⭐⭐⭐ | 编程题/选择 | dp 下标和字符串下标差 1 |
| 区间 DP | ⭐⭐⭐⭐ | 选择/编程 | 枚举顺序：先长度后起点 |
| 滚动数组优化 | ⭐⭐⭐⭐ | 选择/判断 | 只能优化空间，不能优化时间 |
| 01 背包一维化 | ⭐⭐⭐⭐⭐ | 选择/判断/编程 | j 要逆序遍历 |
| 子序列 vs 子串 | ⭐⭐⭐⭐ | 选择/判断 | 子序列不连续，子串连续 |
| 记忆化搜索 | ⭐⭐⭐ | 选择/判断 | 和递推 DP 等价 |
| DP 最优子结构 | ⭐⭐⭐⭐ | 选择/判断 | 大问题最优解包含子问题最优解 |
| 重叠子问题 | ⭐⭐⭐ | 选择/判断 | 子问题被反复计算，适合 DP |
3. 第 4 章 图的定义及遍历
| 考点 | 星级 | 出题形式 | 易错点 |
|---|---|---|---|
| 图的基本概念（顶点、边、度） | ⭐⭐⭐⭐ | 选择/判断 | 有向图入度出度分开算 |
| 完全图边数计算 | ⭐⭐⭐⭐ | 选择/计算 | n(n−1)/2，别忘除以 2 |
| 邻接矩阵存储 | ⭐⭐⭐⭐⭐ | 选择/编程 | 空间 O(n²)，适合稠密图 |
| 邻接表存储 | ⭐⭐⭐⭐⭐ | 选择/编程 | 空间 O(n+m)，适合稀疏图 |
| 无向图邻接表边数 | ⭐⭐⭐⭐⭐ | 选择/判断 | 每条边存两次，总和 = 2m |
| DFS 深度优先搜索 | ⭐⭐⭐⭐⭐ | 编程题/选择 | 递归 + visited 标记 |
| BFS 广度优先搜索 | ⭐⭐⭐⭐⭐ | 编程题/选择 | 队列 + dist 距离数组 |
| BFS 求最短路径 | ⭐⭐⭐⭐⭐ | 选择/判断 | 只适用于无权图 |
| 连通分量 | ⭐⭐⭐⭐ | 编程题/选择 | 多次 DFS/BFS 计数 |
| DFS vs BFS 对比 | ⭐⭐⭐⭐ | 选择/判断 | 栈 vs 队列，适用场景 |
| visited 数组 | ⭐⭐⭐⭐⭐ | 代码填空/选择 | 防止重复访问 |
4. 第 5 章 泛洪算法
| 考点 | 星级 | 出题形式 | 易错点 |
|---|---|---|---|
| Flood Fill 基本思想 | ⭐⭐⭐⭐ | 选择/判断 | 种子点 + 连通区域扩散 |
| 方向数组 dx/dy | ⭐⭐⭐⭐⭐ | 代码填空/选择 | 四连通 vs 八连通，对应关系 |
| 边界检查 | ⭐⭐⭐⭐⭐ | 编程题/代码填空 | x>=0 && x<n && y>=0 && y<m |
| BFS 实现 Flood Fill | ⭐⭐⭐⭐⭐ | 编程题/选择 | 入队时就标记 visited |
| DFS 实现 Flood Fill | ⭐⭐⭐⭐ | 编程题/选择 | 递归深度大可能栈溢出 |
| BFS vs DFS | ⭐⭐⭐⭐ | 选择/判断 | 结果相同，实现方式不同 |
| 岛屿数量统计 | ⭐⭐⭐⭐⭐ | 编程题/选择 | 遍历 + Flood Fill + 计数 |
| 连通块大小 / 面积 | ⭐⭐⭐⭐⭐ | 编程题 | 每访问一个格子面积 +1 |
| 四连通 vs 八连通 | ⭐⭐⭐⭐ | 选择/判断 | 八连通多 4 个对角线方向 |
| 栈溢出问题 | ⭐⭐⭐⭐ | 选择/判断 | DFS 递归深度大可能溢出 |
| visited 数组标记时机 | ⭐⭐⭐⭐⭐ | 代码填空/选择 | 入队时标记，不是出队时 |
5. 第 6 章 哈希表
| 考点 | 星级 | 出题形式 | 易错点 |
|---|---|---|---|
| 哈希表基本概念 | ⭐⭐⭐⭐ | 选择/判断 | 理想 O(1)，最坏 O(n) |
| 哈希函数 | ⭐⭐⭐⭐ | 选择/判断 | 除留余数法最常用 |
| 哈希冲突必然性 | ⭐⭐⭐⭐⭐ | 选择/判断 | 鸽巢原理，不可避免 |
| 链地址法 | ⭐⭐⭐⭐⭐ | 选择/判断/编程 | 同一位置链表串联 |
| 开放寻址法（线性探测） | ⭐⭐⭐⭐⭐ | 选择/计算 | 二次聚集问题 |
| 再哈希法 | ⭐⭐⭐ | 选择/判断 | 多个哈希函数 |
| 装填因子 | ⭐⭐⭐⭐ | 选择/判断 | α = 元素数 / 表长 |
unordered_map / unordered_set | ⭐⭐⭐⭐⭐ | 编程题/选择 | 底层哈希表，无序 |
map vs unordered_map | ⭐⭐⭐⭐⭐ | 选择/判断 | 红黑树 vs 哈希表，有序 vs 无序 |
| Two Sum 经典应用 | ⭐⭐⭐⭐⭐ | 编程题 | 哈希表存已遍历元素 |
| 统计次数 / 去重 | ⭐⭐⭐⭐ | 编程题 | unordered_map 计数 / set 去重 |
| 开放寻址删除 | ⭐⭐⭐ | 选择/判断 | 不能直接删，要标记墓碑 |
三、选择题 / 判断题「陷阱」20 条
sin(x)的 x 是弧度——sin(30)求的不是 30°。log(x)= ln x；log10(x)才是以 10 为底——判断题最爱考。pow(2, 3)返回8.0（double），int a = pow(2,3)有精度风险。sqrt()参数不能为负（NaN）；返回 double。ceil(-1.2) = -1，floor(-1.2) = -2——负数方向别记反。abs(-3.7) = 3（int 版被截断），要fabs(-3.7) = 3.7。- 两个浮点数判断相等必须
fabs(a-b) < 1e-9。 - LIS 的
dp[i]定义为"以 i 结尾"，答案是全体最大值。 - LCS 的
dp数组多开一维，dp[i][j]对应A[i-1]与B[j-1]。 - 区间 DP 三层循环顺序是 len → i → k，写错顺序就全错。
- 滚动数组只降空间，时间复杂度不变。
- 01 背包一维化必须倒序，否则变成完全背包。
- 完全图边数：无向
n(n−1)/2，有向n(n−1)——分清楚。 - 无向图邻接表中每条边存两次，总长度 2m。
- 邻接矩阵适合稠密图（O(n²) 空间），邻接表适合稀疏图。
- BFS 求最短路只适用于无权图（或边权全相等）。
- Flood Fill 里
visited必须在入队时标记，否则同一格会入队多次。 - 八连通 = 四连通 + 4 个对角线方向（共 8 个邻居）。
- 哈希冲突不可避免，只能缓解——"好的哈希函数能消除冲突"是错的。
map是有序的（红黑树 O(log n)），unordered_map是无序的（哈希 O(1)）。
四、考前 30 分钟速查卡
【数学库】 sin/cos/tan 用弧度：角度 × PI / 180
log = ln，log10 = 以10为底，log2 = 以2为底
pow/sqrt/exp 均返回 double；abs(int) / fabs(double)
浮点比较：fabs(a-b) < 1e-9
ceil 向上（负数是往 0 方向）、floor 向下（负数是远离 0）
【二维DP】 状态 dp[i][j]；注意边界初始化
【LIS】 dp[i] = 以 i 结尾的最长长度；答案 = max(dp)
【LCS】 dp[i][j] 对应 A[i-1]、B[j-1]；答案 = dp[n][m]
【区间DP】 for len → for i → for k（分割点）
【滚动数组】只降空间不降时间；01 背包一维化必须倒序
【图】 无向完全图 n(n-1)/2；邻接矩阵 O(n²)、邻接表 O(n+m)
无向图邻接表每条边存两次，总 2m
DFS 递归+visited；BFS 队列+dist（无权图最短路）
【FloodFill】四连通 4 方向 / 八连通 8 方向
边界：x>=0 && x<n && y>=0 && y<m
visited 入队即标记；DFS 深了会栈溢出
【哈希】 冲突不可避免（鸽巢原理）
链地址法 / 开放寻址（线性探测有二次聚集）
装填因子 α = 元素数/表长
map 有序（红黑树）；unordered_map 无序（哈希表）
【考试】 单选 15×2 + 判断 10×2 + 编程 2×25 = 100 分，180 分钟本表由各章「考点总结表」聚合而成；若与正文冲突，以正文最新修订为准（见附录 E）。