Ch13 计算与操作系统 · 阶段测试题 (25 题)¶

测试目标: 全面考察 Ch13 五节内容: 离散数学(§01) / 计算机架构(§02) / 操作系统(§03) / 并发并行(§04) / 编程语言(§05) 难度分布: ★ 基础 / ★★ 中等 / ★★★ 拔高 / ⭐⭐⭐⭐ 竞赛

Part A 选择题 (10 题, 每题 3 分)¶

A1 (★★)¶

题目: \(C(8, 4)\) 等于? - A) 1680 - B) 70 - C) 24 - D) 40320

答案: B (\(8!/(4! \cdot 4!) = 70\))

A2 (★★★)¶

题目: CPU 时间 \(T = IC \cdot CPI \cdot T_{\text{cycle}}\), 哪个优化最难? - A) 减 IC - B) 减 CPI - C) 减 \(T_{\text{cycle}}\) - D) 都一样

答案: C (受工艺限制, 减 \(T_{\text{cycle}}\) 最难)

A3 (★★)¶

题目: Amdahl 定律中, \(p = 1, n \to \infty\) 时加速比? - A) \(\infty\) - B) \(n\) - C) 1 - D) 0

答案: B (\(S = 1/(0 + 1/n) = n\))

A4 (★★★)¶

题目: 死锁四条件中, 哪个最容易破坏? - A) 互斥 - B) 占有并等待 - C) 不剥夺 - D) 循环等待

答案: B (一次性申请所有资源)

A5 (★★)¶

题目: GPU SIMT 中 warp 大小? - A) 16 - B) 32 - C) 64 - D) 128

答案: B

A6 (★★★)¶

题目: 虚拟内存的主要目的是? - A) 提高 CPU 速度 - B) 扩大程序可见内存, 提供隔离 - C) 减少磁盘 IO - D) 加快缓存命中

答案: B

A7 (★★)¶

题目: Lambda 演算 Church 数 \(c_3\) 应用一次 \(f\) 后是? - A) \(c_2\) - B) \(c_3\) 本身 - C) \(c_4\) - D) 错误

答案: C (因为 \(c_3 = \lambda f. \lambda x. f(f(f(x)))\))

A8 (★★★)¶

题目: 静态类型语言的优势? - A) 灵活 - B) 编译期检查错误 - C) 无需写类型 - D) 运行更快

答案: B

A9 (★★)¶

题目: MapReduce reduce 阶段输入? - A) 单个 \((k, v)\) - B) \((k, \text{list}(v))\) - C) 排序后的 \(v\) - D) hash 表

答案: B

A10 (★★★)¶

题目: P 与 NP 的关系? - A) \(P = NP\) 已证明 - B) \(P \neq NP\) 已证明 - C) \(P \subseteq NP\) - D) 不相交

答案: C

Part B 简答题 (8 题, 每题 5 分)¶

B1 (★★★)¶

题目: 解释大 O 记号, 给出 \(O(n)\), \(O(n^2)\), \(O(2^n)\) 各一个算法例子。

要点: - 上界定义 - \(O(n)\): 线性扫描 - \(O(n^2)\): 冒泡排序 - \(O(2^n)\): 子集枚举

B2 (★★★)¶

题目: 解释内存墙 (Memory Wall) 及其对 AI 的影响。

要点: - CPU 算力 >> 内存带宽 - 性能受内存限制 - AI: 模型加载 / KV cache 都受带宽限制 - 解决: 缓存 / 预取 / 量化

B3 (★★★)¶

题目: 进程 vs 线程的区别, 各举一个合适场景。

要点: - 进程独立内存, 线程共享 - 进程: Chrome 多标签 (隔离) - 线程: Web 服务器并发请求

B4 (★★★)¶

题目: CUDA block / grid / warp 关系。

要点: - grid = 所有 blocks - block = 多个 warps (每个 32 threads) - 1 SM 调度多个 blocks - 线程索引: blockIdx, threadIdx

B5 (★★★)¶

题目: 解释 GC 三种算法的优劣。

要点: - 引用计数: 简单, 但循环引用 - 标记清除: 处理循环, 但碎片 - 复制: 无碎片, 但 50% 浪费

B6 (★★★)¶

题目: Hindley-Milner 类型推导如何工作?

要点: - 算法: 自顶向下, 未知类型 + unify - let 多态: 自动泛化 - ML, Haskell 标配

B7 (★★★)¶

题目: 解释 P vs NP 问题的意义。

要点: - P: 可快速解 - NP: 可快速验证 - P = NP? 仍未解 - 若 =, 密码学崩

B8 (★★★)¶

题目: MapReduce 在 LLM 训练中的应用。

要点: - 概念上: 数据并行 / 模型并行 - 实际: PyTorch DDP = AllReduce - 跨节点: parameter server / ring allreduce

Part C 编程题 (5 题, 每题 10 分)¶

C1 (★★★)¶

题目: 用 Python 实现 4 个排序, 比较 \(O(n^2)\) vs \(O(n \log n)\)。

要点: - bubble sort \(O(n^2)\) - merge sort \(O(n \log n)\) - 时间测量 time.perf_counter - \(n=10000\) 时差距显著

C2 (★★★)¶

题目: 实现 CUDA kernel: 向量加法。

要点: - __global__ void add(float* a, float* b, float* c, int n) - idx = blockIdx.x * blockDim.x + threadIdx.x - if (idx < n) c[idx] = a[idx] + b[idx] - 启动: <<<(n+255)/256, 256>>>

C3 (★★★)¶

题目: 实现 PyTorch DDP 单机多卡训练。

要点: - init_process_group - DistributedSampler - DistributedDataParallel - 启动: torchrun --nproc_per_node=N

C4 (★★★)¶

题目: 用 Python multiprocessing 实现并发计算。

要点: - Pool 进程池 - apply_async 异步 - map 分布 - 比 serial 快 N×

C5 (★★★)¶

题目: 实现 Lambda 演算解释器 (Church 数加法)。

要点: - 用 Python 函数表示 lambda 项 - add = lambda m: lambda n: lambda f: lambda x: m(f)(n(f)(x)) - 测试 add(c_2)(c_3) == c_5

Part D 综合题 (2 题, 每题 15 分)¶

D1 (⭐⭐⭐⭐)¶

题目: 设计一个 LLM 推理服务, 用 Ch13 概念解释每个组件: - KV cache 内存 - Batching 调度 - 量化策略 - 分布式部署

要点: - KV cache: 虚拟内存分页 (PagedAttention) - 调度: CFS-like 公平调度 - 量化: GPU INT8 kernel - 分布式: TP + PP + DP

D2 (⭐⭐⭐⭐)¶

题目: 综述 2024 年 LLM 推理优化技术 (vLLM, TGI, SGLang, TensorRT-LLM)。

要点: - Continuous batching - PagedAttention - Speculative decoding - Quantization (INT4/8)

评分标准¶

题型	题数	总分
选择	10	30
简答	8	40
编程	5	50
综合	2	30
合计	25	150

自测建议¶

目标	分数	行动
及格	75	复习 §01-§02, 默写大 O + CPU 公式
良好	100	复习 §03-§04, 跑通编程 C1-C3
优秀	120	复习 §05 类型系统, 完成综合 D1-D2