2026年408真题

核心：顺序表把元素紧密连续存放在数组下标 0…length-1 上。当向第 i 位插入/删除时，必须把 [i, length-1] 这段元素整体后移或前移一格，移动的元素数 = 受影响区间的长度。

逐个核对：

• I 表头插入：插入位置 i = 0，需把 [0, length-1] 全部后移一格 → 移动 length 次。必然移动。
• II 表头删除：删除位置 i = 0，需把 [1, length-1] 全部前移一格 → 移动 length-1 次。必然移动。
• III 表尾插入：插入位置 i = length，新元素直接写到 a[length]，length++ → 0 次移动。
• IV 表尾删除：直接 length-- 即可，原 a[length-1] 被"忽略"（下次写入时被覆盖）→ 0 次移动。

所以"必然产生移动"的是 I 和 II。

最终答案是 A。

先读懂题：每个结点有两个指针字段 p1 和 p2，其中 p1 是双向链表的"指向直接后继"指针（即 next），p2 是要被赋值的辅助指针。需求是 cu->p2 = cu->p1->p1，即让 p2 指向"下下个结点"。

关键边界：当 cu 是尾结点时，cu->p1 == NULL，没有"下下个结点"，应令 cu->p2 = NULL。

正确实现必须同时满足三点：

1. 进入 cu->p1->p1 之前必须判断 cu->p1 != NULL，否则空指针崩溃；
2. 尾结点不能跳过——它的 p2 应被显式置为 NULL；
3. cu = cu->p1 必须放在 if/else 之外（即不论是否进入 if，都要推进），否则尾结点上死循环。

逐项核对：

• A ✗ 缺第 1 条边界检查，尾结点会触发空指针解引用。
• B ✗ 把判断字段误用为 p2，并且把"应该被赋值"的结点提前放过去了。
• C ✗ 满足第 1 条，但违反第 2、3 条——推进语句被困在 if 里，且尾结点 p2 未置 NULL。
• D ✓ 三条都满足：if 里赋值"下下个"，else 把尾结点 p2 置 NULL，cu = cu->p1 在 if/else 之外，能在尾结点这一轮做完赋值后把 cu 推进到 NULL，正常退出。

最终答案是 D。

编者注（生僻术语）：题干 "结构为 [p2, p1]" 是原题对结点字段的简写表示（结点中含 p2 和 p1 两个指针字段）；"初始时 head = cu" 在 C 语义里赋值方向看似反了，但按上下文应理解为"用 cu 从 head 开始遍历"——本题保留原题原文，不做改动。p1 实际承担常规的"指向直接后继 (next)"职责，p2 是题目要求的辅助指针。

重建步骤：

Step 1：层序首位是根，故 根 = a。在中序里以 a 切分：b, e, d, f, c | a | g。左子树中序 = b, e, d, f, c；右子树中序 = g。

Step 2：右子树中序只剩 g，所以右子树 = 单结点 g。

Step 3：在层序剩余 b, g, c, d, e, f 中，第一个属于左子树（即左子树根）的是 b。中序里 b 在最左 → b 没有左子树；右子树中序 = e, d, f, c。

Step 4：层序中接下来属于 b-右子树的第一个是 c（g 已被右子树拿走，c 在 d/e/f 之前）。在中序 e, d, f, c 里 c 在最右 → c 没有右子树；左子树中序 = e, d, f。

Step 5：层序里接下来出现的是 d（在 e、f 之前）。在中序 e, d, f 里 d 居中 → d 的左孩子 = e，右孩子 = f。

重建出的二叉树：

a(b(_, c(d(e, f), _)), g)

后序遍历（左-右-根）按子树分块：

• d 子树：e, f, d
• c 子树：(d 子树), c → e, f, d, c
• b 子树：(c 子树), b → e, f, d, c, b
• a 子树：(b 子树), g, a → e, f, d, c, b, g, a

最终答案是 C（e, f, d, c, b, g, a）。

关键事实 1（单棵树）：森林转二叉树用孩子兄弟法——单棵 m 节点树转出的二叉树根没有右孩子（因为根没有兄弟），左子树包含其余 m-1 个节点。这左子树是任意 m-1 节点的二叉树，原树结构可自选 → 左子树最小高度 = $\lceil \log_2 m \rceil$。所以单棵 m 节点树转二叉树的最小内部高度

$$h(m) = 1 + \lceil \log_2 m \rceil$$

代入题中 5 个节点数：

关键事实 2（多棵树串联）：森林 $T_1, T_2, \dots, T_k$ 转二叉树，$T_i$ 的根处于二叉树的层 $i$（第一棵的根在层 1，第二棵的根在层 2 即第一棵根的右孩子，依次类推）。所以每棵树对总高度的"贡献" = $(i-1) + h(m_i)$，森林二叉树总高度

$$H = \max_{i=1..k} \big[(i-1) + h(m_i)\big]$$

关键事实 3（排序使 max 最小）：要让 max 最小，把 $h$ 大的树放到 $i$ 小的位置（贪心地"先消耗大头"）。本题 $h$ 列表 = {4, 4, 3, 3, 2}，降序排到位置 1…5：

最大值 = 6。

（验证一下别的排法：升序 2,3,3,4,4 给出 max = 2,4,5,7,8 → 8；中间打乱也不会比 6 更小。）

最终答案是 B。

哈夫曼构造（每次取最小两数合并，把它们作为新结点的左右孩子）：

画出最终哈夫曼树（根记为深度 0）：

                    42
                  /    \
                18      24
               /  \    /  \
              e    f  12   g
                       /\
                      d  7
                         /\
                        3  c
                       /\
                      a  b

逐叶子核对深度：

与 e 同深度（深度 2）的叶子是 f 和 g。

最终答案是 D。

邻接表的存储结构：一个长度为 $|V|$ 的头指针数组，每个表头挂出该顶点的出边链表。问题在于：邻接表只直接记录出边，入边没有单独表（除非额外维护逆邻接表）。

求顶点 v 的入度：

1. 对每个顶点 i = 1..|V|，遍历 i 的出边链表；
2. 凡看到一条 (i, v) 的边，入度计数器 +1；
3. 扫完所有顶点的链表后得到入度。

开销分析（必须把两部分都算上）：

• 遍历所有 $|V|$ 个头指针：$O(|V|)$；
• 遍历所有 $|E|$ 条边：$O(|E|)$。

合计 $O(|V| + |E|)$，写成等价形式 $O(\max(|V|, |E|))$。

为什么 C 不严谨：在稠密或一般连通图中 $|E| \ge |V|$，此时 $O(|E|) = O(\max(|V|, |E|))$，C 和 D 渐近等价；但没有这个假设时 D 才是紧的上界——比如一个只有几条边的稀疏图，扫描 $|V|$ 个头指针的代价就主导了。

最终答案是 D。

先把"路径"读清楚：本题中 S 包含所有路径对应的边标记字符串，路径可以重复顶点（这是允许讨论"绕环长度"的前提）。

两种情形分别分析：

Case 1：G 无环

• 任何路径都不能重复顶点（重复就成环了）→ 这就是简单路径；
• 简单路径最多覆盖 n 个不同顶点 → 最多 n−1 条边；
• 字符串长度上限 n−1，不存在长度恰为 n 的字符串；
• 简单路径数上界 ≤ n!，S 有限。
• 故 A ✓，B ✗（B 是错误说法）。

Case 2：G 有环

• 可沿环绕任意多圈，每圈把字符串延长一段固定子串 → 字符串长度可任意大，必然存在长度 > n 的字符串。C ✓。
• 有环 → 至少有边 → 单条边即为长度 1 的字符串，1 < 2n。D ✓。

结论：错误的说法只有 B。

最终答案是 B。

条件回顾：AVL 树高度 4（根算第 1 层），求根的左右子树节点数差的最大值。

思路：让一棵子树尽量胖、另一棵尽量瘦。

Step 1：高度约束

整棵树高度 4 → 至少有一棵子树高度 3（否则整树高度只到 3）。AVL 平衡条件允许另一棵子树高度比这棵差 1，即高度 2。

最佳分配：胖的子树高 3，瘦的子树高 2。

Step 2：胖子树最多节点

高度 3 的二叉树最多节点 = 满二叉树 = $2^3 - 1 = \mathbf{7}$。

Step 3：瘦子树最少节点（AVL 高度 h 最少节点的递推）

$$N(h) = N(h-1) + N(h-2) + 1, \quad N(1) = 1, \ N(2) = 2$$

高度 2 的最少节点 = N(2) = 2。

Step 4：节点数之差

$$\text{最大差} = 7 - 2 = \mathbf{5}$$

举例验证（一棵高度 4 的合法 AVL）：

                root
               /    \
            (高3满)  (高2最少)
              7节点    2节点

整棵树高度 4，根的左右子树高度差 |3-2|=1 ≤ 1（AVL 合法），节点差 5。

最终答案是 D。

核心规律：直接插入排序对第 i 个元素 (i ≥ 2)，从已排序部分末尾向前比较，直到找到合适位置或越界。最好情况（已升序）每个新元素只比 1 次，总比较 n−1；最坏情况（已降序）第 i 个元素比 i 次，总比较 $n(n-1)/2$。

逐项数比较次数（n=7，对 a[2..7] 共 6 个元素插入）：

A. 30, 27, 56, 41, 80, 95, 69

合计 9 次。

B. 31, 43, 26, 55, 63, 99, 77

合计 8 次。✓ 最少。

C. 61, 84, 51, 23, 34, 91, 40

逐项算：1 + 2 + 3 + 4 + 1 + 5 = 16 次。

D. 93, 32, 48, 81, 50, 21, 72

逐项算：1 + 2 + 2 + 3 + 5 + 3 = 16 次。

汇总：A=9，B=8，C=16，D=16。

观察 B 序列的结构：除了 26 要插到最前（贡献 2 次比较）和 77 略往前插（2 次），其余都是后一个数大于已排序末尾，每次只 1 次比较——B 序列"基本升序"的程度最高。

最终答案是 B。

多关键字排序的标准做法：基数排序（LSD，Least Significant Digit 最低位优先）。

具体到本题，主关键字是 $C_1$、次关键字是总分 $C_1 + C_2$，按 LSD 思路实现：

1. 第一趟：以"总分"为关键字，对所有记录做稳定排序；
2. 第二趟：以"$C_1$"为关键字，对上一趟结果再做稳定排序。

为什么这样得到的结果正确：第二趟按 $C_1$ 排，稳定性保证当 $C_1$ 相同时，原有的相对顺序不变——而原有顺序正是第一趟排好的总分升序。两遍稳定排序合起来恰好满足"主关键字 $C_1$ 升序、$C_1$ 相同时总分升序"。

其他三个算法的问题：

虽然 B/C/D 通过改写比较函数也能完成任务，但题目问的是**"最适合"**——基数排序是教材里专为多关键字排序设计的算法。

最终答案是 A。

外排序两阶段：

1. 生成初始归并段：每次把内存能装下的一批记录读进来，内排序后写回外存，得到一个有序段。重复直到所有记录处理完，共得到 $m$ 个初始段；
2. k 路归并：每趟把 k 个段合并成 1 个，反复进行直到只剩 1 个段。趟数

$$d = \lceil \log_k m \rceil$$

逐项核对：

• Ⅰ. $k$ 越大，$d$ 越小 ✓
  $d = \lceil \log_k m \rceil$，对数底数 $k$ 增大 → 对数值减小（m 固定时），所以 d 单调减少。

• Ⅱ. 初始归并段数不影响 $d$ ✗
  公式里 $m$ 直接进入 $d$。$m$ 越大，$\log_k m$ 越大 → d 越大。比如 $k=4$、$m=16$ 时 $d=2$；$m=64$ 时 $d=3$。

• Ⅲ. 内存大小限制初始归并段的最大长度 ✓
  生成初始段时，一次只能把内存能容纳的记录放进来排序，所以每个初始段的长度上限 = 内存容纳记录数。内存越大，初始段越长，需要的初始段数 $m$ 也越少（间接也让 d 变小）。

正确的说法是 I 和 III。

最终答案是 C。

题目考点：计算机系统的多层抽象模型，重点在 ISA 与 微架构 / 物理实现 这两层之间的关系。

层次模型速查（自顶向下）：

逐项判断：

C 错在哪：把"微架构"和"物理实现层"画了等号。微架构回答的是"用什么样的数据通路 / 控制器去执行 ISA"（属于逻辑层面），而物理实现回答的是"用什么晶体管、什么工艺、什么版图把这些电路造出来"（属于物理层面）。同一套 ISA 可以有多种微架构（比如 x86 的奔腾系列 vs 酷睿系列），同一种微架构也可以由不同物理工艺生产——两层的关注点完全不同，不能混为一谈。

最终答案是 C。

前置概念——算术移位的补位规则：

原数 1010 0110B，符号位为 1（表示负数）。

第一步：算术右移 3 位

每次右移高位补 1（符号位），低位 1 位被挤掉：

得到 1111 0100B。

第二步：算术左移 2 位

每次左移低位补 0，高位 1 位被挤掉：

得到 1101 0000B。

验证（可选，按真值检查）：

原数 1010 0110B 是补码 → 真值 $-128 + 32 + 4 + 2 = -90$。
算术右移 3 位 ≈ 真值 ÷ 8 = $-90 / 8 = -11.25$，向负无穷取整为 −12，对应补码 1111 0100B ✓。
算术左移 2 位 = 真值 × 4 = $-12 \times 4 = -48$，对应补码 1101 0000B ✓（注意若结果超出补码可表示范围会溢出，本题未溢出）。

最终答案是 A（1101 0000B）。

易错点速查：

• 算术右移 ≠ 逻辑右移：前者高位补符号位，后者高位补 0
• 算术左右移不可逆：被挤出去的位丢失，先右后左 ≠ 净位移右 1
• 算术左移可能改变符号位（导致溢出），右移不会

IEEE 754 单精度格式（共 32 位）：

width: 32
fields:
  [31, 31] S
  [30, 23] E
  [22, 0] M

• S：1 位符号位（0 正 1 负）
• E：8 位阶码（移码，偏移量 127）
• M：23 位尾数（隐含前导 1）

第一步：把 12.1 写成二进制

整数部分 12 = 1100B（4 位）。

小数部分 0.1 不能精确表示，是无限循环二进制：

所以 $0.1 = 0.0001\,1001\,1001\,1001\,\ldots\,B$（首位 0001 后无限循环 0011）。

合起来：$12.1 = 1100.0001\,1001\,1001\,1001\,1001\,1001\,1001\,\ldots\,B$。

第二步：规格化

把小数点左移到最高位 1 后面：

$$12.1 = 1.100\,0001\,1001\,1001\,1001\,1001\,1001\,1001\,\ldots \times 2^3$$

尾数小数点后从左数第 23 位的截止位置：

位号:   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | 24 25 ...
尾数:   1  0  0  0  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1  1  0  0  1 | 1  0  0  1  1  ...

第 23 位（最低位）是 1，第 24 位起的"被舍部分" = 1 0011 0011 ...（首位是 1，后续非零）。

第三步：就近舍入

本题被舍部分 1 0011... 后续非零 → 向上进位：

$$\underbrace{1001}_{\text{原最低 4 位}} + 1 = 1010$$

尾数最终：100 0001 1001 1001 1001 1010

第四步：拼装 32 位

合并：

0 | 1000 0010 | 100 0001 1001 1001 1001 1010

按 4 位重新分组：

0100 0001 0100 0001 1001 1001 1001 1010
=  4    1    4    1    9    9    9    A

机器数 = 4141 999AH。

最终答案是 B（4141 999AH）。

关键易错点：

1. 12 = 1100B（4 位），不是 11100B（5 位）——位数算错全盘错
2. 0.1 是无限循环 0001 1001 1001 ...，循环节是 0011，不是 1100
3. 就近舍入时被舍部分是 1xxxx... 且至少一位非零 → 进位；不是简单地"看第 24 位是 1 就进"

结构分析：

• 8 个芯片，每片 64M × 8bit = 64MB，位扩展每次读 8bit
• 64bit 总线 = 8 字节，每次访存要 8 个芯片同时各供 1 字节 → 这就是低位交叉编址的工作模式
• 每个芯片就是一个"体"，体号 = 字节地址 mod 8

地址低 3 位 = 体号（芯片号）：

也就是说：

$$\text{芯片号} = \text{字节地址} \bmod 8 = \text{字节地址的低 3 位}$$

目标地址 0018 001DH 的体号：

末位 D = 1101B，取最低 3 位 = 101B = 5。
所以目标地址在芯片 5。

逐项判断"低 3 位是否 = 101"（注意 D 后缀是 B 表示二进制，不是十六进制）：

容量校验（顺手）：

8 片 × 64MB/片 = 512MB = $2^{29}$ 字节 ≈ 5.4 × $10^8$，地址需要 29 位。A、B、C 的十六进制地址均小于 0x20000000 < $2^{29}$，在范围内；D 是二进制 0101 0011B = 83 字节，自然也在范围内。

最终答案是 A（0000 01D5H）。

速记口诀：

• 低位交叉编址：相邻地址分散到不同体（高速并行）
• 高位交叉编址：连续地址在同一体内（容量扩展）
• 判同体：看"地址 mod 体数"是否相等，等价于看二进制最低 $\log_2 \text{体数}$ 位

核心区分——ISA（软硬件接口）与微架构（硬件实现）的边界：

判定法则：

软件（编译器、OS、汇编）能"看见"并依赖的接口 → ISA 规定；
同一个 ISA 上多种实现可以互相替换、对软件透明的 → 微架构决定。

逐项判断：

为什么 D 是答案：

超级流水线把 5 段流水拆成更细（如 10–20 段）以提高主频，但对软件来说，看到的还是同一套指令、同一套寄存器、同一种执行顺序——同一个 ISA 既可以用 5 段简单流水实现，也可以用 20 段超级流水实现，软件完全不需要改动。这正是微架构层面的"自由"，与 ISA 无关。

最终答案是 D。

记忆抓手：

"ISA = 程序员手册里写的东西"——你查不到"我这颗 CPU 用几段流水"，但能查到"有哪些指令、寄存器、中断、内存布局"。前者是微架构，后者是 ISA。

关键概念辨析——题目问的是"程序下一条指令的地址"。这里的"程序"应理解为主程序逻辑流，而不是单条指令的 PC+1。判据：执行该指令后，主程序原本约定要执行的下一条指令是否被打断 / 替换。

逐项判断：

为什么 IV 返回算"不改变"：

CALL+RET 是配对操作。把 CALL 之前的"主程序"看成一条单线程的指令流：

也就是说，从主程序的视角，CALL+子程序+RET 这一整段执行下来，主程序的执行序列没有被打断——RET 恰好把控制权送回了"主程序原本要执行的下一条"。这是 IV 区别于 II、III 的关键：II 把控制权送往别处（子程序），III 把控制权送往陷入处理程序，只有 IV 把控制权"还原"。

对比 I 和 IV 的"不改变"含义：

• I 条件转移可能不改变：分两种情况，条件不满足时不跳转
• IV 返回总是不改变主程序流：从主程序视角看是恢复，不是打断

题目用"可能不改变"涵盖这两种情况：I 是"有时不改变"，IV 是"从主程序视角不改变"——两者都符合"程序原本下一条指令地址未被打断"。

最终答案是 B（Ⅰ、Ⅳ）。

易错点：

• 这道题的"程序下一条指令的地址"指的是程序逻辑流上的下一条，不是 RET 这条单独指令的 PC+1
• 过程调用 II 是无条件的，不要因"看得见跳到哪里"而以为可以"不跳"
• 陷入指令 III 与中断处理同质，必然进入异常处理程序，没有"不进入"的分支

地址划分通用流程（组相联映射）：

width: 32
fields:
  [31, 13] Tag
  [12, 5]  组号
  [4, 0]   块内偏移

上图按本题参数（5 位块内偏移 + 8 位组号 + 19 位 Tag）画出，与标准 32 位地址布局一致。

第一步：求各字段位数

第二步：把字节地址 1028 拆成上面三段

地址 1028 的二进制：

$$1028 = 1024 + 4 = 2^{10} + 2^2 = \texttt{0000\,0000\,0000\,0000\,0000\,0100\,0000\,0100B}$$

按 [Tag | 组号 | 块内偏移] 切片（自高位到低位 = 19 + 8 + 5 位）：

第三步（验证）：用除法核对

两种方法都得到组号 32。

最终答案是 C（32）。

关键速查：

避坑：

• 1024 是总行数，不是组数。组数 = 行数 ÷ 路数 = 256
• 块号要用字节地址 ÷ 块大小，不能直接用字节地址 mod 组数
• "4 字节数据"是访问长度，与块大小无关

第一步：算 TLB 字段宽度

第二步：算页号 22 在 TLB 中的位置

把 8 位页号拆成 [Tag (6 位) | 组号 (2 位)]：

$$22 = \texttt{0001\,0110B}$$

所以页号 22 落在 TLB 组 2，对应的 Tag = 05H。

第三步："页表与 TLB 同步" 的含义

题目说主存页表与 TLB 表项已同步。意思是：TLB 中存在的页表项必须和主存页表内容一致——但这里有重要区别：

"同步" 只对有效条目（V=1）做约束。V=0 的条目内容是历史残留 / 任意值，与页表当前状态无关。

所以同步后的约束是：

如果 TLB 组 2 中某项的 Tag = 05H 且 V=1，那么它的 PPN 必须等于主存页表中页号 22 的 PPN——而页号 22 的 P=0（未装入），意味着页表中根本没有有效的 PPN 可"同步"过来，TLB 中该位置如果 V=1 就矛盾了。

第四步：逐项核对组号 2 的 TLB 内容

关键判据：

• 页号 → Tag：Tag = 页号 ÷ 组数 = 页号的高位部分；不同页号的 Tag 通常不同
• 同 Tag 才指同页：A 的 Tag=05H 唯一对应页号 22；B 的 Tag=06H 对应的是页号 26
• V=0 时所有其他字段都不受约束

最终答案是 A。

易错抓手：

1. 不要看到 PPN 一样就判"冲突"——不同虚页映射到同一物理页是常见情况（共享页）
2. V=0 的 TLB 项中 PPN、Tag 都是垃圾值，不能用"PPN 应等于 X" 反推
3. 真正的冲突只发生在 V=1 且 Tag 指向已知"未装入"页号的情形

核心区分——三种数据通路与 CPI 的关系（理想稳态）：

逐项验证：

Ⅰ. 单周期 CPI = 1 ✓

定义：一条指令从取指到写回，全部在一个时钟周期内完成（电路足够长，让信号在一个 tick 里跑完所有部件）。

代价：时钟周期 = 最慢指令所需时间（如 LW 要 IF+ID+EX+MEM+WB 全跑），所有指令都按这个长周期算。

CPI 计算：$\frac{\text{总周期数}}{\text{总指令数}} = \frac{N}{N} = 1$。

Ⅱ. 多周期 CPI > 1 ✓

定义：一条指令拆成多个段（如 IF / ID / EX / MEM / WB），每段占一个时钟周期，下一条指令必须等当前指令做完所有段后才能发射。

具体值：取决于指令类型——

平均 CPI = 各类指令的加权平均，必然 $\geq 3$，不可能等于 1。

Ⅲ. 流水线 CPI = 1（理想稳态） ✓

定义：把多周期的多个段重叠执行——指令 i 在 EX 段时，指令 i+1 已在 ID 段，指令 i+2 在 IF 段……每个时钟周期都有一条指令完成（从 WB 段流出）。

stages: IF, ID, EX, MEM, WB
instructions:
  I1 @ 1: IF ID EX MEM WB
  I2 @ 2: IF ID EX MEM WB
  I3 @ 3: IF ID EX MEM WB
  I4 @ 4: IF ID EX MEM WB
  I5 @ 5: IF ID EX MEM WB

5 条指令、9 个时钟周期完成；当 N 足够大时，CPI = $N / (N + 4) \to 1$。题目"不考虑访存额外开销和异常中断"正是为了把这个理想稳态条件成立。

全部 Ⅰ、Ⅱ、Ⅲ 都正确。

最终答案是 D（Ⅰ、Ⅱ、Ⅲ）。

速记口诀：

注意"CPI = 1"不一定意味着性能好——单周期的时钟周期被拖得很慢，绝对速度反而最差；流水线的时钟周期短得多，相同 CPI 下性能最高。

特权指令 vs 非特权指令 的判据：

一条指令是否能威胁系统安全 / 让操作系统失去控制？能 → 必须是特权指令，只能在内核态执行。

特权指令的几大类（必须内核态）：

非特权指令（用户态可用）：

• 算术 / 逻辑运算（ADD、SUB、AND）
• 数据传送（MOV、LOAD、STORE，通过虚地址）
• 控制流（JMP、CALL、RET、条件跳转）
• 系统调用指令（SYSCALL / TRAP / INT）

为什么系统调用指令不是特权指令：

系统调用指令的目的恰恰是"让用户态程序主动陷入内核"——用户写 read() 库函数最终编译成 SYSCALL 指令，这条指令本身必须能在用户态执行，否则用户根本进不了内核，整个系统调用机制就崩了。

它与特权指令的关系：

用户态 ──── SYSCALL（非特权，从用户态执行）─────▶ 进入内核态
                                                     │
                                                     ├─ I/O 指令（特权）
                                                     ├─ 关中断（特权）
                                                     ├─ 中断返回（特权）
                                                     │
                                                     └─ IRET ───▶ 返回用户态

陷入内核之后，CPU 自动切换到内核态，此时才能执行特权指令。SYSCALL 是"陷入"动作，不是"特权"操作——区别在于"它是允许从用户态发起的、安全的入口"。

逐项判断：

最终答案是 D。

易混淆抓手：

"用户能用的接口（系统调用）"和"内核才能用的指令（特权指令）"是接力关系：用户态发起 SYSCALL（非特权）→ 陷入内核 → 内核里执行特权指令 → IRET 返回用户态。SYSCALL 是入口、不是特权操作。

中断响应和处理过程的硬软件分工：

为什么"保存断点"必须硬件做：

断点 = PC + PSW（被打断时下一条指令的地址 + 处理器状态）。保存断点必须发生在响应中断的瞬间——如果不立刻保住：

1. 隐指令第三步要把 PC 改写为中断入口地址，原 PC 一旦覆盖就再也找不回来（无法返回原程序）
2. 关中断动作改变了 PSW 的中断使能位，原 PSW 需保护
3. 软件根本来不及介入——保存动作必须在硬件级别完成，没有任何机会让软件先跑一段代码

而保存通用寄存器则不一样——

• 通用寄存器在进入 ISR 后才保护，因为 ISR 头几行还没"用脏"通用寄存器
• 哪些寄存器要保护、保护到哪个内存区，由 OS / 编译器约定的调用约定（ABI）决定，不是硬件能决定的
• 只需软件在合适时机 push 即可

逐项审计：

最终答案是 C（保存断点）。

关联题对照（中断隐指令系列）：

• 2010-21：单级中断 ISR 内执行顺序（I → V → VI → II → VII）
• 2011-21：多重中断屏蔽字设置
• 2012-22：隐指令包含哪些步骤（关中断 + 保断点 + 送入口）
• 2017-22：多重中断中 CPU 是否全程关中断
• 2018-22：中断响应的前提条件（IF = 1）
• 2026-22：哪一步必须由硬件做

把这六道连起来看，"中断响应 + 多重中断 + 屏蔽字 + 硬软件分工"基本就闭环了。

判定原则：一个程序是不是在内核态运行，看它是否必须使用特权指令——访问硬件、修改页表、分配物理内存、屏蔽中断等动作只能在内核态做；纯粹的数据加工（读/写文件、字符串处理、算术运算）通过系统调用走一遭就够了，本体仍在用户态。

逐项分析：

A、B、D 三者都是"用户态应用程序"，它们如果需要内核服务（比如读文件、创建进程），就发起系统调用进内核走一趟，回来仍在用户态。只有装入程序因为要直接操作页表、分配物理内存、设置进程上下文，本质上是 OS 内核的一部分，必须在内核态执行。

最终答案是 C。

编者注（解题技巧）：判定"是否在内核态"只看一句话——这个程序要不要直接动页表/物理内存/特权指令。要动 → 内核态；只读写文件就能完事 → 用户态。"听起来重要"或"和 OS 相关"都不算证据。

判定思路：抓住"虚存系统中谁做哪一步"的标准分工：

逐项核对：

• A 错：地址转换由 MMU 硬件完成，不是 OS。
• B 错：页表项由 OS 填写，不是编译器。
• C 错：缺页只是硬件触发异常，真正"处理"——找空闲页框、触发置换、读盘、改页表——是 OS 软件做的。
• D 对：所有异常（缺页、越权、非法指令、除零等）都遵循"硬件检测 → 触发异常 → OS 处理"的模式。

一句话归纳：简单/高频的操作交硬件做（MMU 翻译地址），复杂/罕见的处理交 OS 做（异常、缺页、I/O）——这是"软硬件协同"的设计哲学。

最终答案是 D。

逐项判断：

核心知识点：

• 谁创建：用户级线程 → 用户线程库；内核级线程 → 操作系统
• 谁私有：栈、寄存器、PC、TCB
• 谁共享：堆、全局变量、代码段、打开文件、地址空间

线程的"轻"，正是因为共享了进程的大部分资源（堆、代码、文件），切换时只需保存/恢复少量私有数据（寄存器和栈指针）。

最终答案是 D。

信号量语义回顾（这两条是这题的全部）：

1. wait(S)：先 S--；若 S < 0，调用进程阻塞进入 S 的等待队列；若 S ≥ 0，进程继续执行进入临界区
2. 信号量为负时，$|S|$ 恰好等于阻塞队列上的进程数——这是判断阻塞数最快的捷径

逐步推导：

到 S = −2 时：

• $m$ = 当前在临界区访问资源的进程数 = 5（这正是信号量初值——临界区"容量"被 5 卡死，无法多于 5）
• $n$ = 阻塞队列长度 = $|S|$ = 2

两条速记结论：

• $S$ 为正时：表示剩余可用资源数
• $S$ 为负时：$|S|$ 表示阻塞队列长度；同时正在访问资源的进程数已达初值上限

最终答案是 A（5, 2）。

Bernstein 条件：进程 P 与 Q 可安全并发的充要条件是下面三组集合两两不相交：

唯一不需要的是"读读不相交"——两个进程同时读同一变量，谁也不会改它，互不影响。

对照题目四个选项：

• Ⅰ. $R(Q)\cap W(P)=\emptyset$ → 等价于 $W(P)\cap R(Q)=\emptyset$，写后读冲突 ✓
• Ⅱ. $R(P)\cap R(Q)=\emptyset$ → "读读不相交"，不必要 ✗
• Ⅲ. $W(P)\cap W(Q)=\emptyset$ → 写写冲突 ✓
• Ⅳ. $R(P)\cap W(Q)=\emptyset$ → 读后写冲突 ✓

需要同时满足的是 Ⅰ、Ⅲ、Ⅳ。

记忆口诀："写写、读写、写读三冲突，读读相安无事"——三个含 W 的方向都要不相交，只剩 RR 不用管。

最终答案是 C。

判断思路：分两步——① 一个三级页表占多少页框；② 总共有多少个三级页表。

步骤 1：一个三级页表的大小

题目给的 9-9-9-12 切分配 64 位 PTE，让"一个页表正好等于一个页框"——这是多级页表的标准设计，让每级页表自己也能像普通页一样换入换出。

步骤 2：三级页表的总个数

逐级展开：

步骤 3：合并

$$\text{三级页表占用页框数} = 256\text{K（个三级页表）} \times 1\text{（页框/个）} = \mathbf{256\text{K}}$$

为什么不是 256M：虚地址 64 位中只有 39 位（$9+9+9+12$）被有效使用——上面 25 位是"补充位"，不参与任何索引，所以总寻址空间是 $2^{39}$ 而非 $2^{64}$。从这 $2^{39}$ 字节里，按 4KB 页划分能得到 $2^{27}$ = 128M 个页框（这是数据页），但承载这些数据页所需的三级页表个数是 $2^{18}$ = 256K，差了一个数量级，因为每个三级页表覆盖了 $2^9 \times 4\text{KB} = 2\text{MB}$ 的虚拟地址空间。

最终答案是 C（256K）。

判定原则：把每种方法对"平均访存时间公式"的贡献位置看清楚。

简化模型：

$$\overline{T_{\text{访存}}} \approx T_{\text{地址转换}} + (1 - p_{\text{缺页}}) \cdot T_{\text{内存}} + p_{\text{缺页}} \cdot T_{\text{缺页处理}}$$

降低任一项就能降低整体——重点是这两项：地址转换时间、缺页率/缺页处理代价。

逐项分析：

关键辨析：

• TLB 是硬件 cache，命中率通常 95%+，对访存时间是数量级的改善
• 多级页表是空间-时间权衡：用更多次访存换更省的页表内存；想抵消它带来的延迟开销正是 TLB 的作用
• 工作集理论的实际收益体现在缺页率上——缺页一次几毫秒，普通访存几纳秒，省一次缺页相当于省百万次普通访存
• 页缓冲队列（如 Linux 的 buddy + LRU 页面回收链）是 OS 层的"软 cache"，缺页时先查它再考虑读盘

只有 Ⅰ、Ⅲ、Ⅳ 真正降低访存时间；Ⅱ 是节省空间、反而增加单次访存时延。

最终答案是 C（Ⅰ、Ⅲ、Ⅳ）。

核心机制：进程间共享文件（典型实现是 mmap MAP_SHARED 或 SysV shmget）的本质——

让两个进程的页表项指向同一个物理页框，从而实现"两边看到的字节内容时刻一致"。

对照四个维度：

逐项核对：

• A 错：物理页框号必然相同，"完全不同"是错的；只有部分标志位可能不同。
• B 对：共享的本质就是物理地址相同——这是"共享"二字的工作机理。
• C 错：共享映射下一方写、另一方立即可见，这正是它和"写时复制"的关键区别。
• D 错：虚地址在各自独立的地址空间，没必要相同。

速记：共享文件 ⇔ 物理地址相同——其余四项（虚地址、PTE 内容、修改可见性）都不绑定。

最终答案是 B。

题面是反向措辞："错误的是（ ）"——找的是错的那个。

分析四个论断：

字符设备 vs 块设备 的本质区别：

正因为这两类设备的访问模式完全不同，OS 在 I/O 子系统里给它们设了两条独立的处理路径（Linux 里就是 chrdev 和 blkdev 两套子系统）——绝不是"同一种 I/O 方式"。D 是错的。

最终答案（错误的描述）是 D。

判定思路：把"鼠标按了一下"到"应用程序拿到事件"这个全链路按层次拆开，看每一层各做什么——中断处理程序只负责其中一段。

完整数据流（从下到上）：

中断处理程序的关键设计原则是**"快进快出"**——只做必须立即做的最小工作（搬数据离开寄存器、确认中断），其余复杂处理（语义解析、唤醒进程、与用户交互）都交给上层。

逐项核对：

速记：中断处理 = 把数据从硬件寄存器抢救到内核缓冲区，前后两端都不归它管：之前是硬件、之后是用户的事。

最终答案是 D。

分层网络体系结构的设计动机：把复杂的通信问题切成若干独立模块，每层只解决一个子问题，上下层之间通过定义良好的**接口（服务原语）**交互。这一设计带来三个直接好处：

1. 模块化：每层有明确的功能边界（→ A 对）
2. 独立演化：下层换实现，只要接口不变，上层无感（→ C、D 对）
3. 简化设计与教学：每层只关心自己的问题，便于工程分工与学术研究

逐项核对：

• A 对：每层职责清晰是分层的前提。OSI 七层、TCP/IP 四层都是这一原则的体现。
• B 错：层次越多 ≠ 效率越高。每多一层就多一份封装 / 解封装开销、多一份头部字节、多一次跨层调用。OSI 七层比 TCP/IP 四层"完整"但实际部署中 TCP/IP 胜出，正是因为分层是工程权衡——既要够分（解耦清楚），又不能太多（避免冗余）。
• C 对：分层最大的实际收益。例：以太网物理层从 10 Mbps 双绞线演化到 100 Gbps 光纤，IP 层完全不受影响。
• D 对：上层通过下层暴露的接口调用服务，对下层的具体实现机制（用什么介质、用什么帧格式）保持透明——这就是"协议栈"和"封装"的核心思想。

题问"错误的是"，唯一错误项是 B。

最终答案是 B。

编者注（生僻术语）："功能边界"在网络分层语境里指每层负责的职责范围——物理层只管 0/1 信号、链路层只管点对点成帧、网络层只管端到端路由。"边界明确"= 每层不越界做别人的事，也是分层架构能成立的前提。

第一步：用香农定理算信道极限容量

$$C = B \log_2(1 + S/N) = 200 \times 10^3 \times \log_2(1 + 1023) = 200 \times 10^3 \times 10 = 2 \times 10^6 \text{ bps}$$

关键中间值 $\log_2(1024) = 10$（这是题面给 1023 的明显意图——凑成 $2^{10}$ 整数，方便心算）。

第二步：把分组长度换算成比特

$$L = 1500 \text{ B} \times 8 = 12000 \text{ bit}$$

第三步：传输时延 = 长度 / 信道速率

$$T = \frac{L}{C} = \frac{12000}{2 \times 10^6} = 6 \times 10^{-3} \text{ s} = 6 \text{ ms}$$

为什么是"至少"？ 香农定理给的是信道容量上限——实际链路速率不可能超过 C，所以真实传输时延不可能短于 $L/C$。题面问"至少"，等价于问"按理论极限的最优速率，最快多久发完"，答案就是 6 ms。

最终答案是 D（6 ms）。

编者注（生僻术语）：题里 S/N=1023 是数比形式（线性比值）。考研题里如果遇到 S/N 给 dB 值（如"信噪比 30 dB"），要先换算回数比再代公式：$10\lg(1+S/N) = 30 \Rightarrow 1+S/N = 10^3 = 1000 \Rightarrow S/N = 999$。

完整 CSMA/CA 帧交换流程（数据帧 + ACK，无碰撞场景）：

题面起点是"开始发送数据帧"——也就是从阶段 ② 开始。①（DIFS）已经在起点之前结束了。

计算阶段 ② + ③ + ④ + ⑤：

• 阶段 ②：$\dfrac{1500 \times 8 \text{ bit}}{300 \times 10^6 \text{ bps}} = \dfrac{12000}{3 \times 10^8} = 4 \times 10^{-5}$ s = 40 μs
• 阶段 ③：SIFS = 28 μs（必经流程，不能省，否则发送方还来不及切到接收态）
• 阶段 ④：题面规定忽略 → 0
• 阶段 ⑤：题面规定忽略 → 0

合计 $40 + 28 = 68$ μs。

最终答案是 B（68 μs）。

编者注（生僻术语）：DIFS（Distributed Inter-Frame Space）和 SIFS（Short Inter-Frame Space）是 802.11 里两个不同优先级的帧间间隔。SIFS 最短（28 μs，本题数值），用于最高优先级动作（ACK / CTS 等紧接前一帧的回应）；DIFS 较长（128 μs，本题数值），用于普通数据帧竞争信道前的等待。SIFS < DIFS 这条不等式保证了 ACK 总是抢在新数据帧之前发出去，不会被打断。

两条转发规则锁定答案：

1. VLAN 隔离：跨 VLAN 帧（含单播 + 广播 + 未学习的 MAC 泛洪）一律被交换机丢弃在源 VLAN 内，不会跨 VLAN 转发（要互通须靠三层设备，本题无）。
2. 不向入端口回转：交换机绝不把帧再从它进来的那个端口送出去，所以主机自己发的帧自己永远收不到（哪怕是广播）。

逐帧判定：

H3 收到的帧 = F1 + F3。

最终答案是 B（仅 F1、F3）。

编者注（生僻术语）："不向入端口回转"是 IEEE 802.1D 透明网桥转发规则的兜底约束——既适用于已学习的 MAC（直接查表转发到对应端口）、也适用于未学习的 MAC 泛洪（向除入端口外所有同 VLAN 端口送）、还适用于广播帧（向同 VLAN 所有端口送但不送回入端口）。三种情形都遵守这条不回转规则。

第一步：算 t1 时刻 R1 到各外部子网的最短路径（Dijkstra）

链路 R1-R2 断后，R1 直连邻居只剩 R3（cost 6）、R4（cost 3）。各目的子网由谁直连：

验证 R1 → R4 → R3 → R2（3+4+5=12）确实比 R1 → R3 → R2（6+5=11）大，所以走 R3。R1 → R4 → R3（3+4=7）也比 R1 → R3（6）大，所以到 R3 直接走 R1-R3 链路即可。

第二步：CIDR 聚合规则

两条路由能合并必须同时满足：

1. 下一跳相同（否则合并后无法决定送往哪边）
2. IP 前缀连续可合并（去掉若干位掩码后能覆盖且只覆盖原来的范围）

逐对检查：

• .0/27（next R3）+ .32/27（next R3）→ 下一跳同；前缀 199.10.20.0 与 199.10.20.32 在 /26 下都属于 199.10.20.0/26 ✅ → 合并为 199.10.20.0/26 → R3
• .64/27（next R4）+ .128/25（next R4）→ 下一跳同，但 .64 与 .128 在二进制位上非相邻区间（中间隔着 .96~.127），不能聚合 ❌
• .0/26（next R3）+ .64/27（next R4）→ 下一跳不同 ❌

第三步：清点 t1 时刻 R1 的路由表

nodes:
  Net1 [cloud] @ (0, 0) | "199.10.20.0/27"
  R2 [router] @ (2, 0) | "R2"
  R3 [router] @ (4, 0) | "R3"
  Net2 [cloud] @ (6, 0) | "199.10.20.32/27"
  Internet [cloud] @ (0, 1.5) | "Internet"
  R1 [router] @ (2, 1.5) | "R1"
  R4 [router] @ (4, 1.5) | "R4"
  Net3 [cloud] @ (6, 1.5) | "199.10.20.64/27"
  Host [server] @ (2, 3)
  Net4 [cloud] @ (4, 3) | "199.10.20.128/25"
edges:
  Net1 -- R2
  R2 -- R3 : "5"
  R3 -- Net2
  Internet -- R1 (S0)
  R1 (S2) -- R3 : "6"
  R1 (S3) -- R4 : "3"
  R3 -- R4 : "4"
  R4 -- Net3
  R1 -- Host
  R4 -- Net4
highlight:
  edges: R1--R3, R2--R3

上图为 t1 时刻拓扑（已删除断开的 R1-R2 链路）。蓝色高亮的 R1 → R3 → R2 即为 R1 到 199.10.20.0/27 子网的新最短路径。

聚合后 R1 路由表：

合计 5 条。

最终答案是 C（5）。

编者注（生僻术语）："充分路由聚合"在 408 题里意思是——所有可以合并的连续前缀都要合（等价于 CIDR Supernetting 用到极致），但绝不能跨下一跳合也绝不能合并不连续前缀。这两条边界考点经常出现在错项里。

第一步：先按"内部网关协议（IGP）vs 外部网关协议（EGP）"分类：

III 排除：BGP 不是 IGP，与题面要求"内部网关协议"矛盾。

第二步：在剩下的 IGP（RIP、OSPF）里看谁支持区域划分：

• OSPF 的 area：把一个 AS 切成多个 area（编号 0、1、2…，area 0 必为骨干）。区域内部跑链路状态算法（每台路由器持有 area 内完整 LSDB），区域之间通过 ABR（Area Border Router）汇总通告。这样做的收益：
  1. 限制 LSA 泛洪范围——LSA 只在本 area 内泛洪，跨 area 由 ABR 摘要重发，控制控制平面开销
  2. 缩小 LSDB 大小——每台路由器只装本 area 的拓扑，节省内存
  3. 加快收敛——一个 area 内拓扑变化不会触发别的 area 重新计算
• RIP 不支持区域：RIP 只有"自治系统"一个层级，所有路由器同等地相互广播 RIP 报文，不存在 area 概念。RIP 的扩展能力靠"跳数硬上限 15"硬扛，规模一大就崩。

III 排除（已在第一步），II 排除，仅 I 满足。

最终答案是 A（仅 Ⅰ）。

编者注（生僻术语）：BGP 自身确实有一种叫 "联邦（confederation）" 的机制把一个大 AS 拆成若干子 AS，看起来"像"分区。但这是 BGP 在 EGP 角色下的内部组织手段，不属于 IGP 的区域划分，且术语是"sub-AS / 联邦"不是"area"。考研题里只要看到"内部网关协议 + 区域划分"就锁定 OSPF。

第一步：算新前缀长度

原网络 /22 划成 32 个均衡子网，借 $\log_2 32 = 5$ 位作为子网号 → 新前缀 $22 + 5 = 27$，即每个子网都是 /27。

第二步：算每个子网容量

/27 的主机位 = $32 - 27 = 5$ 位 → 每个子网 $2^5 = 32$ 个 IP 地址（包含网络号和广播）。

第三步：定位 123.4.5.11 所属 /27

把 IP 写成二进制（重点是第三、第四字节，前两字节 123.4 不变）：

/27 网络位 = 前 27 位 = 前两字节 16 位 + 第三字节 8 位 + 第四字节高 3 位。

第四字节 0000 1011 的高 3 位 = 000，对应主机位为 0 1011。

把主机位清零得到子网网络号：

子网网络号 = 123.4.5.0/27，覆盖范围 .5.0 ~ .5.31，123.4.5.11 落在区间内 ✓。

验证另一种思路（按 /27 步长 32 跳）：

• /27 子网网络号步长 = 32
• 第四字节边界：.0、.32、.64、.96、.128、.160、.192、.224
• 11 < 32 → 落在以 .0 起始的子网

第三字节按步长 1 递增（每个 /27 里第四字节走完一轮 32 个就推进第三字节，但第三字节本身完整保留），123.4.5.x 所在那一段以 .5.0 / .5.32 / .5.64 / … 划开，11 在 [0, 32) 内 → 123.4.5.0/27。

最终答案是 C（123.4.5.0/27）。

编者注（生僻术语）："规模均衡"在子网划分题里特指"所有子网容量相同"——所以从 /22 划 32 个等容量子网就是统一借 5 位、统一变 /27。如果是"规模不等"则要走 VLSM（Variable Length Subnet Mask），按需分配不同长度的前缀。

Cookie 是什么：RFC 6265 定义的 HTTP 状态保持机制——HTTP 协议本身无状态，每个请求互相独立；服务器通过 Set-Cookie 响应头把一段小数据（≤ 4 KB）写入客户端，浏览器之后每次访问同域名都自动在 Cookie 请求头里把它带回服务器，从而让服务器识别"是谁来了"。

Cookie 的典型用途（围绕"识别 + 持久化少量状态"展开）：

为什么 D 错：缩短响应时间是 Web 缓存（浏览器缓存、Cache-Control / ETag、代理缓存、CDN）的功能，不是 cookie 的功能。两个机制完全独立：

• 缓存 解决的是"同一份资源不必重复传输"——通过 Cache-Control、ETag、Last-Modified 这些头部协商。
• Cookie 解决的是"如何识别用户身份"——它甚至会增加每次请求的开销（每个请求都要带回服务端）。

把这两者混为一谈是 D 项的核心陷阱。

最终答案是 D（缩短 Web 对象的响应时间）。

编者注（生僻术语）："Web 对象"指 HTTP 响应里的资源实体（HTML 页、图片、CSS、JS 文件等）。缩短 Web 对象响应时间的标准手段：① 浏览器本地缓存（Cache-Control: max-age）；② 条件请求（If-None-Match + 304 Not Modified）；③ 代理缓存 / CDN；④ HTTP/2 多路复用；⑤ 持久连接（Connection: keep-alive）。这些都跟 cookie 无关。

(1) 设计思想 [4 分]

关键洞察：BST 中离 K 最近的关键字最多只有两个。把树中所有关键字放到中序序列里就是有序数组，K 在数轴上的位置无非三种：

• K 命中某个结点 → 距离为 0，答案唯一就是 K；
• K 落在两个相邻关键字之间 → 答案就是这两个邻居：比 K 小的最大值（记为 floor） 和 比 K 大的最小值（记为 ceil） 之一，或两者并列；
• K 比整棵树最小值还小（或比最大值还大）→ 只有 ceil（或只有 floor）。

为什么不需要遍历整棵树？一旦确定了 floor 和 ceil，离 K 比这两个邻居更远的所有结点都可以丢掉——不可能更近。BST 的结构刚好支持「沿一条路径」就找出 floor 和 ceil：

• 当前结点 cur->data < K：cur 自身和它的整个左子树都 < K，但右子树里可能藏着比 cur 更接近 K（仍 < K）的结点，所以 cur 是当下最佳的 floor 候选，然后向右走继续找；
• 当前结点 cur->data > K：对称，cur 是当下最佳的 ceil 候选，然后向左走；
• 当前结点 cur->data == K：直接命中，距离 0，结束。

完整流程：

1. 从根开始，用迭代方式下降；下降途中每访问一个结点就按上述规则更新 floor 或 ceil，并向对应方向走；命中则提前结束。
2. 走到空指针时停止。此时 floor、ceil 至少有一个存在。
3. 比较 K − floor 与 ceil − K：哪边小输出哪边；相等则两个都输出。

整条路径长度 ≤ BST 高度 h，所以时间 O(h)，空间 O(1)（只用了几个标量）。

编者注（生僻术语）：术语 floor (下界) 指 BST 中 ≤ K 的最大键，ceil (上界) 指 ≥ K 的最小键。这两个名字出自数学里的「向下取整 / 向上取整」，在 BST / 有序集合面试题中是高频概念，记住它能省下很多解释。

(2) 代码实现 [9 分]

typedef struct BSTNode {
    int data;
    struct BSTNode *left, *right;
} BSTNode;

// 找出 BST 中与 K 之差绝对值最小的所有关键字并打印
// 输出形式：第一行为最小 |差|，第二行升序输出对应关键字
void closestKey(BSTNode *T, int K) {
    int hasFloor = 0, hasCeil = 0;     // floor / ceil 是否已经找到
    int floorV = 0,  ceilV = 0;        // 当前最佳的 floor / ceil 值
    BSTNode *cur = T;

    while (cur != NULL) {
        if (cur->data == K) {                 // 命中：差为 0，唯一答案就是 K
            printf("0\n%d\n", K);
            return;
        } else if (cur->data < K) {
            // cur 比 K 小，是更优的 floor 候选；右子树里可能还有更接近 K 的下界
            if (!hasFloor || cur->data > floorV) {
                hasFloor = 1;
                floorV = cur->data;
            }
            cur = cur->right;
        } else {                              // cur->data > K
            if (!hasCeil || cur->data < ceilV) {
                hasCeil  = 1;
                ceilV    = cur->data;
            }
            cur = cur->left;
        }
    }

    // 路径走完，根据 floor / ceil 是否存在以及谁更近输出结果
    if (!hasFloor) {                                          // 整棵树都比 K 大
        printf("%d\n%d\n", ceilV - K, ceilV);
    } else if (!hasCeil) {                                    // 整棵树都比 K 小
        printf("%d\n%d\n", K - floorV, floorV);
    } else {
        int df = K - floorV, dc = ceilV - K;
        if (df < dc)      printf("%d\n%d\n", df, floorV);
        else if (dc < df) printf("%d\n%d\n", dc, ceilV);
        else              printf("%d\n%d %d\n", df, floorV, ceilV);  // 并列双解，升序
    }
}

关键点说明：

• 沿一条路径下降，绝不递归整棵树。考研学生最容易写的版本是「中序遍历整棵树挨个比较」——它能算出正确答案、拿到正确性那部分分，但它是 O(n)、完全没用上 BST 的性质，会丢掉最优性那部分分。本题真正想考的，就是用 BST 性质把它做到 O(h)：能做对是基础，能做到最优才是这道题的区分点。
• floor/ceil 各更新一次就够吗？够。沿路径走时，每转向右就保证 floor 在变大、每转向左就保证 ceil 在变小，所以走到底时 floor 是路径上 ≤ K 的最大者、ceil 是路径上 ≥ K 的最小者；又因为 BST 性质保证「不在路径上的结点不可能比路径上的结点更接近 K」，floor/ceil 即为全局最优。
• 并列输出顺序：题目说「所有结点」，并列时 floor < K < ceil，所以 floorV ceilV 自然就是升序，无需额外排序。
• 复杂度：时间 O(h)，h 为树高（平均 O(log n)，最坏退化成单链时 O(n)）；空间 O(1)，只用了几个标量。如果用递归写，则会多 O(h) 的栈空间，本题用迭代更优。

(1) 出栈序列判定

答案：第一个 {2, 3, 1, 6, 4, 7, 5, 8} 不可以；第二个 {2, 3, 1, 4, 6, 5, 7, 8} 可以。

判定方法：模拟"按 1, 2, 3, ... 顺序入栈，按目标序列要求出栈"的过程，若某一步出栈要的元素不在栈顶就判失败。

序列 1 模拟（输入 1..n 依次入栈）：

结论：序列 1 不可由栈得到。

序列 2 模拟——按相同方法逐步推，可以走通至最后 P_8 = 8 出栈，全程无矛盾。具体过程可由读者自行验证（关键点：4 直接出后再 push 5,6，先 pop 6 再 pop 5）。结论：序列 2 可以由栈得到。

(2) 不能由栈得到的序列中 P_i, P_j, P_k 的大小关系

答案：存在 i < j < k 满足 $P_j < P_k < P_i$（即 P_i 最大、P_j 最小、P_k 居中），下标递增但值呈"大-小-中"模式。

证明（反证）：若出栈序列出现 i<j<k 满足 $P_i > P_k > P_j$（即 $P_j < P_k < P_i$），考察 P_i 出栈那一刻——

• $P_j > P_i$？不，$P_j < P_i$。所以 P_j 在 1..n 中比 P_i 小，P_j 入栈在 P_i 之前（按 1..n 顺序入栈，小数先入）；
• 既然 P_j 入栈在 P_i 之前，且 P_j 在 P_i 之后才出（因为 i < j），P_i 出栈时 P_j 必在栈中且在 P_i 下方；
• 同样地，$P_k < P_i$，P_k 也是入栈在 P_i 之前。但 $P_k > P_j$，且 P_k 比 P_j 后出（j < k），所以 P_i 出栈时 P_k 在栈中且在 P_j 上方、P_i 下方。

P_i 出栈后，栈顶是 P_k（不是 P_j，因为 P_k 在 P_j 上方）。要让 P_j 在 P_k 之前出（j < k 意味着 P_j 先出）就违反栈 LIFO——栈顶必先出，即 P_k 应先于 P_j 出栈。矛盾。

用序列 1 验证：{2, 3, 1, 6, 4, 7, 5, 8}。取 i=4, j=5, k=7（1-indexed）：$P_4=6, P_5=4, P_7=5$。$P_5 < P_7 < P_4$（4 < 5 < 6）✓——刚好是不可由栈得到的关键三元组。

(3) n = 4 时以 2 开头的出栈序列个数

答案：5 个，分别是 {2,1,3,4}, {2,1,4,3}, {2,3,1,4}, {2,3,4,1}, {2,4,3,1}。

推导：P_1 = 2 意味着已 push 1、push 2、pop 2，当前栈 = [1]，待入 = [3, 4]。从此状态出发的所有合法栈操作：

                [1] | 待入 [3,4]
               /                \
        pop 1 (→ 21..)        push 3 (→ 23..)
        |                     |
       [] | [3,4]            [1,3] | [4]
      /        \             /          \
   ...2,1,3,4  ...2,1,4,3  pop 3      push 4
                             |          |
                           [1] | [4]   [1,3,4] | []
                           /     \      |
                       pop 1   push 4   pop 4,3,1 → 2,4,3,1
                         |       |
                  ..2,3,1,4  ..2,3,4,1

共 5 条到达终点的路径，对应 5 个序列：

(4) 用 M（n=k−1 时的总数）表达 n=k 的几个数量

设 n 个数依次入栈出栈的合法出栈序列总数为 $C_n$（恰好是卡特兰数 Catalan number）。题面给定 $C_{k-1} = M$。

以 1 开头的出栈序列数

答案：M 个。

P_1 = 1 意味着 push 1 后立刻 pop 1，状态变为"栈空 + 待入 2..k"——这正是 n = k − 1 个数（2, 3, ..., k）的独立栈操作问题，序列数 = $C_{k-1} = M$。

以 2 开头的出栈序列数

答案：M 个。

P_1 = 2 意味着 push 1、push 2、pop 2，状态：栈 = [1]，待入 = [3, ..., k]，还要再出 k−1 个数。

记 1 在 P_t 位置出栈（$t \in \{2, 3, ..., k\}$）。在 P_1 与 P_t 之间出栈的 t−2 个数必为 {3, ..., t} 中元素（因为 1 在栈底，能出栈的"上层"必是 3..t）；P_t 之后出栈的 k−t 个数是 t+1..k。这两段彼此独立，分别对应 $C_{t-2}$ 和 $C_{k-t}$ 种组合。求和：

$$\text{以 2 开头的数} = \sum_{t=2}^{k} C_{t-2}\cdot C_{k-t} = \sum_{j=0}^{k-2} C_j\cdot C_{k-2-j}$$

由卡特兰数卷积恒等式 $C_n = \sum_{j=0}^{n-1} C_j \cdot C_{n-1-j}$，把 $n = k-1$ 代入即得右式 = $C_{k-1} = M$。

与 (3) 验证：n = 4 时以 2 开头 = $C_3$ = 5 ✓。

n = k 时的总出栈序列数

答案：$C_k = \dfrac{4k-2}{k+1}\, M$。

推导——卡特兰数的递推 $C_k$ 与 $C_{k-1}$ 的比值：

$$\frac{C_k}{C_{k-1}} = \frac{\binom{2k}{k}/(k+1)}{\binom{2k-2}{k-1}/k} = \frac{k}{k+1}\cdot\frac{(2k)(2k-1)}{k\cdot k} = \frac{2(2k-1)}{k+1} = \frac{4k-2}{k+1}$$

所以 $C_k = \dfrac{4k-2}{k+1}\cdot C_{k-1} = \dfrac{(4k-2)M}{k+1}$。

直观验证（k=4，M=5）：$C_4 = \dfrac{14}{5}\cdot 5 = 14$ ✓（卡特兰数 1, 1, 2, 5, 14, 42 ...）。

编者注（生僻术语）：n 个数依次入栈所有合法出栈序列数 = 第 n 个卡特兰数 $C_n = \dfrac{1}{n+1}\binom{2n}{n}$。这一结果有多种等价模型——括号匹配、不相交弦、二叉树形态、网格路径等。考研只考"出栈序列计数"这一种，记住 $C_4 = 14$、$C_5 = 42$ 这几个常用值就能秒应对小 n 题；大 n 用递推 $C_k = \dfrac{4k-2}{k+1} C_{k-1}$。

本题考查 定长指令字下三种指令格式（R/I/M）的字段划分、操作码空间分配、指令译码与执行、以及用给定指令集实现一段表达式。四问层层递进：先从「按字节编址 + 字长」定宽度，再从「字段位置」判操作码能否复用，接着完整译码并追踪一次执行，最后做指令编码填空。

(1) 主存单元与通用寄存器的宽度 [2 分]

• 主存单元宽度 = 8 位：题面明确「按字节编址」——每个存储器地址对应一个字节，所以一个主存单元就是 1 字节 = 8 位。
• 通用寄存器宽度 = 16 位：本机是 16 位计算机（字长 16 位）；R 型/I 型的运算结果、M 型一次取/存的数据都以「字」为单位，寄存器必须能容纳一个完整的字 → 16 位。

编者注（易错点）：主存单元宽度由「编址单位」决定（按字节编址 = 8 位、按字编址 = 字长），不是字长；寄存器宽度才由字长决定。两个「宽度」问的是不同东西，别都写 16 位。

(2) op1 与 op2、op2 与 op3 能否同编码 [2 分]

先看三个操作码字段各自的位置：

• op1 与 op2 可以相同。op1 在低 4 位 [3:0]，op2 在高 4 位 [15:12]，分属不同字段；指令类型先由 [15:12] 判定——[15:12]=0000 才是 R 型（再看 [3:0] 的 op1），[15:12]=op2(≠0000) 是 I 型。即使 op1 与 op2 取相同的 4 位值，一个看 [3:0]、一个看 [15:12]，互不干扰。
• op2 与 op3 不可以相同。两者都占 [15:12]，分别区分 I 型与 M 型；若 op2=op3，取指时读到这个 [15:12] 值就无法判断指令是 I 型还是 M 型 → 译码冲突。
• 补充：op2、op3 还必须都 ≠ 0000（否则与 R 型前缀相撞）。题给 op2=0100、op3=1110/1111，确实互不相同且都 ≠0000 ✓。

编者注（解题套路）：「操作码能否相同」一律先问「它们在不在同一字段」。同字段 → 必须互不相同（否则译码歧义）；不同字段 → 可以相同（由别的字段消歧）。

(3) 指令 0000 0010 1001 0001 的执行结果 [2 分]

先译码（[15:12]=0000 → R 型）：

所以指令语义是 R[2] ← R[2] + R[9]（rt 既是被加数也是结果寄存器）。

再执行：R[2]=ABCDH，R[9]=F001H，按 16 位相加（最高位进位丢弃）：

  ABCD
+ F001
------
  9BCE     D+1=E；C+0=C；B+0=B；A+F=0x19 → 留 9 进 1，进位超出 16 位被丢弃

• R2 = 9BCEH
• R9 = F001H（源寄存器只读，不参与写回，保持不变）

编者注（题面笔误）：题面 R(9)=F00H1 应为 F001H（H 后缀位置笔误），本解析按 F001H 计算。

编者注（易错点）：① A+F 产生的最高位进位在 16 位机里自动丢弃，结果取低 16 位 9BCEH，不要写成 5 位的 19BCEH；② R 型 R[rt] ← R[rt] op R[rs] 只改 rt（R2），rs（R9）只读不写。

(4) 用 4 条指令实现 y = 16x − 5 [4 分]

变量布局：x、y 都是 16 位带符号整数 = 2 字节；按字节编址、依低→高连续存放，x 的地址在 R15。所以 x 在 M[R15+0]、y 在 M[R15+2]（x 占 R15 与 R15+1 两个字节，y 紧随其后）。

算法：y = 16x − 5 = (x << 4) − 5，四步——取 x → 左移 4 位（×16）→ 加 (−5) → 存到 y。

对照填空位置：

• ① = 1110（I1 的 [15:12]，取数 op3）
• ② = 0000 0100（I2 的 [11:4]：rt=0000 即 R0、num=0100 即移 4 位）
• ③ = 1111 1011（I3 的 [7:0]：−5 的 8 位补码 = FBH）
• ④ = 0000 0000 0010（I4 的 [11:0]：offset = +2，指向 y）

编者注（易错点）：

• y 的偏移是 +2 不是 +1——16 位整数占 2 字节，按字节编址下相邻整数的地址差 2。
• −5 必须填补码并符号扩展：imm8 = 1111 1011（FBH），加立即数时符号扩展成 FFFB 再加，等价于减 5；若填 0000 0101（+5）就把减做成了加。
• 左移的 num 是移位位数（4）直接写在 [7:4]，不是寄存器号；×16 = 左移 4 位。

本题在 2026-43 的指令系统之上，就一个单总线 / 多路选择器风格的 CPU 数据通路考查 多路选择器识别、立即数扩展宽度、取指阶段控制信号、左移指令控制信号。

通用思路：每一类指令在每一阶段都对应一组确定的控制信号取值。读题时先想清楚"这一拍数据流向哪里"，再去逐一确定每个控制信号。

控制信号速查（以图 44 约定）：

(1) ① 和 ② 是什么部件 [1 分]

多路选择器（MUX）。

理由： 不同指令类型对寄存器编号的取法不同——

• R 型指令读 / 写 rs、rt（来自 IR.rs / IR.rt 字段）；
• M 型指令固定取 R[0] 作存数 / 取数寄存器、R[15] 作基址。

需要在 "IR 字段" 与 "固定 0 / 15" 之间二选一 → 多路选择器。

(2) EXTOP 至少几位 [2 分]

1 位。

理由： 题干给出三类立即数情形：

• I 型 imm8 当带符号 → 符号扩展；
• I 型 imm8 当无符号 → 零扩展；
• M 型 offset 当带符号 → 符号扩展。

总共只有 零扩展 / 符号扩展 两种模式，1 位即可编码（0 表零扩展，1 表符号扩展）。

易错点： "EXTop 几位"看的是有多少种扩展模式，不是有多少种指令。本题虽然有 R/I/M 三种指令格式，但扩展操作只有 2 种，故 1 位足够。

(3) 取指周期的 4 个控制信号 [4 分]

取指阶段要做的事：

1. 把 PC 当作主存地址送 MAR；
2. 读主存把指令送 IR；
3. 同时把 PC + 2 算出，更新 PC（题目要求"取指周期完成 PC 增量"）。

逐个确定：

编者注（生僻术语）： "取指期完成 PC 增量"是教学型 CPU 的常见简化——把 PC 自增的 ALU 操作和指令读取并行做，省一个时钟周期。真实 CPU 里通常用 专用 PC 加法器（不与主 ALU 共用），同样能并行。

(4) 左移指令周期的控制信号 + EXTop 是否同 M 型 [2 分]

左移指令是 R 型（OP1 = 0010，从 2026-43 (4) 推得 num 字段直接当移位位数）。

执行阶段动作：把寄存器内容左移立即数指定的位数，写回 rt。

EXTop 与 M 型的对比：

• M 型：offset 是带符号整数 → EXTop = 1（符号扩展）；
• 左移指令：num 字段是无符号移位位数（从来不是负移位）→ EXTop = 0（零扩展）。

结论：左移指令与 M 型的 EXTop 不同。 左移用零扩展，M 型用符号扩展。

易错点： "立即数扩展"不是只有一种——要看立即数的语义。地址偏移可正可负，必须符号扩展；移位位数恒为非负，零扩展即可。两者使用同一个扩展器但 EXTop 取值相反。

（1）逐时刻推演

关键约束（请反复看 3 遍）：抢占只在时钟中断（每 10 ms）时发生。所以"P3 在 t=12 到达"、"P4 在 t=14 到达"这种非中断时刻只让进程进就绪队列，不会立刻抢 CPU。

完整时间线

CPU 占用时序图（t=0 到 t=225）：

total: 225
schedule:
  idle @ 0-10
  P2 @ 10-20
  P4 @ 20-70
  P2 @ 70-80
  P4 @ 80-90
  P1 @ 90-140
  P3 @ 140-180
  P1 @ 180-225

答案统计

• 时钟中断次数：从 t=10 起到 t=225，每 10 ms 一次，依次是 10、20、30、…、220 共 22 次
• CPU 调度次数：发生在 t = 10、20、70、80、90、140、180 共 7 次
• 首次调度时刻：