11 判断 / 选择 / 填空专项与高频陷阱

本章把题库里全部 45 道判断题、12 道选择题、5 道填空题做成"速查速记表"，每条给出答案 + 一句话理由，陷阱用 ⚠️ 标出。深入原理见各专题文档，本章用于考前快速过一遍、把确定分拿满。

判断题是本课最稳的分，且各年高度重复。建议把下面的表反复默背到"看题面就知道对错和理由"。

---

一、判断题速记（第 1～45 条，按知识点分组）

题型说明：在正确陈述前打 √、错误的打 ×。措辞差异本身常是考点（同一知识点换个说法答案可能就变），务必逐条看清。

1.1 渐进记号与复杂度（详见 01）

#	题面（简记）	答案	一句话理由
1	$f(n)=O(f(n))$	✓	大 O 自反，取 $c=1$
2	$O(f)+O(g)=O(max\{f,g\})$	✓	和的阶由大者定
3	$O(f)+O(g)=O(min\{f,g\})$	✗	⚠️ 应取 $max$ 不是 $min$
4	$f=\mathrm{\Omega }(g),g=\mathrm{\Omega }(h)\Rightarrow f=\mathrm{\Omega }(h)$	✓	$\mathrm{\Omega }$ 传递
5	$f=O(g)\Rightarrow g=\mathrm{\Omega }(f)$	✓	$O$ 与 $\mathrm{\Omega }$ 对偶
6	$f=\mathrm{\Omega }(g)\Rightarrow g=\mathrm{\Omega }(f)$	✗	⚠️ 应是 $g=O(f)$，方向反了
7	$max(f,g)=\mathrm{\Theta }(f+g)$	✓	非负函数下同阶
8	$2^{n+1}=O(2^n)$ 且 $2^n=O(2^{2n})$	✓	指数 $+1$ 只差常数倍
9	$2^{n+1}=O(2^n)$ 且 $2^{2n}=O(2^n)$	✗	⚠️ $2^{2n}=4^n$，比值 $\to \mathrm{\infty }$
10	算法复杂度 $f(n)\Rightarrow C(p)\le f(n)$	✓	一个算法给一个上界
11	最坏情况比平均情况易算	✓	平均要对分布求期望

1.2 排序与查找下界（详见 01、08）

#	题面（简记）	答案	一句话理由
12	合并排序使用了分治策略	✓	二分 + 合并
13	（确定性）快排 worst case 出现于输入已按非降序排列	✓	取首/尾为枢轴，已序退化 $O(n^2)$
14	随机化快排 worst case 出现于输入已按非降序	✗	⚠️ 随机选枢轴后与具体输入无关
15	随机化快排能把平均复杂度降得更低	✗	⚠️ 仍是 $O(n\log n)$，只消除对输入依赖
16	比较排序下界是 $0.5n\log n$	✓	即 $\mathrm{\Omega }(n\log n)$，合法下界
17	找最大与最小值的下界是 $n/2$	✓	合法（非紧）下界，紧下界 $\lceil 3n/2\rceil -2$
18	找最大值的下界是 $\mathrm{\Omega }(n/3)$	✗	⚠️ 找最大需 $n-1$ 次，紧下界 $\mathrm{\Omega }(n)$
19	找最小值的下界是 $\mathrm{\Omega }(n/2)$	✓	合法下界

1.3 算法策略概念（详见 00、04、05、06）

#	题面（简记）	答案	一句话理由
20	回溯法用深度优先搜索状态空间树	✓	回溯本质即 DFS
21	回溯法用深度优先或广度优先搜索	✗	⚠️ 仅 DFS；BFS 式属分支限界
22	回溯法用深度优先或广度优先搜索	✗	⚠️ 同上，仅 DFS
23	动态规划通过增加空间复杂性来降低时间复杂性	✓	以表存子问题解，空间换时间
24	DP 中各阶段所定策略构成的序列称为"决策"	✗	⚠️ 该序列应称"策略"，单阶段选择才叫"决策"
25	贪心每步产生的部分解不一定是可行的	✗	⚠️ 贪心每步在可行范围内选，部分解保持可行
26	贪心通过增加空间复杂性来减少时间复杂性	✗	⚠️ "空间换时间"是 DP 的特征，不是贪心
27	经典贪心每步选择可基于局部信息也可基于全局信息	✓	按 merged 答案键
28	正确算法对每个合法输入都在有限时间内输出满足要求的结果	✓	正确性 + 有限性

1.4 概率算法（详见 07）

#	题面（简记）	答案	一句话理由
29	拉斯维加斯有时不能给解，但给出就正确	✓	Las Vegas 的定义
30	Las Vegas 只要给解就正确	✓	同上
31	Monte Carlo 有时不给解，但给出就正确	✗	⚠️ 这是 LV 的性质；MC 总给解但可能错

1.5 P / NP 理论（高频陷阱区，详见 09）

#	题面（简记）	答案	一句话理由
32	所有问题中最难的一组是 NP 完备问题	✗	⚠️ NP 内最难，非"所有问题"中最难
33	NP 完全问题比其它所有 NP 问题都难	✗	⚠️ NP 完全彼此等难，只是"至少一样难"
34	NP 完备是所有 NP 中最难、且未找到多项式算法	✗	⚠️ 症结在"比所有都难"；等难
35	"$P\subset NP$ 表示"是错误的	⚠️	见 09 解析（$P\subseteq NP$ 已知，真包含未证）
36	P 与 NP 不可以用 $P\subset NP$ 表示	✓	按 merged 答案键
37	若一个问题是 NP 问题，则它一定不是 P 问题	✗	⚠️ $P\subseteq NP$，P 也是 NP
38	若一个问题不是 NP 问题，则它可能是 P 问题	✗	⚠️ 非 NP $\Rightarrow$ 非 P
39	P 是易解的、NP 是易验证的	✓	标准直观刻画
40	$P_2$ 多项式转化为 $P_1$，则 $P_2$ 至少与 $P_1$ 一样难	✗	⚠️ 应是 $P_1$ 至少与 $P_2$ 一样难
41	"对 CNF 求一组真值赋值使其为真"是判定问题	✗	⚠️ 这是搜索/构造问题，非 yes/no
42	"求图 $G$ 中最大团尺寸 $K$"是判定问题	✗	⚠️ 这是优化问题

1.6 近似算法（详见 08）

#	题面（简记）	答案	一句话理由
43	FPTAS：每个 $A_{\epsilon }$ 在输入规模的多项式时间内运行	✗	⚠️ 漏了 $1/\epsilon$；要对 $n$ 与 $1/\epsilon$ 都多项式
44	极小化某实例解 $s_a$、最优 $s_a/3$，则性能比为 3	✗	⚠️ 单实例只是下界，非算法性能比
45	极大化某实例解 $s_a$、最优 $2s_a$，则性能比为 2	✗	⚠️ 同上，单实例 ≠ 性能比

---

二、选择题速记（第 1～12 题，详见 06、07、01）

#	题面（简记）	答案	要点
1	分支限界与回溯二者关系	C	求解目标相同、搜索方式不同
2	回溯法的搜索方式	A	深度优先
3	解空间树不会是	D	无序树（是有序树/子集树/排列树）
4	一个活结点最多一次机会成为扩展结点的是	B	分支限界法
5	不是常见分支限界方式的是	C	栈式分支限界法（栈对应回溯）
6	适合求问题近似解的概率算法	B	蒙特卡罗算法
7	能求解但无法有效判定解正确性的	B	蒙特卡罗算法
8	素数测试所用的数学原理	A	费尔马小定理
9	关于判定问题难易处理的正确叙述	C	多项式时间可解的是易处理的
10	大 O 定义中 $f$ 的阶（）$g$ 的阶	A	不高于
11	$n$ 元素子集树问题叶结点数目	B	$2^n$
12	$n$ 元素排列树问题计算时间复杂性	C	$n!$

---

三、填空题速记（第 1～5 题，详见 01、02、08）

#	题面（简记）	答案
1	对 $x,y,z$ 升序排序的判定树填结果	按比较 a:b、a:c、b:c 的结果，在各叶填排序结论（如 b<a<c）
2	算法具有（）（）（）（）的性质	输入、输出、确定性、有限性
3	评价算法的标准包括（）（）及正确性、简单性	时间复杂性、空间复杂性
4	棋盘覆盖 L 型骨牌个数 = （）；$T(k)=$（）	$(4^k-1)/3$；$T(k)=4T(k-1)+O(1)=O(4^k)$
5	近似算法性能比 $\eta =$（）	$\eta =max\{c/c^{\ast },c^{\ast }/c\}$

---

四、易混概念对照速记（成对记忆）

概念 A	概念 B	一句话区别	详见
分治	动态规划	分治子问题独立；DP 子问题重叠要存表	02/04
贪心	动态规划	贪心每步选当前最优不回头、不一定最优；DP 保证最优	05/04
回溯	分支限界	目标相同；回溯深度优先求可行解，分支限界广度优先/优先队列求最优	06
蒙特卡罗	拉斯维加斯	MC总有解但可能错；LV解必对但可能不给	07
归约	转化	归约：拿 B 算法当子程序解 A；转化：把 A 实例构造成 B 实例且 yes/no 对应	09
P 类	NP 类	P 能多项式求解；NP 能多项式验证一个给定解	09
NP 完全	NP 难	NPC 必须本身属于 NP；NP-hard 不要求、范围更广	09
减治	分治	减治通常只解一个子问题；分治解多个	03
队列式分支限界	优先队列式分支限界	队列式 = FIFO/BFS 波前；优先队列式 = 最小耗费优先（类 Dijkstra）	06

---

五、历年最毒陷阱 TOP 榜（务必记牢）

1. NP 完全"比所有 NP 都难"——错，是彼此等难（判断 33、34）。
2. 单实例比值断定性能比——错，性能比要取所有实例最坏（判断 44、45、Q13）。
3. 加法取 $min$——错，取 $max$（判断 3）。
4. 随机化快排"平均复杂度更低"——错，仍 $O(n\log n)$（判断 15）。
5. 回溯"也可广度优先"——错，仅深度优先（判断 21、22）。
6. Monte Carlo"不给解但给出就对"——错，那是 Las Vegas（判断 31）。
7. "贪心空间换时间"——错，那是动态规划（判断 26）。
8. 转化方向：$P_2{\le }_p{P}_1\Rightarrow P_1$ 更难（判断 40 反了）。
9. 求赋值/求最大尺寸不是判定问题（判断 41、42）。
10. FPTAS 要对 $n$ 和 $1/\epsilon$ 都多项式（判断 43）。

---

自测清单

• [ ] 把判断题 1～45 默背到"看题面就知对错 + 理由"。
• [ ] 记住 ⚠️ 标注的所有陷阱条目（这些最常考、最容易丢分）。
• [ ] 选择题 1～12 的答案能直接报出（C A D B C B B A C A B C）。
• [ ] 填空题 5 条答案能默写。
• [ ] 易混概念对照表的 9 对能各说出一句话区别。
• [ ] "历年最毒陷阱 TOP 榜"10 条能复述。