# 1. 贪心正确性证明的'安全边'框架中以 Kruskal 为例，如何用切割性质（cut property）证明每次选择的边都属于某个最小生成树？ A Kruskal 选择的是最大权边，因此不满足切割性质 B 按权值升序处理边，分属不同连通分量的边因端点所在分量的切割性质而成为安全边 ✓ 正确答案 C 切割性质只适用于稠密图，不适用于 Kruskal D 安全边框架要求 A 必须是完整生成树
# 2. 区间贪心问题的变体中区间选点、区间覆盖与最大不相交区间的贪心策略分别是什么，为什么排序键不同？ A 三者都按左端点升序排序 B 最大不相交区间与区间选点按右端点升序，区间覆盖按左端点升序并选右端点最远的区间 ✓ 正确答案 C 三者都按区间长度排序 D 区间选点按左端点，区间覆盖按右端点
# 3. 拟阵（matroid）与贪心算法中为什么贪心在拟阵上正确，Kruskal 最小生成树与拟阵贪心的一般化关系？ A 拟阵满足遗传性与交换性，贪心在其上最优；图拟阵（森林）使 Kruskal 成为拟阵贪心的特例 ✓ 正确答案 B 拟阵不要求交换性，贪心仍最优 C 0-1 背包满足交换性，故贪心正确 D 拟阵贪心只能求最大权，与 MST 无关
# 4. 贪心算法的适用性判定中如何判断问题具有贪心选择性质与最优子结构，用 0-1 背包 vs 分数背包说明反例？ A 0-1 背包按单位价值贪心正确 B 分数背包按单位价值贪心正确；0-1 背包因不可分割破坏贪心选择性质，贪心会失败需 DP ✓ 正确答案 C 分数背包需 DP，0-1 背包可贪心 D 两者都满足贪心选择性质
# 5. 交换论证（Exchange Argument）的证明框架中以活动选择、任务调度为例说明贪心正确性？ A 交换论证把最优解逐步调整为贪心解而不劣化，从而证明贪心最优；活动选择（结束最早）与 SPT 调度（短先）均适用 ✓ 正确答案 B 交换论证直接证明贪心解是唯一解 C 交换论证只适用于任务调度，不适用于活动选择 D 交换论证要求贪心解一定等于最优解
# 6. 归约（Reduction）在复杂度证明中的应用中如何证明问题 A 不慢于问题 B（A ≤p B）？ A A≤p B 表示若 B 多项式可解则 A 也可解（A 不慢于 B），且需保证实例双向保持 ✓ 正确答案 B A≤p B 表示 B 不慢于 A C 归约只需单向保持 yes 实例 D 归约不要求多项式时间
# 7. 基于决策树证明比较排序 Ω(n log n) 下界的完整推导？ A 决策树需至少 n! 个叶子，树高 h≥log2(n!) = Ω(n log n)，故任何比较排序至少需这么多比较 ✓ 正确答案 B 该下界只适用于归并排序，不适用于堆排序 C 决策树叶子数可以少于 n!，因为排序不需要区分所有排列 D 决策树高度上界是 log2(n!)，故比较排序可达到 O(n) 下界
# 8. 证明最小生成树的 Cut Property（切割性质），为什么跨越切割的最小权边必在某个 MST 中？ A 最小权跨切割边一定属于所有 MST B 切割性质只在连通图且所有权边互不相同时成立 C 任意切割的最小权跨切割边必在某个 MST 中，可用"替换 MST 中跨切割边不增权"的反证证明 ✓ 正确答案 D 切割性质与 Prim/Kruskal 无关
# 9. CLRS 第 16 章活动选择问题的最优子结构与贪心选择性质？ A 贪心应选开始最早的活动 B 活动选择缺贪心选择性质，只能用 DP C 具备最优子结构，且结束最早的活动可替换最优解首活动而不劣化，故贪心（选结束最早）最优 ✓ 正确答案 D 活动选择没有最优子结构
# 10. 比较排序下界的决策树模型，n! 种可能输出要求决策树高度至少 log2(n!)=Ω(n log n)，如何写出严格的树高论证？ A 该模型只适用于基于比较的排序，不适用于归并排序 B 决策树可以少于 n! 个叶子，因为排序可重复输出 C 树高上界是 log2(n!)，比较排序可达到 O(n) 下界 D 叶子数 ≥ n!，树高 h 满足 2^h≥n!，故 h≥log2(n!)=Ω(n log n)，即最坏比较次数下界 ✓ 正确答案
# 11. 拟阵的秩函数（rank function）为什么满足次模性，次模性在证明拟阵贪心算法最优性中起什么作用？ A 次模性只在无权拟阵中成立，与贪心无关 B 秩函数满足超模性，不满足次模性 C 秩函数 r 满足 r(A)+r(B)≥r(A∪B)+r(A∩B)（次模性），其"边际增益递减"是拟阵贪心最优性的关键 ✓ 正确答案 D 秩函数的次模性使贪心在任意权重下都一定得到唯一最优解
# 12. 归约（reduction）的构造与验证中从 3-SAT 归约到 CLIQUE/SUBSET-SUM 时，如何保证'yes 实例 ↔ yes 实例'双向保持？ A 归约只需验证 yes 方向，no 方向无需证明 B 构造需建立变量赋值与目标问题解的一一对应，并分别验证"可满足→有解"与"有解→可满足"两个方向 ✓ 正确答案 C 3-SAT 归约到 CLIQUE 无需保证双向保持 D 归约构造不要求多项式时间
# 13. 信息论与对抗下界的结合中为什么找中位数的下界不能仅靠信息论得出，需要更精细的对手论证（约 2n 次比较）？ A 对手论证只适用于找最大值，不适用于中位数 B 信息论直接给出中位数 ~2n 的下界 C 找中位数只需 log n 次比较 D 信息论只给出 log n 下界（太松），需对手论证以"最坏响应"证明约 2n 次比较的下界 ✓ 正确答案
# 14. 拟阵与匹配的界限中二分图匹配不是拟阵（匹配并集不满足交换性），这如何解释匈牙利算法的复杂性？ A 匹配满足交换性，匈牙利算法可简化为贪心 B 匹配是拟阵，故贪心可求最大匹配 C 匹配并集不满足交换性（如 A={(u1,v1)},B={(u1,v2),(u2,v1)}），故匹配非拟阵，匈牙利算法需增广路径而非贪心 ✓ 正确答案 D 匈牙利算法复杂度 O(n log n)，与拟阵无关
# 15. Huffman 编码最优性的交换论证中两个最小频率的字符一定可以位于编码树最深的两片叶子，如何归纳证明？ A 最小频率字符应放在最浅叶子 B 两个最小频率字符可交换到最深叶子而不增代价，合并它们后归纳可证 Huffman 每次合并最小频率得最优码 ✓ 正确答案 C Huffman 算法不保证最优，只是一个近似 D 交换论证只适用于等概率情形
# 16. 贪心正确性的交换论证中以任务调度/区间覆盖为例展示"交换不劣化"证明？ A 核心是证明把最优解某决策换成贪心决策后代价不增，任务调度（短先）与区间覆盖（覆盖最远）都符合 ✓ 正确答案 B 交换论证只证明贪心解是可行解，不涉及其最优性 C 交换论证要求贪心解与最优解完全相等 D "交换不劣化"只适用于区间覆盖，不适用于任务调度
# 17. 对手论证（adversary argument）如何证明找最小值需要至少 n-1 次比较，与决策树方法的区别？ A 找最小值只需 log n 次比较 B 每个非最小元素都必须输过才可能被排除，每次比较至多淘汰一个，故至少 n−1 次比较；对手论证比决策树更精细 ✓ 正确答案 C 对手论证与决策树方法完全等价，无区别 D 对手论证只能证明存在性，不能给下界
# 18. 信息论下界中需要 log2(n!) 约等于 n log n 个比较位才能区分 n! 种排列，决策树叶数如何推出 Ω(n log n)？ A 决策树叶子数可以少于 n!，因为排序不要求唯一输出 B 信息论下界给出比较排序 O(n) 的上界 C 区分 n! 种排列需 log2(n!) 位信息，每比较给 1 位，故至少 log2(n!)=Ω(n log n) 次比较，由叶数≥n! 与树高 2^h≥叶数推出 ✓ 正确答案 D 每个比较给 log2(n) 位信息，故下界是 log2 n
# 19. 归约的传递性中如何用已知困难问题归约证明新问题也困难？ A 为证新问题难，应把新问题归约到已知难问题（P≤p Q） B 归约不具备传递性 C 若 A≤p B 且 B≤p C 则 A≤p C；为证新问题难，把已知难问题归约到新问题（Q≤p P） ✓ 正确答案 D 归约只能证明问题容易，不能证明困难
