# 1. 线性一致性 vs 顺序一致性中 Raft/多主复制各自保证哪种一致性，客户端如何观测？ A 多主复制天然保证线性一致性 B 顺序一致性要求操作顺序与真实时间完全一致 C 线性一致性要求操作按与真实时间一致的全局顺序生效，Raft 单主复制可实现 ✓ 正确答案 D 线性一致性只要求最终一致
# 2. 缓存替换策略的适用场景中 LRU 适合时间局部性强、LFU 适合热点稳定、ARC/W-TinyLFU 如何自适应，如何用 trace 评估命中率？ A LFU 对突发热点响应最快 B LRU 适合时间局部性强的负载但怕扫描污染，W-TinyLFU 用频率 Sketch 兼顾突发与长期热点 ✓ 正确答案 C ARC 不需要自适应调节 D 缓存策略优劣与负载特征无关
# 3. 在线广告拍卖中 Adwords 的贪心与 VCG 的激励相容性，为什么次模福利最大化有 1-1/e 近似保证？ A 次模福利最大化的贪心算法有 1-1/e 近似保证，VCG 保证诚实报价是占优策略 ✓ 正确答案 B 贪心算法对任意函数都有 1-1/e 近似 C VCG 在有预算约束时仍完全激励相容 D Adwords 问题的最优竞争比是 1/2
# 4. 在线算法的设计原则中无法预知未来时如何用保守策略保证竞争比，与离线算法的对照（ski rental、list update）？ A 竞争比衡量在线算法相对最优离线算法的代价上界，ski rental 确定性最优竞争比为 2 ✓ 正确答案 B 在线算法总能达到与离线相同的代价 C MTF 策略的竞争比与列表长度成正比 D 随机化只会让在线算法更差
# 5. 算法替换的收益评估中从 O(n²) 到 O(n log n) 的改造如何选择（如排序、哈希、平衡树），何时不值得替换？ A 算法替换需综合规模、常数、输入分布与实现成本，n 很小时 O(n²) 可能仍占优 ✓ 正确答案 B 渐近复杂度完全决定实际性能 C 哈希表的 O(1) 保证所有场景最优 D 只要从 O(n²) 改到 O(n log n) 就必然值得
# 6. 数据结构选型中哈希（O(1) 点查）、平衡树（有序遍历）、日志结构（追加写）在时间/空间/并发上的权衡矩阵？ A 哈希表天然支持范围查询 B 日志结构写放大低、写并发友好但读放大高，哈希适合点查，平衡树适合有序操作 ✓ 正确答案 C 日志结构的读路径只有一层 D B 树在任何负载下都优于哈希
# 7. 在线算法的竞争比中 ski rental 与在线二分等经典问题的竞争比分析入门？ A 竞争比只需给出一个输入下的比值 B ski rental 的确定性最优策略竞争比为 2，随机化可达 e/(e-1) ✓ 正确答案 C 在线二分问题的竞争比是常数 D 下界论证不需要对抗输入
# 8. 并行算法的效率中 Amdahl 定律与并行归约/前缀和的加速比分析？ A 并行归约的工作量为 O(n log n) B 并行前缀和的深度为 O(n) C Amdahl 定律中串行部分占比决定加速比上界，Blelloch 前缀和的工作量为 O(n) 深度 O(log n) ✓ 正确答案 D 加速比可以超过 1/s 只要核数足够多
# 9. 外部排序的两阶段流程中如何用败者树做 k 路归并，I/O 代价（归并趟数）如何随内存大小变化？ A 内存大小不影响外部排序的 I/O 次数 B 败者树每输出一个元素需要 O(k) 比较 C 外部排序趟数为 ⌈log_k(N/M)⌉，内存增大可减少归并趟数与 I/O 代价 ✓ 正确答案 D 替代选择算法生成的 run 长度平均为 M/2
# 10. 带宽受限环境下的算法设计中如何用压缩、差分同步与增量传输减少网络开销，与批量/流式传输的取舍？ A 压缩可以完全消除带宽需求 B 批量传输的延迟一定比流式低 C rsync 用块哈希比对实现差分同步，只传输变化的块 ✓ 正确答案 D 增量传输需要重新发送全部历史数据
# 11. CUDA 并行的性能模型中如何用块/线程/共享内存组织归约与扫描，访存合并（coalescing）与 bank conflict 的影响？ A bank conflict 与共享内存无关 B 全局内存访问需相邻线程访问连续地址才能合并成少量事务，共享内存同 bank 冲突会串行化 ✓ 正确答案 C 归约只能在全局内存中完成 D 访存合并与线程索引无关
# 12. 在线算法的竞争比分析中 ski rental 的确定性 2-竞争与随机化 e/(e-1) 竞争比如何推导，与最优离线（OPT）的对照？ A 下界论证不需要构造对手输入 B 随机化策略的竞争比总是 ≥ 2 C OPT 的代价总是已知的 D ski rental 确定性 2-竞争通过"短/长序列"分情形论证，随机化用 Yao 原理证明 e/(e-1) 下界 ✓ 正确答案
# 13. 负载均衡的随机策略中 Power of Two Choices 为何优于随机选择，Join the Shortest Queue 的通信代价如何取舍？ A 采样队列数越多通信开销越低 B JSQ 不需要任何全局信息 C 两选一策略用两次随机采样把最大负载降到 O(log log n)，远优于随机选择的 O(log n/log log n) ✓ 正确答案 D 两选一的负载均衡效果与随机选择相同
# 14. MPI 与 OpenMP 的分工中分布式内存用消息传递、共享内存用线程并行，如何组合（MPI+OpenMP）处理大规模计算？ A OpenMP 可以跨节点通信 B MPI 用于跨节点分布式内存的进程间消息传递，OpenMP 用于节点内共享内存线程并行 ✓ 正确答案 C MPI 进程间共享地址空间 D 混合模型会增加消息数量
# 15. Narwhal & Tusk 的 DAG 共识中为什么把交易广播（Narwhal）与排序（Tusk）分离能提升吞吐，与 HotStuff 的对比？ A Tusk 需要传统的三阶段投票才能排序 B Narwhal 负责高吞吐 DAG 广播、Tusk 在其上做轻量排序，解耦使传播与共识并行流水 ✓ 正确答案 C Narwhal & Tusk 的延迟低于 HotStuff 且吞吐更高 D DAG 构建与排序耦合是提升吞吐的关键
# 16. 在线定价（Online Pricing）问题中卖家如何在不预知估值分布时定价逼近最优收益，与 secretary problem 的联系？ A secretary problem 与定价无关 B 在线定价需要预知所有买家的估值 C 未知分布下固定价格策略达到 O(log n) 竞争，关键是按 2 的幂分档选择近似最优单价 ✓ 正确答案 D 定价问题的最优竞争比是 1
# 17. 经典在线问题的工程映射中 ski rental（资源购买时机）、paging（缓存淘汰）、secretary（择优时机）分别在哪些系统场景出现？ A ski rental 映射云资源租/买决策，paging 映射缓存淘汰，secretary 映射择优决策场景 ✓ 正确答案 B paging 问题与缓存系统无关 C ski rental 只适用于滑雪板租赁 D secretary 问题只用于招聘
# 18. 内存受限环境（Flash/SSD/PMem）的算法设计中如何用外存模型（B 树、LSM）与缓存友好的数据结构降低随机访问？ A LSM 的随机写比 B 树更快 B B 树的树高与数据量成正比 C 外存模型以块传输次数衡量代价，B 树用大扇出降树高，LSM 用顺序写与布隆过滤器 ✓ 正确答案 D PMem 不需要崩溃一致性处理
# 19. 功耗受限（Edge/IoT/Mobile）的算法取舍中如何用近似/降采样/离线压缩在电池预算内完成任务，与云端卸载的权衡？ A 近似计算不损失任何精度 B 卸载计算总是比本地计算省电 C 无线通信的单位能耗远高于本地计算，降采样与压缩可显著降耗 ✓ 正确答案 D 功耗优化与延迟无关
# 20. 增量算法中如何维护随数据到达而更新的聚合结果（增量统计、增量索引），与全量重算的复杂度对比？ A 可分解聚合（sum/count/min/max）可 O(1) 增量维护，不可分解聚合需 Sketch 类流式结构 ✓ 正确答案 B 去重计数可以精确 O(1) 增量维护 C 增量索引比全量重建更精确 D m 次全量重算的复杂度是 O(m + n)
# 21. 延迟受限（HFT/Realtime/Embedded）场景的算法约束中如何用预计算、近似与低延迟数据结构在期限内返回结果？ A 实时系统优化平均延迟即可 B 延迟受限场景要求最坏情形延迟有上界，预计算与查找表把运行时开销降到 O(1) ✓ 正确答案 C 动态内存分配在实时场景没有风险 D 近似算法在实时场景不被允许
# 22. 成本受限（Serverless/Spot/Preemptible）下的计算策略中如何用容错重试与状态外置应对节点回收，成本与延迟的权衡？ A 应对 Spot 节点回收需状态外置与检查点重放，检查点频率是恢复延迟与写成本的权衡 ✓ 正确答案 B 检查点越频繁成本越低 C Spot 实例不会被回收 D 幂等重试无法处理重复执行
# 23. 流处理的窗口与状态中滚动/滑动/会话窗口如何划分，状态后端（RocksDB）如何支持大状态 exactly-once？ A 会话窗口按不活动间隔切分，滑动窗口重叠，状态后端用 RocksDB + WAL + checkpoint 实现 exactly-once ✓ 正确答案 B 滚动窗口允许窗口重叠 C 水位线用于窗口的数据合并 D exactly-once 不需要状态快照
# 24. 算法基准测试的正确做法中 JMH/hyperfine/criterion 如何消除 JIT 预热与测量噪声，为什么微基准容易误导？ A 基准测试不需要统计置信区间 B 单次运行的结果即可代表性能 C 微基准可以完全预测系统性能 D JMH 用预热与 Blackhole 消除 JIT 与死代码消除干扰，微基准结果需宏观基准验证 ✓ 正确答案
# 25. 性能剖析的方法中 perf/FlameGraph 如何定位 CPU 热点与缓存缺失，与直觉优化的差异？ A 直觉优化通常能准确找到热点 B 火焰图的 y 轴表示采样数量 C perf 用周期采样与硬件计数器定位 CPU 热点与缓存缺失，火焰图 x 轴宽度表示开销占比 ✓ 正确答案 D 剖析只需关注 CPU 时间，忽略等待时间
# 26. 热路径（Hot Path）优化的原则中如何识别高频代码段并做针对性优化（分支预测、内联），与过早优化的界限？ A 内联总是能提升性能 B 热路径优化应先 profiling 确认热点，再做分支/内联/局部性定向优化，并每次验证收益 ✓ 正确答案 C 过早优化指优化任何未验证的代码 D 分支预测优化与性能无关
# 27. 并行算法的加速比中 Amdahl 定律对可并行部分比例的要求，与并联网算法的效率？ A 稀疏图比稠密图更容易获得高并行效率 B 核数无限时加速比无限增长 C Amdahl 定律要求串行部分占比极小才有高加速比，并行图算法受负载不均与同步开销限制 ✓ 正确答案 D 同步开销不影响并行效率
# 28. 分布式一致性与算法中 Raft 多数派读写如何实现线性一致，CAP 的工程含义？ A Raft 用多数派提交保证写线性一致，ReadIndex/Lease Read 保证读一致 ✓ 正确答案 B Raft 领导者本地读一定是最新的 C CAP 中的 CA 系统在分布式下可以实现 D AP 系统分区时也保证强一致
# 29. Avalanche 共识的随机抽样投票中为什么多次子采样投票能以高概率收敛，与经典 BFT（PBFT）在假设上的差异？ A Avalanche 的收敛需要全局广播 B Avalanche 用随机子采样投票使偏好滚雪球收敛，安全性是概率性的，PBFT 是确定性安全 ✓ 正确答案 C PBFT 的提交是概率性的 D 两种共识的拜占庭假设完全相同
# 30. 区块链共识的效率设计中 DPoS 的委托投票与 PoH（Solana）的可验证延迟如何提升吞吐，各自的安全假设？ A DPoS 不依赖任何质押机制 B PoH 的时间戳可以并行加速生成 C DPoS 用少量委托出块节点提升吞吐，PoH 用可验证延迟序列作为全局时钟减少排序开销 ✓ 正确答案 D 两者都保持完全去中心化的出块权
# 31. Dask 的惰性计算图中如何把 Python 任务组织成有向无环图并调度到多进程/分布式，与 Spark 的 RDD 图差异？ A Dask 的 compute() 只是记录操作 B Dask 用惰性任务图 + 依赖拓扑调度 Python 任务，Spark 以分区与阶段为单位执行 ✓ 正确答案 C Spark 的任务粒度比 Dask 更细 D Dask 无法分布式执行
# 32. Flink 的流处理保证中 checkpoint 与 exactly-once 状态一致性如何实现，与 Spark Streaming 的微批模型差异？ A Flink 按批次处理事件 B Flink 用 Barrier 对齐的分布式快照 + 两阶段提交实现流式 exactly-once ✓ 正确答案 C Spark Streaming 的延迟可到毫秒级 D 微批模型天然支持逐事件语义
# 33. 节俭计算（Frugal Computing）的思想中如何在资源受限时用近似/采样/离线预处理换取数量级收益，典型例子有哪些？ A 采样误差随样本量线性下降 B Count-Min Sketch 是精确计数结构 C 节俭计算用有界误差的 Sketch、采样与离线预处理换取数量级资源节省 ✓ 正确答案 D 近似结构适用于所有精度要求的场景
# 34. GPU Direct RDMA 中如何让 GPU 绕过 CPU 直接访问网卡内存，在分布式训练（NCCL）中的带宽收益与部署条件？ A GDR 只影响延迟，不影响带宽 B GDR 仍然需要 CPU 参与每次拷贝 C 任意网卡都支持 GPU Direct D GPU Direct RDMA 让 GPU 显存直接 DMA 到网卡，绕过主机内存与 CPU，提升 NCCL 集合通信带宽 ✓ 正确答案
# 35. MapReduce 的执行模型中 shuffle 按 key 分区排序是关键步骤，Combiner 如何在 map 端预聚合降低网络量？ A Combiner 可以随意使用任何聚合函数 B shuffle 按 key 分区排序实现分组与负载均衡，Combiner 在 map 端预聚合减少网络传输 ✓ 正确答案 C shuffle 不需要排序 D shuffle 的传输量通常不是性能瓶颈
# 36. PBFT 与 HotStuff 的对比中为什么 HotStuff 用线性视图切换与门限签名把消息复杂度降到 O(n)，两者在 BFT 假设上的异同？ A HotStuff 用链式三阶段 + 门限签名 + 线性视图切换把消息复杂度降到 O(n) ✓ 正确答案 B PBFT 的视图切换复杂度是 O(n) C HotStuff 不需要门限签名 D 两者对拜占庭节点比例的假设不同
# 37. Paxos 与 Raft 的工程差异中为什么 Raft 通过强领导者与日志复制的简化使其更易实现，两者的多数派读写语义？ A Paxos 规定了完整的日志管理 B Raft 用强领导者 + 有序日志复制 + 选举日志完整性约束简化实现，两者都依赖多数派交集保证线性一致 ✓ 正确答案 C Raft 的读操作不需要确认领导者 D Raft 允许多领导者并发提案
# 38. Ray 的分布式任务模型中 actor 与 task 如何支持 Python 的弹性调度，与 Dask/Spark 在细粒度并行上的差异？ A Ray 用 task 与 actor 提供细粒度动态任务图与分布式对象存储，Spark 是阶段批式模型 ✓ 正确答案 B Ray 的任务图在运行时不可扩展 C Spark 支持细粒度的动态任务 D Ray 对象必须经磁盘传输
# 39. 流式 Sketch 的选型中 Count-Min 估频率、HLL 估基数、Misra-Gries 找频繁项，各自的空间/误差边界如何比较？ A Misra-Gries 是概率性的，可能漏掉频繁项 B HLL 可以估计每个元素的频率 C Count-Min 估计频率误差 ≤ εN，HLL 估基数相对误差 ~1.04/√m，Misra-Gries 确定性找频繁项 ✓ 正确答案 D Count-Min 的空间与误差参数无关
# 40. Spark 的 RDD 血统（lineage）容错中为什么通过记录转换操作而非数据副本恢复分区，与检查点（checkpoint）的取舍？ A checkpoint 不需要额外存储开销 B 血统容错需要存储数据副本 C RDD 血统记录转换操作，分区丢失时重放重算，长血统或昂贵转换时用 checkpoint 截断 ✓ 正确答案 D 血统重算只适用于短血统，长血统无法恢复
# 41. TLA+ 建模分布式协议中如何用状态机与不变量验证 Raft/Paxos 的安全性，模型检查在什么规模下会状态爆炸？ A 模型检查可以验证无限规模的协议 B TLA+ 用状态变量 + 非确定性 Next 建模协议，TLC 穷举可达状态验证不变量 ✓ 正确答案 C 不变量只能表达活性 D 状态爆炸与节点数无关
# 42. Tendermint 的 BFT 共识中为什么两轮投票+锁定期能保证安全性，与 PBFT 在视图切换上的简化？ A Tendermint 的视图切换与 PBFT 一样复杂 B 锁定期会阻止所有后续提案 C Tendermint 只需要一轮投票 D Tendermint 用两轮投票 + 锁定期防止双提交，换轮只需广播锁与投票信息 ✓ 正确答案
# 43. 大数据处理框架的选型中批处理（MapReduce/Spark）、流处理（Flink）与迭代图计算（Pregel）各适合什么负载？ A Pregel 适合 SQL 聚合 B 批处理适合离线全量分析，流处理适合低延迟实时事件，Pregel 适合迭代图算法 ✓ 正确答案 C Flink 只能做批处理 D 图计算可以直接用 MapReduce 高效完成每轮迭代
# 44. 分治思想在大数据中的应用中外排序、分布式聚合（两阶段归并）与 MapReduce 的契合，如何划分数据减少 shuffle？ A 两阶段聚合无法处理局部聚合 B combiner 会增加 shuffle 数据量 C 数据倾斜与分区器无关 D 外排序、两阶段聚合与 MapReduce 都是"划分 + 归并"的分治结构 ✓ 正确答案
# 45. 常数优化的层次中缓存局部性、SIMD 向量化与 cache-oblivious 布局分别优化什么，如何用 profiling 定位瓶颈？ A profiling 无法区分访存瓶颈与计算瓶颈 B cache-oblivious 布局需要知道缓存大小 C SIMD 对随机访问同样高效 D 缓存局部性优化访问模式，SIMD 做数据级并行，cache-oblivious 用递归分块适配任意缓存 ✓ 正确答案
# 46. 写时复制（COW）与路径复制（Path Copying）的性能收益中共享不可变结构能减少复制，CRDT 的合并开销如何控制？ A 共享不可变结构无法支持多版本访问 B COW 在写多读少时收益最大 C CRDT 合并必须处理全部历史操作 D 路径复制只复制修改路径并共享未变子树，复制量正比于改动规模而非数据总量 ✓ 正确答案
# 47. 算法并行化的模式中 Fork-Join 分治、MapReduce 数据并行与 CUDA 线程并行各自的加速比受什么因素限制（Amdahl）？ A Fork-Join 受分治串行部分与任务粒度限制，MapReduce 受 shuffle 通信与倾斜限制，CUDA 受访存与占用率限制 ✓ 正确答案 B Fork-Join 的任务粒度越细越好 C MapReduce 的数据倾斜不影响加速比 D CUDA 的占用率越高越好，无副作用
# 48. 嵌入式/移动端的资源受限设计中近似、在线与流式算法如何在小内存低功耗约束下给出可用结果？ A 浮点运算在 MCU 上开销与定点相同 B 嵌入式设备可以缓存全部历史数据 C 流式 Sketch 与采样用 O(1) 内存处理无限数据流，定点/量化与查表用精度换算力 ✓ 正确答案 D 流式算法需要预知数据总量
# 49. 近似算法的选型中贪婪（集合覆盖 ln n）、LP 舍入（顶点覆盖 2）、局部搜索（k-median）各自的近似比与适用问题？ A 集合覆盖用贪婪得 ln n 近似，顶点覆盖用 LP 舍入得 2 近似，k-median 用局部搜索得常数近似 ✓ 正确答案 B 贪婪算法对所有问题都达到常数近似 C LP 舍入得到的解一定是最优整数解 D 局部搜索保证全局最优
# 50. 采样算法中蓄水池抽样（等概率）、加权采样与流式采样的实现，采样误差如何随样本量减小？ A 加权采样用均匀随机数即可 B 蓄水池抽样需要预知流长度 C 蓄水池抽样让每个元素以 k/n 概率入选（O(1) 内存），采样标准误按 1/√n 收敛 ✓ 正确答案 D 样本量与总体规模成正比才能保证精度
