2025年计算机408真题

答案：B。

时间复杂度要统计基本操作执行的总次数，不能只看外层循环有多少次。外层条件是 $i^2\le n$，所以令 $m=\lfloor\sqrt n\rfloor$，i 依次取 1、2、……、m。给定一个 i，内层的 count++ 恰好执行 i 次，因此总次数为

$$T(n)=\sum_{i=1}^{m}i=\frac{m(m+1)}2=\Theta(n).$$

外层循环自身的比较、递增只需 $\Theta(\sqrt n)$ 次，不会改变总复杂度的数量级。按题目要求选紧确的数量级，时间复杂度为 $O(n)$。

A 把这段循环误认成每次将变量倍增或减半的对数循环；C 多加了并不存在的 $\log n$ 因子；D 把外层误算成 n 次、内层也误算成 n 次。复杂度分析按整数运算不会溢出的算法模型进行。

答案：D。

括号匹配的栈算法是：遇到左括号入栈，遇到右括号时检查并弹出对应左括号。已经闭合的括号不再占用栈，因而所需最大容量等于表达式的最大嵌套深度，而不是表达式中左括号的总数。

D 在读入 (d+e) 的左括号时，前三层括号还未闭合，需要第 4 个栈单元，容量 3 的栈会溢出。A、B、C 虽然都有多个括号，但最大同时在栈中的括号数不超过 3，均能处理。

答案：D。

二叉树采用从下标 0 开始的顺序存储时，结点 i 的左、右孩子位置分别为 $2i+1$、$2i+2$；非根结点的父位置为 $\lfloor(i-1)/2\rfloor$。空位置用 -1 标记后，一个非空结点的父结点必须存在，否则该结点无法连接到根。

D 中，R[8]=19，其父位置为

$$\left\lfloor\frac{8-1}{2}\right\rfloor=3,$$

但 R[3]=-1，即值 19 的结点拥有一个不存在的父结点，故不能表示合法二叉树。

A 中 35 的父位置是 2，对应 40；B 中每个非空位置都有非空父结点；C 中 12 的父位置是 2，对应 10，均合法。C 的结点 10 只有右孩子也完全允许。题目要求的是普通二叉树，不是二叉排序树，不需要检查左值小于根、右值大于根。

答案：B。

森林是若干棵互不相交的树。采用“左孩子、右兄弟”表示法，把每个结点的第一个孩子作为二叉树的左孩子，把下一个兄弟作为右孩子；各棵树的根也按兄弟关系相连，就能把任意非空森林转换成一棵二叉树。空森林相应表示为空二叉树，因此 B 正确。

A 错：完全二叉树允许有一个度为 1 的结点，其唯一孩子是左孩子。例如只有根和根的左孩子的树，就是完全二叉树。

C 错：对任意非空二叉树，叶结点数满足 $n_0=n_2+1$，这里 $n_2$ 是度为 2 的结点数。分支结点还包括度为 1 的结点，数量为 $n_1+n_2$，不能直接拿它与叶结点数比较。三个结点连成单孩子链时，分支结点有 2 个、叶结点只有 1 个。

D 错：表达式树中的运算符必须在所需子表达式计算完成后执行。根运算符组合整棵树的计算结果，通常最后计算，而不是最先计算。

答案：D。

哈夫曼树每次从当前权值中选出两个最小值合并，新权值再参与下一次选择。字符的编码长度等于它作为叶结点时到根的边数。对频次 2、3、4、6、8、10、11，合并过程是

$$2+3=5,\quad4+5=9,\quad6+8=14,\quad 9+10=19,\quad11+14=25,\quad19+25=44.$$

从最后一次合并向下追踪，可以得到各叶的深度：

例如频次 2 的路径依次经过权值 5、9、19、44，共 4 条边；频次 10 只经过 19、44，共 2 条边。编码长度至少为 3 的字符是频次为 2、3、4、6、8 的五个字符，所以选 D。A、B、C 都少计了满足长度条件的叶结点，不能只统计最小频次的两三个字符。

答案：C。

无向图若没有回路，就是森林。森林的每个非平凡树分量必有度为 1 的叶结点，孤立顶点的度则为 0。因此，若所有顶点的度都至少为 2，该图不可能是森林，必存在回路，C 正确。

A 错：有向图可能是有向环，如 $v_1\to v_2\to v_3\to v_1$，每个顶点的入度都是 1，没有入度为 0 的顶点。必须加上“无环”等条件才可保证存在入度为 0 的顶点。

B 错：有向无环图一定有拓扑序，但不一定唯一。两个互不约束的顶点可以交换先后次序；仅当各顶点的先后关系足够严格时，拓扑序才唯一。

D 错：普通 BFS 按边数从少到多扩展，能求无权图或等权图的最短路，不能保证一般带权图的最小权值路径。例如直接边权为 10，而经过一个中间顶点的两条边各为 1，BFS 优先发现直接边，但其总权值并不是最小值。一次 BFS 也只解决一个源点的可达和最短路问题。

答案：C。

设每块有 s 个元素，则共有 $b=400/s$ 块。分块查找先在索引表中顺序查找目标块，再在块内顺序查找目标元素。各元素等概率且均匀分块时，两部分成功查找的平均比较次数分别为 $(b+1)/2$ 和 $(s+1)/2$，所以

$$ASL=\frac{400/s+1}{2}+\frac{s+1}{2} =1+\frac12\left(\frac{400}{s}+s\right).$$

由 $s+400/s\ge2\sqrt{400}=40$，当 $s=20$ 时取最小值。也可以直接比较四个选项：

A、B 的块过小，导致顺序查索引表的代价大；D 的块内顺序查找代价增加，超过了索引查找所节省的代价。C 在两部分代价之间取得最优平衡。

答案：C。

4 阶 B 树每个结点最多有 4 个孩子、3 个关键字。非根结点至少有 1 个关键字；非叶根至少有 1 个关键字、2 个孩子；所有叶子位于同一层。七个关键字互不相同，按从小到大的顺序固定后，每一种合法形状及各结点关键字个数都唯一确定关键字的分配，无须再乘排列数。

单层树最多存 3 个关键字，不可能容纳 7 个。两层树按根中的关键字个数分类：

三层树的最小形状是：根有 1 个关键字、两个孩子，第二层两个结点各有 1 个关键字、两个孩子，第三层四个叶结点各有 1 个关键字。总数恰为 $1+2+4=7$，只有 1 种。四层树至少需要 $1+2+4+8=15$ 个关键字，不能出现。

故总数为 $1+6+1+1=9$。A、B 少计了合法分配或三层的最小形状，D 则多计了不满足结点容量或同层叶子条件的情况。

答案：A。

散列冲突指待插入关键字探查的位置已经被占用。“同义词”专指散列函数值相同的不同关键字；探查过程中相撞的两个关键字未必是同义词。

线性探查使用 $(H(key)+i)\bmod m$，i 依次为 0、1、……，能够循环访问长度为 m 的散列表的全部位置。因此只要还有空闲单元，就一定能够找到，A 正确。

B 错：二次探查按平方偏移探查，未必覆盖全部位置。例如表长为 8、初始位置为 0，采用正负平方偏移时只能访问 0、1、4、7 等位置，即使其他位置为空，也可能找不到。

C 错：某关键字因冲突移到了另一个位置，该位置又可能正好是其他关键字的原散列位置，后者就与非同义词发生冲突。

D 错：两个关键字的初始散列地址相同，采用二次探查时第一步仍会冲突，所以二次探查并不能排除同义词冲突。

答案：D。

本题比较的是“元素移动次数”，不是关键字比较次数。简单选择排序每趟扫描未排序部分，找出最小元素后至多交换一次；共进行 n-1 趟，所以最多交换 n-1 次。若一次交换用临时变量完成，需要 3 次元素赋值，则移动次数至多为 $3(n-1)$，为 $O(n)$。

A 错：起泡排序在逆序情况下，每一对逆序元素都需要通过相邻交换消除，交换数达到 $n(n-1)/2$，移动量是二次量级。

B 错：直接插入排序在逆序情况下，第 i 趟要把已有的 i 个元素向后移动，累计移动量包含 $1+2+\cdots+(n-1)$，也是二次量级。

C 错：快速排序在多层划分中可能反复交换、移动同一批元素，存在超线性移动的输入序列，无法保证简单选择排序那样的线性移动上界。不能仅凭快速排序的最坏时间复杂度就断言其每一种实现的最坏移动数；排除它所需的关键事实是其最坏移动量并非四种算法中最小。

简单选择排序虽然仍需 $\Theta(n^2)$ 次比较，但元素移动很少，故选 D。

答案：A。

希尔排序对按某个增量间隔取出的子序列分别进行插入排序。检验第 1 趟是否使用增量 3：将原序列按从 0 开始的下标分成三组，

把三组放回原下标，正好得到第 1 趟的 5、10、20、30、15、35、45、25、40。

再以增量 2 分成偶数下标组 5、20、15、45、40 和奇数下标组 10、30、35、25。组内分别排序为 5、15、20、40、45 和 10、25、30、35，交错放回正好得到第 2 趟的序列。因此两趟增量分别为 3、2，选 A。

B 错：按个位进行基数排序时，个位为 0 与个位为 5 的关键字应集中成组，与第 1 趟不符。C 错：自底向上的归并排序第 1 趟会合并相邻单元素，如 40、30 变成相邻的 30、40，而题目按间隔重排。D 错：折半插入排序每趟扩大连续的有序前缀，不会同时把多个间隔子序列排好。

答案：D。

short 型的 si 的数值是 -32767。将负整数转换为 32 位 unsigned int 时，结果按模 $2^{32}$ 取得，即找到与 -32767 同余的非负整数：

$$ui=2^{32}-32767=2^{32}-2^{15}+1.$$

从机器数看，si 的 16 位补码是 8001H，按数值转换到 32 位后对应 FFFF8001H；把这个 32 位位串按无符号数解释，也得到上述结果。

A 的 $2^{15}+1=32769$ 相当于把 16 位 8001H 直接当作无符号数并零扩展，丢失了原变量的负数含义。B 的 $2^{15}$ 既不是原数值，也不是转换结果。C 对应 $2^{32}-32769$，把 -32767 错算成了 -32769。这里不能因为目标类型无符号，就直接对原 short 位串做零扩展。

答案：D。

IEEE754 单精度格式由 1 位符号、8 位阶码和 23 位小数组成。正规数的值为

$$(-1)^s(1.f)_2\,2^{E-127}.$$

47300000H 按字段拆分如下：

该阶码既不是全 0，也不是全 1，是正规数，因此有效尾数必须加上隐含的整数位 1。最终

$$x=(1+0.375)\times2^{15}=1.375\times2^{15}.$$

A 同时漏掉隐含 1 并把指数少算 1；B 的有效尾数正确但指数应为 15；C 的指数正确却漏掉隐含 1。D 的两个字段解释都正确。

答案：D。

8 位补码的数值范围是 -128～127。A3H 的最高位为 1，数值为 $163-256=-93$；75H 的最高位为 0，数值为 117。数学上的差为

$$x-y=-93-117=-210,$$

已经超出 8 位补码能表示的范围。

运算器计算减法时实际做 $[x]_{\text{补}}+[-y]_{\text{补}}$。75H 按位取反加 1 得 8BH，于是

$$\mathrm{A3H}+\mathrm{8BH}=\mathrm{12EH}.$$

只保留低 8 位为 2EH，按带符号数解释得到 46。负数减正数却得到正的机器结果，说明发生有符号溢出，OF=1。因此选 D。

A、B 的输出值 24 实际是 x+y=-93+117 的结果，把题目要求的减法误算成了加法；C 虽得出 46，却误将“结果能写进 8 位”视为“没有溢出”。OF 判断的是数学真值是否超出范围，不能只看截断后的结果。

答案：C。

32 位计算机中的 int 占 4 B，并按 4 B 边界对齐。结构体布局为：

所以每个 record 占 20 B，即 14H B。数组下标从 0 开始，employee[1].id 的地址是

$$\mathrm{A0B0H}+\mathrm{14H}=\mathrm{A0C4H}.$$

小端存储把低有效字节放在低地址。12345678H 的四个字节按地址递增排列为：

因此 56H 位于 0000A0C5H。A 的地址尚未进入第二个结构体的 id；B 指向其最低有效字节 78H；D 指向 34H。先算结构体步长，再按小端定位字节，不能把两步混在一起。

答案：C。

ISA 是软件可见的指令集规范，它规定程序员和编译器如何编码、使用指令，例如指令格式、操作码、寻址方式及可见寄存器。是否采用定长指令字格式会直接影响指令编码与取指解释，必须由 ISA 规定，所以 C 正确。

A 的阵列乘法器是实现乘法的硬件方案，也可用其他乘法器实现同一乘法指令。B 的微程序控制器和硬连线控制器是控制单元的不同实现方式。D 的单总线或多总线数据通路是处理器内部组织方案。三者均属于微体系结构，程序使用同一套 ISA 时不必知道它们的具体选择。

答案：C。

RISC 常见设计思路是让指令操作和格式较规则，减少复杂的指令内操作，使取指、译码、执行、访存、写回更容易划分为流水段。因此“难以采用流水线数据通路”与这一特点相反，C 是错误叙述。

A 正确：较简单、规则的指令控制通常便于使用硬连线方式。B 正确：Load/Store 风格将访存集中在加载和存储指令中，算术逻辑指令主要在寄存器之间操作，有利于统一流水线。D 正确：通用寄存器较丰富，过程调用常用寄存器传递前若干个参数，减少访存。

这些是 RISC 的常见特征，并不要求每一种 RISC 实现都完全相同；本题应辨认与典型设计方向明显矛盾的 C。

答案：B。

CPI 是执行程序时平均每条指令消耗的时钟周期数，即“总执行周期数÷已执行指令数”。它既受指令类型比例影响，也包括访存等待、流水线停顿等实际开销。Cache 缺失率提高时，处理器通常需要更多周期等待主存，因此程序 CPI 与 Cache 缺失率有关，B 错误。

A 正确：加载、分支、乘除法等指令可能需要不同周期数，平均 CPI 要结合各类指令的执行比例计算。

C 正确：单周期 CPU 每条指令都必须在一个周期内完成，其时钟周期至少要容纳最耗时指令的完整数据通路延迟。

D 正确：流水线各段共用时钟，周期至少要容纳最长流水段的延迟，实际还需考虑流水寄存器等开销。时钟周期描述一个周期有多长，CPI 描述每条指令需要多少周期，二者不能混淆。

答案：A。

程序计数器 PC 保存下一次取指的地址，是具有特定用途的寄存器。通用寄存器组主要供指令保存一般操作数和结果，PC 可以独立实现，并不要求被包含在通用寄存器组中。因此 A 的“应该包含”不成立。

B 正确：处理器必须识别指令操作码，才能产生相应操作的控制信号，所以控制器需要操作码译码功能，即使采用微程序控制也仍需从操作码确定控制入口。

C 正确：单周期控制器主要根据当前指令产生组合控制信号；多周期控制器还要记录当前执行步骤、控制状态转移，因此通常更复杂。

D 正确：流水线重叠执行多条指令，后续指令可能依赖尚未写回的结果，分支又可能改变取指方向，必须处理数据冒险和控制冒险等问题。

答案：A。

带宽等于“每秒传送次数×每次传送的数据量”。题目已明确 1333 实际表示 1333 MT/s，即每秒传送 $1333\times10^6$ 次，这个有效传送率已经包含每时钟周期 4 次传送，不能再乘 4。

总线宽度为 64 位，每次传送 $64/8=8$ B，所以

$$B=1333\times10^6\times8 =10.664\times10^9\ \mathrm{B/s} \approx10.66\ \mathrm{GB/s}.$$

B 的 42.66 GB/s 是在已给出的有效传送率上重复乘 4。C 的 85.31 数值来自 $1333\times64$，计算的是 Gb/s，却将单位写成 GB/s。D 同时重复乘 4，并未完成位到字节的转换。此题必须按题设对“1333”的单位说明计算。

答案：B。

DMA 由控制器在设备和主存之间直接进行成批数据传送。CPU 负责设置传送参数并处理完成通知，不必为每个字节都执行一次读写，因此尤其适合数据量大、速率高的设备。

网卡要连续收发网络帧，固态硬盘要批量传送磁盘块，二者都符合 DMA 的使用特点。键盘的输入零散且速度低，针式打印机的输出也较慢，通常采用中断等方式即可，逐次处理的 CPU 开销较小。因此应选择 II、III，即 B。

A、C 都把低速键盘或打印机与高速设备混在一起，并遗漏了另一个适合 DMA 的高速设备；D 包含适合的固态硬盘，却错误地用针式打印机替换了网卡。判断依据是传输速率、批量性和 CPU 逐次服务的成本，而不是设备是否属于输入设备。

答案：A。

外部中断请求来自 CPU 之外的硬件，例如时钟或 I/O 控制器。DMA 控制器完成一批设备与主存之间的传送后，需要通知 CPU 进行后续处理，因而会发出外部中断请求，A 正确。

B 错：一次普通总线事务完成只说明该次读写已经结束，它通常通过总线控制或握手信号结束，不必触发 CPU 的中断。

C 错：页故障本身是由当前指令访存触发的内部异常；页故障处理完成后恢复执行属于异常处理的返回过程，不是一个新的外部中断请求。

D 错：断点指令由 CPU 执行指令时主动触发，属于内部异常或陷阱。区分内外中断时应看触发来源，而不是看处理程序是否在内核中运行。

答案：D。

进程上下文是让进程暂停后能够继续执行所需的状态。切换到另一个进程时，CPU 必须恢复该进程的通用寄存器和程序计数器，否则操作数或继续执行的位置会错误。采用分页管理时，不同进程通常还有各自的页表，需要更新页表基址寄存器，使地址转换使用正确的地址空间。

内核中断向量表保存各类中断或异常服务程序的入口，是系统共用的内核结构。它的基址不由当前用户进程决定，所以普通进程上下文切换不需要更新该寄存器，选 D。

A、C 都是进程执行状态，必须恢复；B 决定当前进程的虚拟地址如何映射到物理地址，也需要随相应地址空间切换。不能把“系统公共状态”与“每个进程自己的状态”混为一谈。

答案：C。

VMM，即虚拟机监控器，负责管理虚拟机、控制其资源使用，并拦截或处理客户操作系统的敏感操作。它必须具有比客户操作系统更强的实际控制能力，不能笼统认为二者处于相同特权级。硬件辅助虚拟化可以利用根模式与非根模式等机制建立这种控制关系，故 C 错误。

A 正确：虚拟机向客户系统提供可运行的虚拟硬件环境，操作系统可以在其中运行。B 正确：VMM 可以划分处理器时间、内存和设备资源，使一台主机运行多个虚拟机。D 正确：借助指令解释或动态翻译等模拟技术，虚拟机可以在一台主机上模拟不同的 ISA；并不是只有与宿主机相同的 ISA 才能被模拟。

这里比较的是 VMM 与客户操作系统的实际权限关系，不能仅凭客户操作系统认为自己处于最高权限，就认为它能直接控制全部物理硬件。

答案：C。

题目给出的就绪队列是按优先权排列的单链表，队头始终是最高优先权进程。新进程到来时，为维持这一有序性，要从队头开始查找合适的插入位置；最坏需扫描全部 n 个结点，寻找位置为 $O(n)$。找到前驱后，修改链指针本身只需 $O(1)$，总插入复杂度仍是 $O(n)$。

选择下一运行进程时，不必再寻找最大优先权，直接取队头并更新头指针即可，为 $O(1)$。因此“插入、选出”依次为 $O(n)$、$O(1)$。

A 只看到了修改插入指针的常数开销，漏掉了寻找位置的扫描；B 把有序链表的插入与选出代价颠倒；D 忽略了最高优先权已经被维护在队头这一条件。若队列无序，两种代价可能相反，但不能改变本题给定的组织方式。

答案：B。

LRU 每次淘汰“最长时间没有被访问”的页面；命中也必须更新最近使用次序。固定分配、局部置换表示该进程只能在已分配的 3 个页框中换页，不能借用其他进程的页框。

页面 0、1、2 起初都在内存，所以访问序列的前 3 项全命中。访问完这三项后，从最久未用到最近使用的次序为 0、1、2。之后逐项跟踪：

缺页出现在访问 5、1、4、3、0、2 时，共 6 次。A 少计了一次实际被淘汰后重新访问的页面；C、D 多计了命中，常见原因是把起初已装入的页也计为缺页，或者没有在命中时更新 LRU 次序。

答案：D。

“最少页框数”关注的是：一条指令为了完成执行，最少必须让多少相关页面同时驻留。它不是让整个进程所有代码和数据同时装入内存所需的页框数。

例如一条指令可能需要取指令本身所在页、访问间接地址所在页，再访问最终操作数所在页；某些操作数还可能跨页。支持哪些寻址方式、一次指令最多访问哪些位置，会影响完成指令所必需的页面数量，因此应考虑指令系统支持的寻址方式，选 D。

A 的代码长度影响程序总共占多少页，并不能直接决定完成单条指令的最少驻留页数；B 的虚拟地址空间大小是可使用地址的上限；C 的物理地址空间大小决定系统可提供的容量。二者也都不是这一最低执行需求的决定因素。需求分页可以只装入当前需要的页面，因此不能简单按程序总大小计算最低页框数。

答案：C。

VFS，即虚拟文件系统，是操作系统中的文件系统抽象层。它为打开、读取、写入、查找目录等操作规定统一接口，具体文件系统再实现这些接口。因此应用程序可使用相同的文件操作访问不同类型的文件系统，C 正确。

A 错：“虚拟”指接口与对象的抽象，不是指该文件系统必须运行在虚拟内存中。B 错：VFS 的主要作用是统一访问方法、屏蔽具体实现差异，增加抽象层并不保证访问速度更快；缓存等机制是否提速是另一问题。D 错：网络文件系统也可以实现 VFS 接口，VFS 并不限于本地磁盘文件系统。

可以把 VFS 理解为上层应用与多种具体文件系统之间的统一入口，而不是一种特殊的物理存储介质。

答案：C。

采用索引节点方式时，目录项通常保存“文件名、索引节点号”，索引节点则保存文件的访问权限、所有者、大小、时间和数据块地址等属性。文件名到文件属性的查找过程是：先在目录中找到索引节点号，再据该号访问索引节点。

新建文件 F 时，要分配并初始化 F 的索引节点，同时在所属目录文件中增加 F 的目录项，并在其中写入文件名和索引节点号。因此 A、B、D 都是应执行的操作。

F 的访问权限保存在 F 的索引节点中，不需要再作为 F 的属性写入目录项，故 C 是不会做的操作。所属目录本身也有自己的访问权限，但那是目录的索引节点属性，不能与新文件 F 的权限混淆。

答案：A。

内存映射文件建立“文件的某段内容、偏移”与“进程的一段虚拟地址”的对应关系。此后访问这段虚拟地址，就相当于访问相应文件内容，系统负责按需装入文件页，并按映射方式处理修改，所以 III 正确。

如果多个进程建立同一文件区域的共享映射，它们可以通过该区域读写并交换数据，故 I 正确。实际通信仍需根据需要进行同步，以免并发读写产生冲突。

II 不能作为内存映射文件的正确功能表述：文件页具体位于哪些磁盘块，由文件系统的文件偏移到盘块的定位机制及分页机制处理；内存映射文件直接建立的是进程虚拟地址区间与文件内容的关系，不能把内部的页面、盘块对应关系等同于该接口所建立的映射。

IV 错：映射建立在进程虚拟地址空间中，物理页框可按需分配、换入或换出，不是将文件固定映射到系统物理地址空间。因此只有 I、III，选 A；B 引入错误的 IV，C、D 引入了层次不准确的 II。

答案：C。

文件分配表 FAT 为盘块建立表项，用表项值表示该块的状态：空闲、坏块、文件链的下一块或链尾等。扫描这些表项即可知道哪些外存块尚未被分配，所以 FAT 能提供外存空闲空间的使用情况，C 正确。

A 的目录主要用于按文件名定位文件及其控制信息，不是全盘空闲块状态表。B 的系统打开文件表记录当前已打开文件及其运行时状态，没有覆盖所有未打开文件和空闲盘块。D 的 FCB 描述某一个文件的属性与分配情况，也不是整个外存的空闲管理结构。

判断关键是结构是否描述盘块的全局分配状态，而不是它是否包含某些已分配块的地址。

答案：B。

文件系统用逻辑盘块组织文件数据，可以根据存储介质和系统需求确定逻辑块大小。这一管理功能对温彻斯特硬盘和固态硬盘都适用，所以 B 正确。逻辑盘块通常由一个或多个设备扇区组成。

A 错：划分物理扇区属于设备层、低级格式化等工作，不是文件系统确定逻辑块大小的同一操作。

C 错：文件系统通过连续或邻近分配可减少机械硬盘的寻道，但固态硬盘没有磁头移动，也没有机械寻道时间。本题问两种硬盘共同适用的功能，所以不能选“降低寻道时间”。

D 错：磨损均衡主要针对闪存擦写寿命，由固态硬盘控制器及其闪存转换层等实现；温彻斯特硬盘不具有同样的闪存擦写寿命问题，因此也不是两种硬盘的共同文件系统功能。

答案：B。

文件长度为 $2\times10^6$ B，即 $16\times10^6$ bit。图中三条链路的速率依次为 10 Mbps、100 Mbps、1000 Mbps。

电路交换先建立连接，然后按 10 Mbps 连续传送，所需时间为

$$T_{cs}=32\ \mu\mathrm{s}+\frac{16\times10^6}{10\times10^6} =1.600032\ \mathrm{s}.$$

分组交换把文件分为 $2\times10^6/400=5000$ 个分组，每组 3200 bit。R1、R2 必须收到一个完整分组才转发，但可以与其他分组在前一链路上的发送形成流水线。第一条链路最慢，后两条不会积累排队。最后一个分组在 1.6 s 时完整到达 R1，再经后两条链路发送，故

$$T_{ps}=1.6+\frac{3200}{100\times10^6} +\frac{3200}{1000\times10^6} =1.6000352\ \mathrm{s}.$$

报文交换必须在每台路由器处收完整个文件后才继续转发，不能对同一报文形成分组流水线，因此

$$T_{ms}=\frac{16\times10^6}{10\times10^6} +\frac{16\times10^6}{100\times10^6} +\frac{16\times10^6}{1000\times10^6} =1.776\ \mathrm{s}.$$

于是 $T_{ms}>T_{ps}>T_{cs}$。特别是 $T_{ps}-T_{cs}=3.2\ \mu\mathrm{s}$，差距虽小仍为正。A 把报文交换低估且把电路交换高估；C 将两个非常接近的传输时间反排；D 把分组交换误算成比整报文存储转发还慢。

答案：C。

两个码字的汉明距离是对应位不同的个数，可以通过异或后统计 1 的个数计算。设四个码字依次为 $c_1,c_2,c_3,c_4$，六对距离为：

例如前两个码字异或得 11000110，其中有 4 个 1，所以最小码距 $d_{\min}=4$。

少于 4 位的错误不会把一个合法码字变成另一个合法码字，因此能保证检测不超过 $d_{\min}-1=3$ 位错误。要唯一纠正 t 位错误，不同码字周围半径 t 的错误集合不能相交，要求 $2t<d_{\min}$，所以最多保证纠正 1 位错误。

A 把可保证的最大检错能力少算为 2 位；B、D 都声称能纠正 2 位，但两个相距 4 位的码字可能在各错 2 位后产生同一个接收位串，无法唯一判断原码字。正确组合是检测 3 位、纠正 1 位，即 C。

答案：C。

10BaseT 的速率为 10 Mb/s，CSMA/CD 的退避基本时隙为 512 比特时间，因此

$$\tau=\frac{512}{10\times10^6} =51.2\ \mu\mathrm{s}.$$

截断二进制指数退避在第 n 次冲突后令 $k=\min(n,10)$，从 $0$ 到 $2^k-1$ 中随机选择一个整数 r，等待 $r\tau$ 后再尝试发送。发生连续 11 次冲突时 k 已截断为 10，最大 r 为 1023，所以最大退避间隔为

$$1023\times51.2\ \mu\mathrm{s} =52.3776\ \mathrm{ms}.$$

A、B 分别相当于只等待 10、11 个时隙，错误地把冲突次数直接作为最大随机数。D 对应 2047 个时隙，即未将指数截断而使用 $2^{11}-1$。本题求退避算法给出的最大等待值，不是平均等待值。

答案：C。

图示过程属于新主机初次申请地址：服务器已提供候选地址 192.168.5.9，主机发送 DHCP REQUEST 表示选择该地址，但还没有得到 DHCP ACK 并完成配置。因此 REQUEST 所在 IP 数据报的源地址仍为 0.0.0.0。

在这一选择阶段，REQUEST 采用广播，让本地网络中的 DHCP 服务器都能得知主机选中了哪个服务器和地址，所以目的地址为 255.255.255.255。题目按“目的、源”的顺序提问，答案为 C。

A、B 将 REQUEST 错当成向 192.168.5.1 的单播；B、D 又提前把待确认的 192.168.5.9 当作已配置的源地址。图中出现的候选地址是 DHCP 地址申请信息，不能直接代替封装 IP 数据报的源地址。此结论对应初次申请阶段，不能与已有地址后的续租过程混淆。

答案：B。 本题采用考试常见的 NAT 端口地址转换（NAPT）语境，按路由器为外发报文改写源端口、UDP 使用非零有效校验和的模型判断。

按本题考查的 NAT 端口地址转换（NAPT）过程，路由器把内网源 IP 转换成对外地址，并对源端口建立映射，以便返回数据能找到对应内网主机和应用。因此需要处理的 UDP 端口字段是源端口 I；服务器的目的端口 II 保持不变。

转换没有增加或删除 UDP 数据，UDP 总长度 III 不变。UDP 的有效校验和还覆盖伪首部中的源、目的 IP 地址，以及 UDP 首部和数据。源 IP 或源端口变化后，非零有效校验和 IV 要相应更新。因此本题选择 I、IV，即 B。

A、C 都错误地认为报文长度会改变；C、D 把外发报文的目的端口作为转换对象。此题使用的是端口地址转换的考查语境，不能推广成任何形式的 NAT 都必然改动端口；IPv4 UDP 原本不启用校验而使用零校验和的情况也不属于这里的有效校验和更新。

答案：A。

TCP 的发送窗口受拥塞窗口 cwnd 和接收窗口 rwnd 共同限制，大小取两者的较小值；窗口内已经发送但未确认的数据还会占用窗口空间。

在 $t_0$ 时 cwnd=2000 B，阈值为 8000 B，处于慢开始阶段。甲已经发送序号 2001～3000 和 3001～4000 的两个 1000 B 段。在 $t_1$ 收到 ack_seq=3001，表示序号小于 3001 的数据已确认，只确认了第一个段。新的有效确认使 cwnd 增加一个 MSS：

$$cwnd=2000+1000=3000\ \mathrm{B}.$$

确认段给出 rwnd=4000 B，所以新的发送窗口为 $\min(3000,4000)=3000$ B，从序号 3001 起覆盖 3001～6000。其中 3001～4000 已发未确认，占 1000 B，剩余可新发的数据为 2000 B，即 2 个 MSS 段。

B 只用 3000 B 窗口除以 MSS，漏减已发未确认的数据；C 只看 4000 B 接收窗口，忽略拥塞窗口限制；D 超过了两种窗口能提供的空间。反向确认段的 seq=4001 是乙方向的序号，不能作为甲新发送数据的起点。

答案：B。

往返时间 RTT 为 8 ms。为展示时间线，可按两个方向各 4 ms 的对称情形表示这一往返；最终计算只依赖两方向时延之和为 8 ms，忽略报文发送和处理开销。

UDP 无需建立连接：客户发出请求，4 ms 后到达服务器，服务器立即返回时间，再经 4 ms 到达客户，总计 1 RTT，即 8 ms。

TCP 需要先完成建连。Time 服务器在连接建立后可以直接发送时间，不要求客户再发送一条独立的应用请求。其最短时间线为：

所以 TCP 最少为 2 RTT，即 16 ms。A 忽略了 TCP 建连；C 把两种协议的开销颠倒；D 错误地给 UDP 也增加了一个建连往返。无需计入服务完成后的连接关闭时间。

答案：A。

POP3 是邮件读取协议，用户代理可以连接邮件服务器，检查并取回自己的邮件，所以 I 正确。一次 POP3 会话中可以连续发出读取多封邮件的命令，数据通过同一条 TCP 连接传送，所以 IV 正确。

II 错：用户代理把新邮件提交给邮件服务器使用 SMTP，不是 POP3。III 错：邮件服务器之间发送、转发邮件也使用 SMTP，POP3 不承担服务器之间的邮件传递。

因此正确项只有 I、IV。B 选中了两个 SMTP 的功能；C 包含 II、III 且漏掉 IV；D 虽含 I、IV，却又加入错误的 III。区分协议时应先看邮件的流向：POP3 面向用户取信，SMTP 面向提交和转发。

（1）基本设计思想。

对固定的 i，允许配对的 A[j] 来自后缀 $A[i\ldots n-1]$，包含 A[i] 自身。设该后缀最小值为 low、最大值为 high。乘积的选择规则由 A[i] 的符号决定：

• A[i]>0：乘数越大，乘积越大，取 high。
• A[i]<0：乘以负数会反转大小关系，乘数越小，乘积越大，取 low。
• A[i]=0：所有乘积均为 0，可与非负分支统一处理。

所以不需要对每个 i 再遍历全部后缀。由右向左扫描数组，每读到一个元素就将其纳入 low、high，再计算 res[i]，即可重复利用已经求出的后缀极值。必须先更新极值、后计算结果，才能包含允许的 $j=i$。

以 A={1,4,-9,6} 为例：

最终得到 res={6,24,81,36}。仅使用后缀最大值会遗漏负数乘负数的最大结果；仅比较相邻元素也不能覆盖全部合法 j。

（2）C 语言算法。

题设结果数组为 int，以下算法按所有正确乘积均能用 int 表示的前提编写。若允许任意 int 输入，某些平方可能超出 int 范围，此时需要扩展结果数组的类型，仅扩大中间变量不能让 int 型 res 容纳超范围答案。

void calMulMax(int A[], int res[], int n)
{
    if (n <= 0) return;

    int low = A[n - 1];
    int high = A[n - 1];

    for (int i = n - 1; i >= 0; --i) {
        int x = A[i];

        // 纳入当前元素，使极值对应 A[i..n-1]，包含 j=i
        if (x < low) low = x;
        if (x > high) high = x;

        // 正数取后缀最大值，负数取后缀最小值；零也得到零
        res[i] = (x >= 0) ? x * high : x * low;
    }
}

正确性说明。 初始时 low、high 均为末尾元素，正确描述长度为 1 的后缀。假设处理 i 之前它们已描述 $A[i+1\ldots n-1]$，将 A[i] 与两个极值比较后，就得到 $A[i\ldots n-1]$ 的真实最小、最大值。再根据乘法的单调性和 A[i] 的符号选择极值，所得 res[i] 就是所有合法乘积中的最大值。由归纳可知每个位置均正确。

（3）复杂度。

循环访问每个元素一次，每次仅做常数次比较和乘法，时间复杂度为 $\Theta(n)$。计算 n 个输出本身就需要线性时间，已经达到这一数量级的最优值。除输入、输出数组外只用 low、high、i、x 等常数个变量，辅助空间复杂度为 $O(1)$；若把题设输出数组 res 也计入总存储量，则它占 $O(n)$ 空间。

（1）最短工期与关键活动。

AOE 网的顶点表示事件，边表示活动。一个事件只有在所有进入该事件的活动都完成后才能发生。因此事件最早时间 $ve(v)$ 取各前驱完成时间的最大值；事件最晚时间 $vl(v)$ 则从终点反向取各后继允许开始时间的最小值：

$$ve(v)=\max_{u\to v}\{ve(u)+w(u,v)\},\qquad vl(u)=\min_{u\to v}\{vl(v)-w(u,v)\}.$$

图中源点为事件 1，终点为事件 5。虽然编号不是拓扑顺序，但可以按 1、3、4、2、6、7、5 的拓扑顺序计算。正向计算的关键步骤是：

$$\begin{aligned} ve(1)&=0,\\ ve(3)&=0+2=2,\\ ve(4)&=\max(0+3,\,2+3)=5,\\ ve(2)&=\max(0+5,\,5+4)=9,\\ ve(6)&=\max(2+1,\,5+1)=6,\\ ve(7)&=\max(5+4,\,6+1)=9,\\ ve(5)&=\max(9+2,\,5+1,\,9+3)=12. \end{aligned}$$

令终点 $vl(5)=12$，反向计算，例如
$vl(4)=\min(10-4,12-1,8-1,9-4)=5$，全部事件时间如下：

对活动 $u\to v$、持续时间 w，最早开始时间 $e=ve(u)$，最晚开始时间 $l=vl(v)-w$，时间余量为 $l-e$：

零余量活动就是关键活动，因此关键活动为 a、e、m、n，关键路径为 $1\to3\to4\to7\to5$。持续时间之和为 $2+3+4+3=12$，最短工期为 12 个时间单位。

（2）可能与 e 同时进行的活动。

e 是关键活动，其开始时间固定为 2，结束时间固定为 5。采用最早开始安排时，b 在 0～5 进行，d 在 0～3 进行，c 在 2～3 进行，三者都与 e 有实际时间重叠。因此答案为 b、d、c。

活动 a 必须在 e 开始前完成；f、g、j、m 都从事件 4 出发，而事件 4 要等 e 在时刻 5 完成后才能发生。h、k、n 又依赖这些后续事件，最早也在 5 之后开始，均不能与 e 重叠。只在同一时刻结束和开始不算一段时间内同时执行。

（3）最大时间余量。

由活动表，j 的时间余量最大，为

$$l(j)-e(j)=vl(5)-1-ve(4)=12-1-5=6.$$

也就是说 j 最早可在 5 开始，最晚可在 11 开始而于 12 完成，允许延迟 6 个时间单位。这是保持工程工期不变的总余量，不是 j 自身的持续时间。

（4）b 在时刻 6 开始时的调整。

设 b 的新持续时间为 t。事件 2 既要等待 b，也要等待 f；f 最早在 $5+4=9$ 完成，所以事件 2 最早为 $\max(6+t,9)$。随后 k 还需 2，必须满足

$$\max(6+t,9)+2\le12.$$

于是 $6+t\le10$，即 b 最多持续 4 个时间单位。取 t=4 时，b 在 10 完成，k 在 10～12 进行，仍可按 12 完工。

若 b 保持原持续时间 5，则它在 11 完成，路径 b、k 最早要到 $11+2=13$ 才完成。要把该路径压缩回 12，必须将其后继活动 k 至少压缩 1 个时间单位，即从 2 压缩到 1。此时事件 2 在 11 发生，k 在 12 完成，其他路径仍可按原安排在 12 前完成。压缩与 b、k 无关的活动不能消除这条路径的 1 单位超时。

本题按考试常用口径：一次读或一次写各计为一次 Cache 访问，缺失损失是相对于命中的额外耗时。每个元素的完整读写耗时另行说明。

（1）Cache 地址字段与可用虚拟索引位。

Cache 数据区大小为 $32\ \mathrm{KB}=32768$ B，一个主存块为 64 B，因此共有 $32768/64=512$ 个 Cache 行。8 路组相联表示每组 8 行，故共有 $512/8=64$ 组。

块内有 64 个字节，需要 $\log_2 64=6$ 位块内地址；64 组需要 6 位组号。所以低 6 位地址为块内偏移，随后 6 位为组号，即组号对应地址位 11～6，块内地址对应位 5～0。

页大小为 $4\ \mathrm{KB}=2^{12}$ B，虚拟地址 VA11～VA0 是页内偏移，地址转换不改变这些位。VA11～VA6 可直接用作 Cache 组选索引，VA5～VA0 可直接用于块内字节选择，两者都可在页号转换完成前使用。

（2）d[100] 的虚拟地址与组号。

每个 int 占 4 B，因此 d[100] 相对数组首地址偏移 $100\times4=400=\mathrm{190H}$ B：

$$VA(d[100])=\mathrm{01800020H}+\mathrm{190H} =\mathrm{018001B0H}.$$

组号从位 11～6 取得，也就是页内地址除以 64 后取整数部分：

$$\left\lfloor\frac{\mathrm{1B0H}}{\mathrm{40H}}\right\rfloor=6.$$

因此对应 Cache 第 6 组（组号从 0 开始）。其所在块的块内偏移为 30H。虽然未给出虚拟页对应的物理页号，但组号所需位全部位于不变的页内偏移中，所以仍可确定组号。

（3）块内偏移、Cache 缺失率与平均时间。

d[0] 地址的低 6 位为 20H，因此在所在主存块中的偏移量是 20H，即 32 B。数组占 $2048\times4=8192$ B，起点没有按块边界对齐，跨越的块数为

$$\left\lceil\frac{32+8192}{64}\right\rceil=129.$$

首块只含数组的前 8 个 int，末块含最后 8 个 int，中间 127 块每块含 16 个 int，合计 $8+127\times16+8=2048$。数组跨三个页，每页有 64 个块，Cache 也有 64 组，且组号位均位于页内偏移中。每页对同一组最多贡献一个数组块，因此同一组最多占 3 行，小于每组 8 行；这一结论不要求三个物理页连续。因此本次顺序访问没有由数组自身引起的替换缺失。

每次循环先读取 d[i]，除法后再写回 d[i]，共 $2048\times2=4096$ 次数据 Cache 访问。每个块第一次读取时缺失，装入后同块后续读取及该元素写回均命中，故缺失 129 次：

$$\text{缺失率}=\frac{129}{4096}\times100\% \approx\boxed{3.15\%}.$$

题给“缺失损失 200 周期”是一次缺失相对于命中的额外代价。以一次读或写为一次 Cache 访问，平均访问时间为

$$t_{\text{一次访问}}=2+\frac{129}{4096}\times200 =8.298828125\approx\boxed{8.30\text{ 个时钟周期}}.$$

若把“一个数组元素的访问”理解为完成该元素的一次读取加一次写回，则应累计两次命中基础开销，并把 129 次块缺失分摊到 2048 个元素：

$$t_{\text{每元素读写}}=2\times2+\frac{129}{2048}\times200 =16.59765625\approx\boxed{16.60\text{ 个时钟周期}}.$$

这两个数描述不同统计口径：8.30 是单次 Cache 访问的平均值，16.60 是每个元素读写所需的平均访存时间，均不包括除法和循环控制开销。不能一边用 4096 次读写求缺失率，一边把单次访问时间直接当成完整元素读写时间。

（4）分布页数与缺页次数。

数组首地址的页内偏移是 20H，8192 B 数据不能恰好装在两页中：

$$\text{页数}=\left\lceil\frac{32+8192}{4096}\right\rceil=3.$$

具体分布为：

代码已经在主存，不计代码缺页。数组的三页起初均不在主存，按顺序访问时在 d[0]、d[1016]、d[2040] 处首次触及相应页，各发生一次缺页；页面装入后该页的后续数组访问不再缺页，故共 3 次缺页。Cache 缺失按 64 B 块统计，缺页按 4 KB 页统计，不能将二者混用。

（1）除法器的初值、计数器和 ALU 运算。

mov 先把 d[i] 的 32 位机器数装入 R1；scov 再按符号扩展到 {R0,R1} 的 64 位组合。87654321H 的最高位为 1，表示负数，扩展时高 32 位全部补 1。因此除法开始前，被除数的高半部送入余数寄存器 R，低半部送入余数/商寄存器 Q，除数送入 Y：

不能把 x=0xFF 看成 8 位带符号数 -1。本题除数寄存器宽度为 32 位，-1 的机器数应是 FFFFFFFFH。

图中 控制逻辑 包含计数器，用来记录迭代次数、决定何时停止生成商位。除法按位迭代时，需要让部分余数与除数相加或相减，因此 ALUop 控制的运算有 加法、减法。图中 {R,Q} 的联合左移由移位通路实现，不应把它当成这里 ALUop 所选择的加减运算。

（2）除法异常与异常响应。

给出的序列将 32 位 d[i] 按符号扩展后除以 32 位 x，结果商也要用 32 位补码表示。需要检测两类异常：

溢出情形为何只有这一对？32 位补码负数的最小值绝对值为 $2^{31}$，正数最大值却只有 $2^{31}-1$。除数绝对值至少为 1，除法不会增大被除数绝对值；只有最小负数除以 -1，把无法表示的绝对值变成正数时才越界。最小负数除以 1 仍是可表示的最小负数，不能误判为溢出。

发生异常后，CPU 的初始响应应完成以下工作：

1. 停止当前指令的正常完成，记录异常类型，避免把无效除法结果当作正常结果提交。
2. 保存异常断点和程序状态，使处理程序能够识别出错现场并决定如何返回。除法异常属于指令执行故障时，断点应指向引发异常的 idiv，而不是笼统地保存其下一条指令。
3. 切换到内核态，并按异常入口要求设置中断屏蔽状态，保护初始响应过程。
4. 根据异常类型取得对应服务程序入口，更新 PC，转入异常处理程序。

异常处理程序随后才执行报告、终止进程或其他处置，完整处置不能与 CPU 的硬件异常入口响应混为一谈。

信号量及初值。

这是具有容量限制的流水同步问题，同时甲、乙还竞争铁锹。采用 4 个信号量：

水桶只由丙使用，没有第二个使用者与它竞争，因此不需要另设水桶互斥信号量；也不需要为只有单一执行者的“放树苗”单独设置互斥量。

三人的操作。

甲：
while (true) {
    wait(slot);          // 先取得一个坑位名额
    wait(shovel);
    挖一个树坑;
    signal(shovel);
    signal(pit);         // 挖好后，乙才可以处理该坑
}

乙：
while (true) {
    wait(pit);           // 没有挖好的坑时等待
    放入一棵树苗;
    wait(shovel);
    填土;
    signal(shovel);
    signal(slot);        // 填完后，该坑不再计入未填坑数量
    signal(tree);        // 填土完成后，丙才可以浇水
}

丙：
while (true) {
    wait(tree);
    用水桶给一棵已填土的树苗浇水;
}

正确性说明。

slot 的每个名额在甲开始挖坑前取得，到乙填土完成后才归还，因此“已预留正在挖的坑加已挖未填的坑”总数不会超过 3，自然保证实际未填坑不超过 3。不能在乙刚放入树苗时就归还 slot，因为尚未填土的坑依然存在。

pit 只有在甲挖好后增加，乙必须先 wait(pit)，所以放树苗必定在挖坑之后；tree 只有在乙填土后增加，丙必须先 wait(tree)，所以浇水必定在填土之后。shovel 的初值为 1，使挖坑与填土不能同时占用铁锹。

甲必须先 wait(slot) 再 wait(shovel)，乙必须先 wait(pit) 再 wait(shovel)。这样任何人等待同步条件时都不占有铁锹，不会出现甲拿着铁锹等待坑位、乙需要铁锹填土才能释放坑位的死锁。4 个信号量分别承担容量、两级先后顺序与铁锹互斥，已经省去了无竞争资源的多余信号量。

（1）PCB 的位置与等待输入时的状态。

PCB 保存进程标识、运行状态、调度信息、寄存器上下文和资源管理信息等，是操作系统管理进程的内核数据结构。因此位于图中的 内核区，不应放在进程的用户栈、堆或用户数据区中供用户程序直接修改。

执行 scanf 等待键盘输入时，进程尚未具备继续执行的 I/O 条件，会进入 阻塞态（等待态）。等输入到达、相关 I/O 条件满足后，操作系统再将它唤醒为就绪态，之后由调度器决定何时运行。等待输入不是继续占用 CPU 的运行态，也不是已经具备运行条件的就绪态。

（2）代码位置与需要驱动参与的直接调用。

main 的机器指令位于图中的 只读代码区。代码区保存可执行指令，通常不允许普通数据写入，以防程序意外破坏自身指令。

main 直接调用的函数为 malloc、scanf、strlen、printf、free。其中 scanf 和 printf 的题设输入、输出功能需要相应驱动参与：scanf 从键盘或终端读入字符，printf 向显示终端输出结果，库函数通过操作系统的 I/O 服务，最终由设备驱动与设备交互。

strlen 在已有内存字符串中寻找结束符，不进行设备 I/O；malloc 和 free 管理运行时堆的分配和释放，必要时可以申请操作系统的内存管理服务，但不是这里要求的键盘、显示等设备驱动功能。

（3）变量本身与字符串的位置。

ptr 的内容是一个地址：malloc 返回堆中区域的地址后将其保存在这个全局指针变量内，scanf 再把输入字符写到该地址所指向的堆区域。free(ptr) 释放的是堆中动态区域，不是释放可读/写数据区中的全局变量 ptr。指针放在哪里，与它所指向的数据放在哪里，是两个不同问题。

本题采用理想化链路计算约定：按给定轨道高度估算地面—卫星—地面的传播路程，端到端上传时间按瓶颈链路的发送时间与单向传播时间相加，忽略题设列出的开销，并按考试模型近似忽略以太网发送、转发开销。

（1）传播时延、吞吐量与上传时间。

从 R1 到 R2，信号先从地面到高度 36000 km 的卫星，再从卫星回到地面，按题给高度计算的总传播路程为 $2\times36000=72000$ km。因此单向传播时延为

$$t_p=\frac{72000}{300000}=0.24\ \mathrm{s} =240\ \mathrm{ms}.$$

按图中以太网速率高于卫星链路的常用模型，卫星链路每方向只有 200 kb/s，是端到端瓶颈，因此H 向总部服务器可达到的最大吞吐量为 200 kb/s。对称全双工表示反方向也能同时以 200 kb/s 传输，不能把两个方向相加得到本方向 400 kb/s。

4000 B 文件有 $4000\times8=32000$ bit，在瓶颈链路上的发送时间为

$$t_t=\frac{32000}{200000}=0.16\ \mathrm{s}.$$

最后一比特还要经历单向传播，因此按瓶颈发送加传播计算，上传的理想时间下限为

$$t_{\min}=0.16+0.24=\boxed{0.40\ \mathrm{s}}.$$

0.40 s 是按上述链路参数得到的理想下限或约值。题目忽略了以太网传播，若进一步计入以太网每跳的发送、拆帧和转发开销，实际值还会增加；该小问未给具体拆帧和转发参数，不能据此虚构更精细的数值。这里求单向上传完成时间，不需要额外加一次返回确认的往返时间。

（2）发送窗口与序号位数。

一个 SLP 数据帧有 $1500\times8=12000$ bit，发送时间为

$$t_f=\frac{12000}{200000}=0.06\ \mathrm{s}.$$

第一帧从开始发送，到全部抵达 R2，再到 ACK 返回 R1，需 $t_f+2t_p=0.06+0.48=0.54$ s。ACK 长度忽略表示不计 ACK 发送时间，但不能忽略它的传播时间。

窗口为 W 时，在无差错、无超时的理想情形下可连续发送 W 帧；若未等到确认就用完窗口，需要等待。因此单向信道利用率为

$$U=\min\left(1,\frac{W\,t_f}{t_f+2t_p}\right) =\min\left(1,\frac W9\right).$$

要求 $U\ge0.8$，得到 $W\ge7.2$，故最小整数窗口为 8 帧。验证：W=7 时利用率为 $7/9\approx77.78\%$，不足；W=8 时为 $8/9\approx88.89\%$，满足。

GBN 的接收窗口为 1，为避免新旧帧序号混淆，若序号字段有 b 位，发送窗口需满足

$$W\le2^b-1.$$

W=8 要求 $2^b\ge9$。3 位仅有 8 个序号，最大允许窗口为 7；4 位有 16 个序号，可支持窗口 8，所以序号字段至少 4 位。

（3）三个子网的 CIDR 地址。

常规子网需扣除网络地址和广播地址。生活区不少于 120 个可分配地址，至少要 7 位主机号，因为 $2^7-2=126$，对应 /25；作业区、管理区各不少于 60 个，至少要 6 位主机号，因为 $2^6-2=62$，均对应 /26。

图中 H 位于管理区，地址为 10.10.10.33/26。/26 的子网步长为 64，最后一字节 33 落在 0～63，因此管理区网络地址确定为 10.10.10.0/26。余下的 64～127 正好是一个 /26，128～255 正好是一个 /25，得到：

三个地址块大小分别为 64、64、128，共 256 个地址，恰好覆盖给定 /24，既不重叠也不越界。10.10.10.33/26 是管理区的主机地址，不是该子网的 CIDR 网络地址；/25 也必须从 0 或 128 这种合法边界开始，不能把剩余地址任意拼接成一个子网。