# 1. CLRS Part III Data Structures 中栈、队列、链表、散列表、二叉搜索树的工程取舍。 A 链表缓存不友好，但插入删除灵活，适合频繁增删场景 ✓ 正确答案 B 二叉搜索树保证摊还 O(1) 查询 C 栈与队列支持随机访问 D 散列表提供有序遍历能力，取代二叉搜索树
# 2. CLRS Part II Sorting and Order Statistics 中堆排、快排、归并、计数、桶、基数的工业实现差异。 A 归并排序不需要额外内存 B 堆排是缓存最友好的排序 C 快排因缓存友好与平均性能成为工业默认，introsort 用堆排兜底 ✓ 正确答案 D 基数排序是比较型排序
# 3. CLRS Part IV Advanced Design and Analysis 中动态规划、贪心、分治、摊还分析的工程应用。 A 贪心在局部最优不一定推出全局最优时仍保证正确 B 动态规划依赖最优子结构与重叠子问题，用状态表避免重复计算 ✓ 正确答案 C 摊还分析分析的是一次操作的最坏复杂度 D 分治只适用于排序问题
# 4. CLRS Part V Advanced Data Structures 中 B 树、斐波那契堆、van Emde Boas 的工程取舍。 A B 树通过低扇出减少磁盘 IO B 斐波那契堆理论复杂度优秀但常数大，工程中常被二叉堆取代 ✓ 正确答案 C van Emde Boas 树内存开销小，适合通用场景 D 斐波那契堆是最常用的工程堆
# 5. Radix Sort 在数据库排序（Radix Partition Join）的工程应用。 A 它无法并行化 B 它只适用于字符串键 C 用基数分桶把数据按哈希高位分桶，减少缓存缺失提升连接性能 ✓ 正确答案 D 它比比较型排序更依赖比较操作
# 6. Online Vertex Cover 的 deterministic 与 randomized 竞争比分析。 A 随机化不会影响竞争比 B 确定性算法可达到任意小的竞争比 C 确定性算法有竞争比下界 2，随机化可突破该下界 ✓ 正确答案 D 在线算法无需立即决策
# 7. Rotating Sweep（旋转扫描）在凸包、几何对踵点的 O(n) 推导。 A 对踵点随旋转单调推进，可用双指针 O(n) 求解 ✓ 正确答案 B 旋转卡壳需要 O(n log n) 且无法优化 C 它对任意简单多边形都适用 D 其复杂度为 O(n²)
# 8. Adwords 算法的广义版本与 budget 约束的工程实现。 A 其竞争比可以是任意大 B 它不考虑预算，只最大化收益 C 它只适用于离线场景 D 在预算约束下在线分配广告，用随机化达到 1-1/e 竞争比 ✓ 正确答案
# 9. Antithetic Variates、Control Variates、Rao-Blackwellization 在方差缩减的工程实现。 A 控制变量用无关变量调整 B 对偶变量用正相关样本消除方差 C 方差缩减会增加样本量 D Rao-Blackwell 化用条件期望替代估计，方差不增 ✓ 正确答案
# 11. BSP（Binary Space Partitioning）树在光线追踪、碰撞检测的工程实现。 A BSP 树是动态场景的默认选择 B BSP 树无法用于碰撞检测 C BSP 树不进行空间分割 D 用平面递归二分空间，支持沿光线方向剪枝减少相交测试 ✓ 正确答案
# 12. Bandits 中 UCB1、Thompson Sampling、Contextual Bandits、EXP3 的工程取舍。 A 所有算法都要求环境是非平稳的 B EXP3 面向对抗性环境，UCB1 适合平稳环境 ✓ 正确答案 C Contextual Bandits 不适合个性化推荐 D Thompson Sampling 只适用于对抗性环境
# 13. CDT（Constrained Delaunay Triangulation）在约束线段保留的工程实现。 A CDT 只用于平面剖分，不用于网格生成 B CDT 会忽略约束边 C CDT 不满足 Delaunay 空圆性质 D 在 Delaunay 剖分基础上用边恢复等方法强制保留约束线段 ✓ 正确答案
# 14. CLRS Part I Foundations 中算法分析、渐近记号、Master 定理、概率分析、势能法的工程语义。 A 概率分析只用于非随机算法 B Master 定理用于求解所有随机递推 C 渐近记号描述精确操作次数 D 势能法通过势函数分析摊还操作的总代价 ✓ 正确答案
# 15. Central Limit Theorem（CLT）在样本均值收敛的工程应用。 A 样本均值误差随样本量线性衰减 B CLT 只适用于正态分布 C 大量独立同分布样本的均值近似正态，用于构造置信区间与误差估计 ✓ 正确答案 D CLT 无需样本独立前提
# 16. Chebyshev 不等式在弱大数律的工程应用。 A 只需方差有限即可给出偏离均值的概率上界，无需分布假设 ✓ 正确答案 B 它要求变量服从正态分布 C 它给出的概率界是线性的 D 它只能用于下界
# 17. Concentration Inequality 在概率算法的工程应用。 A 集中不等式只适用于确定性算法 B 它们给出的概率界是线性的、不衰减 C 给出随机变量偏离期望的指数衰减概率界，用于证明随机算法的高概率保证 ✓ 正确答案 D 所有集中不等式都要求变量独立且无界
# 18. Curve Reconstruction（曲线重建）在点云→曲线的工程算法。 A 曲线重建只需线性插值，无需处理噪声 B 它不关心连通性 C 通过构造邻接关系并连接点成折线，从点云恢复曲线 ✓ 正确答案 D 曲线重建只能用于二维
# 19. Engineering Radix Sort 在 32/64-bit 整数的高吞吐工程实现。 A 桶数越多越好，无需考虑缓存 B 它依赖大量比较操作 C 无法并行化 D 通过分桶、顺序访问与 SIMD/并行优化实现高吞吐 ✓ 正确答案
# 20. Exponential Weights、Hedge、Randomized Weighted Majority 的工程实现。 A 按损失指数更新权重并随机按权重选择，保证 O(√T) 遗憾界 ✓ 正确答案 B 它只保留一个最优专家 C 它不提供任何遗憾保证 D 权重更新与损失无关
# 21. Gaussian Process 入门在贝叶斯优化的工程实现。 A 采集函数只进行利用 B GP 只给出点预测，不提供不确定性 C 贝叶斯优化不依赖代理模型 D GP 提供后验均值与方差，采集函数平衡探索与利用选择采样点 ✓ 正确答案
# 22. Hoeffding 不等式在 PAC 学习边界的工程应用。 A Hoeffding 界只适用于无界变量 B 用 Hoeffding 界推导样本复杂度，得到样本量与泛化误差保证的定量关系 ✓ 正确答案 C PAC 学习不需要样本量保证 D Hoeffding 界给出的是线性界
# 23. Markov 不等式在粗略概率界的工程应用。 A 它只适用于正态分布 B 它要求变量有界且方差已知 C 只需期望即可给出 P(X≥a) ≤ E[X]/a 的粗略概率界 ✓ 正确答案 D 它给出的是最紧的界
# 24. Metrical Task System（MTS）在 k-server 问题的统一框架。 A k-server 是 MTS 的特例，MTS 为在线问题提供统一竞争比分析框架 ✓ 正确答案 B MTS 与 k-server 无关 C MTS 不涉及状态转移 D k-server 不涉及移动代价
# 25. Minkowski Sum 在机器人运动规划、碰撞检测的工程应用。 A Minkowski Sum 与碰撞检测无关 B 凸情形的 Minkowski Sum 需要 O(n²) 时间 C 它只适用于二维 D 用机器人-障碍物的 Minkowski Sum 构成配置空间障碍，简化碰撞检测 ✓ 正确答案
# 26. Reservoir Sampling 的 Algorithm R 与 Algorithm Z 在流式采样的工程差异。 A Algorithm Z 用指数跳跃跳过无需替换的元素，减少随机数生成 ✓ 正确答案 B Algorithm Z 牺牲均匀性换效率 C Algorithm R 每元素都生成随机数，与 Z 相同开销 D Algorithm Z 只能采样固定大小
# 27. SIMD Radix Sort 在 AVX-512、VPSHUFB 的向量指令工程实现。 A VPSHUFB 用于整数比较 B 用 AVX-512/VPSHUFB 向量化直方图与重排，实现高吞吐排序 ✓ 正确答案 C 它只能串行处理，无法向量化 D SIMD 排序不依赖内存带宽
# 28. SimHash 与 MinHash 在 Jaccard 与余弦相似度的误差界推导。 A MinHash 估计 Jaccard、SimHash 估计余弦，误差随投影数 k 减小 ✓ 正确答案 B MinHash 估计余弦相似度 C 两者都给出精确相似度 D 误差与投影数无关
# 29. k-server 问题的 (2k-1) 竞争比与 work function algorithm。 A 最优竞争比为 2k B work function algorithm 以离线最优代价为势函数，达到 2k-1 竞争比 ✓ 正确答案 C work function 不涉及离线最优 D 确定性算法竞争比下界为 1
