2018年计算机408真题

答案：B。

**思路：**栈遵循后进先出，S₁ 的栈顶是 2，S₂ 的栈顶是 +。每次先弹出的数记为 a，后弹出的记为 b，而实际运算必须是 b op a。加法、乘法交换次序不影响结果，减法却不能颠倒。

第一次弹出 a=2、b=3 和 +，算 $3+2=5$，S₁ 从栈底到顶变为 [5,8,5]。第二次弹出 a=5、b=8 和 −，算 $8-5=3$，栈变为 [5,3]。第三次弹出 a=3、b=5 和 ×，算 $5\times3=15$，栈只剩 [15]，因此选 B。A 的 −15 常见于把第二次减法算成 5−8；C、D 的 ±20 都不符合这三次弹出、运算、压回的状态变化。不能把原数列直接按通常算术表达式优先级计算。

答案：C。

**基础：**队列只能从队头依次取出 1～6，取出的元素可以立即输出，也可以暂存在栈中；栈中的暂存元素最后只能逆序输出。判定时重点看为了输出前面的某个元素，哪些更早入队的元素必须先压栈。

A 可立即输出 1、2，把 3、4 压栈，再立即输出 5、6，最后弹出 4、3。B 可把 1 压栈，立即输出 2～6，再弹出 1。D 可把所有元素按 1～6 压栈，再从栈顶依次弹出 6～1，均可实现。C 要先输出 3、4、5、6，就必须把 1、2 暂存栈中，其中 2 在 1 上方；之后想先输出 1 再输出 2，违反栈顶只能先出 2 的规则，因此 C 不可能。三种允许操作中没有把栈内元素直接调换位置的操作。

答案：A。

**基础：**对称矩阵满足 $m_{i,j}=m_{j,i}$，只存上三角即可保留全部独立元素。本题上三角包括主对角线，按行优先意味着先存第 1 行的 12 项，再存第 2 行的 11 项，依此类推。矩阵行列号从 1 开始，但 C 数组下标从 0 开始。

在 $m_{6,6}$ 之前，前 5 行已经存入 $12+11+10+9+8=50$ 个元素。第 6 行上三角从 $m_{6,6}$ 开始，它是该行第一项，行内没有额外偏移，所以其下标就是 50，选 A。B 的 51 是从 1 开始计数时的存储序号；C 的 55 多计了下三角部分；D 的 66 与前面行数之和不符。通用计算是先累加此前各行长度，再加本行偏移 j−i，本题偏移为 0。

答案：A。

**思路：**题设每个非叶结点都有两个孩子，说明没有度为 1 的结点。设非叶结点有 t 个，叶结点有 k 个，则总结点数为 k+t。一棵非空树的边数等于总结点数减 1，而每个非叶结点向下连两条边，因此还可以把边数写成 2t。

令 $2t=k+t-1$，得到 $t=k-1$，所以总结点数为 $k+(k-1)=2k-1$，选 A。B 的 2k 忽略了根没有父边这一差别；C 的 $k^2$ 与边数关系不符；D 的 $2^k-1$ 错把叶结点数 k 当成了树的层数。也可用满二叉树关系复核：若有 h 层，叶数 $k=2^{h-1}$，总结点 $2^h-1=2k-1$。k=1 时树只有根一个结点，公式仍成立。

答案：A。

**步骤：**哈夫曼编码每次合并当前权值最小的两棵树。按 d=2、b=3、f=4、a=6、c=8、e=10 排序，依次合并为 d+b=5、f+5=9、a+c=14、9+e=19、14+19=33。沿树边指定 0、1，左右取法可以互换，但兄弟及层次关系必须符合合并过程。

A 中 a、c 为 00、01，对应权 14 的子树；d、b 为 1010、1011，共同形成权 5，再与 f=100 组成权 9，最后与 e=11 合并，正好符合构造。B 的 a=00 是 d=000、e=0010 的前缀，C 的 a=10 是 b=1011 的前缀，都不能成为前缀编码。D 虽无前缀冲突，却把最小权值的 b=3、d=2 放在不同子树，违背它们首先合并为兄弟的必然关系。因此选 A。

答案：C。

**基础：**二叉排序树要求一个结点的左子树所有关键字都比它小，右子树所有关键字都比它大，不只是直接孩子满足关系。图中 x₁ 的右孩子为 x₂，x₂ 的左孩子为 x₃；x₃ 的右孩子为 x₄，x₄ 的左孩子为 x₅。

x₅ 位于 x₃ 的右子树中，所以 $x_3<x_5$；同时 x₅ 是 x₄ 的左孩子，所以 $x_5<x_4$，合得 $x_3<x_5<x_4$，选 C。完整中序序列为 x₁、x₃、x₅、x₄、x₂，故 $x_1<x_3<x_5<x_4<x_2$。A 把最大值 x₂ 放在 x₅ 前，B 把 x₄、x₅ 顺序颠倒，D 把 x₄ 放在 x₃ 前，均错误。读图时要根据左右子树的整体范围确定大小。

答案：D。

**基础：**拓扑序列要求每一条有向边 u→v 的起点 u 排在终点 v 之前。图中主要约束为 1→2、1→3、5→2、2→3、2→6、3→4、6→4、5→4；因此 2 必须在 1 和 5 之后，3、6 必须在 2 之后，4 必须在 3、6 之后。

A 的 1、5 在前，随后 2、3、6、4，符合全部依赖；B 的 5、1、2、6、3、4 只交换了没有先后依赖的 3、6，也合法；C 的 5、1、2、3、6、4 同样合法。D 的 5、2、1、6、3、4 把 2 放在 1 前，直接违反边 1→2，所以它不是拓扑序列，选 D。不能仅看某个顶点有几条出边决定顺序，而要逐条检查它依赖的前驱是否已排在前面。

答案：B。

**基础：**3 阶 B 树一个结点最多有 3 棵子树、2 个关键字。非根内部结点至少有 $\lceil3/2\rceil=2$ 棵子树，至少有 1 个关键字；非叶根至少有 2 棵子树，也至少有 1 个关键字。题目高度按包含关键字的结点层数计算，叶层同样含关键字。

要让高度为 5 而关键字最少，各内部结点都取最少的两个孩子，每个结点都只存一个关键字。五层的结点数依次为 1、2、4、8、16，因此最少关键字数为 $1+2+4+8+16=31$，选 B。A 的 15 只对应 4 层；C 的 62 把每结点错误地强制存 2 个关键字；D 的 242 是按每结点 3 个孩子、2 个关键字得到的最大规模，不是最少。

答案：C。

**步骤：**线性探测遇到冲突后依次试下一槽，探测下标按表长 7 回绕。三个关键字的初始地址分别是 $22\bmod7=1$、$43\bmod7=1$、$15\bmod7=1$，都落在 1 号槽。

插入 22 时槽 1 为空，一次探测成功；插入 43 时槽 1 已有 22，再探测槽 2，共两次；插入 15 时槽 1、2 都已占用，直到槽 3 才插入，共三次。查找成功时必须从各自散列地址沿同样路径比较，所以查找长度为 1、2、3，等概率平均为 $(1+2+3)/3=2$，选 C。A 的 1.5、B 的 1.6 没有正确平均三条查找路径；D 的 3 是最长一次的比较数，不是平均数。不能只看到三个元素最终都能直接读到，就把每次查找都算成 1。

答案：D。

**基础：**希尔排序按间隔 d 把下标差为 d 的元素分为一组，对每组作插入排序。用从 1 开始的位置编号，d=5 时初始序列分组为：位置 1、6、11 的 (8,1,6) 排成 (1,6,8)；位置 2、7 的 (3,4) 不变；位置 3、8 的 (9,7) 排成 (7,9)；位置 4、9 的 (11,5) 排成 (5,11)；位置 5、10 的 (2,10) 不变，恰得第一趟结果。

对第一趟再用 d=3：位置 1、4、7、10 的 (1,5,4,10) 排成 (1,4,5,10)；位置 2、5、8、11 的 (3,2,9,8) 排成 (2,3,8,9)；位置 3、6、9 的 (7,6,11) 排成 (6,7,11)，恰得第二趟。故选 D。A、B 的第一增量 3 不符；C 的第二增量 2 应使奇偶位置各自有序，但第二结果的奇数位 1、6、3、5、11、9 并未有序。

答案：A。

**本题采用的建堆约定：**按教材常用的自底向上建堆算法，从最后一个非叶结点开始，按下标递减的顺序逐个向下调整。对 7 个元素用下标 1～7 表示，最后一个非叶结点为 $\lfloor7/2\rfloor=3$，所以依次调整下标 3、2、1。调整父结点前，其左右子树都已是大根堆；调整时与较大的孩子比较并交换。

**逐步调整：**初始序列为 6,1,5,9,8,4,7。

1. 下标 3 的元素 5 的两个孩子是 4、7，和较大的 7 交换，得 6,1,7,9,8,4,5。
2. 下标 2 的元素 1 的两个孩子是 9、8，和较大的 9 交换，得 6,9,7,1,8,4,5。
3. 调整根：6 与孩子 9、7 比较，先和 9 交换，得 9,6,7,1,8,4,5；6 下移后继续与孩子 1、8 比较，再和 8 交换，得 9,8,7,1,6,4,5。

这四个状态正是 A。B 先调整下标 2，再调整下标 3，不符合本题默认的下标递减扫描；C、D 也提前调整了根，均不符合这一标准流程。

**严谨边界：**大根堆本身只要求每个父结点不小于其孩子，并不要求任意建堆算法都按同一顺序进行。下标 2 和 3 的子树互不依赖，若允许先调 2 再调 3，B 也能合法建成大根堆。因此选择 A 是采用本题的标准建堆扫描约定，不能把 B 说成在所有建堆方法下都不合法。

答案：D。

**基础：**二进制只用 0、1 两种符号，这与电子器件的两种稳定状态天然对应，例如高低电平。数字电路无需把许多细微电平精确区分为不同数字，因而器件制造与状态判别更容易，II 正确。

I 也正确，二进制加法只有少数基本组合：0+0=0、0+1=1、1+1=10，乘法也很简单，易形成统一的运算规则。III 正确，0、1 可以直接对应布尔变量，通过与、或、非、异或等逻辑门组成半加器、全加器，进而实现多位算术运算。三项都解释了采用二进制的原因，选 D。A 漏掉逻辑电路实现方面，B 漏掉器件易制造方面，C 漏掉运算规则简单方面。二进制位串虽然可能更长，但电路实现简洁是这里关注的主要优势。

答案：C。

**步骤：**32 位補码最高位为 1 时表示负数。对 FFFFFFDFH 取反得到 00000020H，再加 1 得 00000021H=33，所以 x=−33；y 的符号位为 0，$41\mathrm H=4\times16+1=65$，所以 y=65。

差为 $x-y=-33-65=-98$。98 的十六进制为 62H，取反加 1 得 $\sim00000062\mathrm H+1=FFFFFF9E\mathrm H$；−98 在 32 位有符号整数范围内，不发生溢出。故选 C。A、D 既把 x 算成 −65，又把十六进制 41H 当成十进制 41；B 虽然 x、y 正确，但 FFFFFF9DH 表示 −99，少了取反后的“加 1”。补码负数求值与构造都要完整执行取反加一。

答案：A。

**基础：**IEEE 754 单精度由 1 位符号、8 位阶码和 23 位尾数字段组成。规格化有限数的阶码编码为 1～254，真指数为“阶码编码−127”，有效尾数具有隐含的最高位 1，形式为 $1.f$。

最小规格化正数应取符号位 0、最小有效阶码编码 1、尾数字段全 0。真指数为 $1-127=-126$，有效尾数为 1.0，故数值为 $1.0\times2^{-126}$，选 A。B 的 −127 不能由规格化最小阶码得到；C 的 −128 更不属于该指数下界；D 的 $2^{-149}$ 是最小非规格化正数，其阶码字段全 0、尾数字段仅最低位为 1。题目有“规格化”限定，不能把全部正浮点数中最小的非规格化值拿来作答。

答案：A。

**步骤：**原指令最后 4 字节是写入 i 的立即数 0，其余 C7 45 FC 描述相同的操作及存放位置。改为 i=−64 时，只需把立即数部分改为 −64 的 32 位补码，不能把整条指令按小端整体倒排。

64=40H，对 00000040H 取反加 1 得 FFFFFFC0H。小端表示最低有效字节放在最低地址，四个立即数字节依次为 C0、FF、FF、FF，所以完整机器代码为 C7 45 FC C0 FF FF FF，选 A。B 的 0C 把 C0 的十六进制数位倒置；C 把正确的补码按大端顺序存放；D 同时存在字节顺序和数位错误。小端调换的是多字节数的字节顺序，不调换一个字节内部的高低半字节。

答案：B。

**基础：**右移时原来的最低位被移出，其余位向右移动一位；区别在最高位补什么。逻辑右移不考虑符号，最高位一律补 0；对补码数作算术右移时，最高位复制原符号位，以尽可能保持有符号数的数值意义。

原机器数为 11011000，移走末尾的 0 后，其余 7 位为 1101100。逻辑右移补 0，得 01101100；算术右移的原符号位为 1，补 1 后得 11101100，选 B。A 把逻辑右移也补了符号位，C 把两种结果次序颠倒，D 把算术右移错误补 0。若按 8 位补码解释，原数为 −40，算术右移得 −20；逻辑右移则得到无符号位串对应的 108，不能用它代替有符号除二。

答案：C。

**基础：**2K×1 位表示有 $2K=2048=2^{11}$ 个存储单元，所以行地址位数与列地址位数之和为 11。DRAM 采用行列地址引脚复用，先送行地址再送列地址，共用引脚数取两者位数的最大值。

要让引脚最少，应把 11 位拆得尽量接近，即 5+6 或 6+5，均需 6 个地址引脚。对应 32 行×64 列与 64 行×32 列。刷新按行进行，行数越少，一个刷新周期内要刷新的行越少，所以在两种最少引脚的方案中选 32 行、64 列，即 C。A 的 2048 行×1 列、D 的 1 行×2048 列都要 11 个地址引脚；B 虽只需 6 个引脚，却有 64 行，刷新开销比 C 大。先满足最少引脚，再比较刷新行数。

答案：B。

**本题采用的机器模型：**按计算机组成原理考试中常用的双精度浮点模型，double 型元素占 8 B，即 $\operatorname{sizeof}(\text{double})=8$。变址寄存器保存数组下标，而不是字节偏移；元素地址等于“数组首地址 + 下标 × 元素大小”。

本次访问地址为 2100H，首地址为 2000H，所以字节偏移为

$$2100\mathrm H-2000\mathrm H=0100\mathrm H=256\text{ B}.$$

设进入本次循环时的变址值为 $k$，则 $k\times8=256$，解得 $k=32$，选 B。C 的 64 相当于误将 double 当成 4 B 元素；A 的 25、D 的 100 都不满足 256 B 的偏移关系。题目问的是进入本次循环时的值，尚未执行取完后的自动加 1；该次取完后寄存器才变为 33。

**严谨边界：**8 B 是本题采用的双精度机器模型约定，并非 C 语言对所有实现强制规定的 double 宽度。如果机器模型另行指定 double 占 $s$ B，一般关系应是 $k=256/s$。本题依照 8 B 模型得 32，不应把数组下标 32、字节偏移 256 和取完后的寄存器值 33 混为一谈。

答案：A。

**基础：**CF 反映无符号减法是否借位，OF 反映有符号补码结果是否越界；同一位串在这两种判定中要按不同数值解释，不能看到操作数最高位都为 1 就判断溢出。

按无符号解释，FFFFFFFH=$2^{32}-1$，FFFFFFF0H=$2^{32}-16$，被减数大于减数，差为 15，不需向字长范围之外借位，所以 CF=0。按有符号解释，它们分别为 −1、−16，运算为 $-1-(-16)=15$，可在 32 位补码范围内正确表示，因此 OF=0。结果机器数为 0000000FH，选 A。B 错判借位，C 错判有符号溢出，D 两项都错。这里 CF 按题目减法借位标志的定义判断，不把加法器内部的进位输出直接当作它。

答案：D。

**基础：**同步流水线的所有段共用一个时钟周期，最慢的功能段也必须在一个节拍内完成；此外，流水段寄存器还要完成数据锁存与输出，题目给出这部分延迟为 20 ps，必须计入周期下界。

A～E 五段功能部件耗时分别为 80、50、50、70、50 ps，最长为 A 的 80 ps。因此 $T_{\rm clk}\ge\max(80,50,50,70,50)+20=100$ ps，选 D。A 的 60 ps、B 的 70 ps 无法容纳最慢功能段；C 的 80 ps 只计组合逻辑而漏掉段寄存器延迟。五段时间总和加寄存器开销可用于单条指令经过整个流水线的延迟分析，但不能把总和当作各段共用的时钟周期。

答案：B。

**基础：**同步总线的数据率取决于每次能传多少位、每秒能做多少次传输，以及控制与地址阶段占用的额外周期。I 增加总线宽度，使一次并行传的数据更多；II 提高工作频率，使相同周期数内的传输更快；III 突发传输先给一次起始地址，再连续传多个数据单元，摊薄地址与控制开销，三项都可提高有效传输率。

IV 地址/数据线复用使同一组引脚在不同阶段分别传地址和数据，主要收益是减少引脚和线路，不能同时传这两类信息，反而需要分时占用。因此不把 IV 作为提高数据率的措施。选 B 的 I、II、III。A 漏掉突发传输，C 包含错误的 IV且漏掉 I、II，D 同样多包含 IV。要区分节省硬件成本与增加数据吞吐量。

答案：C。

**基础：**外部 I/O 中断由设备提出请求，但 CPU 是否响应还取决于中断允许状态、屏蔽情况和优先级。题目讨论通常的可屏蔽 I/O 中断，CPU 处于中断允许状态是响应的必要条件，C 正确；“允许”并不意味着每个请求都立即获准。

A 错误，中断控制器通常按预设优先级或相应仲裁规则排队，不能仅按请求到达先后决定优先级。B 错误，中断隐指令主要完成保存断点、关中断、取得服务入口等响应操作，通用寄存器现场一般由服务程序显式保存。D 错误，普通外部中断通常在一条指令执行完成的中断检测点被响应，不能把当前指令随意截断。区分设备发出请求、CPU 响应中断和软件服务中断三个阶段，选 C。

答案：C。

**基础：**多任务系统允许多个任务在一段时间内共同推进，单 CPU 上可通过交替运行实现并发；CPU 与 I/O 设备也可同时工作，多处理器上还可使多个任务真正同时执行。因此按本题对系统整体活动的描述，I 的并发和并行特征成立，不能把“并行”仅限于两个进程同一时刻占用 CPU。

II 正确，多个任务共享内存、文件和设备等资源，若不保护，可能产生竞争、数据破坏和访问越权，需要同步互斥及访问控制。III 错误，多任务并不要求多 CPU，一台单处理器计算机同样能用调度与切换运行多个任务。于是仅 I、II 正确，选 C。A、B 各漏掉一项，D 把多处理器错误当成必要条件。要区分支持多任务的软件机制与提供多个处理器的硬件条件。

答案：D。

**步骤：**优先权值越大越先运行，所以调度顺序为 P₂(30)、P₃(20)、P₁(10)。采用非抢占策略，每个进程获得 CPU 后执行完所需时间才调度下一进程。每次调度与切换都用 1 μs，T 时刻开始的首次调度也要计入。

周转时间从进程进入系统开始，不能只计 T 之后。平均值为 $(40+80+105)/3=75$ μs，选 D。A 的 54 μs 是只平均 T 后完成时间；B 的 73 μs 漏掉全部调度开销，C 的 74 μs 常见于漏计首次调度。

答案：B。

**基础：**图中每个线程的“加 1”都分为读 x 到寄存器、寄存器自增、写回 x 三条机器指令。单条指令可按题目模型交错，但每个线程内部必须保持读→加→写的顺序。不能把三条指令合起来视为不可分割操作。

初始 x=0，若两个线程都在任何一次写回前读到 0，它们各自只算出 1，最终 x=1。要得到 2，必有一个线程读到另一个已经写回的 1。前线程从读到写的三条都必须先完成，后线程才能执行自己的第一条读；后线程剩下两条按顺序完成。因此只有“thread1 三条→thread2 三条”和“thread2 三条→thread1 三条”两个序列，选 B。A 漏掉对称顺序，C、D 多计了不能使第二次读得到 1 的交错序列。

答案：A。

**基础：**安全性检测尝试找一个进程完成顺序：每一步用当前可用资源满足某个进程的剩余最大需求，该进程完成后返还原来占有的资源，再继续。总资源为 4，已分配 $2+1+0=3$，初始可用数 Work=1。

只有 P₃ 尚需 1≤Work，可以先完成。但检测中完成后 Work 增加的是其原占有量 0，仍为 1；借给它的 1 台随后归还，只是恢复原可用数。P₁、P₂ 各还需 2，都无法继续，所以不存在安全序列，选 A。B、C、D 均错误认定安全；尤其不能把 P₃ 的最大需求 1 当作额外释放资源，误把 Work 增到 2。不安全不等于此刻必已死锁。

答案：C。

**基础：**阻塞表示进程等待某个事件或资源，即使给它 CPU 也无法继续；就绪表示已具备执行条件，只是尚未获得 CPU。题目问“可能导致”，只需说明事件在合适条件下能使进程等待。

I 申请临界资源时若资源正在被其他进程使用，P 可因等待互斥条件而阻塞；II 从磁盘读数据时若需等待 I/O 完成，P 也会阻塞。III 系统把 CPU 给更高优先权进程，只是抢占了 P 的处理机，P 没有缺少运行所需条件，应从运行转为就绪，而不是阻塞。因此仅 I、II 符合，选 C。A、B 各漏掉一种阻塞原因，D 混淆了就绪和阻塞。临界资源空闲或使用异步 I/O 时也可能不阻塞，所以不能把 I、II 理解为每次必然阻塞。

答案：D。

**基础：**管程用互斥入口保证同一时刻只有一个进程执行其中代码，条件变量则用于等待某个逻辑条件，例如“缓冲区非空”。调用 x.wait() 表示当前条件尚未满足，应把调用者挂起并加入 x 对应的等待队列，同时释放管程的访问权，让其他进程有机会进入并改变条件，选 D。

A 描述的是互斥访问，管程入口已提供这项机制，wait 的作用不是保护变量 x。B 唤醒等待者对应 x.signal() 等通知操作。C 把条件变量误当成保存资源数量的计数信号量；通常由程序先判断实际共享状态，再决定是否调用 wait，wait 本身不按一个整数 x 的值决定阻塞。若等待时不释放管程，其他进程无法进入完成条件，会导致等待无法被解除。

答案：D。

**基础：**定时器周期性产生中断，操作系统据此推进时间、统计 CPU 使用量和实现时间片调度。I 更新内核时钟变量，使系统能够表示当前时间、判断睡眠或定时等待是否到期；II 把本次时钟间隔计入当前运行进程的 CPU 用时；III 相应扣减该进程在当前时间片内的剩余时间，三项都属于时钟服务的工作。

例如时间片开始有 10 个时钟单位，每次滴答都把剩余值减 1，到 0 时即可设置重新调度条件，同时累计已用 CPU 时间。故选 D。A 漏掉剩余时间片，B 漏掉内核时间，C 漏掉进程用时统计。更新计时信息与实际完成进程切换可处在不同的内核步骤，但这不影响三类信息需要由时钟事件维护。

答案：A。

**基础：**磁臂黏着指当前磁道持续有新请求时，算法不断服务该磁道，导致其他磁道请求长期得不到处理。FCFS 严格按请求到达次序服务；若其他磁道的请求已经排在队列中，之后到达的当前磁道请求不能越过它，因此不会因这种偏好而一直停在当前磁道，选 A。

B SSTF 每次选距离当前磁头最近的请求，当前磁道距离为 0，新请求可能不断压过远处请求，容易黏着。C SCAN、D CSCAN 若直接把扫描中不断新到达的当前磁道请求继续加入当次服务，也可能迟迟离开；它们的扫描方向并没有自动排除这种情形。通过固定当轮请求集合等变体可改善，但题目没有指定这些额外规则。判断关注“新请求能否持续插到已等待的其他请求前面”。

答案：D。

**逐项判断：**I 提前读在程序访问当前块时预先读取可能很快访问的后续块，顺序读文件时可减少等待。II 连续的簇让相邻数据更接近，减少磁头移动，也便于连续传输。III 延迟写先把修改保存在内存中，再把多次修改合并或集中写出，减少实际磁盘操作次数。IV 磁盘高速缓存让后续访问可直接从内存获得已有数据，比重新访问磁盘更快。

四种方法都能在相应访问情形下提高文件访问速度，选 D。A 漏掉写入和缓存优化，B 漏掉提前读与缓存，C 漏掉连续簇。提前读、延迟写利用的是访问规律与批量处理，并非每个工作负载都必然受益；题目问可用的优化方法，满足“可以提高”即可。不要因延迟写没有立即写盘，就误认为它只会降低效率。

答案：C。

**基础：**让权等待要求进程不能进入临界区时主动放弃处理机，转入阻塞，由其他进程继续运行，等条件满足后再被唤醒。记录型信号量的 P 操作在资源不足时把进程加入等待队列并阻塞，V 操作在资源释放时唤醒等待者，因此能实现让权等待，选 C。

A Peterson 方法用 while 条件循环等待另一进程退出，属于忙等。B swap 指令和 D TestAndSet 指令能原子地修改锁值，但以它们构成的基本自旋锁也要反复执行检测循环，通常并未放弃 CPU。因此三者能用于互斥，却不满足本题的让权等待要求。原子性解决“同时抢锁会不会都成功”，阻塞机制解决“抢不到时是否还占 CPU”，两项不能混为一谈。实际系统可组合原子指令和阻塞机制，本题比较的是所列基本方法。

答案：B。

**基础：**传输层无连接服务通常由 UDP 提供，发送数据报前无需三次握手建立连接。DNS 的普通查询和应答可以通过 UDP 交换，因此 B 符合“可以使用”；DNS 在其他情形也可使用 TCP，不影响本项成立。

A FTP 的控制连接和数据连接使用 TCP，以可靠传输命令及文件。C SMTP 发送邮件使用 TCP 的可靠字节流。D 按这道题所采用的传统 HTTP 传输模型使用 TCP，需要建立连接，所以不选。区分“可以使用 UDP”与“只能使用 UDP”：题目并没有声称 DNS 不支持 TCP。也不能因为一个应用只发少量数据，就认为它自然属于无连接服务，必须以协议规定的传输方式判断。

答案：C。

**基础：**物理层接口规范描述如何在传输介质上实际传送比特，包括机械、电气、功能和规程特性。A 接口形状属于机械特性，例如插头尺寸、连接方式；B 引脚功能规定各引脚承担发送、接收或控制等用途；D 信号电平规定以哪些电压等物理量表示状态，属于电气特性，三者都在物理层接口范围内。

C“物理地址”通常指 MAC 地址，它用来在数据链路层识别帧的源和目的接口，不是连接器或电压等物理接口规范，故选 C。名称中有“物理”二字不代表属于 OSI 的物理层；应看它是在规定比特如何形成信号，还是在标识帧交给谁。物理层负责传比特流，不负责根据 MAC 地址作帧转发判断。

答案：D。

**基础：**无线局域网用 CSMA/CA 尽量避免碰撞。要预约信道，发送站先发 RTS（请求发送），接收站在可接收时回 CTS（允许发送）；这两个帧携带持续时间等信息，听到它们的其他站点据此设置网络分配向量 NAV，在预约时间内推迟发送，故选 D。

A 确认帧 ACK 用来告知数据帧已成功收到，处在数据传输后，不是预约的请求和许可过程。B 二进制指数退避用于竞争失败后调整随机等待范围，可减少冲突，但没有由双方交换预约信息。C 使用多个 MAC 地址与信道预约无关。RTS/CTS 还可使发送端附近与接收端附近的站点分别获知占用时间，缓解隐藏站点导致的碰撞。不要把确认成功、随机竞争与事先预约这三个机制混为一谈。

答案：D。

**基础：**停等协议每发送一个数据帧就等待确认，一个周期包括帧发送时间、单程数据传播和单程确认传播。确认帧发送时间按题设忽略，但确认的传播时间不能忽略。设帧发送时间为 t，单程传播为 200 ms=0.2 s，则周期为 t+0.4 s。

信道利用率是有效发送时间占周期的比例，有 $t/(t+0.4)=0.4$，解得 $0.6t=0.16$，所以 $t=4/15$ s。数据率 3 kbps=3000 bit/s，帧长为 $L=3000\times4/15=800$ bit，选 D。A 的 240 bit、B 的 400 bit、C 的 480 bit 对应发送时间分别为 0.08、0.1333、0.16 s，代回利用率都小于 40%。最常见错误是仅计一次 200 ms，把往返等待少算一半。

答案：D。

**基础：**IP 分组跨网络转发时，两端 IP 地址保持描述最终源与目的，而链路层 MAC 地址按每一跳重新封装。H1 在 192.168.3 网络，H2 在 192.168.4 网络，不能用一个以太网帧直接跨过路由器交给 H2。

第一跳 H1 先把帧交给本网络的路由器接口 192.168.3.1，所以帧的目的 MAC 是该入口的 00-1a-2b-3c-4d-51。R 拆掉第一跳帧后，在通向 H2 的接口 192.168.4.1 上重新封装，新帧源 MAC 是出口的 00-a1-b2-c3-d4-61，目的 MAC 才是 H2 的地址。因此选 D。A、B 把第一跳目的 MAC 错写成 H2 的地址；C 把 H2 收到帧的源 MAC 错写成 H1 的地址。交换机只转发所在链路的帧，不使源 MAC 跨路由器保持不变。

答案：C。

**步骤：**一个 /21 包含 $2^{32-21}=2048$ 个地址，第三字节跨度为 8。四个网络依次覆盖第三字节 32～39、40～47、48～55、56～63，连续无空洞，而且转发接口相同，适合聚合。

四个等大的块合并，总地址数变为原来的 4 倍，前缀长度减少 $\log_2 4=2$ 位，即 /19。/19 的第三字节按 32 的倍数对齐，32 是合法起点；其范围恰为 35.230.32.0～35.230.63.255，所以聚合地址为 35.230.32.0/19，选 C。A 的 35.230.0.0/19 覆盖 0～31，范围错误；B 的 /20 范围和起点都不符；D 的 32.0/20 只覆盖 32～47，漏掉后两个网络。聚合既要前缀长度正确，也要网络边界对齐。

答案：B。

**基础：**分用是接收端把传输层收到的数据交给正确应用进程的过程。UDP 首部的目的端口号标识接收端的服务或套接字，例如收到目的端口 53 的 DNS 查询，应交给相应 DNS 服务，因此选 B。

A 源端口号说明发送端由哪个端口发出，可供接收方构造返回数据报，但它不能单独确定本地应该接收的应用。C 长度说明数据报大小，D 校验和用于检测传输差错，都不用于标识接收服务。实际系统还会结合本地 IP 地址等信息完成套接字匹配，但在本题列出的 UDP 首部字段中，承担基本分用作用的是目的端口号。发送时多个应用的数据汇入 UDP 称为复用，接收时按端口分发称为分用。

答案：D。

**基础：**基本 SMTP 的邮件内容传输采用 ASCII 文本形式，因此 D 的 ASCII 文本无须先转换即可直接传输。题目考查基础邮件协议的内容表示范围，而不是说电子邮件无法发送图片或附件。

A JPEG 图像、B MPEG 视频、C EXE 文件都属于二进制数据，任意字节可能超出基本 SMTP 的文本字符范围，需要先采用 MIME 定义的编码方式，例如 Base64，把内容转换成可传送的文本表示；接收端再按相应类型与编码还原。三者即使最终能作为邮件附件发送，也不符合“无须转换”的条件。区别在于原始内容能否直接进入基础 SMTP 的文本通道，不能把“邮件客户端支持某种附件”误当作“SMTP 直接传任意原始二进制”。

**（1）设计思想。**先缩小答案范围：n 个数组元素最多覆盖 n 个不同正整数，所以 1～n+1 不可能全都出现，最小缺失正整数必在这个区间。负数、0 和大于 n 的数，不会影响我们判断 1～n 中谁缺失。

开一个长度 n、初值全 0 的标记数组 present，其中 present[k−1]=1 表示正整数 k 出现过。扫描原数组，只对 1～n 内的值打标记，重复值重复置 1 不产生额外作用。再从标记数组开头向后找第一个 0，返回对应整数；若全部为 1，说明 1～n 都已出现，返回 n+1。

例如 {-5,3,2,3} 的 n=4，标记结果为 [0,1,1,0]，首先缺 1；{1,2,3} 标记全部为 1，答案是 4。本题只要求时间尽可能高效，没有要求常数额外空间，所以采用标记法即可达到线性时间。

**（2）C++ 实现。**用 k−1 映射数组下标，检查范围后再访问标记数组，避免负值和大值造成越界。返回类型采用long long，最后先提升n再计算n+1，使n等于INT_MAX时的理论答案仍可表示，避免int加法溢出。

#include <vector>

long long firstMissingPositive(const int a[], int n) {
    std::vector<unsigned char> present(n, 0);
    for (int i = 0; i < n; ++i) {
        if (a[i] >= 1 && a[i] <= n) present[a[i] - 1] = 1; // 仅标记候选正数。
    }
    for (int i = 0; i < n; ++i) {
        if (!present[i]) return i + 1; // 第一个未出现的正整数。
    }
    return static_cast<long long>(n) + 1;
}

**（3）正确性与复杂度。**第一次扫描后，对于每个 k∈[1,n]，标记为 1 当且仅当 k 出现过；第二次按从小到大检查，第一次遇到的缺失值自然是最小的。若无缺失，则由 n 个位置恰好覆盖 1～n，可确定 n+1 未出现。全是非正数时返回 1，重复值不会错误占用其他候选标记，n=1 时也能正确处理。

初始化和两次扫描都为 $O(n)$，整体时间 $O(n)$；标记数组占 $O(n)$ 额外空间，原数组内容没有改变。一般情况下至少要检查所有输入值，否则未查看的位置可能恰好含某个候选整数，所以线性时间已达到所需的高效目标。

**（1）所有最经济方案。**要连通 8 个城市且不浪费费用，应求无向带权图的最小生成树，共选 7 条边。用 Kruskal 思路从小权值开始，加入不会成环的边。图中的五条费用 2 的边 XA—BJ、XA—WH、TL—JN、JN—QD、QD—NJ 可全部加入，它们形成三个分量：{XA,BJ,WH}、{TL,JN,QD,NJ} 和 {CS}，累计费用 10。

接下来，CS 通过 QD—CS（3）连接比通过 WH—CS（4）便宜，所以费用 16 的最优树必须含 QD—CS。剩下两个分量可通过 WH—QD（3）或 BJ—TL（3）连接，二者等价且只能任选其一，否则多出环。BJ—WH（3）和 JN—NJ（3）连接的是已有分量内部结点，不能用于合并分量；费用 4 的其他边也无法获得同样低的总费用。

因此两个方案共同包含以下六条边：

第七条边有且仅有两种选择：**WH—QD（3）**或 BJ—TL（3）。两棵最优生成树的总费用均为 $5\times2+3+3=16$。费用不可能更小，因为最多只有五条费用 2 的边，连通还需至少两条费用不小于 3 的边；两方案均达到此下界。下面给出两棵带权图：

**（2）存储结构与算法。**可以采用邻接矩阵，矩阵项记录两城市间费用，无边处置为无穷大，且无向图矩阵对称；也可以采用邻接表，为每个城市记录邻居及边权。求最小生成树使用 Kruskal 或 Prim，前面按边权从小选边的过程是 Kruskal，检测成环可借助并查集。若要枚举全部最优树，应在同权值的合法边之间保留不同选择，不能只运行一次后认定方案唯一。

**（3）TTL 是否足够。**IP 分组每被一个路由器转发一次，TTL 减 1；减至 0 就丢弃，不能继续送向下一跳。方案 1 使用 WH—QD，树中 TL 到 BJ 的唯一道路为 TL→JN→QD→WH→XA→BJ。分组从 H1 以 TTL=5 进入 TL 路由器，在 TL、JN、QD、WH 转发后 TTL 依次为 4、3、2、1，到 XA 再减为 0，被丢弃，H2 收不到。

方案 2 使用 BJ—TL，唯一道路只有 TL→BJ，分组经过这两个路由器后 TTL 仍为 3，可交给 H2。因此是否收到取决于采用哪棵最优树；光纤费用相同不表示路由器跳数相同，不能用边权费用来扣减 TTL。

**基础与参数。**接口的 32 位缓冲寄存器一次保存 $32/8=4$ B。CPU 每秒有 $500\times10^6$ 个周期，时钟周期为 2 ns；CPI=4 表示一条指令平均耗时 8 ns。传输率按十进制单位 $1\mathrm{MB}=10^6\mathrm B$ 换算。

**（1）设备 A 的查询。**A 以 $2\times10^6$ B/s 传数据，产生一份 4 B 数据需要 $4/(2\times10^6)=2\,\mu s$。寄存器没有更多缓冲空间，故必须在下一份数据到来前取走已有数据，最大查询间隔为 2 μs。

每秒至少需要 $2\times10^6/4=500000$ 次查询与传送。每次至少 10 条指令，耗 $10\times4=40$ 周期，所以每秒 CPU 用于 A 的周期数至少为 $500000\times40=2\times10^7$。比例为 $2\times10^7/(500\times10^6)\times100\%=4\%$。这里的最小占比按每次刚好 10 条指令计算；查询更频繁或操作更多只会增加开销。

**（2）设备 B 的中断。**B 产生 4 B 数据只用 $4/(40\times10^6)=0.1\,\mu s$，而一次中断响应和处理至少耗 $400/(500\times10^6)=0.8\,\mu s$，比数据到达间隔长 8 倍。每秒需 $10^7$ 次中断，至少消耗 $4\times10^9$ 个 CPU 周期，是 CPU 总能力的 8 倍。因此在给定接口和开销下，不能采用这种逐 4 B 中断方式保证不丢数据。

**（3）设备 B 的 DMA。**按最大传输率，每秒块数为 $40\times10^6/1000=40000$。CPU 对每块只做预处理和后处理，共 500 周期，这已是周期数，无需再乘 CPI。最大 CPU 开销为 $40000\times500=2\times10^7$ 周期/s，占比 $2\times10^7/(500\times10^6)\times100\%=4\%$。DMA 数据块本身由控制器传送，不能把全部传块时间都算成 CPU 执行 I/O 指令的时间。

**（1）物理地址位数。**图中虚地址为 20 位虚页号加 12 位页内地址，共 32 位。TLB 转换后给出实页号，图中实页号如 0040H、F800H，占 16 位；页内地址原样保留。也可直接读 Cache 输入地址字段 20+3+5，所以物理地址共 28 位，即 16 位实页号加 12 位偏移。

（2）TLB 的组织。图中虚页号送往所有条目的比较器，没有另外抽出索引字段选择固定组，因此采用全相联映射。TLB 是高速地址转换缓冲，通常由 SRAM 实现，以便快速读取映射；比较器完成并行标记匹配，不能仅因它缓存页表项就把它当成主存 DRAM。

**（3）Cache 类型、附加位与容量。**图中物理地址分为 20 位 Tag、3 位组号、5 位块内偏移。3 位组号表示 $2^3=8$ 组，每组同时比较两路 Tag，所以为 2 路组相联；5 位偏移表示每行 $2^5=32$ B，总共 16 行，纯数据容量 512 B。

回写策略在修改 Cache 数据时不立即同步主存，需增加 1 位脏位，标识被替换时是否要写回。LRU 则需增加用于记录两路最近使用关系的替换状态。本题按考试常用的“每行计入 1 位 LRU 状态，并把数据及管理位一并计入总容量”的口径作答。每行有 256 位数据、20 位 Tag、1 位有效、1 位脏位和 1 位 LRU，总容量为

$$8\times2\times(32\times8+20+1+1+1)=4464\text{ bit}=558\text{ B}.$$

有效位为 1 表示该行已存入可用的主存块；为 0 时，即使 Tag 数值恰好相同也不能认定命中。

**容量口径的边界：**本题主要答案为 4464 bit=558 B，对应每行保存 1 位 LRU 的组织。对于两路 Cache，最少只需每组 1 位来区分哪一路更久未用；若实际实现把 LRU 状态集中在组上，总存储量便是 $16\times(256+20+1+1)+8=4456$ bit=557 B。若只问数据容量，则是 512 B。三者采用的计数范围或状态组织不同，作答时应写清本题采用每行 1 位 LRU、并包含管理位的口径。

**（4）逐字段转换与匹配。**虚地址 0008C040H 拆为虚页号 0008CH、页内偏移 040H。TLB 中 Tag=0008CH 的条目有效位为 1，给出实页号 0040H，所以物理地址为 $0040\mathrm H\times1000\mathrm H+040\mathrm H=0040040\mathrm H$。

把该物理地址按 Cache 格式拆开：Tag=$0040040\mathrm H\gg8=00400\mathrm H$，组号=$((0040040\mathrm H\gg5)\mathbin{\&}7)=2$，偏移为 0。第 2 组左路 Tag=00400H 虽匹配，但有效位为 0；右路有效位为 1，却是 Tag=01600H，不匹配，所以 Cache 未命中。

对虚地址 0007C260H，只求组号无需知道实页号。地址转换保持低 12 位页内偏移，而组号占物理地址第 5～7 位，完全落在页内偏移中。因此组号为 $(260\mathrm H\gg5)\mathbin{\&}7=13\mathrm H\mathbin{\&}7=3$。

**（1）构造虚拟地址。**地址格式从高到低为 10 位页目录号、10 位页表索引、12 位页内偏移。目录号 6 要左移 22 位，页表索引 6 要左移 12 位，偏移 8 留在低位；三个字段互不重叠，可直接相加或按位或：

$$VA=(6\ll22)+(6\ll12)+8=\mathrm{01806008H}.$$

分项结果为 $6\ll22=01800000\mathrm H$、$6\ll12=00006000\mathrm H$，再加 8 得 01806008H。这里“相应页表中的页号 6”是第二级索引，不是把整个 20 位虚页号直接写为 6。

（2）PDBR 与切换。PDBR 保存当前进程页目录的物理起始地址。硬件要用它加目录项偏移来读取页目录，页目录本身不能再次依赖尚未完成的同一虚地址转换，否则会形成递归定位问题。

不同进程通常有不同虚拟地址空间及页目录，所以进程切换时需把 PDBR 更新为新进程页目录的物理基址，确保同一个虚地址按正确进程解释。同一进程内的线程共享地址空间与页目录，仅切换线程的寄存器、栈等执行状态，不需改变 PDBR。不能把线程拥有独立执行栈误认为拥有独立页目录。

**（3）改进型 CLOCK。**需在页表项中设置访问位 A 和修改位 M。访问位表示页面近期是否被访问，修改位表示装入后是否写过，决定淘汰时是否需要写回外存。算法优先考虑未近期使用、且未修改的 (A,M)=(0,0) 页面；其次考虑未近期使用但已修改的 (0,1) 等类别，同时扫描中可清除访问位。仅有访问位只能实现普通 CLOCK，无法进一步优先选择写回代价较低的页面。

**（1）最大文件长度。**簇大小为 4 KB=4096 B，每个地址项 4 B，所以一个间接索引簇能存 $4096/4=1024$ 个簇号。8 个直接项各管理一个数据簇；一级间接项管理 1024 个数据簇；二级间接项先管理 1024 个一级索引簇，总计 $1024^2$ 个数据簇；三级同理管理 $1024^3$ 个数据簇。最大数据长度为

$$L_{\max}=(8+1024+1024^2+1024^3)\times4\mathrm{KB}.$$

各级索引簇本身属于管理开销，不能把它们的空间加到文件可保存的数据长度中。

**（2）最多图像文件数。**数量同时受索引结点区与数据区限制。一个索引结点 64 B，一簇可存 $4096/64=64$ 个结点，1M 个簇共能存 $64\mathrm M$ 个文件的索引结点，其中 $M=2^{20}$。

每个图像 5600 B，大于一簇、小于两簇，因此需 $\lceil5600/4096\rceil=2$ 个数据簇，尾簇剩余空间不能分给另一个普通文件。512M 个数据簇可容纳 $512\mathrm M/2=256\mathrm M$ 个图像。每图像仅用两个直接地址，不需额外间接索引簇。两种限制取最小，最多 $\min(64\mathrm M,256\mathrm M)=64\mathrm M$ 个，即 67108864 个。

**（3）最后簇号的获取。**F1=6 KB 占 $\lceil6/4\rceil=2$ 簇，第 2 簇号直接在 inode 的直接地址项中。F2=40 KB 占 10 簇，前 8 簇用直接地址，第 9、10 簇要经一级间接索引；取得最后簇号必须先找到一级间接索引簇，再读其相应地址项。因此在 inode 已有、间接索引尚未缓存的同等条件下，F2 多一次索引簇访问，时间不同。若间接索引已有缓存，实际磁盘耗时可能缩短；结构上的索引层次数仍然不同。

（1）子网与剩余主机数。/24 均分为两个子网，需要借 1 位主机位，得到 /25，掩码 255.255.255.128。根据图中销售部地址 .1～.20 和接口 .126，其网络为 192.168.1.0/25，广播为 192.168.1.127；技术部 .129～.208 和接口 .254 位于另一个子网，网络地址为 192.168.1.128，广播为 .255。

每个 /25 有 128 个地址，扣除网络和广播后可用 126 个。技术部已分给主机的 .129～.208 包含 $208-129+1=80$ 个地址，还需扣除路由器 F1 使用的 .254。因此可再连接 $126-80-1=45$ 台主机，不能把路由器接口的地址也分给新主机。

**（2）IP 分片。**技术部出口 MTU=800 B，包含分片自己的 IP 首部。首部长 20 B，留给数据的最大空间为 780 B；片偏移以 8 B 为单位，所以非末片数据长度必须是 8 的倍数，最大的合法值为 $\lfloor780/8\rfloor\times8=776$ B，而非 780 B。

原分组总长 1500 B，原始数据长 $1500-20=1480$ B。第一片取 776 B，剩余 $1480-776=704$ B，第二片可容纳，故至少分 2 片：

第二片数据从原数据的第 776 字节开始，片偏移字段为 $776/8=97$；第一片从原数据起点开始，偏移为 0。偏移相对于原分组的数据，不包含原首部，也不以 1 B 为单位。两片分别增加自己的 20 B 首部，总长为 796 B、724 B，均不超过 MTU；第一片后面还有分片，MF=1，最后一片 MF=0。