软考系统架构设计师 · 计算题全集（合并终版）

文档定位：覆盖软考系统架构设计师考试 95% 以上计算题型的单一总文档。
四层结构：① 思维导图+公式速查 → ② 深度推导与演练 → ③ 跨领域综合题 → ④ 速记卡+口诀总表+背诵路线
口诀双轨：每类题型配「顺口溜」+「谐音」两套记忆法，任选其一即可牢记。
合并来源：原《软考架构师计算题型大全_总文档》(26章) + 原《软考架构师计算题总文档》(22题型)，去重保特、深度融合。

---

目录

编号	题型	公式	演练	口诀
一	关键路径法 CPM	✓	3题	✓
二	PERT 三点估算	✓	3题	✓
三	挣值管理 EVM	✓	4题	✓
四	圈复杂度 McCabe	✓	3题	✓
五	功能点分析 FPA	✓	3题	✓
六	COCOMO 模型	✓	3题	✓
七	可靠性计算	✓	4题	✓
八	性能计算（Little/MIPS/Amdahl）	✓	4题	✓
九	流水线计算	✓	2题	✓
十	存储与 Cache	✓	5题	✓
十一	网络划分（子网/VLSM/CIDR）	✓	5题	✓
十二	校验码（海明/CRC/奇偶）	✓	4题	✓
十三	风险分析 EMV 决策树	✓	3题	✓
十四	数据库（关系运算+候选键+范式）	✓	3题	✓
十五	集合运算与容斥原理	✓	2题	✓
十六	面向对象度量 LK	✓	2题	—
十七	PV 操作与同步互斥	✓	5题	✓
十八	内存页面置换算法	✓	5题	✓
十九	内存管理（页式/段式/段页式）	✓	5题	✓
二十	索引（B+树）与文件索引	✓	4题	✓
二一	死锁避免与银行家算法	✓	4题	✓
二二	磁盘调度与进程调度	✓	4题	✓
二三	位示图与空闲区管理	✓	2题	✓
二四	RSA 加密计算	✓	1题	✓
二五	哈夫曼编码	✓	1题	✓
二六	浮点数与补码	✓	1题	✓
二七	二叉树与图论计算	✓	1题	✓
二八	主存编址与总线	✓	1题	✓
二九	跨领域综合题	—	12题	—
三十	速记卡+口诀总表+背诵路线	—	—	✓

---

第1章 思维导图总览

软考架构师计算题型
├── 进度管理
│   ├── 关键路径 CPM：ES/EF/LS/LF/TF/FF
│   ├── PERT 三点估算：(O+4M+P)/6, σ=(P-O)/6
│   └── 赶工决策：斜率最低优先
├── 成本管理
│   ├── 挣值管理 EVM：PV/EV/AC/CPI/SPI/EAC
│   ├── 功能点 FPA：UFC×TCF
│   └── COCOMO：a×KLOC^b
├── 质量与测试
│   ├── 圈复杂度 McCabe：判定+1
│   └── 覆盖标准：语一判二条二组四路二
├── 可靠性
│   ├── 串联 R=∏Ri / 并联 R=1-∏(1-Ri)
│   ├── N模冗余表决 R=ΣC(n,k)R^k(1-R)^(n-k)
│   ├── MTBF/MTTR/可用性 A=MTBF/(MTBF+MTTR)
│   └── 失效率 λ=1/MTBF, R(t)=e^(-λt)
├── 性能
│   ├── Little律 L=λW / 并发=吞吐×响应
│   ├── CPI/MIPS=主频/CPI
│   ├── 阿姆达尔 S=1/((1-p)+p/n), 极限1/(1-p)
│   ├── Gustafson S=np+(1-p)
│   └── 流水线 T=(k+n-1)Δt, S=nk/(k+n-1)
├── 存储体系
│   ├── Cache 命中率/平均访问时间
│   ├── 映射方式（直接/全相联/组相联）
│   ├── 磁盘 IOPS/RAID 容量
│   └── 主存编址/芯片扩展/总线带宽
├── 网络
│   ├── 子网划分/VLSM/CIDR
│   ├── IP聚合（超网）
│   └── 网络号/广播/可用范围
├── 校验码
│   ├── 海明码 2^r≥k+r+1
│   ├── CRC 循环冗余
│   └── 码距与检错纠错
├── 风险
│   ├── EMV=Σ(概率×收益)
│   ├── 决策树（圆算方取）
│   └── 风险暴露度 RE=概率×影响
├── 数据库
│   ├── 关系运算（选择/投影/连接/除）
│   ├── 候选键求法/范式判断
│   └── 无损连接判断
├── 集合运算
│   ├── 容斥原理（两/三集合）
│   ├── 笛卡尔积/幂集/鸽巢
│   └── 排列组合
├── PV操作
│   ├── 信号量/前驱图转PV
│   ├── 生产者-消费者/读者-写者
│   └── 死锁条件/资源数公式
├── 页面置换
│   ├── OPT/FIFO/LRU/CLOCK
│   ├── Belady异常
│   └── 有效访问时间EAT
├── 内存管理
│   ├── 页式/段式/段页式地址转换
│   ├── 访存次数（2/2/3）
│   └── 多级页表
├── 索引
│   ├── B+树阶数与高度
│   ├── 文件索引（直接/一级/二级/三级）
│   └── 最大文件大小
├── 死锁
│   ├── 银行家算法
│   └── 资源数无死锁 m≥n(k-1)+1
├── 调度
│   ├── 磁盘调度（FCFS/SSTF/SCAN/C-SCAN）
│   └── 进程调度（FCFS/SJF/SRTF/RR/HRRN）
├── 其他
│   ├── 位示图/空闲区管理
│   ├── RSA加密
│   ├── 哈夫曼编码WPL
│   ├── 浮点数IEEE754/补码
│   ├── 二叉树度数/最小生成树
│   └── 面向对象度量LK/内聚排序

---

第一部分：公式速查与深度讲解

---

第2章 关键路径法（CPM）

2.1 核心公式

指标	公式	说明
ES（最早开始）	ES = max(所有紧前活动EF)	正向推，遇多入边取最大
EF（最早完成）	EF = ES + 工期	—
LF（最晚完成）	LF = min(所有紧后活动LS)	逆向推，遇多出边取最小
LS（最晚开始）	LS = LF − 工期	—
总时差 TF	TF = LF − EF = LS − ES	=0 则在关键路径上
自由时差 FF	FF = min(紧后ES) − EF	不影响紧后最早开始

关键路径：总时差全为 0 的路径 = 工期最长的路径。

2.2 速算技巧

1. 正向推 ES/EF：从起点出发，加法，遇多入边取最大
2. 逆向推 LS/LF：从终点出发，减法，遇多出边取最小
3. 一眼找关键路径：从终点倒推，每次选 EF 最大的前驱，回溯到起点
4. ⚠️ 易错点：LF = min(紧后LS)，不是 min(紧后LF)！这是最常见的错误。

2.3 赶工成本

$$赶工斜率 = \frac{赶工成本 - 正常成本}{正常工期 - 赶工工期}$$

赶工原则：只压缩关键活动；优先压缩斜率最小的；压缩后重新检查关键路径。

2.4 口诀双轨

类型	口诀
顺口溜	正早最大加，逆晚最小减，时差零关键
谐音	郑早最大家，李晚最小姐，差零关见

2.5 演练例题

例题1：某项目活动如下表，求关键路径、总工期及各活动总时差。

活动	紧前	工期(天)
A	—	3
B	—	5
C	A	4
D	A	6
E	B,C	5
F	D,E	4
G	F	2

第一步：正向推 ES/EF（正早最大加）

活动	ES	EF
A	0	3
B	0	5
C	3	7
D	3	9
E	max(5,7)=7	12
F	max(9,12)=12	16
G	16	18

总工期 = 18 天

第二步：逆向推 LS/LF（逆晚最小减）

活动	LF	LS
G	18	16
F	16	12
E	12	7
D	12	6
C	E的LS=7	7−4=3
B	E的LS=7	7−5=2
A	min(C的LS=3, D的LS=6)=3	3−3=0

第三步：总时差 TF = LF − EF

活动	TF
A	0
B	2
C	0
D	3
E	0
F	0
G	0

关键路径：A→C→E→F→G，工期 18 天。

例题2（自由时差）：FF = min(紧后ES) − EF

活动	紧后	min(紧后ES)	EF	FF
A	C,D	min(3,3)=3	3	0
B	E	7	5	2
C	E	7	7	0
D	F	12	9	3
E	F	12	12	0
F	G	16	16	0
G	—	18	18	0

规律：关键路径上 FF=0；若唯一紧后在关键路径上，FF=TF。

例题3（赶工决策）：需将工期从 18 天压缩到 15 天（压缩 3 天）。

活动	正常工期	赶工工期	正常成本	赶工成本	可压天数	赶工斜率
A	3	2	3000	5000	1	2000
C	4	3	4000	6000	1	2000
E	5	3	5000	8000	2	1500
F	4	2	4000	7000	2	1500
G	2	1	2000	4000	1	2000

策略：优先赶关键路径上斜率最低的活动。

1. 赶 E 压 1 天 → 工期 17，成本 +1500
2. 赶 F 压 1 天 → 工期 16，成本 +1500
3. 赶 E 再压 1 天 → 工期 15，成本 +1500

总赶工成本 = 1500×3 = 4500

2.6 易错避坑

陷阱	说明
LF用紧后LF	LF = min(紧后LS)，不是LF！
ve用min/vl用max	ve正序max，vl逆序min
关键路径多条	总时差=0的活动可能组成多条路径
压缩后路径变	压缩关键活动后可能产生新关键路径

---

第3章 PERT 三点估算

3.1 核心公式

$$T_E = \frac{TO + 4TM + TP}{6}, \quad \sigma = \frac{TP - TO}{6}$$

$$\mu_{路径} = \sum T_{Ei}, \quad \sigma_{路径} = \sqrt{\sum \sigma_i^2}, \quad Z = \frac{目标工期 - \mu}{\sigma_{路径}}$$

• TO = 乐观估计，TM = 最可能估计，TP = 悲观估计

3.2 常用 Z 值表

Z	0	0.5	1.0	1.5	2.0	3.0
概率	50%	69.1%	84.1%	93.3%	97.7%	99.9%

速记：零五十八四九七 → Z=0→50%, Z=1→84%, Z=2→97%, Z=3→99.9%

3.3 口诀双轨

类型	口诀
顺口溜	乐悲加四倍中，除六得期望；极差除以六，标准差便当
谐音	岳飞加四倍中，除六得期望

3.4 演练例题

例题1：TO=8, TM=15, TP=20：

• T_E = (8+4×15+20)/6 = 88/6 = 14.67天
• σ = (20-8)/6 = 2天

例题2（路径概率）：

活动	TO	TM	TP	TE	σ
A	2	4	6	4	0.667
B	3	5	10	5.5	1.167
C	4	6	14	7	1.667

• μ = 4+5.5+7 = 16.5
• σ总 = √(0.667²+1.167²+1.667²) = √4.586 = 2.14
• Z = (18-16.5)/2.14 = 0.70 → 概率 ≈ 75.8%

例题3：σ₁=2, σ₂=3, σ₃=4 → σ总 = √(4+9+16) = √29 ≈ 5.39

---

第4章 挣值管理（EVM）

4.1 三基本值

指标	全称	理解
PV	计划价值	“该干的活预算”
EV	挣值	“已干的活预算”
AC	实际成本	“已花的钱”

4.2 偏差与指数

指标	公式	>0 含义
CV	EV − AC	省钱
SV	EV − PV	超前
CPI	EV / AC	>1 省钱
SPI	EV / PV	>1 超前

4.3 完工预测

指标	公式	适用
EAC（典型）	BAC / CPI	当前偏差代表未来
EAC（非典型）	AC + (BAC − EV)	剩余按计划
EAC（最悲观）	AC + (BAC−EV)/(CPI×SPI)	偏差+进度影响
ETC	EAC − AC	还要花多少
VAC	BAC − EAC	完工偏差
TCPI	(BAC−EV)/(BAC−AC)	剩余必须效率

4.4 EV 的三种给法

题目说法	公式
“完成总工作的 X%”	EV = X% × BAC
“完成计划的 X%”	EV = X% × PV
各活动完成率	EV = Σ(预算ᵢ × 完成率ᵢ)

4.5 口诀双轨

类型	口诀
顺口溜	EV 是核心，减 AC 省成本，减 PV 超进度；CPI 除得 EAC，剩余加 ETC
谐音	衡屋是核心，减埃西省成本，减皮维超进度

4.6 演练例题

例题1：BAC=200万，PV=120万，AC=130万，实际完成计划的80%。

• EV = 80% × PV = 0.8 × 120 = 96万
• CV = 96−130 = −34万（超支）
• SV = 96−120 = −24万（落后）
• CPI = 96/130 = 0.738（<1 超支）
• SPI = 96/120 = 0.800（<1 落后）

例题2（三种EAC对比）：BAC=200, EV=96, AC=130, CPI=0.738, SPI=0.800

假设	EAC 公式	EAC	ETC	VAC
典型	BAC/CPI	271	141	−71
非典型	AC+(BAC−EV)	234	104	−34
最悲观	AC+(BAC−EV)/(CPI×SPI)	306	176	−106

例题3（TCPI）：TCPI = (200−96)/(200−130) = 104/70 = 1.486，剩余必须以1.486效率完成。

例题4（EV三种给法辨析）：

题目说法	公式	示例
“完成总工作40%”	EV=40%×BAC	100万→40万
“完成计划80%”	EV=80%×PV	PV=60→48万
各活动完成率	EV=Σ(预算×完成率)	30×1+50×0.6+20×0=60万

---

第5章 圈复杂度（McCabe）

5.1 三种公式

方法	公式
边节点法	V(G) = E − N + 2
判定节点法	V(G) = 判定节点数 + 1
区域法	V(G) = 封闭区域数 + 1

5.2 速算技巧

• 首选"判定节点+1"：数 if/while/for/switch-case，最快
• 复合条件 if (a && b) 算 2个 判定节点
• switch 的 n 个 case 算 n 个判定节点
• 独立路径数 = V(G)，测试用例下界 = V(G)

5.3 覆盖标准速记

覆盖标准	用例数
语句覆盖	1
判定覆盖	2
条件覆盖	2
判定/条件覆盖	2
条件组合覆盖	4
路径覆盖	2（单判定）

速记：语一判二条二组四路二

5.4 口诀双轨

类型	口诀
顺口溜	边减点加二，判定加一数，区域数最直
谐音	边减点加二，判官加一数

5.5 演练例题

例题1：

void example(int a, int b, int c) {
    if (a > 0) {           // 判定1
        if (b > 0) {       // 判定2
            printf("1");
        }
    }
    while (a < 10) {       // 判定3
        a++;
    }
    if (a > 0 && b > 0) {  // 判定4,5（&&拆开）
        printf("2");
    }
    switch(c) {
        case 1: break;     // 判定6
        case 2: break;     // 判定7
        case 3: break;     // 判定8
    }
}

V(G) = (1+1+1+2+3) + 1 = 9，至少需9个测试用例实现路径覆盖。

例题2：E=15, N=10 → V(G) = 15−10+2 = 7。区域法：6个封闭区域+1=7 ✓

---

第6章 功能点分析（FPA）

6.1 信息域权重表

信息域	低	中	高
外部输入 EI	3	4	6
外部输出 EO	4	5	7
外部查询 EQ	3	4	6
内部逻辑文件 ILF	7	10	15
外部接口文件 EIF	5	7	10

6.2 核心公式

$$UFC = \sum (权重 \times 数量)$$

$$FP = UFC \times (0.65 + 0.01 \times \sum F_i)$$

• 14 个复杂性调节因子 Fi，每个 0~5，ΣFi 范围 0~70
• 基准点：ΣFi=35 时系数=0.65+0.35=1.0，FP=UFC
• 速算：ΣFi 每增 10，系数 +0.1

6.3 LOC/FP 语言对照

语言	LOC/FP
C	128
C++/Java	53
Python	27
COBOL	91
汇编	320

6.4 口诀双轨

类型	口诀
顺口溜	输入查询三四六，输出四五七，接口五七十，逻辑七十十五
谐音	三叔四舅四姑五妻五姐七姨七叔十姥

系数口诀：六五加零点一，因子和来调；三十五为中，恰好等于一

6.5 演练例题

例题1（UFC）：

信息域	数量	复杂度	权重	小计
EI	5	中	4	20
EO	4	高	7	28
EQ	3	低	3	9
ILF	2	中	10	20
EIF	1	高	10	10

UFC = 20+28+9+20+10 = 87

例题2：ΣFi=53 → FP = 87×(0.65+0.01×53) = 87×1.18 = 102.66 ≈ 103

例题3：Java开发，FP=103 → LOC = 103×53 = 5459行 ≈ 5.5KLOC

---

第7章 COCOMO 模型

7.1 基本 COCOMO

$$E = a \times (KLOC)^b, \quad D = c \times E^d$$

项目类型	a	b	c	d	KLOC 范围
有机型	2.4	1.05	2.5	0.38	<50
半分离	3.0	1.12	2.5	0.35	50~300
嵌入型	3.6	1.20	2.5	0.32	>300

7.2 中级 COCOMO

$$E = a \times (KLOC)^b \times \prod EAF_i$$

15 个成本驱动因子乘积调整。

7.3 详细 COCOMO

按阶段（设计/编码/测试等）分别应用驱动因子。

7.4 速算技巧

• b≈1 时，E ≈ a × KLOC
• $KLOC^{0.05} ≈ 1 + 0.05 \times \ln(KLOC)$

7.5 口诀双轨

类型	口诀
顺口溜	二四三六，指数一二；二五不变，周期点三八
谐音	二四三六（2.4,3.6），一零五二零（1.05,1.20）

项目类型口诀：小五十大三百，有机半离嵌

7.6 演练例题

例题1：32KLOC，有机型：

• E = 2.4 × 32^1.05 ≈ 2.4 × 38.05 = 91.3人月
• D = 2.5 × 91.3^0.38 ≈ 2.5 × 5.56 = 13.9月
• 人员数 N = E/D = 91.3/13.9 ≈ 6.6人

例题2：基本E=50人月，EAF=1.35 → E调整 = 50×1.35 = 67.5人月

例题3：有机型50KLOC → E = 2.4 × 50^1.05 ≈ 2.4 × 53.59 ≈ 128.6人月

7.7 易错避坑

陷阱	说明
KLOC单位	千行代码，50KLOC=50000行
类型选错	有机<50KLOC，嵌入>300KLOC
人员数	N=E/D，不是直接给

---

第8章 可靠性计算

8.1 基本概念

指标	全称	含义	公式
MTBF	Mean Time Between Failures	平均无故障时间	—
MTTR	Mean Time To Repair	平均修复时间	—
A	Availability	可用性	A = MTBF / (MTBF + MTTR)
R(t)	Reliability	可靠性	R(t) = e^(-λt)
λ	失效率	单位时间失效概率	λ = 1/MTBF

8.2 串并联

结构	公式
串联	R = ∏Rᵢ
并联	R = 1 − ∏(1−Rᵢ)
两件并联特例	R = R1 + R2 − R1×R2
n个相同并联	R = 1 − (1−R)^n

8.3 N模冗余（表决系统）

n个相同部件，至少k个正常则系统正常：

$$R = \sum_{i=k}^{n} \binom{n}{i} R^i (1-R)^{n-i}$$

三模表决（TMR, n=3, k=2）：R = 3R²(1−R) + R³ = 3R² − 2R³

8.4 失效率与可用性

• 串联：λ总 = Σλi
• 并联（两相同）：MTBF = 1.5 × 单模块 MTBF
• MTTR≪MTBF 时：A ≈ 1 − MTTR/MTBF
• R(t) = e^(-λt)，λt小时 R(t) ≈ 1 − λt

8.5 常用可靠度速记

单元 R	串联(2)	并联(2)
0.9	0.81	0.99
0.8	0.64	0.96
0.99	0.9801	0.9999

8.6 口诀双轨

类型	口诀
顺口溜	串联乘可靠，并联减失效；可用除总时，失效率倒置
谐音	串乘并减，可用除总

补充：两并一倍半（两相同并联 MTBF = 1.5×单模块）；TMR是3R²-2R³

8.7 演练例题

例题1（串并联混合）：A(0.95)与B(0.9)串联，再与两个C(0.8)并联冗余串联：

• R_AB = 0.95 × 0.9 = 0.855
• R_CC = 1 − (1−0.8)² = 1 − 0.04 = 0.96
• R系统 = 0.855 × 0.96 = 0.8208

例题2（2/3表决）：R=0.9 → R = 3×0.9²×0.1 + 0.9³ = 0.243 + 0.729 = 0.972

• 对比：单模块0.9 < 2/3表决0.972 < 3并联0.999

例题3（可用性）：MTBF=1000h, MTTR=10h → A = 1000/1010 = 0.9901 ≈ 99.01%

例题4（并联MTBF）：两相同模块并联，单模块MTBF=1000h → MTBF并联 = 1.5×1000 = 1500h

例题5（失效率）：λ=0.001/小时，t=100h → R(100) = e^(-0.1) ≈ 0.9048

8.8 易错避坑

陷阱	说明
TMR写成R³	用3R²-2R³
串并联搞反	串联相乘、并联用补集
并联失效率	并联不是简单相加，要用可靠度算
TMR门槛	n模冗余k=⌈(n+1)/2⌉

---

第9章 性能计算（Little/MIPS/Amdahl）

9.1 Little 律

$$L = \lambda \times W$$

L=系统中平均请求数，λ=到达率，W=平均响应时间

9.2 吞吐量与并发

$$并发数 = 吞吐量 \times 平均响应时间$$

9.3 CPI 与 MIPS

$$CPI = \frac{\sum (指令数_i \times CPI_i)}{总指令数}, \quad MIPS = \frac{主频(MHz)}{CPI}, \quad 执行时间 = \frac{指令数 \times CPI}{主频}$$

9.4 Amdahl 定律

$$S_n = \frac{1}{(1-p) + p/n}, \quad S_{极限} = \frac{1}{1-p}, \quad 效率 E = \frac{S}{n}$$

p	极限加速比
0.5	2
0.8	5
0.9	10
0.95	20
0.99	100

速记：九成十倍，九五二十，九九一百

9.5 Gustafson定律

固定时间，扩大问题规模：$$S = n \times p + (1 - p)$$

	阿姆达尔	Gustafson
假设	问题规模固定	时间固定，规模扩大
加速比	有上限1/(1-p)	近线性

9.6 口诀双轨

类型	口诀
顺口溜	频除 CPI 得 MIPS，指令乘 CPI 除频得时；阿姆达尔一除串加并除n，极限一减p分之一
谐音	频除 CPI，指 C 除频；一除串并除n

9.7 演练例题

例题1（Little）：λ=50请求/秒, W=0.2秒 → L = 50×0.2 = 10个

例题2（MIPS）：主频2GHz，CPI=1.9 → MIPS = 2000/1.9 = 1052.6；T = 10⁹×1.9/(2×10⁹) = 0.95秒

例题3（Amdahl）：p=0.9, n=10 → S = 1/(0.1+0.09) = 5.26倍；S极限 = 1/0.1 = 10倍

例题4（并发数）：吞吐量100TPS，响应0.05s → 并发 = 100×0.05 = 5

例题5（反求p）：8核加速比5 → 5=1/((1-p)+p/8) → (1-p)+p/8=0.2 → p≈0.914

例题6（反求n）：p=0.95，要S≥10 → 0.05+0.95/n=0.1 → n=19

9.8 易错避坑

陷阱	说明
p是并行占比	不是串行占比，串行是(1-p)
n→∞上限	S_max=1/(1-p)，不是∞
效率=S/n	不是S×n
Gustafson公式	S=np+(1-p)，别和阿姆达尔混

---

第10章 流水线计算

10.1 基本参数

• k：流水线段数（级数），Δt：时钟周期（最长段时间），n：指令条数

10.2 核心公式

$$T = (k + n - 1) \times \Delta t$$

$$TP = \frac{n}{(k + n - 1) \times \Delta t}, \quad TP_{max} = \frac{1}{\Delta t}$$

$$S = \frac{nk}{k + n - 1}, \quad S_{max} = k, \quad E = \frac{n}{k + n - 1}$$

10.3 口诀双轨

类型	口诀
顺口溜	时间k加n减一，吞吐n除总时间；加速nk除以k加n减一，效率S除k
谐音	克加恩减一

10.4 演练例题

例题1：5段流水线，每段1ns，执行100条指令：

• T = (5+100-1)×1 = 104 ns
• TP = 100/104 ≈ 0.962 条/ns
• S = 100×5/104 ≈ 4.81
• E = 100/104 ≈ 0.962

例题2：4段流水线，段时间1ns/2ns/3ns/1ns → Δt = max(1,2,3,1) = 3ns，TP_max = 1/3

10.5 易错避坑

陷阱	说明
Δt取平均	取最长段时间
建立时间	第一条k×Δt，排空(k-1)×Δt

---

第11章 存储与 Cache

11.1 Cache 命中率与平均访问时间

$$命中率\ h = \frac{命中次数}{总访问次数}, \quad 平均访问时间 = h \times t_{cache} + (1-h) \times t_{内存}$$

11.2 多级Cache

两级Cache：t_avg = h1×t1 + (1-h1)×[h2×t2 + (1-h2)×t_mem]

11.3 Cache映射方式

方式	地址结构	特点
直接映射	Tag+行号+块内偏移	每块唯一位置，冲突多
全相联	Tag+块内偏移	任意位置，比较慢
组相联	Tag+组号+组内行号+偏移	折中，n路组相联

例：主存1MB，Cache 32KB，块64B，直接映射：

• 主存块数=16384(14位)，Cache行数=512(9位)，偏移6位
• 地址 = Tag(5) + 行号(9) + 偏移(6) = 20位

11.4 写策略

策略	说明
写直达(Write Through)	同时写Cache和主存，简单但慢
写回(Write Back)	只写Cache，替换时写回，需脏位
写分配	写缺失时先调入Cache再写
不写分配	写缺失直接写主存

11.5 磁盘 IOPS

$$IOPS = \frac{1000}{平均寻道 + 旋转延迟 + 传输时间}(ms), \quad 旋转延迟 = \frac{30000}{转速(rpm)}$$

转速	旋转延迟
7200	4.17ms
10000	3ms
15000	2ms

11.6 内存编址

• 1KB=2¹⁰, 1MB=2²⁰, 1GB=2³⁰
• 容量 = 末地址 − 首地址 + 1
• 末地址 = 起始地址 + 容量 − 1
• 芯片数 = 总容量 / 单片容量

11.7 RAID 可用容量

级别	可用容量	最少盘数
RAID 0	N	2
RAID 1	N/2	2
RAID 5	(N−1)	3
RAID 6	(N−2)	4
RAID 10	N/2	4

11.8 口诀双轨

类型	口诀
顺口溜	K十M二十G三十，容量除片得片数
谐音	凯十埃姆二十吉三十

RAID口诀：0全1半5减1，6减2加10半

11.9 演练例题

例题1：h=0.9, t_cache=20ns, t_mem=100ns → T = 0.9×20+0.1×100 = 28ns

例题2：缺失率5%，每指令访存1.5次，缺失代价100周期 → Stalls = 0.05×1.5×100 = 7.5周期

例题3：7200RPM，寻道8ms → IOPS = 1000/(8+4.17) = 82.2

例题4：起始A0000H，容量32KB=8000H → 末地址 = A0000H+8000H−1 = A7FFFH

例题5：6块2TB硬盘：RAID0=12TB, RAID1=6TB, RAID5=10TB, RAID6=8TB, RAID10=6TB

---

第12章 网络划分（子网/VLSM/CIDR）

12.1 IP地址分类

类	首位	默认掩码	主机位	每网主机数
A	0	/8	24	2^24-2
B	10	/16	16	2^16-2
C	110	/24	8	254

12.2 子网划分

• 子网数 = 2ⁿ（n=借的位数）
• 每子网主机数 = 2ʰ − 2（h=主机位剩余）
• 子网掩码：/(24+n) → 最后段 = 256 − 2ʰ
• 子网步长 = 2ʰ

12.3 VLSM（可变长子网掩码）

不同子网使用不同掩码长度，按需求从大到小分配。

1. 按主机需求降序排列
2. 每个求最小2的幂（≥需求+2）
3. 依次分配连续地址块

12.4 CIDR（路由聚合/超网）

将多个连续网络合并为一条路由。判断能否聚合：起始地址在聚合后块内对齐。

12.5 掩码速算

/n	十进制
/24	255.255.255.0
/25	255.255.255.128
/26	255.255.255.192
/27	255.255.255.224
/28	255.255.255.240
/29	255.255.255.248
/30	255.255.255.252

末字节 = 256 − 2^(32-n)

12.6 口诀双轨

类型	口诀
顺口溜	借n位出二n网，主机位减二得数；VLSM从大往小分，CIDR聚合找对齐
谐音	借位出网，主机减二

12.7 演练例题

例题1：192.168.1.0/24，需6个子网，每子网≥25主机：

• n=3（2³=8≥6），h=5（2⁵−2=30≥25），掩码/27，步长32

子网	网络地址	可用范围	广播
1	.0	.1~.30	.31
2	.32	.33~.62	.63
3	.64	.65~.94	.95
4	.96	.97~.126	.127
5	.128	.129~.158	.159
6	.160	.161~.190	.191

例题2（同子网判断）：IP1=192.168.1.130, IP2=192.168.1.165, /26 → 步长64，边界0/64/128/192。130和165都在128~191 → 同子网

例题3（VLSM）：172.16.0.0/16分配：总部500、分部A 200、B 100、C 50、D 25

• 总部500→/23，172.16.0.0/23
• A 200→/24，172.16.2.0/24
• B 100→/25，172.16.3.0/25
• C 50→/26，172.16.3.128/26
• D 25→/27，172.16.3.192/27

例题4（CIDR聚合）：聚合192.168.0.0/24~192.168.3.0/24 → 4个/24=2² → /22，聚合后192.168.0.0/22

例题5（网络号/广播）：172.16.5.0/22 → 块大小1024，第三字节块大小4，5/4=1，网络号172.16.4.0，广播172.16.7.255，可用172.16.4.1~172.16.7.254

12.8 易错避坑

陷阱	说明
主机数-2	全0和全1不可用
子网数是否-2	现代CIDR不-2
VLSM顺序	从大到小
聚合对齐	起始地址必须对齐块大小

---

第13章 校验码（海明/CRC/奇偶）

13.1 海明码

校验位r位，信息位k位：$$2^r \geq k + r + 1$$

数据位 k	校验位 r
1~4	3
5~11	4
12~26	5
27~57	6

海明码位置：校验位在2^i位置（1,2,4,8…），信息位填其余。
纠错：S的十进制值 = 出错位号
纠错能力：r位校验可纠1位错，检2位错。

13.2 码距与检错纠错

• 检 e 错：码距 ≥ e+1
• 纠 t 错：码距 ≥ 2t+1
• 同时检 e 纠 t（e>t）：码距 ≥ e+t+1

13.3 CRC循环冗余校验

1. 信息位后补 k 个 0（k=生成多项式位数−1）
2. 模 2 除（异或）生成多项式
3. 余数 = CRC 校验码

13.4 奇偶校验

• 奇校验：使1的个数为奇数
• 偶校验：使1的个数为偶数
• 只能检奇数位错，不能纠错

13.5 口诀双轨

类型	口诀
顺口溜	海明二r大于k加r加一，校验位在二的幂；CRC模二除取余，奇偶只检奇数错
谐音	二阿大于克加阿加一

13.6 演练例题

例题1：m=16 → r=5（2⁵=32≥22），总长21位

例题2（海明码纠错）：接收1011001（位7~位1）：

• S1 = 位1⊕位3⊕位5⊕位7 = 1⊕1⊕0⊕1 = 1
• S2 = 位2⊕位3⊕位6⊕位7 = 0⊕1⊕0⊕1 = 0
• S4 = 位4⊕位5⊕位6⊕位7 = 1⊕0⊕0⊕1 = 0
• S=S4S2S1=001=1 → 位1出错，纠错后：1011000

例题3（海明码编码）：信息1010，求海明码。

• 校验位P1(1),P2(2),P3(4)，信息D1=1(3),D2=0(5),D3=1(6),D4=0(7)
• P1 = D1⊕D2⊕D4 = 1⊕0⊕0 = 1
• P2 = D1⊕D3⊕D4 = 1⊕1⊕0 = 0
• P3 = D2⊕D3⊕D4 = 0⊕1⊕0 = 1
• 海明码 = 1,0,1,1,0,1,0 → 1011010

例题4（CRC）：信息位1010，G(x)=1011：

1. 补3个零：1010000
2. 模2除1011 → 余数=100
3. 发送码 = 1010100

---

第14章 风险分析（EMV决策树）

14.1 期望货币价值

$$EMV = \sum (概率_i \times 收益_i), \quad 风险暴露度\ RE = 概率 \times 影响$$

14.2 决策树

• 机会节点（圆圈）：取 EMV（加权平均）
• 决策节点（方框）：取 max（选最大收益）
• 从右向左算（叶→根）
• 概率和必须 = 1（验算）

14.3 口诀双轨

类型	口诀
顺口溜	圆圈算期望，方框取最大；从右向左推，概率和为一
谐音	圆算方取，右左推一

14.4 演练例题

例题1（决策树）：

方案	高需求(0.6)	低需求(0.4)	投资
大厂	年100万	年20万	300万
小厂	年40万	年30万	100万

10年净收益：大厂高700/低−100，小厂高300/低200

• EMV大厂 = 0.6×700+0.4×(−100) = 380万
• EMV小厂 = 0.6×300+0.4×200 = 260万
• 选建大厂

例题2：A成功(0.7)170/失败(0.3)−80；B成功(0.7)140/失败(0.3)−30

• EMV_A = 0.7×170+0.3×(−80) = 95万
• EMV_B = 0.7×140+0.3×(−30) = 89万
• 选A

例题3：概率5%，损失200万 → RE = 0.05×200 = 10万元，缓解措施投入不应超过10万

---

第15章 数据库计算（关系运算+候选键+范式）

15.1 关系运算

运算	符号	含义	结果度数
选择	σ_F®	选取满足条件F的元组	元组数≤|R|，属性同R
投影	π_A®	选取属性集A的列	属性数=|A|，元组去重
并	R∪S	两关系元组合并	要求同模式
差	R-S	在R中不在S中	要求同模式
笛卡尔积	R×S	元组两两拼接	度数=度®+度(S)，|R×S|=|R|·|S|
连接	R⋈_{F}S	笛卡尔积后选择满足F	—
自然连接	R⋈S	等值连接+去重复属性	度数=度®+度(S)-公共属性数
除	R÷S	象象运算，常用于"全部"	度数=度®-度(S)

15.2 除运算计算步骤

1. 设R(X,Y)，S(Y)，X是R中Y以外的属性
2. 结果 = π_X® - π_X( (π_X® × S) - R )

例：R(A,B)={(a1,b1),(a1,b2),(a2,b1),(a3,b1),(a3,b2)}，S(B)={(b1),(b2)}

• π_A®={a1,a2,a3}，π_A®×S={(a1,b1),(a1,b2),(a2,b1),(a2,b2),(a3,b1),(a3,b2)}
• (π_A®×S)-R = {(a2,b2)}，π_A(…)={a2}
• R÷S = {a1,a2,a3}-{a2} = {a1,a3}

15.3 候选键求法

1. 只在左部出现的属性 → 必在候选键中
2. 既不在左部也不在右部 → 必在候选键中
3. 只在右部出现的属性 → 必不在候选键中
4. 剩余属性与必在属性组合，看能否函数决定全属性

15.4 范式判断

范式	条件
1NF	属性不可分
2NF	非主属性完全依赖候选键（消除部分依赖）
3NF	非主属性不传递依赖候选键（消除传递依赖）
BCNF	所有决定因素都是候选键
4NF	消除非平凡多值依赖

15.5 口诀双轨

类型	口诀
顺口溜	选择挑行投影列，投影去重记心间；笛卡尔积行相乘，自然连接去重叠；一不可分，二消部分，三消传递，BC决定必键
谐音	一分二部三传，毕决定必键

候选键口诀：左必入，右必不入，待定要组合

15.6 演练例题

例题1（候选键）：R(A,B,C,D,E)，F={A→B, B→C, C→D, DE→A}

• E只在左部→必在；其余待定
• {E,A}⁺={A,B,C,D,E}✓，{E,B}⁺=✓，{E,C}⁺=✓，{E,D}⁺=✓
• 候选键：EA, EB, EC, ED

例题2（范式）：R(A,B,C,D)，F={A→B, A→C, C→D}，候选键=A

• 1NF✓ 2NF✓（A单属性无部分依赖） 3NF✗（A→C→D传递依赖）
• 属于2NF不属于3NF，分解为3NF：R1(A,B,C), R2(C,D)

例题3（无损连接）：R(A,B,C,D)，F={A→B, B→C}，分解R1(A,B)和R2(B,C,D)

• R1∩R2={B}，B→C已知但B→D未知 → 有损连接

例题4（元组数）：R(A,B,C,D)有100元组，S(C,D,E)有50元组

• R×S：元组数=5000，度数=7
• R⋈S（自然连接）：度数=5，元组数≤5000
• π_{A,B}®：度数=2，元组数≤100

15.7 易错避坑

陷阱	说明
投影不去重	投影自动去重，集合语义
自然连接度数	度数=度®+度(S)-公共属性数
除运算方向	R÷S，结果属性是R中S没有的

---

第16章 集合运算与容斥原理

16.1 基本公式

运算	公式
并	|A∪B| = |A|+|B|-|A∩B|
三集合容斥	|A∪B∪C| = |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
差	|A-B| = |A| - |A∩B|
对称差	|A△B| = |A|+|B|-2|A∩B|
笛卡尔积	|A×B| = |A|·|B|
幂集	|P(A)| = 2^|A|

16.2 鸽巢原理

n个物品放入m个盒子，至少有一个盒子有⌈n/m⌉个物品。

16.3 排列组合

$$P(n,r) = \frac{n!}{(n-r)!}, \quad C(n,r) = \frac{n!}{r!(n-r)!}$$

值	结果
C₅²	10
C₆²	15
C₆³	20
C₇³	35
C₈³	56

16.4 德摩根定律

• (A∪B)^c = A^c ∩ B^c
• (A∩B)^c = A^c ∪ B^c

16.5 口诀双轨

类型	口诀
顺口溜	容斥加减交替来，笛卡尔积有序对；幂集二的全集次，鸽巢向上取整排
谐音	容斥交替，笛卡有序，幂集二n次

16.6 演练例题

例题1：某班30人，学英语20、数学18、编程15，英数10、英编8、数编7，三门5。

• |A∪B∪C| = 20+18+15-10-8-7+5 = 33

例题2：100人中60喜欢A、50喜欢B，求同时喜欢A和B的最小值。

• |A∩B| = |A|+|B|-|A∪B| ≥ 60+50-100 = 10

---

第17章 面向对象度量（LK）

17.1 LK 度量

指标	含义
WMC	类中方法复杂度之和
DIT	继承树深度
NOC	直接子类数
CBO	耦合类数
RFC	响应集大小
LCOM	内聚度量（方法交集越小内聚越差）

17.2 内聚类型（从低到高）

级别	名称	说明
1	偶然内聚	无直接关系
2	逻辑内聚	功能相似
3	时间内聚	同时执行
4	过程内聚	按特定顺序
5	通信内聚	同一数据集
6	顺序内聚	输出为输入
7	功能内聚	单一功能

口诀：偶逻时过通顺功 / 谐音：我老师过通顺功

17.3 演练例题

例题1：A←B←C, D继承B

类	DIT	NOC	所有后代
A	0	1	B,C,D
B	1	2	C,D
C	2	0	—
D	2	0	—

---

第18章 PV 操作与同步互斥

18.1 信号量基本操作

操作	语义	代码	信号量变化
P(S) / wait(S)	申请资源	S = S − 1	S<0 则阻塞等待
V(S) / signal(S)	释放资源	S = S + 1	S≤0 则唤醒一个等待进程

18.2 信号量分类

类型	初值	含义
互斥信号量	1	保护临界区，同一时刻只允许1个进程进入
同步信号量	0	前驱关系：V在前驱之后，P在后继之前
资源信号量	n	表示有n个同类资源可用

18.3 经典模型

生产者-消费者（缓冲区容量N）：

semaphore mutex=1, empty=N, full=0;
生产者: P(empty); P(mutex); 放产品; V(mutex); V(full);
消费者: P(full);  P(mutex); 取产品; V(mutex); V(empty);

⚠️ P操作顺序不能颠倒：先P(empty/full)再P(mutex)，否则死锁！

读者-写者（读者优先）：

semaphore mutex=1, wsem=1; int readcount=0;
读者: P(mutex); readcount++; if(readcount==1) P(wsem); V(mutex);
      读书;
      P(mutex); readcount--; if(readcount==0) V(wsem); V(mutex);
写者: P(wsem); 写书; V(wsem);

18.4 前驱图转 PV 操作

规则：每条有向边 A→B 对应一个同步信号量 S=0：

• A 的末尾加 V(S)
• B 的开头加 P(S)

18.5 信号量取值范围

• 互斥信号量 S 初值=1：取值范围 [−(n−1), 1]（n个进程竞争）
• 资源信号量 S 初值=n：取值范围 [−(m−n), n]
• S<0时|S|=等待进程数

18.6 口诀双轨

类型	口诀
顺口溜	P申请减一负则等，V释放加一唤等待；互斥初一同步零，资源初值等于N
谐音	皮减负等，维加唤等；互一同零资N

前驱图口诀：前驱末尾V，后继开头P，每边一信号

18.7 演练例题

例题1（前驱图转PV）：S1→S2, S1→S3, S2→S4, S3→S4, S4→S5

边	信号量
S1→S2	a=0
S1→S3	b=0
S2→S4	c=0
S3→S4	d=0
S4→S5	e=0

S1: ...; V(a); V(b);
S2: P(a); ...; V(c);
S3: P(b); ...; V(d);
S4: P(c); P(d); ...; V(e);
S5: P(e); ...;

例题2（取值范围）：3个进程竞争互斥信号量S(初值=1)

• 1个P后S=0，2个P后S=−1，3个P后S=−2
• 取值范围 [−2, 1]

例题3：缓冲区容量5，2生产者3消费者 → empty=5, full=0, mutex=1

例题4（循环等待死锁）：4个进程4个信号量(初值0)，P1:P(S4);V(S1); P2:P(S1);V(S2); P3:P(S2);V(S3); P4:P(S3);V(S4) → 死锁（循环等待，无进程能先执行V）

例题5：5读者同时读，1写者等待 → readcount=5, wsem=0(被读者P了), mutex=1

18.8 易错避坑

陷阱	说明
P/V顺序	生产者P(empty)在P(mutex)前
信号量初值	互斥=1，同步=0，资源=资源数
S<0含义	|S|=等待进程数

---

第19章 内存页面置换算法

19.1 四种算法对比

算法	置换策略	特点
OPT	淘汰未来最久不用的页	理论最优，无法实现
FIFO	淘汰最先进入的页	可能有Belady异常
LRU	淘汰最近最久未用的页	无Belady异常，性能好
CLOCK	淘汰访问位=0的页（二次机会）	LRU的近似实现

19.2 缺页率

$$缺页率 = \frac{缺页次数}{总访问次数}$$

• 首次访问必然缺页；置换时必然缺页；命中时不缺页

19.3 Belady 异常

• FIFO：分配页面数增加，缺页率可能反而增加
• LRU/OPT：不会出现Belady异常（满足栈式算法性质）
• CLOCK：可能出现Belady异常

经典Belady序列：1,2,3,4,1,2,5,1,2,3,4,5（3框缺页9次，4框缺页10次）

19.4 有效访问时间（含TLB）

$$EAT = h \times (t_{TLB} + t_{内存}) + (1-h) \times (t_{TLB} + 2 \times t_{内存})$$

• 命中TLB：查TLB + 1次访存取数据
• 未命中TLB：查TLB + 查页表(1次访存) + 取数据(1次访存) = 2次访存

19.5 口诀双轨

类型	口诀
顺口溜	最优未来最远，先进先出最早，最近最久未用，时钟二次机会
谐音	优远先早近久时二

Belady口诀：FIFO可能反常，LRU永不反常

19.6 演练例题

例题1（FIFO）：序列7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，3块

• 缺页次数=15，缺页率=75%

例题2（LRU）：同一序列，3块

• 缺页次数=12，缺页率=60%

例题3（OPT）：序列1,2,3,4,1,2,5,1,2,3,4,5，3块

• 缺页次数=7

例题4（EAT）：TLB命中率95%，TLB 20ns，内存100ns

• EAT = 0.95×(20+100) + 0.05×(20+100+100) = 114+11 = 125ns

---

第20章 内存管理（页式/段式/段页式）

20.1 页式存储

地址结构：逻辑地址 = 页号 | 页内偏移

参数	公式
页号	页号 = 逻辑地址 / 页大小（整除）
页内偏移	偏移 = 逻辑地址 % 页大小
物理地址	物理地址 = 物理块号 × 页大小 + 页内偏移
页表长度	页表项数 = 逻辑地址空间 / 页大小

20.2 段式存储

地址结构：逻辑地址 = 段号 | 段内偏移

• 物理地址 = 段基址 + 段内偏移
• ⚠️ 需检查：段内偏移 < 段长（越界检查）

20.3 段页式存储

地址结构：逻辑地址 = 段号 | 页号 | 页内偏移

地址转换（3次访存）：

1. 查段表 → 得到页表起始地址
2. 查页表 → 得到物理块号
3. 物理块号 × 页大小 + 偏移 → 物理地址

20.4 多级页表

参数	公式
每级页表项数	页大小 / 页表项大小
页目录项数	2^(虚拟地址位数 − 页偏移位数 − 页表索引位数)

例：32位地址，4KB页，4B页表项 → 每页表1024项 → 10位页号 + 10位页目录 + 12位偏移

20.5 访存次数总结

机制	无TLB	有TLB命中	有TLB未命中
页式	2（页表+数据）	1	2
段式	2（段表+数据）	1	2
段页式	3（段表+页表+数据）	1	3
二级页表	3（目录+页表+数据）	1	3

20.6 口诀双轨

类型	口诀
顺口溜	页式除余偏移定，段式基址加偏移；段页三次访存，页式两次段式两次
谐音	页除余偏，段基加偏；段页三访，页二段二

20.7 演练例题

例题1（页式）：页面4KB，页表[0→2,1→5,2→7,3→8]，逻辑地址0x3C8A

• 页号 = 0x3C8A / 0x1000 = 3，偏移 = 0x8A
• 物理地址 = 8 × 0x1000 + 0x8A = 0x8C8A

例题2（段式）：段表[2→基址0x5000,段长0x1000]，逻辑地址(段号=2,偏移=0x500)

• 越界检查：0x500 < 0x1000 ✓
• 物理地址 = 0x5000 + 0x500 = 0x5500

例题3（段页式）：段号1→页表0x2000，页号2→块号10，页大小1KB，偏移0x0FF

• 物理地址 = 10 × 1KB + 0x0FF = 0x2800 + 0x0FF = 0x28FF
• 访存3次

例题4（多级页表）：32位地址，4KB页，4B页表项 → 10(目录)+10(页表)+12(偏移)=32

例题5（页表占用）：4GB空间，4KB页，4B页表项

• 页表项数 = 4GB/4KB = 1M项，页表大小 = 1M×4B = 4MB

20.8 易错避坑

陷阱	说明
段页式访存3次	不是2次
物理地址用块号×页面大小	不是块号×偏移
段越界检查	分段/段页式要检查偏移<段长

---

第21章 索引（B+树）与文件索引

21.1 B树与B+树

特性	B树(m阶)	B+树(m阶)
每节点最多关键字	m-1	m-1
每节点最少关键字	⌈m/2⌉-1	⌈m/2⌉-1
关键字存储	所有节点	非叶仅索引，叶存全部
查找路径	可在非叶终止	必到叶子

B+树高度：h ≈ log_m(n)，查找I/O次数 = 树高h

21.2 文件索引（UNIX inode）

索引类型	项数	可寻址块数	可寻址字节
直接索引	10	10	10×B
一级间接	1	n	n×B
二级间接	1	n²	n²×B
三级间接	1	n³	n³×B

$$n = B / I（块大小/索引项大小）, \quad 最大文件 = 10B + nB + n^2B + n^3B$$

典型值：B=4KB, I=4B → n=1024：直接40KB + 一级4MB + 二级4GB + 三级4TB

21.3 文件分配方式

方式	特点	优点	缺点
连续分配	文件占连续磁盘块	顺序访问快	外部碎片
链接分配	每块含下一块指针	无外部碎片	随机访问慢
索引分配	索引块存所有块号	随机访问快	索引开销

21.4 磁盘物理地址

$$磁盘容量 = 柱面数 \times 磁头数 \times 扇区数 \times 扇区大小$$

• 柱面号 = LBN / (磁头数 × 扇区数)
• 磁头号 = (LBN % (磁头数 × 扇区数)) / 扇区数
• 扇区号 = LBN % 扇区数

21.5 口诀双轨

类型	口诀
顺口溜	m阶最多m减一，最少上取整减一；查找次数等树高，B加必到叶子找；直接十块一级n，二级n方三n三方
谐音	直十一n二n方三n三方

21.6 演练例题

例题1：10000关键字，m=100阶B+树 → h ≈ log_100(10000) = 2，查找2次I/O

例题2（一级索引）：块4KB，索引项4B，10直接+1一级 → n=1024，最大=10×4KB+1024×4KB = 40KB+4MB

例题3（三级索引）：块1KB，索引项4B → n=256

• 直接10KB + 一级256KB + 二级64MB + 三级16GB ≈ 16GB

例题4（磁盘容量）：200柱面×16磁头×63扇区×512B = 103,219,200B ≈ 98.4MB

例题5（LBN转物理）：4磁头，每磁道16扇区，LBN=50

• 每柱面扇区=64，柱面=50/64=0，磁头=(50%64)/16=3，扇区=50%16=2

21.7 易错避坑

陷阱	说明
B树vs B+树	B+树必到叶子
阶数m含义	m是最大子节点数，最大关键字m-1
n的计算	n=块大小/索引项大小

---

第22章 死锁避免与银行家算法

22.1 死锁四大必要条件

1. 互斥：资源不能共享
2. 占有并等待：持有资源同时申请新资源
3. 不剥夺：不能强行夺走资源
4. 循环等待：存在进程-资源的环形链

22.2 银行家算法

矩阵	含义
Available	系统当前可用资源向量
Max	每个进程最大需求矩阵
Allocation	每个进程已分配矩阵
Need	每个进程还需资源 = Max − Allocation

安全性算法：

1. Work = Available; Finish[i] = false
2. 找 Finish[i]==false 且 Need[i] <= Work 的进程i
3. 若找到：Work = Work + Allocation[i]; Finish[i] = true; 回到步骤2
4. 若所有 Finish[i]==true → 安全序列；否则 → 不安全

22.3 资源数与死锁关系

m个资源，n个进程，每个最多申请k个：

$$无死锁条件：m \geq n \times (k - 1) + 1$$

推导：最坏情况每个进程拿到k−1个（差一个），再多1个就能让某进程完成。

22.4 死锁策略对比

策略	时机	方法	代价
预防	事前	破坏四大条件之一	资源利用率低
避免	运行时	银行家算法	计算开销大
检测	运行时	资源分配图化简	需恢复机制

22.5 口诀双轨

类型	口诀
顺口溜	互占不循四条件，安全序列逐个找；Need小于Work则分配，全完成则安全
谐音	互占不循，需小工则分，全成则安

资源数口诀：m ≥ n(k−1)+1

22.6 演练例题

例题1（安全序列）：Available=(10,5,7)

进程	Max	Allocation	Need
P1	(7,5,3)	(0,1,0)	(7,4,3)
P2	(3,2,2)	(2,0,0)	(1,2,2)
P3	(9,0,2)	(3,0,2)	(6,0,0)
P4	(2,2,2)	(2,1,1)	(0,1,1)
P5	(4,3,3)	(0,0,2)	(4,3,1)

步骤	进程	Work	Need≤Work?	Work+Alloc
1	P1	(10,5,7)	✓	(10,6,7)
2	P2	(10,6,7)	✓	(12,6,7)
3	P3	(12,6,7)	✓	(15,6,9)
4	P4	(15,6,9)	✓	(17,7,10)
5	P5	(17,7,10)	✓	(17,7,12)

安全序列：<P1,P2,P3,P4,P5>

例题2（资源请求）：接上，P1请求(1,0,2)

• Request≤Need ✓，Request≤Available ✓
• 试探：Available=(9,5,5), Allocation[P1]=(1,1,2), Need[P1]=(6,4,1)
• 安全性检查通过 → 真正分配

例题3（资源数）：m=12, n=3, k=4 → 12≥3×3+1=10 ✓ 无死锁
m=9 < 10 → 可能死锁

---

第23章 磁盘调度与进程调度

23.1 磁盘调度算法

算法	策略	特点
FCFS	按请求顺序服务	公平，寻道距离大
SSTF	最短寻道时间优先	性能好，可能饥饿
SCAN	电梯算法，单向扫描到端再折返	无饥饿
C-SCAN	单向扫描到端，直接跳回起点	响应均匀
LOOK	SCAN改进，到最后请求即折返	不走到底
C-LOOK	C-SCAN改进，到最后请求即跳回	不走到底

23.2 进程调度算法

算法	策略
FCFS	先来先服务
SJF	短作业优先（非抢占）
SRTF	最短剩余时间优先（抢占式SJF）
优先级调度	按优先级
时间片轮转RR	每个进程分配固定时间片
多级反馈队列	多队列+不同时间片+降级
HRRN	最高响应比优先

23.3 调度指标

指标	公式
周转时间	完成时间 − 到达时间
等待时间	周转时间 − 运行时间
带权周转时间	周转时间 / 运行时间
平均周转时间	Σ周转时间 / 进程数
响应比	(等待时间 + 服务时间) / 服务时间
CPU利用率	CPU忙时间 / 总时间

23.4 口诀双轨

类型	口诀
顺口溜	先来先服务最公平，最短寻道性能好；电梯扫描到端折返，循环扫描只走一边；周转等于完成减到达，等待等于周转减运行
谐音	先先公，短短好，电扫折返环扫单

23.5 演练例题

例题1（磁盘调度）：磁头在53，请求：98,183,37,122,14,124,65,67，向大方向

• FCFS：53→98→183→37→122→14→124→65→67，总寻道=640
• SSTF：53→65→67→37→14→98→122→124→183，总寻道=236
• SCAN：53→65→67→98→122→124→183→37→14，总寻道=299
• C-SCAN：53→65→67→98→122→124→183→14→37，总寻道=350
• 对比：SSTF(236) < SCAN(299) < C-SCAN(350) < FCFS(640)

例题2（FCFS vs SJF）：

进程	到达	运行
P1	0	7
P2	2	4
P3	4	1
P4	5	4

FCFS：平均周转=(7+9+8+11)/4=8.75，平均等待=4.75
SJF：P1(0-7)→P3(7-8)→P2(8-12)→P4(12-16)，平均周转=(7+4+10+11)/4=8.0，平均等待=4.0

例题3（SRTF抢占）：

进程	到达	运行
P1	0	7
P2	2	4
P3	4	1

• 0-2:P1, 2-4:P2, 4-5:P3, 5-8:P2, 8-12:P1
• 平均周转=(12+6+1)/3=6.33

例题4（RR时间片q=1）：

进程	到达	运行
P1	0	5
P2	1	3
P3	2	1

• 0-1:P1, 1-2:P2, 2-3:P3, 3-4:P1, 4-5:P2, 5-6:P1, 6-7:P2, 7-8:P1
• P1完成8周转8, P2完成7周转6, P3完成3周转1
• 平均周转=(8+6+1)/3=5

---

第24章 位示图与空闲区管理

24.1 位示图法

• 每个磁盘块对应1 bit：1=已分配，0=空闲
• 位示图大小 = 磁盘总块数 / 8 字节
• 块号→位示图位置：行 = 块号 / 字长，列 = 块号 % 字长

24.2 空闲区分配算法

算法	策略	特点
首次适应	从头找第一个足够大的	简单，低址碎片多
最佳适应	找最小的足够大的	小碎片多
最坏适应	找最大的	大请求难满足
循环首次适应	从上次位置继续找	碎片分布均匀

24.3 口诀双轨

类型	口诀
顺口溜	位图一位代表一块，一为分配零空闲；首适最佳最坏循环，分配策略各不同
谐音	位图一零，首佳最循

24.4 演练例题

例题1：磁盘1000块，字长16位，块号35

• 行=35/16=2，列=35%16=3，位示图大小=1000/16=63字=126字节

例题2：空闲区{(10,30),(50,10),(80,50),(120,20)}，请求分配20块

• 首次适应：选(10,30)，剩余(30,10)
• 最佳适应：选(120,20)（最小够用），剩余无
• 最坏适应：选(80,50)（最大），剩余(100,30)

---

第25章 RSA 加密计算

25.1 RSA步骤

1. 选两素数p, q
2. n = p × q
3. φ(n) = (p-1)(q-1)（欧拉函数）
4. 选e：1<e<φ(n)，gcd(e,φ(n))=1
5. 求d：e×d ≡ 1 (mod φ(n))（模逆元，扩展欧几里得）
6. 公钥(e,n)，私钥(d,n)
7. 加密：C = M^e mod n
8. 解密：M = C^d mod n

25.2 口诀双轨

类型	口诀
顺口溜	RSA选两素数乘，欧拉减一减一乘；公钥e私钥d，模逆元扩展欧几里得
谐音	两素乘欧拉减减

25.3 演练例题

例题：p=5, q=11, e=3，明文M=2

• n = 5×11 = 55
• φ = (5-1)(11-1) = 40
• 求d：3×d ≡ 1 (mod 40)，d=27（3×27=81=2×40+1）
• 加密：C = 2³ mod 55 = 8
• 解密：M = 8²⁷ mod 55 = 2

---

第26章 哈夫曼编码

26.1 构造与WPL

带权路径长度(WPL) = Σ(权值 × 路径长度)

重要技巧：WPL = 所有非叶节点（合并产生的新节点）权值之和。

• n个叶子 → 共2n-1个节点，没有度1节点

26.2 平均编码长度与压缩率

• 平均编码长度 = WPL / 总频率
• 压缩率 = 1 - 哈夫曼平均长度 / 原编码长度

26.3 口诀双轨

类型	口诀
顺口溜	哈夫曼每次取最小两，WPL新节点权值和；平均长度除总频，前缀编码不冲突
谐音	新节点权和

26.4 演练例题

例题：A:45, B:13, C:12, D:16, E:9

• 构造：E(9)+C(12)=21, B(13)+D(16)=29, 21+29=50, 50+A(45)=95
• WPL = 21+29+50+95 = 195
• 验证：A:45×1=45, B:13×3=39, D:16×3=48, C:12×3=36, E:9×3=27 → 195 ✓
• 总频率=95，平均长度=195/95≈2.053位
• 原等长3位，压缩率=1-2.053/3=31.6%

---

第27章 浮点数与补码

27.1 IEEE 754

格式	总位	符号	阶码	尾数	偏置
单精度	32	1	8	23	127
双精度	64	1	11	52	1023

值 = (-1)^S × 1.M × 2^(E-偏置)（规格化）

27.2 补码范围

n位补码：-2^(n-1) ~ 2^(n-1)-1

• 8位：-128 ~ 127
• 16位：-32768 ~ 32767

27.3 移码

n位移码 = 补码符号位取反，IEEE754阶码用移码（偏置127）。

27.4 浮点运算步骤

1. 对阶：小阶向大阶看齐（尾数右移）
2. 尾数求和：相加/相减
3. 规格化：尾数调整为1.x形式
4. 舍入：超出位舍入
5. 溢出判断：阶码溢出

27.5 口诀双轨

类型	口诀
顺口溜	IEEE阶码减偏置，尾数隐含一点M；补码负数取反加一，范围负二正二减一
谐音	阶减偏置尾隐M

27.6 演练例题

例题：单精度S=0, E=129, M=0.5(尾数100…0)

• 实际尾数=1.1(二进制)=1.5，指数=129-127=2
• 值=1.5×2²=6.0

例题：将12.0转为IEEE754单精度

• 12=1100=1.1×2³，S=0, E=3+127=130=10000010, M=1000…0
• 结果：0 10000010 10000000000000000000000

---

第28章 二叉树与图论计算

28.1 二叉树度数关系

$$n_0 = n_2 + 1$$

• 总节点 n = n0 + n1 + n2，边数 = n - 1 = n1 + 2×n2

28.2 完全二叉树

n个节点的完全二叉树：

• 高度 h = ⌊log2(n)⌋ + 1
• 叶子数 = ⌈n/2⌉

28.3 哈夫曼树性质

• n个叶子 → 共2n-1个节点，没有度1节点

28.4 最小生成树

• Prim：从一个点开始，每次加入最小权边扩展
• Kruskal：按边权排序，依次加入不构成环的边

28.5 最短路径

• Dijkstra：单源最短路径，非负权
• Floyd：全源最短路径，可负权（无负环）
• Bellman-Ford：可负权，可检测负环

28.6 拓扑排序

AOV网：每次选入度为0的节点输出，删除其出边，结果不唯一。

28.7 口诀双轨

类型	口诀
顺口溜	叶子等度二加一，完全二叉log高度；Prim点扩Kruskal边，拓扑每次入度零
谐音	叶等度二加一

28.8 演练例题

例题：5个度2节点，3个度1节点 → n0=5+1=6，n=6+3+5=14
例题：100节点完全二叉树 → h=⌊log2(100)⌋+1=7，叶子=⌈100/2⌉=50

---

第29章 主存编址与总线

29.1 内存编址

$$内存容量 = 末地址 - 首地址 + 1$$

29.2 存储芯片扩展

• 位扩展：增加字长，地址线不变
• 字扩展：增加容量，片选信号增加
• 字位扩展：两者结合
• 芯片数 = 总容量 / 单片容量

29.3 总线带宽

$$带宽 = 时钟频率 \times 数据宽度 \times 每周期传输次数$$

29.4 口诀双轨

类型	口诀
顺口溜	末减首加一得容量，字扩地址位扩宽；总线频率乘宽度，DDR双倍记心间
谐音	末减首加一

29.5 演练例题

例题1：A0000H到DFFFFH → DFFFF-A0000+1=40000H=262144B=256KB

例题2：16K×8位芯片组成64K×16位 → 字扩4×位扩2=8片

例题3：总线66MHz，32位，每周期1次 → 带宽=66×4=264MB/s
例题4：DDR 200MHz，64位，每周期2次 → 带宽=200×8×2=3200MB/s=3.2GB/s

---

第二部分：跨领域综合题

---

第30章 跨领域综合计算题

综合题1：可靠性+成本

某系统由3个模块串联，模块1可用性0.99(MTBF=990h,MTTR=10h)，模块2和模块3各R=0.9，模块2/3并联冗余。求系统可用性。若要求系统可用性≥0.99，模块2/3的R至少多少？

• 模块2/3并联：R23 = 1-(1-0.9)² = 0.99
• 系统R = 0.99 × 0.99 = 0.9801
• 要求≥0.99：0.99 × R23 ≥ 0.99 → R23 ≥ 1.0 → 不可能，需增加冗余

综合题2：网络划分+主机分配

172.16.0.0/16分配：总部500、分部A 200、B 100、C 50、D 25

• 总部500→/23，172.16.0.0/23
• A 200→/24，172.16.2.0/24
• B 100→/25，172.16.3.0/25
• C 50→/26，172.16.3.128/26
• D 25→/27，172.16.3.192/27

综合题3：关键路径+赶工

关键路径A(5天)→B(7天)→C(3天)，总工期15天。赶工：A压到3天增4000，B压到5天增6000，C压到2天增2000。求压缩到12天的最小成本。

• 斜率：A=2000/天，B=3000/天，C=2000/天
• 压C 1天(2000)+压A 2天(4000) = 6000
• 验证：A=3,B=7,C=2，关键路径=12 ✓

综合题4：阿姆达尔+流水线

算法串行占20%，16核并行。流水线4级每级2ns。求：(1)加速比 (2)效率 (3)流水线执行100条指令时间。

• S = 1/(0.2+0.8/16) = 1/0.25 = 4
• E = 4/16 = 25%
• T = (4+100-1)×2 = 206 ns

综合题5：Cache+磁盘+RAID

RAID5用4块盘，每盘7200rpm，寻道8ms，每磁道1MB，Cache命中率90%(1ns)，主存100ns。求读取4KB有效时间。

• 旋转=60/(2×7200)=4.17ms，传输=4KB/(1MB×120/s)=0.033ms
• 单盘访问=8+4.17+0.033≈12.2ms，RAID5读取=单盘
• Cache层：0.9×1+0.1×100=10.9ns（可忽略）
• 总时间≈12.2ms

综合题6：PV+死锁

4个进程各最多申请3个资源，R=9是否死锁？R=8呢？

• 无死锁条件：R≥4×(3-1)+1=9
• R=9：正好满足，不会死锁
• R=8 < 9：可能死锁

综合题7：功能点+COCOMO

UFC=400，TCF=1.05，C语言(128行/FP)，有机型估算人月。

• FP = 400×1.05 = 420
• 代码行 = 420×128 = 53760 = 53.76 KLOC
• PM = 2.4×53.76^1.05 ≈ 2.4×53.76×1.22 ≈ 157.4人月

综合题8：海明码+CRC

8位信息数据，需多少海明校验位？

• 2^r ≥ 8+r+1，r=4：16≥13 ✓，需4位

综合题9：段页式+访存

段号6位、页号10位、偏移12位。TLB命中率90%。求：(1)虚存空间 (2)平均访存次数 (3)页面大小。

• 虚存 = 2^28 = 256MB
• 访存 = 0.9×1+0.1×3 = 1.2次
• 页面大小 = 2^12 = 4KB

综合题10：哈夫曼+压缩率

A:45, B:13, C:12, D:16, E:9，原等长3位。

• WPL = 195，总频率=95，平均=2.053位
• 压缩率 = 1-2.053/3 = 31.6%

综合题11：EVM+COCOMO综合

UFC=120, ΣFi=42, Java(53 LOC/FP), COCOMO有机型

• FP = 120×(0.65+0.42) = 120×1.07 = 128.4
• LOC = 128.4×53 = 6805 ≈ 6.8KLOC
• E = 2.4×6.8^1.05 ≈ 17.9人月
• D = 2.5×17.9^0.38 ≈ 7.5月

综合题12：30秒速算挑战

题目	速算	答案
EV=BAC×40%, BAC=200	200×0.4	80
CPI=EV/AC=80/100	—	0.8
EAC=BAC/CPI=200/0.8	—	250
0.9并联0.9	1−0.01	0.99
5个if+1个while	6+1	7
PERT (5+4×8+11)/6	48/6	8
子网/28主机数	2⁴−2	14
海明码m=7	2⁴=16≥12	r=4
Amdahl p=0.8极限	1/0.2	5
Little L=100×0.3	—	30
TMR R=0.9	3×0.81−2×0.729	0.972
段页式访存	段表+页表+数据	3次

---

第三部分：速记卡 + 口诀总表 + 背诵路线

---

第31章 速记卡（考前一页纸）

【进度】
PERT: (O+4M+P)/6, σ=(P-O)/6, σ总=√(Σσ²)
CPM: ES=max(前EF), LF=min(后LS), TF=LF-EF
FF=min(后ES)-EF, 关键路径 TF=0
赶工斜率=(赶工成本-正常成本)/(正常工期-赶工工期)

【挣值】
EV=BAC×完成%, CPI=EV/AC, SPI=EV/PV
EAC_典型=BAC/CPI, EAC_非典型=AC+(BAC-EV)
EAC_悲观=AC+(BAC-EV)/(CPI×SPI)
ETC=EAC-AC, VAC=BAC-EAC, TCPI=(BAC-EV)/(BAC-AC)

【功能点】
UFC=Σ(权重×数量), FP=UFC×(0.65+0.01×ΣFi)
权重: EI/EQ=3,4,6; EO=4,5,7; EIF=5,7,10; ILF=7,10,15
ΣFi=35 时系数=1.0

【COCOMO】
E=a×KLOC^b, D=c×E^d
有机: 2.4,1.05,2.5,0.38 | 半分离: 3.0,1.12,2.5,0.35 | 嵌入: 3.6,1.20,2.5,0.32

【圈复杂度】
V(G)=判定+1=E-N+2=区域数
复合条件&&拆开算, case各算一个

【可靠性】
串联: R=ΠRi | 并联: R=1-Π(1-Ri)
A=MTBF/(MTBF+MTTR), MTBF=1/λ
TMR: 3R²-2R³ | 两并一倍半

【性能】
Little: L=λW | MIPS=主频(MHz)/CPI | T=指令×CPI/主频
Amdahl: S=1/((1-p)+p/n), 极限=1/(1-p)
Gustafson: S=np+(1-p)
并发数=吞吐量×响应时间

【流水线】
T=(k+n-1)×Δt, S=nk/(k+n-1), E=n/(k+n-1)
Δt取最长段

【存储】
Cache: T=h×快+(1-h)×慢
IOPS=1000/(寻道+旋转), 旋转=30000/RPM
7200转→4.17ms, 10000转→3ms, 15000转→2ms
RAID: 0全1半5减1, 6减2加10半
内存: 1K=2¹⁰, 1M=2²⁰, 1G=2³⁰, 末地址=起始+容量-1

【网络】
子网: 2^n网, 2^h-2主机, 掩码=256-2^h, 步长=2^h
海明: 2^r≥m+r+1, 纠错位=S的十进制
码距: 检e→≥e+1, 纠t→≥2t+1, 检e纠t→≥e+t+1
CRC: 补零→模2除→余数

【风险】
EMV=Σ(概率×收益), RE=概率×损失
决策树: 圆算期望, 方框取最大, 从右向左

【数据库】
候选键: 左必入, 右必不入, 待定要组合
范式: 1NF不可分, 2NF消部分, 3NF消传递, BCNF决定必键
自然连接度: 度(R)+度(S)-公共属性

【集合】
容斥: |A∪B|=|A|+|B|-|A∩B|
三集合: +A+B+C-AB-AC-BC+ABC
幂集: 2^|A|, 笛卡尔积: |A×B|=|A|·|B|

【PV操作】
P: S=S-1, S<0则阻塞; V: S=S+1, S<=0则唤醒
互斥初值1, 同步初值0, 资源初值N
前驱图: 每边一信号量, 前驱末尾V, 后继开头P
互斥信号量(n进程)取值: [-(n-1), 1]
生产者-消费者: empty=N, full=0, mutex=1
  P操作顺序不能颠倒: 先P(empty/full)再P(mutex)

【页面置换】
OPT: 淘汰未来最久不用; FIFO: 淘汰最早进入
LRU: 淘汰最近最久未用; CLOCK: 二次机会
缺页率=缺页次数/总访问次数
FIFO可能Belady异常, LRU/OPT不会
EAT=h×(TLB+内存)+(1-h)×(TLB+2×内存)

【内存管理】
页式: 页号=地址/页大小, 偏移=地址%页大小, 物理地址=块号×页大小+偏移
段式: 物理地址=段基址+段内偏移, 需检查段长越界
段页式: 段号→页表→块号, 3次访存
访存次数: 页式2次, 段式2次, 段页式3次, 二级页表3次
多级页表: 32位/4KB页/4B项 → 10+10+12

【索引】
B+树: m阶最多m-1关键字, 高度log_m(n), 查找I/O=树高
文件索引: n=块大小/索引项大小
最大文件=10B+nB+n²B+n³B (直接10+一级1+二级1+三级1)
磁盘容量=柱面×磁头×扇区×扇区大小
LBN→物理: 柱面=LBN/(磁头×扇区), 磁头=(LBN%(磁头×扇区))/扇区, 扇区=LBN%扇区

【死锁】
四条件: 互斥/占有等待/不剥夺/循环等待
银行家: Need=Max-Allocation, 安全序列逐个找Need≤Work
资源数无死锁: m≥n(k-1)+1

【磁盘调度】
FCFS按序, SSTF最近, SCAN电梯折返, C-SCAN单向跳回
寻道距离=相邻柱面差之和

【进程调度】
周转=完成-到达, 等待=周转-运行, 带权周转=周转/运行
SJF平均周转最优, SRTF抢占式SJF
HRRN响应比=(等待+服务)/服务

【位示图】
位图大小=块数/8字节, 行=块号/字长, 列=块号%字长
空闲区: 首次适应(从头找), 最佳适应(最小够用), 最坏适应(最大)

【RSA】
n=pq, φ=(p-1)(q-1), ed≡1(mod φ), C=M^e mod n, M=C^d mod n

【哈夫曼】
WPL=新节点权值之和, 平均长度=WPL/总频率

【浮点】
IEEE754: (-1)^S×1.M×2^(E-127), 补码范围-2^(n-1)~2^(n-1)-1

【二叉树】
n0=n2+1, 完全二叉树h=⌊log2(n)⌋+1, 叶子=⌈n/2⌉

【总线】
带宽=频率×宽度×倍率, DDR双倍

【2的幂次】
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536

【覆盖标准】
语一判二条二组四路二

【内聚排序】
偶逻时过通顺功（我老师过通顺功）

---

第32章 口诀总表（谐音双轨）

#	题型	顺口溜	谐音
1	CPM	正早最大加，逆晚最小减，时差零关键	郑早最大家，李晚最小姐
2	PERT	乐悲加四倍中，除六得期望；极差除以六，标准差便当	岳飞加四倍中
3	EVM三值	EV是核心，减AC省成本，减PV超进度	衡屋是核心，减埃西省成本
4	EVM预测	典型除CPI，非典型加剩余，悲观再除SPI	—
5	圈复杂度	边减点加二，判定加一数，区域数最直	边减点加二，判官加一数
6	功能点权重	输入查询三四六，输出四五七，接口五七十，逻辑七十十五	三叔四舅四姑五妻五姐七姨七叔十姥
7	功能点系数	六五加零点一，因子和来调；三十五为中，恰好等于一	刘武加林丹
8	COCOMO系数	二四三六，指数一二；二五不变，周期点三八	二四三六一零五二零
9	COCOMO类型	小五十大三百，有机半离嵌	—
10	可靠性	串联乘可靠，并联减失效；可用除总时，失效率倒置	串乘并减，可用除总
11	TMR表决	三R方减二R三方	—
12	并联MTBF	两并一倍半	—
13	MIPS	频除CPI得MIPS，指令乘CPI除频得时	频除CPI，指C除频
14	Amdahl	阿姆达尔一除串加并除n，极限一减p分之一	一除串并除n
15	Gustafson	古斯塔夫线性增，np加一减p	—
16	流水线	时间k加n减一，吞吐n除总时间；加速nk除以k加n减一	克加恩减一
17	内存编址	K十M二十G三十，容量除片得片数	凯十埃姆二十吉三十
18	RAID	0全1半5减1，6减2加10半	—
19	子网划分	借n位出二n网，主机位减二得数；VLSM从大往小分，CIDR聚合找对齐	借位出网，主机减二
20	海明码	二的r次大于等于m加r加一，校验位在二的幂	二阿大于克加阿加一
21	CRC	CRC模二除取余，奇偶只检奇数错	—
22	EMV决策树	圆圈算期望，方框取最大；从右向左推，概率和为一	圆算方取，右左推一
23	范式	一不可分，二消部分，三消传递，BC决定必键	一分二部三传，毕决定必键
24	候选键	左必入右必不入，待定要组合	—
25	关系运算	选择挑行投影列，投影去重记心间；笛卡尔积行相乘，自然连接去重叠	—
26	容斥	容斥加减交替来，笛卡尔积有序对；幂集二的全集次	容斥交替
27	内聚排序	偶逻时过通顺功	我老师过通顺功
28	覆盖标准	语一判二条二组四路二	—
29	Z值概率	零五十八四九七	—
30	赶工	斜率最低优先赶，关键路径要盯紧	—
31	PV操作	P申请减一负则等，V释放加一唤等待；互斥初一同步零，资源初值等于N	皮减负等，维加唤等
32	前驱图	前驱末尾V，后继开头P，每边一信号	—
33	页面置换	最优未来最远，先进先出最早，最近最久未用，时钟二次机会	优远先早近久时二
34	Belady	FIFO可能反常，LRU永不反常	—
35	内存管理	页式除余偏移定，段式基址加偏移；段页三次访存，页式两次段式两次	页除余偏，段基加偏；段页三访
36	文件索引	直接十块一级n，二级n方三n三方；块大除项得n值	直十一n二n方三n三方
37	死锁条件	互占不循四条件，安全序列逐个找；Need小于Work则分配	互占不循，需小工则分
38	资源数	资源大于进程乘减一加一	m≥n(k−1)+1
39	磁盘调度	先来先服务最公平，最短寻道性能好；电梯扫描到端折返，循环扫描只走一边	先先公，短短好
40	调度指标	周转等于完成减到达，等待等于周转减运行	—
41	位示图	位图一位代表一块，一为分配零空闲；首适最佳最坏循环	位图一零，首佳最循
42	RSA	RSA选两素数乘，欧拉减一减一乘；公钥e私钥d，模逆元扩展欧几里得	两素乘欧拉减减
43	哈夫曼	哈夫曼每次取最小两，WPL新节点权值和	新节点权和
44	浮点	IEEE阶码减偏置，尾数隐含一点M；补码负数取反加一	阶减偏置尾隐M
45	二叉树	叶子等度二加一，完全二叉log高度	叶等度二加一
46	总线	末减首加一得容量，总线频率乘宽度，DDR双倍记心间	末减首加一

---

第33章 高频考点速算清单

题型	关键公式	速算要点
关键路径	TF=LF−EF	找最长路径
PERT	(O+4M+P)/6	先算O+P再加4M
挣值	EV=BAC×完成%	先定EV再套公式
EAC典型	BAC/CPI	CPI>1省钱
圈复杂度	判定+1	数if/while/for
功能点	UFC×(0.65+0.01ΣF)	ΣF=35时系数=1
串联可靠	∏Ri	0.9×0.9=0.81
并联可靠	1−∏(1−Ri)	0.9并0.9=0.99
TMR	3R²−2R³	R=0.9→0.972
Cache	h×快+(1−h)×慢	命中率转小数
海明码	2^r≥m+r+1	m=4→r=3
子网	2^n子网, 2^h−2主机	借位n，主机h
Amdahl	1/((1−p)+p/n)	p=0.9→≤10倍
EMV	Σ概率×收益	圆算方取
Little	L=λW	单位统一
MIPS	主频/CPI	GHz→×1000
流水线	(k+n-1)×Δt	Δt取最长段
PV互斥取值	[−(n−1), 1]	n个进程竞争
页面置换	缺页率=缺页/访问	LRU永不Belady
页式地址	块号×页大小+偏移	页号=地址/页大小
段页式访存	3次	段表+页表+数据
文件索引	10B+nB+n²B+n³B	n=块大小/索引项
银行家	Need≤Work则安全	逐个找安全序列
无死锁	m≥n(k−1)+1	m资源n进程k最大
磁盘SCAN	到端折返	SSTF最近优先
周转时间	完成−到达	等待=周转−运行
RAID5	(n−1)×单盘	—
哈夫曼WPL	新节点权值和	—

---

第34章 六遍背诵路线与应试策略

34.1 六遍背诵路线

遍次	目标	方法	时间
第1遍	建立框架	通读思维导图+各章公式表	1小时
第2遍	公式记忆	背诵速记总表+口诀	2小时
第3遍	例题精练	每题型做2道例题	3小时
第4遍	综合题	做12道跨领域综合题	2小时
第5遍	查漏补缺	重做错题+易错点复习	1.5小时
第6遍	速记强化	速记卡+口诀+速查表	1小时

34.2 选择题策略

1. 可靠性：先判串并联结构，串联直接乘，并联用补集
2. 网络划分：算主机数注意-2，VLSM从大到小
3. 阿姆达尔：代入公式，注意p是并行占比
4. 关键路径：正序ve用max，逆序vl用min
5. PV/死锁：套n×(m-1)+1公式
6. Cache：h×t1+(1-h)×t2
7. 海明码：2^r≥k+r+1试r=1,2,3…
8. 流水线：(k+n-1)×Δt

34.3 案例题策略

1. 画图：可靠性画串并联图，关键路径画AOE网
2. 分步：关键路径分ve→vl→时差三步
3. 验证：算完检查关键路径和=总工期
4. 单位：注意KLOC(千行)、ns/ms/s、MB/GB

34.4 论文题策略

• 可靠性设计：串联降级→并联冗余→N模表决
• 性能优化：阿姆达尔分析瓶颈，Cache命中率优化
• 成本估算：COCOMO+功能点结合，给出人月和工期

34.5 十大高频失分点

#	失分点	正确做法
1	TMR写成R³	用3R²-2R³
2	投影忘记去重	投影是集合运算，自动去重
3	段页式访存写2次	是3次（段表+页表+数据）
4	子网主机数忘记-2	可用=2^主机位-2
5	阿姆达尔p用串行占比	p是并行占比，串行是(1-p)
6	ve用min/vl用max	ve正序max，vl逆序min
7	LF用紧后LF	LF=min(紧后LS)
8	死锁公式忘+1	R≥n×(m-1)+1
9	海明码校验位位置	在2^i位置(1,2,4,8)
10	流水线Δt取平均	取最长段时间

34.6 必考重点（每年出现）

1. 挣值管理（EVM）— 三值、偏差、EAC预测
2. 关键路径（CPM）— ES/EF/LS/LF/TF/FF
3. 圈复杂度 — 判定节点+1
4. 可靠性 — 串并联混联
5. 页面置换（FIFO/LRU/OPT）— 缺页次数与缺页率
6. PV操作 — 前驱图转PV、信号量取值范围
7. 页式/段式地址转换 — 逻辑地址转物理地址
8. 银行家算法 — 安全性序列判断
9. 文件索引 — 最大文件大小计算
10. 磁盘调度 — FCFS/SSTF/SCAN寻道距离

---

附录A：题型分布与权重

题型	选择题出现率	案例题出现率	难度
可靠性	高	中	中
网络划分	高	低	中
关键路径	高	中	中
阿姆达尔	中	低	易
PV/死锁	高	中	中
Cache	高	低	易
流水线	中	低	易
成本估算	中	中	中
海明码	中	低	中
关系运算	中	低	易
段页式	中	低	中
索引	低	低	中
集合/容斥	低	低	易
哈夫曼	中	低	中
RSA	低	低	中
EVM挣值	高	中	中
圈复杂度	高	低	易
EMV风险	中	低	易

附录B：数学基础速算

2的幂次必背

2⁰=1, 2¹=2, 2²=4, 2³=8, 2⁴=16, 2⁵=32, 2⁶=64, 2⁷=128,
2⁸=256, 2⁹=512, 2¹⁰=1024, 2¹¹=2048, 2¹²=4096,
2¹³=8192, 2¹⁴=16384, 2¹⁵=32768, 2¹⁶=65536

常用平方根

值	√值
20	4.47
29	5.39
50	7.07

排列组合

$$C_n^r = C_n^{n-r}, \quad C_5^2=10, \quad C_6^3=20, \quad C_7^3=35, \quad C_8^3=56$$

对数

• log₂10 ≈ 3.32
• log₁₀2 ≈ 0.301
• log_m(n) = ln(n)/ln(m)

概率

• 独立：P(A∩B) = P(A)×P(B)
• 互斥：P(A∪B) = P(A)+P(B)
• 一般：P(A∪B) = P(A)+P(B)−P(A∩B)
• 条件：P(A|B) = P(A∩B)/P(B)
• 贝叶斯：P(Aᵢ|B) = P(Aᵢ)P(B|Aᵢ) / ΣP(Aⱼ)P(B|Aⱼ)

附录C：计算器使用提示

• 软考允许非可编程计算器
• 指数运算：用e^x键算e^(-λt)
• 对数：算log_m(n) = ln(n)/ln(m)
• 组合数：C(n,r) = n!/(r!(n-r)!)
• 模运算：RSA中反复模乘

---

文档说明：本文档为合并终版，整合原《软考架构师计算题型大全_总文档》(26章)与原《软考架构师计算题总文档》(22题型)，去重保特、深度融合。共34章+3附录，覆盖软考系统架构设计师95%以上计算题型。每个题型含公式推导、例题精讲、易错避坑、速记口诀。含12道跨领域综合题、速记卡、46条口诀总表、六遍背诵路线、十大高频失分点。

合并时间：2026-10-27
关联文档：质量属性策略、架构风格、架构评估、前沿AI技术、云原生微服务、23种设计模式