2024年计算机408真题

答案：D。

带头结点的单链表中，h 指向头结点，h->next 才指向第一个存放数据的结点。移动结点时，只需改变 next 的连接关系，不必复制结点的数据。设原首元结点为 first，p 的后继为 q，q 的后继为 r，逐句分析如下。

原来的局部关系 p → q → r 变为 p → r，表头关系 h → first 变为 h → q → first。因此，移动的是 q 所指结点，新位置在头结点之后。题目保证 p 不是尾结点，所以 p->next 非空，能取得 q。

A 错在 q 被从 p 后面移走，并非在 p 后插入；B 错在没有把 p 接到 q 后面；C 错在 p 本身的位置未被改变。D 与四条语句的整体效果一致。

答案：A。

后缀表达式把运算符写在两个操作数之后，例如 z-u 写成 zu-。转换前先确定运算顺序：括号中的减法最先执行，乘除优先于加法，且乘法和除法按从左到右的顺序结合。因此原式相当于 x + ((y * (z-u)) / v)。

也可用栈验证 A：遇到 - 时弹出 u、z 得到 z-u；遇到 * 时计算 y*(z-u)；遇到 / 时再除以 v；最后用 + 与 x 相加。

B 的 xyzu-v/*+ 对应 x+y*((z-u)/v)，改变了乘除的执行次序，不能作为本题要求的严格表达式转换结果；在整数运算中，两者尤其可能因除法截断而不同。C、D 都把运算符放在操作数前面，是前缀写法；其中 C 才对应原式的运算结构，但本题要求的是后缀表达式。

答案：A。

二叉树的中序遍历顺序是“左子树、根、右子树”。序列中 p、v、q 连续出现，表示 p 是 v 的中序直接前驱，q 是 v 的中序直接后继。题目又说明 v 有两个孩子，所以左右子树都非空。

在访问 v 前，必须刚好完成其左子树的遍历。因此 p 是 v 的左子树中最靠右的结点。如果 p 还有右孩子，中序遍历就应在 p 之后继续访问它的右子树，再访问 v，p 就不可能紧挨着 v，所以 p 没有右孩子。

访问 v 后，要先访问其右子树中最靠左的结点，这个结点就是 q。如果 q 还有左孩子，访问 q 前就要先访问该左子树，q 便不可能紧接在 v 后面，所以 q 没有左孩子。

由此得到 A。B 错在断言 q 有左孩子，C 错在断言 p 有右孩子，D 同时违反这两个结论。注意，这里并未要求 p 没有左孩子，也未要求 q 没有右孩子。

答案：B。

无向图中，顶点的度等于与该顶点关联的边数。邻接多重表让一条无向边只占一个边结点：边结点中保存两个端点编号，以及分别通向这两个端点下一条关联边的链接。统计某顶点的度时，应沿该顶点的边链数边，不能把图中指针箭头的条数当成度。

题图的顶点编号为 a=0、b=1、c=2、d=3、e=4。经过一个边结点时，如果当前顶点是该边的第一个端点，就沿 ilink 走；如果是第二个端点，就沿 jlink 走。这样从 b 的首边指针出发，依次经过 {1,3}、{0,1}，共 2 条；从 d 出发，依次经过 {3,2}、{4,3}、{0,3}、{1,3}，共 4 条。因此：

$$\deg(b)=2,\qquad \deg(d)=4.$$

A 把 b 的度误计为 0，并遗漏 d 的边；C 把 d 的度多算为 5；D 把 b 的度多算为 3。本图没有自环，直接按关联边逐条计数即可，答案为 B。

答案：D。

折半查找每次访问当前查找区间的中间元素，再根据关键字大小排除一半区间。要直接采用这种方法，通常需同时满足两个条件：元素按关键字有序；能按逻辑位置随机访问中间元素。

“静态链表用数组存储”不等于“元素按有序顺序连续排列”。若先重新整理为有序顺序表，当然可以折半查找，但那已不是题目所说的直接使用。

四项均不适合，故选 D。A 漏掉两种无序结构；B 漏掉普通链表和静态链表的访问限制；C 漏掉Ⅰ的随机访问问题。

答案：A。

KMP 在模式串位置 j 失配时，将模式指针改为 next[j]，复用已经匹配的前缀与后缀。修正后的数组通常记为 nextval：若回退后的字符仍与原失配字符相同，再比较必然也会失败，就继续跳过它。

采用从 0 开始的下标，约定 next[0]=-1，模式串 aabaab 的两个数组如下。

例如在 j=4 的 a 处失配，普通 next 会先退到 j=1，但那里仍为 a，必然也失配；再退到 j=0 仍为 a，所以修正后直接退到 -1。模式串相对主串右移 $4-(-1)=5$ 个字符，是表中最大值。

因此选 A。B 的 4 是在 j=3 或 j=5 失配时可出现的位移，尚未取最大值；C、D 更小。若使用从 1 开始的编号，数组数值会整体换一种表示，但实际最长右移距离仍是 5。

答案：D。

二叉搜索树要求：一个结点左子树的全部关键字小于该结点，右子树的全部关键字大于该结点。这里的约束适用于整棵子树，而不仅仅是直接孩子。

沿题图从根到 T 的路径依次累积限制：

1. T 在 k1 的右子树中，故 $x>k_1$。
2. T 在 k2 的左子树中，故 $x<k_2$。
3. T 在 k3 的右子树中，故 $x>k_3$。

图中 k3 本身也位于 k1 的右子树、k2 的左子树，因此 $k_1<k_3<k_2$。较强的下界 $x>k_3$ 已包含 $x>k_1$，最终范围为：

$$k_3<x<k_2.$$

A 与 T 位于 k1 右子树的事实矛盾；B 与 T 位于 k2 左子树的事实矛盾；C 的上界 $x<k_3$ 与 T 位于 k3 右子树矛盾。D 同时满足全部祖先的限制。

答案：A。

快速排序的一趟划分选定一个枢轴，把其余元素分到两侧，并确定枢轴的最终位置。按通常的大小划分规则，P 中各元素不大于枢轴，Q 中各元素不小于枢轴。因此任意取 $p\in P$、$q\in Q$，都有 $p\le q$，这就是 块间有序。

一趟划分并未对每一块的内部完成排序。例如以 5 为枢轴，左块可能为 [3,1,4,2]，右块可能为 [9,6,8]：左块的任意元素都小于右块的任意元素，但两块内部都还无序，后续需要递归排序。

A 正确。B 把块间有序误当成块内有序；C 错在块的大小取决于枢轴在全部元素中的排名，非空仅说明枢轴不是极端位置，不保证两块规模接近；D 错在快速排序允许重复关键字，划分不会自动消除相等元素。题设的 $n\ge3$ 且两块非空，也不能推出 C、D。

答案：B。

大根堆用数组按完全二叉树的层序存储，每个父结点不小于其孩子。删除操作删除堆顶最大值，再把最后一个元素放到根处，并与两个孩子中较大的那个交换，反复下滤恢复堆序。

第一次删除 28：末项 5 补到根，堆的有效长度变为 7。

第二次删除 22：末项 15 补到根，有效长度变为 6。

此时 15 的唯一孩子是 12，已满足堆序，下滤结束，结果为 B。

A、C、D 也都能满足大根堆的大小性质，但均不是规定删除过程得到的序列。A 把仍应处于第 4 项的 5 与第 6 项的 12 交换了；C 把第二次补根的 15 错放在第 4 项，实际它应落在第 3 项；D 把 8、12、15 的位置重新排列了，而第二次下滤只需交换根与第 3 项，不会改变第 4、5、6 项。不能仅凭“某序列也是堆”选择答案，必须严格模拟操作。

答案：C。

二路归并每次比较两个有序序列当前尚未输出的首元素，输出较小者；某一序列耗尽后，另一序列剩余元素直接复制，复制过程不再产生关键字比较。题目指定从左至右选序列，故先合并 (3,5) 和 (7,9)，再把结果与 (6) 合并。

总比较次数为 $2+3=5$，选 C。A 的 3 只相当于第二阶段的次数；B 的 4 漏算了实际比较；D 的 6 把某一段耗尽后的直接复制也计成了比较。归并比较次数不是固定等于待归并元素总数减一，本题必须按给定顺序逐次统计。

答案：D。

多路归并同时面对多个已排好序的归并段。要得到升序输出，每一步都应在各段当前尚未输出的首记录中选出最小者。败者树把归并段看作参赛选手，两两比较当前关键字，内部结点保存比较的败者，胜者继续向上，最终冠军单独保存在冠军结点中。

树中通常记录的是 归并段号，再用段号访问该段当前的关键字。这样输出冠军段的首记录后，可以只从该段读入下一条记录，并沿这名选手的比较路径重新比赛。冠军结点因而保存“最小关键字所在的归并段号”，选 D。

A、C 都把升序归并应选最小值误写成最大值；B 虽选对最小关键字，但混淆了比较依据与树结点保存的选手编号。若两个段的当前关键字相等，可按约定选择其中一段先输出，不改变冠军应记录段号这一点。

答案：B。

本题采用组成原理考试中的常用整数模型：int 为 32 位有符号整数，short 为 16 位有符号整数，整数用补码表示；将超出 short 范围的 int 转为 short 时保留低 16 位，再从 short 转回 int 时进行符号扩展。这些是本题的默认解题约定，不能将它们理解成所有 C 语言平台都采用同一类型宽度和窄化转换规则。

首先，i 的值可写为：

$$32777=32768+9=8009\mathrm{H}.$$

执行 short si=i; 后保留低 16 位 8009H，即：

1000 0000 0000 1001

最高位为 1，这组位在 16 位有符号补码中表示负数。可用两种等价方法求其真值：

$$si=-2^{15}+9=-32768+9=-32759,$$

或把这组位先看成无符号值，再减去 $2^{16}$：

$$si=32777-65536=-32759.$$

随后执行 int j=si;，从 16 位有符号数扩展到 32 位时，高 16 位都填入符号位 1，得到 FFFF8009H。符号扩展保持负数的真值，所以 j 仍为 -32759，选择 B。

A 错把补码的符号位理解为给原来的十进制值直接加负号；C 忽略了 8009H 在 16 位有符号补码中的负号；D 忽略了转为 short 时已经超出其正数范围。这里区分的是“位模式如何截取”和“截取后的位模式按哪种类型解释”，不能只看原来的十进制数。

若某个平台的 short 足以表示 32777，或采用不同的超范围转换规则，结果可能不同；本题按上述 32 位 int、16 位 short 的考试默认模型作答。

答案：B。

需要区分“程序员看到的指令写法”和“CPU 内部实际识别的编码”。机器指令以二进制编码存放，CPU 能取指、译码并执行其规定的操作。采用微程序控制的 CPU 中，微指令存放在控制存储器内，由微程序控制器解释，直接产生一组底层控制信号。

例如程序员写出的助记符只是机器指令的符号表示，CPU 并不读取字符文本来完成运算。因此只有Ⅱ、Ⅲ符合，选 B。A 两项都需先翻译；C 把汇编文本当成可直接执行的编码；D 还把伪指令也当成了硬件指令。

答案：C。

题目要求先保证“表数精度”，即范围内的整数参数都能被准确表示，再在选项中选择合适的运算形式。能表示很大的数，与能精确表示范围内每一个整数，是两个不同条件。

对 α，32 位有符号整数的范围为 $-2^{31}$ 到 $2^{31}-1$，完全覆盖 $-2^{20}$ 到 $2^{20}$，可直接进行整数运算。单精度也能精确表示这一范围内的整数，但在已有足够宽度的整数表示时，无需改用浮点数。

对 β，32 位整数装不下 $\pm2^{40}$。单精度浮点数具有 24 位有效二进制精度，只能连续精确表示到 $2^{24}$ 附近的整数，不能精确表示本题范围内的所有整数；例如 $2^{40}-1$ 会丢失低位。双精度有 53 位有效精度，可以精确表示绝对值不超过 $2^{53}$ 的整数，足以覆盖 β 的整个范围。

所以 α 采用 32 位整数，β 采用双精度浮点数，选 C。A 的 β 超出范围；B 的 β 精度不足；D 对 α 采用了不必要的浮点表示。判断浮点数是否适合整数参数时，必须检查有效位数，不能仅查看指数范围。

答案：D。

二进制乘法的基本原理是：乘数某一位为 1，就把对应移位后的被乘数加到积中；该位为 0，就跳过这次相加。例如 $x\times13=x\times(8+4+1)=(x\ll3)+(x\ll2)+x$。这个原理既可由专用硬件实现，也可由程序循环实现。

A 正确：阵列乘法器把产生部分积、相加等逻辑展开为组合电路，只要时钟周期容得下它的传播延迟，就可以在一个周期完成乘法。B 正确：仅使用通常的 ALU 和移位器进行逐位迭代乘法，要反复移位、判断、相加，无法把这些顺序步骤作为一次普通 ALU 操作在一个周期内完成。

C 正确：常数乘数的二进制位已知，编译器可生成固定的移位和加减序列。例如乘以 15 可写成 (x<<4)-x。

D 错误：两个乘数都为变量时，仍可用循环逐位检查乘数，条件相加被乘数，再移位并处理下一位。变量只是让迭代次数和条件由运行时决定，并不妨碍这种软件实现。因此题目要求选“错误”的叙述，答案为 D。

答案：D。

Cache—主存层次用较小而快的 Cache 保存部分主存块，主存—外存层次则在页式虚拟存储系统中用主存保存部分虚拟页。两个层次都利用局部性，但交换单位、管理者和映射限制不同。

A、B、C 的叙述均正确。D 的后半句错误：页号并不固定决定唯一的物理页框，操作系统可为缺页选择一个空闲页框或换出后腾出的页框，映射关系再写入页表。这种可装入任意页框的关系通常视为全相联映射，故不能说主存—外存通常采用直接映射。

答案：C。

TLB 缓存“虚页号到物理页框号”的映射。组相联查找时，先用虚页号中的组索引定位一组，再比较该组各表项的标记，以确认是所需的虚页。页内偏移在同一页中不变，不需要成为 TLB 标记的一部分。

按字节编址且页大小为 $1\text{ KB}=2^{10}\text{ B}$，页内偏移占 10 位，所以虚页号占 $32-10=22$ 位。TLB 总共 32 项、每组 4 项，组数为：

$$32/4=8=2^3.$$

因此用虚页号的 3 位作为组索引，余下位用于区分映射到同组的虚页：

$$\text{标记位数}=22-3=19.$$

选 C。物理地址的 30 位决定物理页框号为 $30-10=20$ 位，那是表项中的映射结果，不能拿来代替虚页标记。A、B 均少保留了虚页号信息，可能把不同虚页误判为同页；D 的 20 常见于把物理页框号位数当成标记位数，也不是本题所问的最少标记位数。

答案：B。

MMU 的任务是把程序给出的虚拟地址转换为物理地址，并检查这个访问是否合法。一次页式地址转换通常先查 TLB；未命中时再访问页表，检查页面是否驻留及访问权限，最后组合物理页框号与页内偏移。

A 的访问越权需要检查页表或 TLB 中的保护信息，例如用户态是否允许访问该页、读写权限是否满足，属于 MMU 的检测。C 的页面缺失由页表存在位等信息发现，会引发缺页异常。D 的 TLB 缺失就是 TLB 未命中，也是在地址转换路径中发现的情况。

B 的 Cache 缺失表示所需数据块未保存在 Cache 中，需要从下一层存储器取块。这是 Cache 标记比较和有效位检查的结果，属于数据缓存访问，不是 MMU 地址转换本身的检测。因此选 B。某些处理器可让 TLB 查询和 Cache 查询部分并行，但并行发生不代表二者的职能相同。

答案：C。

数据冒险出现在后面的指令需要前面指令尚未准备好的结果时。例如 add r1,... 后立即执行使用 r1 的指令，若仍从寄存器堆读取旧值，就会计算错误。旁路可将前一指令已产生、但尚未写回寄存器的结果直接送到后续指令的运算输入。

不过，旁路无法传递“尚未产生的数据”。以相邻的 load—use 为例：

lw  r1, 0(r2)
add r3, r1, r4

在 5 段流水线中，lw 要到访存段结束才获得内存数据，紧随其后的 add 却在同一周期的执行段就需要 r1。即使设置旁路，也通常需要暂停一周期，插入气泡，等数据产生后再转发。

所以 C 的“所有”不成立，答案为 C。A 正确，相邻指令的操作数相关可能触发冒险；B 正确，足够的气泡可以延迟后续使用；D 正确，在保持程序语义的前提下，可用独立指令填补等待，也可以插入足够的 nop。调整顺序不一定总有足够的独立指令，但 nop 可承担必要等待。

答案：B。

总线带宽在本题中指最大数据传输率，即连续处于数据传送阶段时，每秒最多送出的字节数。总线宽度 64 位意味着一次传送 $64/8=8$ B；一个时钟周期传送 2 次，所以每周期传送 16 B。

$B=420\times10^6\times2\times8 =6.72\times10^9\text{ B/s} =6.72\text{ GB/s}.$

因此选 B，GB 在这些选项中按 $10^9$ B 计算。第 4～7 周期共 4 个周期，每周期 2 次，正好完成 8 次数据传送，也与这个峰值计算一致。

A 的 3.84 GB/s 是把一次完整事务的 7 个周期都纳入平均：总数据量 $8\times8=64$ B，事务时间 $7/(420\times10^6)$ s，平均为 3.84 GB/s。地址命令和等待周期会降低事务平均速度，但不是题目所问的最大值。C 的 30.72 是上述事务平均速率换算成 Gb/s 的数值，却误写成 GB/s；D 的 53.76 是峰值的 Gb/s 数值，也把比特与字节单位混淆了。

答案：A。

中断响应优先级解决“多个中断同时请求时，CPU 先响应谁”，通常由硬件中断判优逻辑确定。中断处理优先级解决“某个中断正在处理时，哪些中断可以打断它”，可以通过中断屏蔽字控制。屏蔽字中的相应位表示允许或禁止某类中断，不能据此把它等同于硬件的响应排序。

因此 A 把这两种优先级混为一谈，是错误叙述。其余三项分别描述了响应阶段、软件现场保护和单重中断的特点：

• B 正确。中断响应时，硬件需要保存返回地址，即断点，以及程序状态字，使处理结束后能够恢复原执行状态。
• C 正确。处理程序的软件部分通常保存会被使用的通用寄存器，并按需要设置新的中断屏蔽字。
• D 正确。单重中断不允许中断嵌套，处理期间 CPU 保持关中断，直到恢复现场并返回。

解题关键是区分硬件响应时保存的必要返回状态，与处理程序开始后由软件保存的通用寄存器现场。

答案：C。

DMA 是直接存储器访问。CPU 先向 DMA 控制器设置主存起始地址、传送数量、传送方向等参数；传送开始后，DMA 控制器取得总线控制权，按照这些参数在设备接口和主存之间搬运一批数据，结束时再通知 CPU。

所以数据传输的两端是 设备接口与主存，选 C。DMA 控制器负责地址、计数和读写控制，并不要求数据先经过 CPU 的通用寄存器。这正是它适合批量高速 I/O 的原因。

A 描述 CPU 与主存的数据交换，不能体现外设输入输出的通路；B 把 CPU 与 DMA 控制器之间的参数设置、状态访问当成批量数据通路；D 只写到设备接口与控制器，漏掉了实际数据的另一端主存。要区分“谁控制传输”与“数据最终在谁和谁之间传输”。

答案：A。

CPU 的用户态、内核态描述的是当前执行代码的特权级。中断来自外部事件，异常由正在执行的指令引起，它们都可能在用户程序运行期间发生。例如用户程序执行非法指令或访问未驻留页面时，异常发生的当时可以处于用户态；随后 CPU 才按异常入口转入内核态处理。

A 把“中断或异常发生时”与“处理程序开始执行时”混淆了，因而错误。事件也可能发生在内核执行过程中，所以不能断言发生时必为某一种特权态。

B 正确，系统调用请求最终由相应内核服务例程处理；C 正确，中断处理程序执行时需要内核权限，CPU 已进入内核态；D 正确，添加需中断驱动的新设备时，要将相应服务例程注册到中断处理机制中，才能在设备请求到来后调用它。题目要求找错误项，选 A。

答案：A。

终止进程意味着该进程不再继续执行，操作系统需要完成它自身的资源清理。进程占用的设备应释放或撤销占用，分配给它的内存应回收，进程控制块保存的管理信息在完成必要的退出收尾后也要释放。

但是，子进程是独立的进程，它的生命周期不一定必须与父进程相同。有的系统会在父进程终止时同时终止子进程；有的系统允许子进程继续运行，并由其他进程接管其管理关系。因此“终止子进程”取决于具体策略，不是所有进程终止时都必做的操作，选 A。

B、C、D 都属于被终止进程自身的资源回收。即使退出状态为供父进程查询而暂时保留，也不能由此说进程控制块永远不需释放；题目考查的是终止和清理需要处理哪些资源，而子进程可以继续存在这一点具有本质区别。

答案：D。

进程切换要把 CPU 从一个进程的执行环境切换到另一个进程的执行环境。恢复少量通用寄存器并不够，还必须让 CPU 找到新进程的指令、栈和地址映射。

三个寄存器都属于进程运行所需的上下文，因此三项都需要更新，选 D。A 只切换地址映射而未恢复执行位置和栈；B 漏掉进程地址空间的页表；C 漏掉栈环境。进程切换不同于同一进程内部的一般函数调用，新进程可能具有完全不同的虚拟地址空间。

答案：A。

位图法为外存中的每一个块固定设置一位，用 0、1 表示空闲或已分配。若外存共有 N 个块，位图需要 N 位，约为 $\lceil N/8\rceil$ 字节。分配或回收某个块只改变其位值，不会增加或删除位图中的位置，所以它的长度由总块数决定，与当前有多少空闲块无关。

B 的空闲表通常为每个连续空闲区记录起始块号和长度，记录数量随空闲区的变化而变化；C 的成组链接把空闲块号分组记录，空闲块减少或增加会改变需要记录的组及块号数量；D 的空闲链表在空闲块之间组织链指针，记录范围与空闲块数量相关。它们的结构并非为每个总块数固定预留一位。

因此只有 A 满足题意。这里比较的是管理空闲空间所需信息的规模规律，不是某一具体实现碰巧为表分配了一个固定容量的数组。

答案：A。

伙伴算法把内存按 $2^k$ 大小管理。一个较大的空闲区被分成两个等大的小区时，这两个小区互为伙伴；释放其中一个小区后，只有另一伙伴也空闲，二者才可合并回原来的大区。例如一个 16 KB 区分成两个 8 KB 伙伴，两个 8 KB 都空闲时才能合成 16 KB。

因此每次合并的两块大小必相等，还要满足特定的地址伙伴关系。仅仅“相邻且等大”也未必足够，例如跨越不同原始分裂边界的两个块不一定是伙伴。符合题目描述的是 A。

B、C、D 分别按空闲分区大小或扫描次序选择分配位置。它们回收时可将物理相邻的空闲区合并，即使大小不同，例如相邻的 3 KB 和 5 KB 可合为 8 KB。它们都没有伙伴算法的“只能合并等大伙伴”限制。

答案：B。

线程是进程内部的执行单元。一个进程中的线程共享进程级资源，但每个线程要有自己的程序计数器、寄存器现场和栈，才能独立保存函数调用及局部状态。

Ⅰ 可共享：Ta、Tb 都属于进程 P，使用同一个进程地址空间，可访问进程的代码、全局变量、堆等。Ⅲ 也可共享：打开文件描述符表是进程级资源，T 在创建 Ta、Tb 前已经打开文件，fd 的打开状态可被新线程使用，不需让每个线程再按文件名打开一次。

Ⅱ 不属于共享的线程运行资源：T 的栈用于保存 T 自己的调用和局部变量，Ta、Tb 各有自己的栈。虽然这些栈内存位于同一地址空间，持有有效指针时可能访问别的线程的栈数据，但不能因此说几个线程共同使用 T 的栈作为各自的执行栈。

因此只有Ⅰ、Ⅲ，选 B。A 漏掉共享文件描述符；C 漏掉共享地址空间并错误加入 T 的栈；D 也错误加入Ⅱ。

答案：A。

文件按名查找是根据路径、文件名在目录中定位相应文件，取得其文件控制信息。open() 的参数包含文件路径，因此要解析路径、查找目录项，并在成功后建立打开文件记录，返回文件描述符 fd。

后续操作用 fd 作为索引找到已经建立的打开状态：read() 从该打开文件读数据，write() 向其写数据，close() 释放对应的打开引用。它们无需再用原文件名重新遍历目录。这也是打开文件之后反复读写能够避免重复按名查找的原因。

所以 A 正确。B、C 虽要定位数据块，但这种定位是基于已打开文件信息完成的，不是按文件名查目录；D 关闭的也是描述符关联的打开状态。要区分目录查找与文件内部的数据块查找。

答案：C。

时间片轮转每次从就绪队列队首选一个进程，最多执行一个时间片；未完成的进程回到队尾。周转时间从进程到达开始，计到它执行结束，包含排队等待和自身运行。所有进程初始就在队列中，可把开始时刻记为 0。

P 所需 CPU 时间为 25 ms，时间片为 5 ms，因此需要 $25/5=5$ 次轮到自己。P 初始在队尾，每一轮都要先等前面的 9 个进程各执行 5 ms，再执行自己的 5 ms。

题设说明 P 的 CPU 时间最短，其他进程均至少需要 25 ms，而且不会进入阻塞态。因此前四轮不会有其他进程退出；第五轮其他进程即使恰好完成，也已经各运行了第五个完整时间片，不会减少 P 前面的等待时间。

每轮耗时 $10\times5=50$ ms，P 在第 5 轮末完成，周转时间为 $5\times50=250$ ms，选 C。A 的 200 ms 只到第 4 轮末，P 还剩 5 ms；B 的 205 ms 错把第五轮的 P 放在队首；D 的 295 ms 多算了不必要的等待轮次。

答案：C。

键盘产生输入后，键盘控制器先在自己的数据寄存器中保存输入信息并发出中断请求。CPU 响应中断，键盘中断服务例程读取该寄存器，对输入进行必要处理，再把结果放入操作系统管理的内核缓冲区，等待后续的读操作取走。

因此在中断服务例程结束这一时刻，输入数据通常存放在 内核缓冲区，选 C。这样即使用户程序尚未请求读键盘，内核也能暂存输入，而不要求中断处理程序直接找到某个用户程序的缓冲区。

A 的用户缓冲区是在用户进程通过读等接口获取数据后才成为目的位置；B 的通用寄存器可能只是处理中暂存数据的工具，恢复现场后不能作为保存键盘输入的缓冲区；D 是中断处理前控制器暂存输入的位置，服务例程已经把它读出并交给内核输入队列。

答案：C。

C-SCAN 即循环扫描：磁头只沿一个方向服务请求，到磁盘一端后回卷到另一端，回卷时不服务请求，再按原方向扫描。题目给定当前为 200、服务方向为磁道号减小，所以先处理小于 200 的请求，再回到最大磁道 399 处理另一侧请求。

实际访问及移动顺序为：

200 → 160 → 120 → 110 → 0 → 399 → 300 → 210
                              ↑
                          从0回卷到399

第一段从 200 扫描到 0，距离为 200；回卷从 0 到 399，距离为 399；继续向下从 399 经 300 到 210，距离为 $399-210=189$。所以总移动距离为：

$$200+399+189=788.$$

选 C。A 的 599 恰好只计算到回卷结束，漏掉随后服务 300、210 的 189；B 的 619 只比 599 多 20，而回卷后必须从 399 移到 210，实际还需 189；D 的 799 比实际路程多 11，不能由终点为 210 的三段移动得到。注意从 0 到 399 的距离是 399，不是磁道总数 400；所有请求完成后就停止，不必继续回到原位置，也不能忽略回卷距离。

答案：B。

端到端吞吐量受实际传输路径上的瓶颈链路限制，但图中有多条可选路径，不能直接把全图最小的一条链路当成任何通信都必经的瓶颈。

H1 与左侧路由器之间的接入链路为 10 Mb/s，右侧路由器到 H2 也为 10 Mb/s。因此无论核心网络如何选路，H1 发出和 H2 接收都不可能持续超过 10 Mb/s，这是上限。

上限也能达到：中间可选上方的两条 1000 Mb/s 链路，或下方的两条 100 Mb/s 链路。走任一条这样的路径，核心链路均不比两端接入链路慢，整条路径的瓶颈为 10 Mb/s，最大吞吐量约为 10 Mb/s，选 B。

A 的 1 Mb/s 是中间直连链路的带宽，仅当坚持走该直连路径时才会成为瓶颈；最大吞吐量可以通过其他路径提高。C、D 分别取了某些核心链路的带宽，却忽略两端必须经过的 10 Mb/s 接入链路。

答案：C。

数字调制把数字 0、1 映射为载波信号参数的不同状态。判断题目要看被改变的参数是幅度、频率还是相位。

例如二进制 FSK 可在发送 0 时使用一个频率，发送 1 时使用另一个频率。两个频率必须可区分，接收端才能判断码元。因此符合题意的是 C；A、B、D 都不靠两个不同频率区分二进制符号。

答案：D。

ARP 用于在本地链路上建立 IP 地址到 MAC 地址的对应关系。主机广播 ARP 请求，只有同一广播域的主机能收到并回复。交换机划分 VLAN 后，不同 VLAN 就是不同的二层广播域，即使 IP 地址看起来具有相同前缀，ARP 广播也不会跨 VLAN 转发。

题图中 H4 接在端口 5，属于 VLAN1；VLAN1 还包括端口 13 上的 H1、端口 1 上的 H2、端口 2 上的 H3。选项对应关系如下。

所以选 D。ARP 表的 TTL 表示缓存条目的老化时间，不决定 VLAN 可达范围；A、B、C 的 TTL 差别不使其失效。若需跨 VLAN 通信，应经过三层转发，源主机解析的是本地下一跳的 MAC，而不是远端 H6 的 MAC。

答案：B。

隐藏站 B 可能听不到 A，但能收到 AP 的 CTS，因此根据 CTS 中的持续时间设置 NAV，暂时不争用信道。NAV 要覆盖 CTS 接收结束以后尚未完成的通信时间，已经发生的 DIFS、RTS 和 CTS 本身不应再次计入。

RTS/CTS 预约后的剩余顺序是：

CTS结束 → SIFS → A发送数据帧 → SIFS → AP发送ACK

题设带宽为 54 Mb/s，数据帧总长 1998 B，所以传输时间为：

$t_{\text{data}}=\frac{1998\times8}{54\times10^6}\text{ s} =296\,\mu\text{s}.$

忽略传播时延，NAV 为 $28+296+28+2=354\,\mu\text{s}$，选 B。

A 的 326 μs 等于数据帧加一个 SIFS 再加 ACK，漏掉了 CTS 后等待发送数据的另一个 SIFS；C、D 均大于正确的剩余预约时间，未按 CTS 接收结束这个起点统计。题目给出的 DIFS 和 RTS 时延属于此前争用、预约阶段，不能混入本次 NAV；CTS 时延也已消耗。

答案：D。

选择重传 SR 对每个正确收到的帧分别确认，并且只重传超时未确认的帧。为了避免序号回绕后把旧帧当成新帧，发送和接收窗口相等时，窗口最大为序号空间的一半。3 位序号共有 $2^3=8$ 个取值，所以最大窗口为 4。

初始发送窗口为 [0,1,2,3]，甲发送 F0～F3，其中 F1 丢失。图中在 $t_1$ 前收到 ACK0，窗口下沿由 0 前移到 1，窗口成为 [1,2,3,4]。此时新开放的序号是 4，所以 $t_1$ 可发送新帧 F4。

随后 ACK2 只表示 F2 已被正确接收，不能同时确认 F1。由于最早未确认的 F1 仍在窗口下沿，窗口不能继续越过它。图中 $t_2$ 明确标出 F1 超时，SR 只重传该帧，所以 $t_2$ 发送 F1。ACK3 丢失不会把这次 F1 超时变成重传 F3。

两个时刻分别为 F4、F1，选 D。A、B 在 $t_1$ 过早把动作判成重传 F1；C 把 $t_1$ 判为 F3，但 F3 已在原窗口内发送，既不是此时新增序号，也没有在图中此刻超时。

答案：D。

本题采用考试中的常用 TCP 计算约定：初始拥塞窗口为 1 MSS，采用慢开始；不考虑丢包、重传和处理等待；H 在全部数据获得确认后请求关闭连接，服务器没有待发送数据，可立即连续发送对 FIN 的确认和自己的 FIN（也可合并为 ACK+FIN）。第三次握手的 ACK 可以携带第 1 个数据段。

3000 B 的报文分成 3 个 1000 B 的数据段。初始拥塞窗口只允许发送 1 个数据段，收到确认后窗口增至 2 MSS，再发送其余 2 个数据段。因此，数据发送并获得确认要经历两轮。忽略 TCP 段的传输时延，可按下表追踪时间：

这里需要的时间分为建连 1 RTT、两轮数据确认 2 RTT、从主动关闭到进入 TIME_WAIT 1 RTT，共 4 RTT。服务器无需额外等待应用数据，第二次与第三次挥手可紧接着发出，因此不能把“四次挥手”机械地算成固定 2 RTT。

H 是主动关闭方，发送最终 ACK 后进入 TIME_WAIT，等待 2MSL 才进入 CLOSED。等待时间从进入 TIME_WAIT 时开始，最终 ACK 的传播不需再额外加到这段等待之外。于是：

$T=4RTT+2MSL =4\times0.01+2\times30 =60.04\ \text{s}.$

因此选 D。A、B 只计了 1 个 MSL；C 在本题首轮 1 MSS、两轮数据确认的模型下少计了一个 RTT。

题面没有明示初始拥塞窗口，初始窗口为 1 MSS 是本题采用的教材计算约定，并非所有实际 TCP 实现的固定值。若初始窗口至少为 3 MSS，并仍约定全部数据获确认后关闭、服务器立即响应关闭，则数据阶段只需 1 RTT，结果会变为 $3RTT+2MSL=60.03$ s。应据此理解适用边界，本题按上述考试模型保留 D。

答案：C。

UDP 校验和采用 16 位反码加法：把各个 16 位字相加，若产生第 17 位进位，就将进位回加到低 16 位，直到没有高位进位；最后对 16 位和按位取反。

将两个二进制数转换成十六进制更便于检查：中间和为 B9B6H，最后一个字为 65C5H。

  B9B6
+ 65C5
------
 11F7B    普通加法有一个高位进位

  1F7B + 0001 = 1F7C    回卷进位
  ~1F7C = E083          对16位结果取反

E083H 对应二进制 1110 0000 1000 0011，选 C。A 是只保留低 16 位、既未回加进位也未取反的结果；B 正确回加了进位，但漏了最后取反；D 是对 1F7BH 直接取反，漏掉了回卷进位。不能把反码加法当成普通的模 $2^{16}$ 截断加法。

答案：D。

非持久 HTTP 为每个对象单独建立 TCP 连接。忽略对象传输时间时，下载一个对象至少需要两个 RTT：第一个 RTT 用于建立 TCP 连接，第二个 RTT 用于发送 HTTP 请求并收到响应对象。

本页有 1 个基本 HTML 文件和其中引用的 7 个图像文件，共 8 个对象。浏览器要先取得 HTML，才知道图像的请求地址；又因为题设不支持并行 TCP 连接，7 个图像也必须依次获取。同一网站并不能使 HTTP/1.0 的非持久连接自动复用。

$$\text{总RTT数}=2+7\times2=16.$$

因此选 D。A 的 4 RTT 相当于把所有图像放在同一批并行请求中，违反不支持并行的条件；B 的 9 RTT 可由漏算图像各自建连得到；C 的 14 RTT 只统计 7 个图像，漏掉最开始的 HTML 文件。计算起点已是为 HTML 建立连接，不需另计此前的 DNS 查询。

（1）算法的基本设计思想。

拓扑序列是有向图所有顶点的一个排列，要求每条边 $u\to v$ 的起点 u 都排在终点 v 前面。只有有向无环图才存在拓扑序列。入度为 0 表示当前没有尚未安排的前导顶点，因此它可以作为下一个输出顶点。

采用逐个删除零入度顶点的拓扑排序方法，并在每一步检查选择是否唯一。先按邻接矩阵统计各顶点入度；随后重复下列步骤，直到处理全部顶点：

1. 扫描尚未删除的顶点，统计入度为 0 的顶点。
2. 若没有零入度顶点，剩余图包含环，根本不存在完整拓扑序列，返回 0。
3. 若有至少两个零入度顶点，不能存在唯一拓扑序列，返回 0。若剩余图无环，这两个顶点都可先选，会得到不同的完整序列；若剩余图有环，则根本没有完整序列，同样应返回 0。
4. 若恰有一个，输出并标记删除该顶点，把它的每个出边终点的入度减 1，再进行下一步。

只有所有顶点都被成功删除，并且每一步都恰好只有一个选择，才能返回 1。实现时无需真的改变邻接矩阵，可用入度值 -1 标记已删除顶点。

（2）C 语言算法。 采用邻接矩阵中 0 表示无边、非 0 表示有边的表示方式。

int uniquely(MGraph G) {
    int n = G.numVertices;
    int degree[MAXV] = {0};

    // degree[j] 为尚未删除顶点 j 在剩余图中的入度。
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (G.Edge[i][j] != 0)
                ++degree[j];

    for (int step = 0; step < n; ++step) {
        int only = -1;

        // 查找唯一的、尚未删除的零入度顶点。
        for (int i = 0; i < n; ++i) {
            if (degree[i] == 0) {
                if (only != -1)
                    return 0;  // 选择不唯一，或图本身有环，均不符合要求。
                only = i;
            }
        }
        if (only == -1)
            return 0;          // 未处理完却无零入度顶点，剩余图含环。

        degree[only] = -1;      // 标记删除，避免再次选中。
        for (int j = 0; j < n; ++j)
            if (degree[j] >= 0 && G.Edge[only][j] != 0)
                --degree[j];   // 删除 only 的出边，更新剩余顶点入度。
    }
    return 1;                  // 全部顶点处理成功，且每一步选择唯一。
}

正确性说明。 初始入度由全部边统计得到。每次删除一个顶点及其出边后，只对这些出边的终点减 1，故未删除顶点的入度始终等于其在剩余图中的实际入度。若没有零入度顶点，就无法选择拓扑序列的下一顶点；若有多个，就无法得到唯一完整序列。若每一步只有一个，则任何合法拓扑序列的下一顶点都被强制确定，依次处理全部顶点后所得序列既合法又唯一。因此返回值与题目要求一致。

复杂度。 统计入度访问 $n^2$ 个矩阵元素；至多 n 轮，每轮扫描 n 个入度并扫描 n 个出边位置，所以时间复杂度为 $O(n^2)$。工作数组的逻辑使用量为 $O(n)$，程序用题目给定上界 MAXV 分配数组；不计按值传入图的存储，额外工作空间为 $O(n)$。算法不修改 G 的邻接矩阵。

（1）构造散列表并计算装填因子。

散列函数先计算初始地址 $H_0=(3\times key)\bmod11$。若地址已占用，依次计算 $H_k=(H_0+k^2)\bmod11$，直到遇到空位置。这里每次都从原始 $H_0$ 加上 $k^2$，不能从上一次地址继续累加平方。

最终 HT 如下：

装填因子等于已存关键字数除以散列表总容量，故：

$$\alpha=\frac{7}{11}\approx0.636.$$

（2）查找关键字 14。 查找必须使用与插入相同的探查规则。从 $H_0=9$ 开始：地址 9 中为 3，不等；$k=1$ 时地址 10 中为 18，不等；$k=2$ 时地址 $(9+4)\bmod11=2$ 中为 14，匹配成功。因此关键字比较序列为 3、18、14，共比较 3 次。

（3）查找关键字 8。 初始地址为 $H_0=24\bmod11=2$，探查过程如下。

因此确认失败的散列地址为 7。本表没有删除标记，若 8 曾被插入，它必会落在这个探查序列的第一个空位置；现在先遇到真正的空位置即可判定不存在，不必再探查其后的地址。

（1）通用寄存器数量与移位字段位数。

指令的 rs1、rs2、rd 都用 5 位编码寄存器编号，共可表示 $2^5=32$ 个编号，所以 M 最多有 32 个通用寄存器。字段位数限制的是可编码的数量，不能仅凭一个示例寄存器编号推断数量。

M 的字长为 32 位，一次对一个机器字进行移位，移位量编码范围为 0～31，恰好有 32 种取值，故 shamt 需要 5 位。例如移位 2 的字段是 00010，移位 31 的字段是 11111。

（2）add 的控制信号、计算结果与溢出标志。

add 的功能是把两个源寄存器的内容相加。ALU 的 A 输入已来自 rs1，第二输入应选择 rs2 读出的 B。图中多路选择器的 B 输入标为 0，所以 ALUBsrc=0；若选 1，会错误地把扩展后的立即数送入 ALU。

把给定机器数相加：

   87654321H
 + 98765432H
 ------------
  11FDB9753H

ALU 结果 F 只有 32 位，保留低 8 个十六进制位，故 F=1FDB9753H。超出 32 位的最高进位为 1，所以 CF=1。

若按有符号补码看，两个操作数的最高位均为 1，都是负数；结果 1FDB9753H 的最高位却为 0，是正数。“同号相加，结果异号”说明有符号溢出，所以 OF=1。若该 add 处理无符号整数，判断溢出应查看 CF，因为无符号溢出的含义是和超过 $2^{32}-1$；OF 只判断补码有符号范围是否越界。相同的机器加法可同时产生这两个标志，程序根据数的解释选择相应标志。

（3）slli 为什么可以任选 Ext。

本题给定的 slli 编码中，IR[31:25] 固定为 0000000，IR[24:20] 才是 5 位 shamt。扩展器输入 IR[31:20] 的结构因此为 0000000 | shamt，这个 12 位数的最高位 IR[31] 必为 0。

零扩展在高位填 0；符号扩展复制最高位，而最高位也是 0。因此两种扩展的 整个 32 位输出完全相同，都表示同一个非负移位量。故 Ext 可以为 0，也可以为 1。这一结论直接来自本题的编码，不需另外假设移位器如何屏蔽高位。

（4）lw 的 Ext 与 ALUctr。

lw 的有效地址为 $R[rs1]+imm$，imm 是 12 位补码偏移量，可能为负数。要在 32 位 ALU 中保持其数值，必须把符号位扩展到高 20 位，故 Ext=1。若把负偏移量零扩展，就会把它误解释成一个较大的正数。

地址计算需要加法，题设规定 ALUctr=000 表示加，所以 ALUctr=000。此外，立即数应从选择器的 1 路进入 ALU，即 ALUBsrc=1；访存读取发生在地址计算之后。

（5）解码机器指令并计算存储地址。

按本题 lw 的字段位置拆解 A040A103H：

其操作码与功能字段同时符合 lw，且与 add、slli 的操作码不同，因此在题设指令编码中可确定为 lw，汇编形式是 lw r2, -1532(r1)。

偏移 A04H 的 12 位符号位为 1，故有符号值为 $\text{A04H}-\text{1000H}=-\text{5FCH}=-1532$，符号扩展后为 FFFFFA04H。给定基址 R[01H]=FFFFA2D0H，有效地址为：

FFFFA2D0H - 000005FCH = FFFF9CD4H

因此读取数据的存储地址是 FFFF9CD4H。这里取的是基址加有符号偏移，目的寄存器 rd 的编号不参与地址计算。

（1）各变量所在的寄存器。

M 按字节编址，32 位 int 占 4 B，所以 a[i] 的地址应为“数组首地址 $+4i$”。逐条识别指令中的数据流：

故 a 的首地址、i、sum 的寄存器编号依次是 03H、02H、01H。r4、r5 是中间结果寄存器，不能误当成原变量所在寄存器。

（2）地址、数据、和以及所占页面。

首先计算字节偏移：$i=5$，每个元素 4 B，所以偏移为 $5\times4=20=14\mathrm{H}$。由 r3 中的首地址得到：

$$\operatorname{addr}(a[5])=0013DFF0\mathrm{H}+14\mathrm{H}=0013E004\mathrm{H}.$$

图中从这个地址起连续 4 个字节为：

小端存储把数的低字节放在低地址，因此从高有效字节到低有效字节组合为 FF FF EC DC，即 a[i] 的机器数为 FFFFECDCH。它按有符号 int 解释为负数：其绝对值为 00001324H，即 4900。

初始 sum 为 00001332H，十进制值 4914。相加后为 $4914-4900=14$，机器数为 0000000EH。也可直接检查机器加法：

  FFFFECDCH
+ 00001332H
-------------
 10000000EH  → 取低32位，得到0000000EH

页大小为 $4\text{ KB}=2^{12}\text{ B}$，页内偏移占 12 位，所以页号等于地址右移 12 位。a[i] 地址 0013E004H 的页号为 0013EH，页内偏移为 004H。

数组首地址 0013DFF0H 位于页 0013DH，该页从 0013D000H 到 0013DFFFH；a[5] 已位于下一页 0013EH。数组是连续存放的，且这次合法访问至少需要存在 a[0]～a[5]，对应地址区间 0013DFF0H～0013E007H，跨过页面边界 0013E000H，所以数组至少存放在 2 页中。未知的后续元素可能占更多页，但题目问的是至少数量。

（3）slli 的机器码与 short 元素偏移。

本题给定 slli 的功能字段为 010、操作码为 0010011。应严格使用这些题设编码，把 slli r4, r2, 2 的字段按位排列：

拼接后的 32 位串为：

0000000 00010 00010 010 00100 0010011
= 0000 0000 0010 0001 0010 0010 0001 0011
= 00212213H

所以机器码为 00212213H。若 a 改为 short 数组，一个元素占 2 B，字节偏移应为 $2i$，只需把移位量改为 1，即 slli r4, r2, 1。本小问只要求修改该移位指令的汇编形式。

页大小为 $4\text{ MB}=2^{22}\text{ B}$，所以虚拟地址低 22 位是页内偏移，高 10 位是页号；物理地址低 22 位同样是页框内偏移，高 10 位是页框号。每个页表项占 4 B，编号为 p 的页表项距离页表起点的字节偏移就是 $4p$。

（1）所缺页的页表项位置和更新后的页框号。

虚拟地址 12345678H 的页号为：

$$p=12345678\mathrm{H}\gg22=048\mathrm{H}.$$

其页内偏移为 00345678H。因此本次要更新的是页表中编号 048H 的表项，表项字节偏移为：

$$048\mathrm{H}\times4=120\mathrm{H}.$$

题设页表在虚拟空间中从 B8C00000H 开始，在物理主存中从 65400000H 开始连续存放，同一表项相对这两个起点的偏移都是 120H：

物理地址 BAB45678H 所在页框的起址为 BA800000H，加上 00345678H 恰好恢复该物理地址，说明虚拟地址和物理地址的页内偏移一致。页表项记录页框号 2EAH，不应把完整物理地址或页内偏移写成页框号。

（2）页表本身所在页的映射。

页表也是存储在内存中的数据，它自己的虚拟地址仍属于某个虚拟页。页表有 $2^{10}=1024$ 个表项，总大小为 $1024\times4=4096$ B，远小于 4 MB；起点 B8C00000H 又按 4 MB 页边界对齐，所以整个页表都位于同一个虚拟页中。

该页的页号为：

$$p_{\text{table}}=B8C00000\mathrm{H}\gg22=2E3\mathrm{H}.$$

为了映射这个页，要在 P 的页表中查编号 2E3H 的表项。它相对页表起点的偏移为 $2E3\mathrm{H}\times4=B8C\mathrm{H}$，所以该表项的虚拟地址为：

$$B8C00000\mathrm{H}+B8C\mathrm{H}=\mathbf{B8C00B8C\mathrm{H}}.$$

页表被装入从 65400000H 起的主存，而这个物理起点也按页框边界对齐。因此页表所在页对应的物理页框号是：

$$65400000\mathrm{H}\gg22=\mathbf{195\mathrm{H}}.$$

本小问的三个结果依次为 2E3H、B8C00B8CH、195H。要注意 2E3H 是“页表所在虚拟页的编号”，195H 是它映射到的物理页框号，二者不同；B8C00B8CH 则是描述这项映射的页表项所在地址。

（1）C1 的代码是否是临界区。

是。临界资源指一次只允许一个进程访问的共享资源，访问它的代码就是临界区。B 只能存放一个分组，P1、P2 都执行写入操作 C1，若不互斥，可能同时认为 B 为空，随后各自写入，造成一个分组覆盖另一个，或者让缓冲区内容被交错写坏。

因此 C1 对 B 的访问需要互斥。若代码中包含“检查 B 为空，再写入”的逻辑，检查与写入也应受到一致的同步保护；单独检查为空后再无保护地写入不能保证正确。

（2）一次写入与一次读出的最少信号量。

B 初始为空，P1 只写一次，P2 只读一次。唯一必须建立的先后关系是“P1 的 C1 完成后，P2 才能执行 C2”。定义 1 个同步信号量 ready，初值为 0，表示是否已有一个可供读取的分组。

P1:                 P2:
    C1;                 wait(ready);
    signal(ready);       C2;

wait(ready) 在值为 0 时使 P2 等待；P1 写入完成后执行 signal(ready)，允许 P2 继续读取。若 P1 先运行，信号保留下来供 P2 消耗；若 P2 先运行，它会阻塞到写入完成。两种启动顺序都正确。

不需要再加互斥信号量：本小问只有这一次写与这一次读，ready 已使二者严格先后执行，不会同时访问 B。也不需要 empty 信号量，因为 P1 的唯一一次写入面对的初始 B 已知为空，且没有第二次写入。若改成反复生产消费，条件会变化，但不能为本题的一次操作额外增加不必要的信号量。

（3）两次修改的最少信号量。

B 初始不为空，两次 C3 都只修改已有分组，不会把 B 变为空。两进程无需等待“有数据”，也没有规定谁必须先修改，但必须避免同时读改写同一个分组。定义 1 个互斥信号量 mutex，初值为 1，表示缓冲区当前可被一个进程占用。

P1:                 P2:
    wait(mutex);        wait(mutex);
    C3;                 C3;
    signal(mutex);      signal(mutex);

任何进程执行 C3 前先 wait(mutex) 取得独占权，修改完成后 signal(mutex) 释放。mutex 只有一个许可，所以一个进程进入后，另一个必须等待，保证 C3 的执行不会重叠；第一个完成后第二个才可进入。两个修改都会各执行一次，顺序可以是 P1→P2，也可以是 P2→P1。

因为初始已有分组且 C3 不消耗它，不需空/满同步信号量。这里要保证的是互斥，不是固定的前后顺序；一个 mutex 已足够，也是所需的最少数量。

（1）AS4 应采用的内部网关协议。

选择 OSPF。RIP 用跳数度量距离，最多支持 15 跳，16 表示不可达。AS4 内部主机间的路径可能经过超过 20 个路由器，已经超出 RIP 的有效距离范围。OSPF 使用链路状态和链路代价计算最短路径，没有 RIP 的 15 跳限制，更适合较大的自治系统。

（2）AS3 内 IP 分组的最小初始 TTL。

按本题的逐跳计算，每经过一个路由器转发，IP 分组的 TTL 减 1；若减到 0，路由器就丢弃该分组，而不会继续转发。AS3 内任意两个主机通信最多经过 15 个路由器。要保证经过第 15 个路由器后仍可送到目的主机，初始 TTL 必须大于 15，故至少设为 16。

初始为 16 时，经过 15 个路由器后剩余 1，可完成最终交付；初始为 15 时，恰好在第 15 个路由器减到 0，无法保证正常接收。TTL 统计的是转发路由器造成的消耗，不应把 15 直接当成足够的初值。

（3）RIP 获得两个网络正确路由所需时间。

初始距离向量只包含已知的直接连接网络。210.2.3.0/24 直接连接 R14，210.2.4.0/24 直接连接 R16。同步交换时，一轮只能把已有信息传给相邻路由器：本轮新学到的信息，要等下一轮才能再传给它的邻居。题目明确每 30 s 更新一次，应按这个周期传播模型计算。

AS1 的内部连边为 R11—R12、R12—R13、R11—R14、R14—R15、R15—R16、R13—R16 和 R13—R15。按这些连边，路由器到两个直连路由器的最短链路数如下；这里用链路数计算需要传播几轮，RIP 到目的网络的跳数则还包括直连网络的基本距离。

以“交换初始向量”为 0 时刻，正确最短路由的传播过程为：

例如 R11 到 R16 的最短路径可取 R11→R14→R15→R16，要跨 3 条路由器间链路。初始交换让 R15 学到 R16 的直连网络，30 s 时 R14 再学到，60 s 时 R11 才学到。初始交换本身已经传播第一层，不能把三层直接算为 90 s。

到 .3.0/24 的正确路由全部建立需 30 s，到 .4.0/24 的需 60 s，所以两者同时全部正确至少需要 60 s。

（4）BGP 会话与通告报文。

R44 属于 AS4，R13 属于 AS1，二者在不同自治系统之间交换路由，因此由 eBGP（外部 BGP）会话完成。可达性信息和相应路径属性通过 UPDATE 报文通告。

R13、R14、R15 都属于 AS1，R13 再把学到的外部网络可达性信息传给同自治系统中的 BGP 路由器，使用 iBGP（内部 BGP）会话。iBGP 是在 AS 内部传播 BGP 信息的机制，不能因双方同属 AS 就把这项通告写成 RIP。

BGP 的 OPEN 用于建立会话，KEEPALIVE 用于保持会话，NOTIFICATION 用于报告错误等情况；实际发布或撤销路由使用 UPDATE。三个所问答案依次为 eBGP、UPDATE、iBGP。

（5）R14、R15 到目标网络的下一跳。

在题设无策略约束、未给出差别的其他路径属性相同的情况下，先比较 AS_PATH 长度，优先选择经过自治系统较少的路径：

R11、R13 两条路径在 AS_PATH 长度上相同，再比较 AS1 内到 BGP 下一跳的内部路由代价，选择本地更近的出口。AS1 运行 RIP，可按内部最短跳数比较：

所以 R14 路由表中到 136.5.16.0/20 的下一跳为 R11，R15 的下一跳为 R13。不能仅因目的网络相同就让所有内部路由器选择同一出口；相同外部路径长度下，各路由器到出口的内部距离可能不同。