计算机基础硬核计算题深化

一句话定位

综合知识 75 题中 8~12 题为计算/判定题，本篇把流水线、Cache、可靠度、海明码、CRC、浮点数等考点落成公式 + 真题举一反三，确保 30 秒内套对公式。

NOTE

本篇是 01-cs-fundamentals.mdx 的”计算题深化版”——前者给概念，本篇给解题套路。覆盖计划 §3.1 全部计算考点，事实据官方教材（第 2 版）+ 2020-2025 真题核对（2026-07-29）。

A. 流水线（Pipeline）

核心公式表

指标	公式	说明
流水线周期 Δt	`max(各段执行时间)`	取最慢一段
n 条指令总时间	`(k + n - 1) × Δt`	k=流水线段数
非流水线时间	`n × k × Δt`（理想，各段时间相等）	用于对比
加速比 S	`非流水线时间 / 流水线时间 = n·k / (k+n-1)`	理论上限 = k
吞吐率 TP	`n / [(k+n-1)·Δt]`	单位时间指令数
效率 E	`S / k = n / (k+n-1)`	流水线设备利用率

流水线冲突三类型

冲突类型	原因	对策
结构冲突（资源）	多条指令同时争用同一部件	资源重复（如独立指令/数据 Cache）
数据冲突（相关）	后指令需要前指令的结果	停顿 / 数据转发（旁路）/ 编译优化
控制冲突（转移）	分支跳转改变 PC	分支预测 / 延迟转移 / 循环展开

IMPORTANT

流水线解题套路 callout：

识别 k（段数）、Δt（最慢段时间）、n（指令数）
总时间 = (k+n-1) × Δt（首次填充 k 段 + 后续 n-1 条各一拍）
加速比 = 非流水线 / 流水线 = n·k / (k+n-1)
注意：若有条件转移/数据相关，需加停顿周期数

真题举一反三

2023-11 综合题：5 段流水线，每段 2ns，10 条指令，求加速比。

解：流水线时间 = (5+10-1)×2 = 28ns；非流水线 = 10×5×2 = 100ns；S = 100/28 ≈ 3.57

2021-11 综合题：4 段流水线，每段 5ns，100 条指令，求吞吐率。

解：时间 = (4+100-1)×5 = 515ns；TP = 100/515ns ≈ 0.194 指令/ns = 194MIPS

2024-05 综合题：4 段流水线，段时间分别为 3、5、4、6 ns，求周期与 100 指令总时间。

解：Δt = max(3,5,4,6) = 6ns；总时间 = (4+100-1)×6 = 618ns

B. Cache 高速缓存

核心公式

指标	公式
命中率 h	`h = 命中次数 / 总访问次数`
平均访问时间 t	`t = h × t_cache + (1-h) × t_main`
效率 e	`e = t_cache / t`（命中率越高，效率越接近 1）

三种映射方式对比

方式	地址结构	优点	缺点	适用
直接映射	主存字块标记 + Cache 字块号 + 字块内地址	查找快、实现简单	冲突率高、命中率低	大容量 Cache
全相联映射	主存字块标记 + 字块内地址	命中率高、空间利用率高	查找慢、比较器复杂	小容量 Cache
组相联映射	主存字块标记 + 组号 + 字块内地址	折中直接与全相联	实现较复杂	现代主流（如 8 路组相联）

替换算法与写策略

替换算法	原理	评价
LRU 最近最少使用	淘汰最久没用的	命中率高，主流
LFU 最少经常使用	淘汰访问次数最少的	对突发不敏感
FIFO 先进先出	淘汰最早进入的	简单但命中率低
RAND 随机	随机淘汰	实现最简单

写策略	原理	评价
全写法（写直达 Write-Through）	同时写 Cache 与主存	一致性好，但写慢
写回法 Write-Back	只写 Cache，替换时回写主存	速度快，需脏位标记
写分配 Write-Allocate	写未命中时先调入 Cache 再写	配合写回法
不按写分配 Not-Write-Allocate	写未命中时直接写主存	配合全写法

IMPORTANT

Cache 解题套路 callout：

判定映射方式（直接 / 全相联 / 组相联）
算命中率：先列访问序列 → 标注命中/未命中
平均访问时间 = h·t_cache + (1-h)·t_main
注意 Cache 与主存的容量比、地址字段拆分

真题举一反三

2022-11 综合题：Cache 速度 10ns，主存 100ns，命中率 0.9，求平均访问时间与效率。

解：t = 0.9×10 + 0.1×100 = 9+10 = 19ns；e = 10/19 ≈ 52.6%

2024-11 综合题：某 Cache-主存系统，Cache 命中率 0.95，Cache 周期 20ns，主存周期 200ns，求平均访问时间。

解：t = 0.95×20 + 0.05×200 = 19+10 = 29ns

2025-05 综合题：32KB Cache，块大小 64B，2 路组相联，求组数与地址字段。

解：块数 = 32KB/64B = 512 块；组数 = 512/2 = 256 组；地址：组号 8 位 + 块内 6 位 + Tag 其余位

C. 虚拟存储与地址映射

三种管理方式对比

方式	地址结构	优点	缺点
页式	页号 + 页内偏移	简单、空间利用率高	不便编程、共享难
段式	段号 + 段内偏移	逻辑清晰、便于共享/保护	易产生外部碎片
段页式	段号 + 页号 + 页内偏移	综合两者优点	地址变换复杂

地址转换流程

逻辑地址 = 页号 P + 页内偏移 W
       ↓ 查页表
物理地址 = 物理页框号 F + 页内偏移 W

页大小：通常 4KB（12 位页内偏移）
TLB（快表）：缓存近期访问的页表项，避免每次访存查页表
多级页表：减少页表本身占用空间

真题举一反三

2020-11 综合题：页大小 4KB，逻辑地址 0x2A3F，求页号与页内偏移。

解：4KB = 2^12，0x2A3F = 10815；页号 = 10815 / 4096 = 2；偏移 = 10815 % 4096 = 2623 (0xA3F)

2023-05 综合题：TLB 命中率 0.95，TLB 访问 10ns，页表访问 100ns，求地址变换平均时间。

解：t = 0.95×10 + 0.05×(10+100) = 9.5+5.5 = 15ns

D. 可靠性（必考 1 题）

核心公式

指标	公式	含义
MTBF	平均无故障时间	越大越可靠
MTTR	平均修复时间	越小越好
可用性 A	`MTBF / (MTBF + MTTR)`	系统可用比例
串联可靠度	`R = R1 × R2 × ... × Rn`	任一失效则系统失效
并联可靠度	`R = 1 - (1-R1)(1-R2)...(1-Rn)`	全部失效系统才失效

可靠性框图与计算

串联：  [R1] ── [R2] ── [R3]    R = R1·R2·R3

并联：  ┌─ [R1] ─┐
        ├─ [R2] ─┤  →   R = 1 - (1-R1)(1-R2)(1-R3)
        └─ [R3] ─┘

混联：  [R1] ── ┌─ [R2] ─┐  ── [R4]
                └─ [R3] ─┘
        先并联 R23 = 1-(1-R2)(1-R3)
        再串联 R = R1·R23·R4

IMPORTANT

混联解题套路 callout（四步法）：

画可靠性框图（识别串/并联关系）
先做最内层并联：R_并 = 1 - Π(1-Ri)
再做外层串联：R_串 = Π Ri
多级嵌套由内向外逐层化简

真题举一反三

2021-05 综合题：3 个部件串联，可靠度均为 0.9，求系统可靠度。

解：R = 0.9 × 0.9 × 0.9 = 0.729

2023-11 综合题：某系统由两并联子系统（每子系统含 3 个串联部件，R=0.9）构成，求系统可靠度。

解：子系统 R_sub = 0.9³ = 0.729；系统 R = 1 - (1-0.729)² = 1 - 0.0734 = 0.9266

2024-05 综合题：双工系统（双机热备），单机 MTBF=5000h，MTTR=8h，求系统可用性。

解：单机 A = 5000/(5000+8) = 0.9984；双机可用性 ≈ 1 - (1-A)² = 1 - 0.0016² = 0.9999974

E. 校验码（必考 1~2 题）

三种校验码对比

校验码	码距	检错	纠错	开销
奇偶校验	2	检 1 位错	不能纠错	1 位
海明码	3	检 2 位错	纠 1 位错	log₂(n+1) 位
CRC	2+	检多位错	通常不纠错（重传）	r 位（生成多项式决定）

海明码（Hamming Code）

核心公式：2^r ≥ m + r + 1（m = 数据位数，r = 校验位数）

码距与检纠能力：

码距 d：检 d-1 位错，纠 ⌊(d-1)/2⌋ 位错
海明码码距 = 3：检 2 / 纠 1

校验位位置：放在 2^i 位置（即第 1、2、4、8、16… 位）

IMPORTANT

海明码解题四步 callout：

定 r：解不等式 2^r ≥ m+r+1，取最小整数
填位置：校验位放 2^i 位（P1/P2/P4/P8…），数据位填其余位
算校验值：每个数据位的位号 = 校验位组合（如位 7 = 4+2+1 → 由 P4/P2/P1 覆盖）
- P1 覆盖位号二进制最低位为 1 的所有位（1,3,5,7,9,11…）
- P2 覆盖位号次低位为 1 的所有位（2,3,6,7,10,11…）
- P4 覆盖位号第 3 位为 1 的所有位（4,5,6,7,12,13…）
偶/奇校验：偶校验 = 异或结果使 1 的个数为偶数

CRC 循环冗余校验

IMPORTANT

CRC 解题四步 callout：

补零：信息位 M(x) 后补 k 个 0（k = 生成多项式 G(x) 最高次，也即位数-1）
模 2 除：M·x^k ÷ G(x)，模 2 除法 = 异或运算（不进位不借位）
替换：余数替换补的 0，得 T(x) = M·x^k + 余数
接收校验：T(x) ÷ G(x) 余 0 → 无错

真题举一反三

2020-11 综合题：信息位 7 位，求海明码校验位数。

解：试 r=4：2^4=16 ≥ 7+4+1=12 ✓；r=3：2^3=8 < 11 ✗；r=4

2022-05 综合题：信息 1010，求偶校验海明码。

解：m=4，r=3（2^3=8 ≥ 8 ✓）；位号安排：P1(1)·P2(2)·d1(3)·P4(4)·d2(5)·d3(6)·d4(7)
d1=1, d2=0, d3=1, d4=1（按信息位填入非校验位）
P1（覆盖位 1,3,5,7）= d1 ⊕ d2 ⊕ d4 = 1⊕0⊕1 = 0
P2（覆盖位 2,3,6,7）= d1 ⊕ d3 ⊕ d4 = 1⊕1⊕1 = 1
P4（覆盖位 4,5,6,7）= d2 ⊕ d3 ⊕ d4 = 0⊕1⊕1 = 0
结果：P1 P2 d1 P4 d2 d3 d4 = 0 1 1 0 0 1 1 → 0110011

2024-11 综合题：信息 1101，生成多项式 G(x)=x³+x+1（即 1011），求 CRC 与发送码字。

解：M=1101，补 3 个 0 → 1101000；模 2 除：

     1110       (商)
   ─────────
1011)1101000
     1011
     ────
      1100
      1011
      ────
       1110
       1011
       ────
        1010
        1011
        ────
         001  (余数)

CRC = 001；发送码字 = 1101001

2025-05 综合题：海明码接收码 0110111（m=4，r=3），判断哪位错。

解：S1 = b1⊕b3⊕b5⊕b7 = 0⊕1⊕1⊕1 = 1
S2 = b2⊕b3⊕b6⊕b7 = 1⊕1⊕1⊕1 = 0
S4 = b4⊕b5⊕b6⊕b7 = 0⊕1⊕1⊕1 = 1
错位 = S4S2S1 = 101 = 位 5 错

F. 数据表示（浮点数 + 进制）

四种码制对比（n 位字长）

码制	正数范围	负数范围	特点
原码	0 ~ 2^(n-1)-1	-0 ~ -(2^(n-1)-1)	有 ±0；对称
反码	0 ~ 2^(n-1)-1	-0 ~ -(2^(n-1)-1)	有 ±0；负数取反
补码	0 ~ 2^(n-1)-1	-1 ~ -2^(n-1)	无 ±0；多一个负数
移码	偏移 2^(n-1)	偏移 2^(n-1)	用于浮点阶码

TIP

8 位补码范围：-128 ~ +127（注意负数比正数多一个）；移码 = 补码符号位取反

IEEE 754 浮点数（32 位单精度）

字段	位数	含义
符号位 S	1 位	0 正 1 负
阶码 E	8 位	移码表示，偏移 127
尾数 M	23 位	规格化后小数点后部分（隐含最高位 1）

真值公式：V = (-1)^S × 1.M × 2^(E-127)

特殊值：

E=0, M=0 → ±0
E=255, M=0 → ±∞
E=255, M≠0 → NaN

真题举一反三

2021-11 综合题：8 位补码能表示的整数范围。

解：-128 ~ +127（共 256 个数）

2024-05 综合题：十进制 -25 的 8 位补码。

解：25 = 0001 1001；取反 1110 0110；加 1 → 1110 0111

G. 性能评价指标

评价指标表

指标	全称	含义	典型应用
MIPS	Million Instructions Per Second	每秒百万条指令	通用 CPU 性能
MFLOPS	Million FLoating-point OPS	每秒百万次浮点	科学计算
CPI	Cycles Per Instruction	每条指令平均周期数	CPU 设计分析
IPC	Instructions Per Cycle	每周期指令数（=1/CPI）	现代 CPU
TPC-C	Transaction Processing Council	在线事务处理基准	数据库
TPC-H	—	决策支持基准	数据仓库
SPEC	Standard Performance Evaluation Corp	CPU 整数/浮点基准	工作站

公式

MIPS = 主频 / (CPI × 10^6) 或 指令数 / (执行时间 × 10^6)
执行时间 = 指令数 × CPI / 主频

真题举一反三

2022-05 综合题：主频 2GHz，CPI=2，求 MIPS。

解：MIPS = 2GHz / (2 × 10^6) = 1000 MIPS

H. 反查表（考点 / 公式 / 真题 / 锚点）

考点	公式或决策树	真题年份	本笔记锚点
流水线周期与时间	(k+n-1)·Δt	2023-11, 2021-11, 2024-05	§A
流水线加速比	n·k / (k+n-1)	2023-11	§A
Cache 命中率与平均时间	h·tc + (1-h)·tm	2022-11, 2024-11	§B
Cache 组相联字段拆分	组数=块数/路数	2025-05	§B
页式地址转换	逻辑=页号+页内偏移	2020-11	§C
TLB 命中率	h·t_TLB + (1-h)·(t_TLB+t_页表)	2023-05	§C
串联可靠度	R = Π Ri	2021-05	§D
并联可靠度	R = 1 - Π(1-Ri)	2023-11	§D
混联可靠度	先并后串	2023-11, 2024-05	§D
可用性 A	MTBF/(MTBF+MTTR)	2024-05	§D
海明码校验位数	2^r ≥ m+r+1	2020-11, 2022-05	§E
海明码检错位置	S = 校验组合	2025-05	§E
CRC 余数计算	M·x^k mod G(x)	2024-11	§E
补码范围与转换	取反加 1	2021-11, 2024-05	§F
MIPS 计算	主频/(CPI×10^6)	2022-05	§G
流水线冲突对策	资源重复/转发/分支预测	2024-05	§A

记忆口诀 / 易错点汇总

流水线时间口诀：周期取最大，时间填满加后续（k+n-1 拍）
混联可靠度口诀：先内并（1-Π(1-R)）后外串（Π R）
海明码四步：定 r → 填位置 → 算校验 → 偶/奇验
CRC 四步：补零 → 模 2 除 → 替换 → 校验
补码范围：负多一（n 位补码 = -2^(n-1) ~ +2^(n-1)-1）
浮点 IEEE 754：1+8+23 单精度；偏移 127；隐含 1.M

TIP

避坑建议：

海明码必看偶/奇校验题目要求
CRC 模 2 除法不进位不借位（异或）
混联画框图防分组错
Cache 题注意”读”和”写”分别算命中

交叉引用

本系列笔记

计算机基础速查表：概念速查（PV/页面置换/范式/加密），本篇是其计算题深化版
操作系统深化：PV 操作三大经典模型与银行家算法
数据库网络深化：范式判定与子网计算

主计划文档

详见主计划 §3.1 计算机系统基础的对应内容。

外部延伸

官方教材：《系统架构设计师教程（第 2 版）》§1~§2
真题练习：2020-2025 综合知识计算题（GitHub xxlllq/system_architect）

自测题

流水线：4 段流水线，段时间 3/5/4/6 ns，10 条指令，求总时间与加速比。（答：Δt=6ns，T=78ns，S≈3.08）
可靠性：3 个 R=0.9 部件混联（两串一并），求系统可靠度。（答：1-(1-0.81)(1-0.9)=0.981）
海明码：信息 1011（m=4），求 r 与海明码。（答：r=3，参考 §E 例）
CRC：M=1101, G=1011，求发送码字。（答：1101001，参考 §E 例）
浮点：8 位补码范围是什么？（答：-128~+127）

IMPORTANT

如果只能”看着面熟”但说不出来，说明还没真正掌握，建议回看对应章节并多做真题。

下一篇导引：操作系统深化将讲述 PV 操作三大经典模型、银行家算法、页面置换算法的完整套路，帮助你掌握 OS 模块全部考点。