2009年计算机408真题

答案：B。

**思路：**缓冲区用于暂存主机已经产生、打印机尚未来得及处理的数据。主机可以先把数据写进去，打印机再按自己的速度取出；题目中的两个“依次”要求先写入的数据先打印，否则文字的先后顺序会改变。

队列的规则是先进先出：例如主机依次写入 a、b、c，打印机也依次取出 a、b、c，所以选 B。A 的栈是后进先出，会先取出 c，不能保持输出顺序。C 的树主要表示层次关系，D 的图主要表示结点之间的联系，都不直接提供题目所需的先进先出访问规则。这里判断的是缓冲区的逻辑结构，与它具体使用数组还是链表实现无关。

答案：C。

**思路：**元素出栈后立即进入先进先出的队列，因此最终出队序列就是出栈序列。只需模拟怎样使栈依次弹出 b、d、c、f、e、a、g。以下用方括号表示从栈底到栈顶的内容。

先压入 a、b，弹出 b，栈剩 [a]；再压入 c、d，此时为 [a,c,d]，依次弹出 d、c；再压入 e、f，此时为 [a,e,f]，依次弹出 f、e、a；最后压入并弹出 g。全过程最多同时存放 3 个元素。尤其在 d 出栈前，a、c 还不能弹出，d 必须压在它们上方，所以容量至少为 3。A 的 1、B 的 2 不够，D 的 4 虽能完成却不是最小值，故选 C。

答案：D。

**基础：**N 表示访问当前根结点，L、R 表示递归遍历它的左、右子树；同一规则必须在每棵子树中重复使用。图的根是 1，右子树只有 3，左子树以 2 为根，其中 2 的左孩子是 4，右孩子是 5，5 的左右孩子分别为 6、7。

目标序列先出现 3，再出现根 1，说明先遍历右子树、再访问根，即 RNL。按此规则遍历左子树：5 的子树输出 7、5、6，再输出 2、4，合起来恰为 3、1、7、5、6、2、4。A 的 LRN、C 的 RLN 都是根最后，最终应以 1 结尾；B 的 NRL 是根最先，应以 1 开头；只有 D 符合。

答案：B。

**基础：**平衡二叉树通常指 AVL 树，在满足二叉排序树次序关系的基础上，要求每个结点的左右子树高度差的绝对值不超过 1。题目已经说明各图是二叉排序树，所以只需检查形状的高度条件。取空树高度为 0，叶结点高度为 1。

图 A 的根只有左子树，左子树高度为 2，右子树为 0，差为 2；图 C 的根左子树高度为 1、右子树高度为 3，差为 2；图 D 的根左子树高度为 4、右子树高度为 1，差为 3，均不平衡。图 B 的根左右子树高度都为 2，其两个孩子的左右高度差均为 1，叶结点的差为 0，因此每个结点都满足要求，选 B。

答案：C。

**思路：**完全二叉树除最后一层外，各层必须排满；最后一层的结点从左到右连续排列。第 6 层已有叶结点，树不可能再延伸到第 8 层，否则第 6 层不能出现叶结点。要使总数最大，应让第 1～6 层全部排满，再尽量增加第 7 层结点。

第 6 层最多有 $2^{6-1}=32$ 个结点，其中恰有 8 个叶结点，所以最多有 $32-8=24$ 个非叶结点。令这 24 个结点各有两个孩子，第 7 层便有 48 个结点，而且可以安排在最左侧，满足完全二叉树条件。总数为 $(2^6-1)+48=63+48=111$。A 的 39、B 的 52 不是最大值；D 的 119 需第 7 层有 56 个结点，至少占用 28 个父结点，只能留下 4 个第 6 层叶结点，故选 C。

答案：B。

**基础：**森林转换成二叉树采用“左孩子、右兄弟”规则：左指针指向原树中的第一个孩子，右指针指向原树中的下一个兄弟。题设表示从 u 沿两条二叉树边到达 v，应枚举 LL、LR、RL、RR 四种路径。

LL 是先到孩子再到其孩子，原森林中 u 是 v 的祖父；LR 是先到孩子再到该孩子的兄弟，u 与 v 为父子，故 I 可能。RL 是先到 u 的兄弟再到其孩子，u 与 v 为叔伯和侄辈关系；RR 是连续到两个兄弟，u 与 v 仍为兄弟，故 II 可能。四种路径都不会使 u 的父结点与 v 的父结点成为兄弟，III 不可能。A 漏掉 I，C、D 错含 III，选 B。

答案：A。

**思路：**判断“所有无向连通图都成立”的性质时，一项可用定理证明，一项可用具体反例否定。无向图中每条边对两端顶点的度数各贡献 1，因此所有顶点的度之和为 $2|E|$，一定是偶数，I 正确。

连通图的边数至少是 $|V|-1$，但不一定严格大于它。例如 3 个顶点连成一条链只有 2 条边，正好等于 $3-1$，II 错误。III 也不成立：3 个顶点构成三角形时，图连通且每个顶点度数都是 2，没有度为 1 的顶点。于是只有 I 正确，选 A；B 只保留错误的 II，C、D 分别多包含了错误的 II、III。注意“至少”与“大于”不能混用。

答案：D。

**基础：**m 阶 B 树是平衡的多路查找树，每个结点最多有 m 棵子树、m−1 个关键字；结点内关键字有序，利用关键字把各子树的取值范围分开；所有叶结点处于同一层，保证查找路径长度一致。

A“根最多有 m 棵子树”符合阶数的含义，B“叶结点同层”符合平衡要求，C“关键字升序或降序排列”表示按统一的有序约定组织，均符合定义。D 要求叶结点之间额外用指针相连，这是 B+ 树便于顺序扫描的典型组织方式，不是 B 树定义所要求的结构，故选 D。本题问的是“不符合定义要求”，不能把 B 树与 B+ 树的特征混记。

答案：A。

**基础：**小根堆既是完全二叉树，又要求每个父结点不大于孩子。用下标从 1 开始的数组表示时，下标 i 的父结点是 $\lfloor i/2\rfloor$。插入先放到末尾，以保持完全二叉树形状，再沿父链向上调整。

3 放在第 9 个位置，父结点是位置 4 的 19，交换；3 到位置 4 后与位置 2 的 8 交换；再与位置 1 的 5 交换。最终序列为 3、5、12、8、28、20、15、22、19，选 A。B 中位置 4 的父结点 19 大于位置 8 的孩子 8；C 中位置 2 的父结点 8 大于位置 4 的孩子 5；D 中位置 2 的父结点 12 大于位置 4 的孩子 8，三者都违反小根堆“父不大于子”的条件。插入调整只沿新结点到根的路径进行，其余位置无需改动。

答案：B。

**思路：**观察各排序算法“一趟完成后必须出现的结构”，不用反推唯一的初始序列。直接插入排序把第一个元素视为初始有序区，第一趟插入第二个元素，第二趟插入第三个元素，因此第二趟后只保证前三个元素有序。这里 11、12、13 升序，后面可以仍无序，符合 B。

A 冒泡排序两趟后应把两个最大值放到末尾，或按另一扫描方向把两个最小值放到开头；本序列两端都不满足。C 选择排序两趟后应固定两个最小值 4、5，或两个最大值 23、13，也不符合。D 二路归并排序第二趟把相邻的二元素段归并成四元素有序段，但开头 11、12、13、7 并不有序。因此只能选插入排序。

答案：C。

**基础：**冯·诺伊曼计算机把指令和数据统一存储，同一段二进制本身并没有一个必然能区分二者的标记。CPU 根据当前正在进行的操作赋予位串含义：取指阶段由 PC 给出地址，读出的内容送入指令寄存器并作为指令；执行阶段按指令要求取出的内容作为操作数。

因此区分依据是指令周期的不同阶段，选 C。A 的操作码译码已经以“当前内容是指令”为前提，不能反过来作为首次区分依据。B 的寻址方式用于定位操作数，不是区分所有指令、数据的统一标准。D 也不对，统一存储不要求所有指令与数据分处特定存储区域，同一单元的内容还可能在不同使用情境下有不同含义。

答案：D。

**步骤：**题中 int 按 32 位、short 按 16 位解释。正数 127 的补码与原值一致，$127=7F\mathrm H$，所以 x 为 0000007FH。求 −9 的 16 位补码，可从 $0009\mathrm H$ 按位取反得到 FFF6H，再加 1 得 FFF7H。

C 的表达式 x+y 会把 short 型的 y 提升为 int。因为 y 为负数，扩展时高 16 位全部补 1，得到 FFFFFFF7H；实际数值仍为 −9。相加得到 $127-9=118=76\mathrm H$，z 为 00000076H。A、B 的 FFF9H 实际表示 −7，错在 y；C 的 FFFF0076H 是负数，错在 z；D 的三个值均正确。符号扩展改变表示位宽，不改变数值。

答案：D。

**步骤：**先把较小阶码的 Y 对齐到 X 的阶码 7。Y 的尾数右移 2 位，变为 $5/8\div4=5/32$，故尾数相加为 $29/32+5/32=34/32=1.00010_2$。尾数有 2 位符号位、5 位小数位，未规格化的和可写为 01.00010；双符号位 01 表示尾数发生正向溢出，需要右规。

右规一位得 $17/32=0.10001_2$，同时阶码由 7 增到 8。5 位阶码含两个符号位，正常正数只剩 3 位数值位，最大为 $00111_2=7$；8 的形式为 01000，双符号位不一致，发生阶码上溢。A、B 保留阶码 7，无法表示规格化结果；C 虽给出右规后的尾数，却把溢出的阶码当成合法阶码。因此最终应判溢出，选 D。

答案：C。

**基础：**组相联映射先把主存块映射到一个固定 Cache 组，再允许它放入该组的任一行。组号按“主存块号模组数”计算，不能直接拿字节地址对 Cache 块数取模。

每个主存块有 32 B，按字节编址，因此地址 129 所在块号为 $\lfloor129/32\rfloor=4$，块内偏移为 $129-4\times32=1$。Cache 共 16 块，每组 2 块，故有 $16/2=8$ 组，编号为 0～7。主存块 4 映射到 $4\bmod8=4$ 号组，选 C。A 的 0、B 的 1、D 的 6 都不是映射余数；其中 1 是块内偏移，不能误当组号。题目没有指定组内哪一行，它可由替换策略决定。

答案：D。

**基础：**芯片规格“地址单元数×每单元位数”要同时与容量和字节宽度匹配。主存按字节编址，每个地址需提供 8 位。ROM 区为 4 KB，一片 2K×8 位 ROM 的位宽已经满足要求，容量为 2 KB，只需字扩展：$4/2=2$ 片。

RAM 区容量是 $64-4=60$ KB。一片 4K×4 位 RAM 每个地址只有半字节，必须两片并联，组成 4K×8 位、即 4 KB 的一组。再把 $60/4=15$ 组进行字扩展，共需 $15\times2=30$ 片。A、C 的 ROM 数量 1 少了一半；B 的 RAM 数量 15 忽略了位宽扩展。只有 D 的“2、30”正确。也可用总位数验算：$30\times4K\times4=60K\times8$ 位。

答案：C。

**基础：**相对寻址的目标地址等于执行转移时 PC 的值加上指令给出的相对位移。本题特别说明每取一个字节，PC 自动加 1，因此参与相加的 PC 是整条指令取完后指向下一条指令的值。

转移指令从 2000H 开始，共两个字节。取操作码后 PC=2001H，取位移字节后 PC=2002H。位移 06H 是正数 6，所以目标地址为 $2002\mathrm H+06\mathrm H=2008\mathrm H$，选 C。A 的 2006H 使用了指令起始地址，B 的 2007H 只计入了一个字节的取指增量；D 的 2009H 则多加了一个字节。16 位机器字长不意味着本题每次 PC 增加 2，必须服从按字节取指的明确条件。

答案：A。

**基础：**RISC 即精简指令集计算机，其设计思路是减少指令和寻址方式的复杂性，让常用操作便于快速执行，并方便组织流水线。指令规则较简单时，控制信号通常由硬布线逻辑直接产生，因此 A“普遍采用微程序控制器”是本题要求找出的错误叙述。

B 描述教材中典型 RISC 的特征：大多数简单指令可在一个时钟周期内完成相应操作，有利于流水化；这不表示所有指令在所有实现中都只有一周期延迟。C 的较多通用寄存器可减少访存、保存更多中间结果，符合设计特点。D 的指令数、寻址方式和格式种类较少，也符合“精简”的含义。判断时关注该类体系结构的通常特征，选 A。

答案：A。

**基础：**同步流水线用统一时钟推动各段之间的数据传递。一个节拍结束时，各功能段都必须完成本段操作，否则慢的一段还未产生稳定结果，下一段就开始接收数据，会出错。因此时钟周期至少等于最长功能段的处理时间；若有段间寄存器开销，还需再加相应延迟，本题明确忽略该开销。

四段耗时为 90、80、70、60 ns，故 $T_{\rm clk}\ge\max(90,80,70,60)=90$ ns，选 A。B 的 80 ns、C 的 70 ns、D 的 60 ns 都无法容纳 90 ns 的功能段。不要把四段相加的 300 ns 当作流水线时钟周期：300 ns 是单条指令依次经过各段的处理时间总和，流水线不同指令可以在不同段重叠执行。

答案：D。

**基础：**控制器负责按指令和当前状态产生寄存器读写、ALU 操作、访存等控制信号。硬布线控制器用组合逻辑和时序逻辑直接实现这些关系，信号无需逐条读取微指令，通常控制速度较快。但指令功能与电路结构紧密关联，修改或扩展指令常需重新设计逻辑，比较困难。

微程序控制器则把控制步骤存放在控制存储器中，执行时读取微指令；修改微程序通常比改电路容易，但有读取和解释微指令的开销。于是本题应选“速度快、修改扩展难”的 D。A、B 都把硬布线速度说成慢，C 把修改扩展说成容易。这里比较的是两种控制方式的典型特征，并非仅由某台机器的主频作判断。

答案：B。

**步骤：**带宽表示单位时间内传输的数据量，必须先区分时钟周期与总线传输周期。时钟频率为 $10\mathrm{MHz}=10^7$ 次/s，一个总线周期占 2 个时钟周期，所以每秒只有 $10^7/2=5\times10^6$ 次传输。

每次并行传 4 B，故总线带宽为 $5\times10^6\times4=2\times10^7$ B/s。本题传输率采用十进制单位 $1\mathrm{MB}=10^6\mathrm B$，结果为 20 MB/s，选 B。A 的 10 MB/s 少计了数据量；C 的 40 MB/s 相当于忽略“每次占两个时钟周期”；D 的 80 MB/s 也不符合给出的周期。另一个算法是时钟周期 100 ns、总线周期 200 ns，直接算 $4\mathrm B/200\mathrm{ns}$，结果相同。

答案：D。

**基础：**Cache 命中表示所需数据已经在 Cache 中，未命中表示要从下一层存储器取得它。命中率的分母是总访问次数，分子是命中的次数；未命中率则是未命中次数除以总访问次数，两者相加为 1。

总共访存 1000 次，未命中 50 次，因此命中次数为 $1000-50=950$，命中率 $h=950/1000=0.95=95\%$，选 D。A 的 5% 是 $50/1000$，算出了未命中率；B 的 9.5% 把小数转为百分数时少乘了 10；C 的 50% 与“50 次”这个次数混淆，没有正确除以总次数。该题只求事件比例，不需要 Cache 与主存的访问时间，不能把命中率与平均访存时间混在一起。

答案：A。

**基础：**外部中断来自 CPU 当前执行指令之外的事件，例如 I/O 设备完成操作、时钟到时；内部异常则由当前指令执行中出现的情况引起。判断依据是事件来源，而不是操作系统是否参与处理。

A 键盘输入由键盘控制器等外部设备提出服务请求，属于外部中断，正确。B 除数为 0 是 CPU 执行除法时检测到的算术异常；C 浮点下溢是浮点运算结果超出可表示范围而引起的内部异常；D 访存缺页由当前指令访问的虚拟页面不在内存而触发，也属于内部异常。后三种事件即使最终交给操作系统的处理程序，也不会因此变成外部中断。所以选 A。

答案：D。

基础：“并发”指多个活动在一段时间内交替推进，“并行”强调在同一时刻真正同时进行。单处理机系统只有一个 CPU，同一时刻只能执行一个进程的指令流，多个进程通过切换实现并发，所以 I 不属于本题的可并行情况。

设备启动后可独立进行 I/O，CPU 同时执行计算，II 正确。通道是能独立控制 I/O 的部件，CPU 启动通道后双方可同时工作，III 正确。不同设备也可分别执行各自操作，例如磁盘传输时打印机仍可打印，IV 正确。于是选择 II、III、IV，即 D。A、B、C 都包含错误的 I，且分别漏掉 IV、III、II。不要把用户看到多个程序“同时运行”的表象等同于多个进程同时占用单个 CPU。

答案：D。

**基础：**高响应比优先为每个就绪进程计算响应比 $R=(W+S)/S=1+W/S$，其中 W 是已经等待的时间，S 是预计执行所需的服务时间。每次选择 R 最大的进程，因此它同时利用了等待时间和执行时间，选 D。

例如两个进程都等待 10 个时间单位，服务时间分别为 2、5，其响应比分别为 6、3，较短进程较有优势；一个长进程等待不断增加，其响应比也会升高，有助于避免长期饥饿。A 时间片轮转按队列次序分配时间片，不计算这两项的综合指标；B 短进程优先主要比较服务时间；C 先来先服务主要比较到达先后。只有 D 的决策公式明确综合了两类时间，注意响应比越高越优先。

答案：C。

**思路：**要形成死锁，每个参与进程都尚未拿到其所需的全部资源，又占着已有资源等待。每个进程最多需 3 台，所以一个尚不能完成的进程最多已经占有 2 台。最危险的状态是所有进程都各占 2 台、各等待第 3 台。

若 K=2 或 3，未完成进程至多占有 $2K\le6$ 台，8 台中仍有空闲打印机，至少能满足一个进程的最后一台需求；它完成后释放打印机，其他进程也能继续。因此 A、B 不可能是所求最小值。K=4 时可恰好各占 2 台，把 8 台全部占完，每个再请求 1 台，所有进程都无法完成，可能死锁。K=5 也可能死锁，但不是最少，故选 C。题目问“可能”，并非 4 个进程必然死锁。

答案：A。

**基础：**分区分配把内存的一段连续区域分给某个进程。主要保护目标是让它只能访问自己的分区，防止越界破坏操作系统或其他进程的数据，因此采用界地址保护，选 A。

一种实现是用基址寄存器记录分区起点，用限长寄存器记录分区长度。对逻辑地址 d，先检查 $0\le d<\text{限长}$，合法时才形成“基址+d”的物理地址；也可用上下界寄存器检查物理地址是否在许可区间。越界则产生异常。B 程序代码保护、C 数据保护、D 栈保护分别针对程序中的某类内容，但不能概括分区分配隔离整个进程地址范围的主要机制。易错点是界限检查由硬件在访存时执行，不能仅靠程序自觉遵守。

答案：C。

**基础：**分段系统的逻辑地址由“段号、段内偏移”两部分组成。段号用来选段表项，偏移用来定位该段中的具体字节。最大段长取决于偏移字段的位数，而不是段号能表示多少段。

地址总长 32 位，段号占 8 位，所以段内偏移占 $32-8=24$ 位，取值从 0 到 $2^{24}-1$。按本题选项的字节编址口径，这些偏移可定位 $2^{24}$ 个字节，最大段长为 $2^{24}$ B，即 16 MiB，选 C。A 的 $2^8$ 是可表示的段号数；B 的 $2^{16}$ 没有对应的字段；D 的 $2^{32}$ 把整个地址都当成了偏移。注意最大偏移是 $2^{24}-1$，段的最大长度则是 $2^{24}$。

答案：B。

**思路：**题目要求同时具备“随机访问快”和“扩展容易”两个特点。索引结构为文件建立索引表，记录每个逻辑块对应的磁盘块地址。访问第 i 块时可查相应索引项，不必逐块寻找；扩展时可分配任意空闲数据块并增加索引项，无需保持数据块连续，故选 B。

A 连续结构可以按起始块号和偏移直接定位，适合随机访问，但文件后面的磁盘空间若已被占用，扩展可能需要搬移整文件。C、D 都是链式结构，数据块通过指针串联；查找后部某块通常必须从前向后沿链走，随机访问效率差。磁盘块定长或变长不会消除“必须沿链定位”的问题。索引本身会占空间，但它解决了本题要兼顾的两项要求。

答案：A。

**基础：**SCAN 像电梯一样沿当前方向移动，先服务该方向途中的请求，到端点后再反向，不会每完成一个请求就重新选择最近磁道。磁头在 105 道，当前向大编号方向移动，所以先把大于 105 的请求按升序排为 110、170、180、195。

反向后再把小于 105 的请求按降序服务：68、45、35、12。完整请求服务次序与 A 一致。B 在 110 后马上反向，违反当前扫描方向；C 在反向后先取最小的 12，再向上服务，近似循环扫描的服务顺序；D 忽略了磁头当前位置和初始方向。题目未给磁盘端点，因此只写请求被服务的次序；SCAN 到端点的空走不会改变上述请求顺序。

答案：A。

**基础：**文件访问控制信息包括哪些用户可读、可写、可执行等权限，它属于某个文件自身的管理属性。文件控制块 FCB 保存文件名、位置、长度、所有者和权限等元数据；使用索引结点的系统通常把这些属性放在 inode 中。系统找到文件的管理记录后即可检查访问权限，所以选 A。

B 文件分配表主要记录磁盘块的占用和文件块之间的连接关系，用于定位数据，不适合保存逐文件的访问权限。C 用户口令表用于验证用户身份，只能回答“你是谁”，不能独立决定“你可对这个文件做什么”。D 系统注册表主要是某些系统的配置存储机制，不是文件系统通用的权限保存位置。身份认证与文件授权作用不同，不能混淆。

答案：B。

**基础：**硬链接是另一个目录项直接指向同一个索引结点，因此增加原文件的引用计数；软链接是独立的文件，内容保存目标路径，有自己的索引结点，通常不增加目标文件的引用计数。

最初 F1 的计数为 1。建立 F2 后，F2 自身计数为 1，F1 仍为 1；建立 F3 后，F1、F3 共同指向的索引结点计数增为 2；删除名字 F1 后，它的目录项消失，该索引结点计数减为 1，F3 仍能访问原数据。F2 的文件没有被删除，计数仍为 1，但它保存的 F1 路径失效，成为悬空软链接。因此 F2、F3 为 1、1，选 B。A 把目标失效当成 F2 被删除；C 未减去被删的硬链接；D 混淆了两类链接。

答案：A。

**基础：**设备独立性要求应用程序尽量不依赖具体硬件。程序使用逻辑设备名打开设备，操作系统再根据映射关系找到实际物理设备及其驱动程序。例如程序请求一个逻辑打印设备，系统可把请求映射到当前可用的打印机，替换硬件时应用程序不必重新编写。

所以通常使用 A“逻辑设备名”。B 的物理设备名直接关联某台具体设备，不体现这种抽象。C 主设备号、D 从设备号是某些系统在设备管理中使用的内部标识：主设备号通常选择驱动类别，从设备号通常区分同类设备实例；应用打开设备时通常给出逻辑名称，由系统完成这些内部转换。题目问的是程序员在系统调用接口上使用的标识，而不是驱动层的内部编号。

答案：B。

**基础：**OSI 自下而上依次为物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。低层负责让数据经过链路和网络，传输层在此基础上把服务交给通信两端的进程，是第一个提供端到端服务的层次，选 B。

A 数据链路层的直接服务范围是相邻结点，一条经过多个路由器的路径会经历多个链路层帧的接收与重新封装。网络层负责主机间的分组传送，而传输层进一步处理端进程的通信和复用等问题。C 会话层、D 应用层位于传输层之上，也涉及端系统间的活动，但它们不是自下而上的“第一个”。不要把相邻结点的可靠传输与从源进程到目标进程的端到端服务等同。

答案：B。

**基础：**无噪声、带宽受限信道使用奈奎斯特公式 $R_{\max}=2B\log_2 M$。B 是带宽（Hz），M 是不同的信号状态数；$2B$ 给出最大码元率，每个码元可编码 $\log_2 M$ 个比特。题目强调无噪声，因此不用引入需要信噪比的香农公式。

QAM 同时利用相位和振幅。4 个相位、每个相位 4 种振幅，共有 $M=4\times4=16$ 种状态，每码元携带 4 bit。带宽 $3\mathrm{kHz}=3000\mathrm{Hz}$，于是 $R_{\max}=2\times3000\times4=24000$ bit/s=24 kbps，选 B。A 的 12 kbps 只按 4 种状态计算；C、D 的 48、96 kbps 都超过本题参数代入后的上限。信号状态数应相乘，不能把相位数与振幅数相加。

答案：C。

**基础：**GBN 的接收方通常只按顺序接收帧，并使用累计确认：确认 k 号帧表示 k 及其之前的帧都已正确收到。因此发送方虽未单独收到 1 号帧的确认，只要收到 2 号、3 号确认，就知道 0～3 都已确认，不能把“缺少 ACK1”误判为必须重发 1 号帧。

发送方已经发出 0～7，最新累计确认到 3，尚未确认的是 4、5、6、7。GBN 超时时要从最早未确认帧开始，把后面的未确认帧全部重发，所以共重发 $7-4+1=4$ 帧，选 C。A 的 2、B 的 3 少算了未确认帧；D 的 5 通常是把 1 号也错误加入重发集合。若采用选择重传协议才会按单帧确认处理，本题明确是 GBN。

答案：A。

**基础：**普通以太网交换机工作在数据链路层，收到的协议数据单元 PDU 是以太网帧。它查看帧的目的 MAC 地址，在转发表中查找该地址对应的端口并决定从哪里转发；若目的地址未知，则在相应范围内泛洪。因此转发决策使用目的物理地址，选 A。

C 源物理地址也会被交换机读取，但主要用于学习“这个发送者位于哪个端口”，更新转发表，不能用它代替目的地址决定转发方向。B 目的 IP 地址用于路由器等网络层设备的分组转发；D 源 IP 地址也不是普通交换机的转发查表依据。物理地址在这里就是 MAC 地址，不能因帧内承载 IP 分组就把交换机的查表层次提升到网络层。

答案：D。

**基础：**CSMA/CD 要求发送站在发送期间仍能检测到最远端引起的碰撞，所以最小帧发送时间必须不小于往返传播时间：$L_{\min}/R\ge2d/v$。R 为传输速率，v 为信号传播速度，d 为最远站点距离；往返系数 2 是本题关键。

减少 800 bit，在 $R=10^9$ bit/s 下，最小发送时间减少 $800/10^9=0.8\,\mu s$。要保持上述关系，单程传播时间至少减少一半，即 $0.4\,\mu s$。$v=200000$ km/s=$2\times10^8$ m/s，所以距离至少减少 $2\times10^8\times0.4\times10^{-6}=80$ m，选 D。A、B 的增加方向错误；C 的 160 m 忽略了往返传播的系数 2。

答案：D。

**基础：**TCP 对数据按字节编号。一个段的序列号是该段第一个数据字节的编号；确认号表示接收方下一次期望收到的字节编号，也表示该编号之前的数据已经连续收到。它不是已经收到了多少字节，也不是最后一个字节的编号。

第一个段从 200 开始，载荷 300 B，覆盖 200～499；第二个连续段从 500 开始，载荷 500 B，覆盖 500～999。两个段都正确收到后，下一字节应为 1000，所以确认号是 $200+300+500=1000$，选 D。A 的 500 只确认到第一个段；B 的 700 只加了第二段长度；C 的 800 是两个载荷长度之和，漏加起始序列号 200。题中是已建立连接后的数据段，没有需要额外计数的 SYN 或 FIN。

答案：C。

**基础：**按题目采用的经典 TCP 拥塞控制口径，超时被视为严重拥塞：慢开始阈值 ssthresh 设为原拥塞窗口的一半，cwnd 回到 1 个最大报文段 MSS。MSS=1 KB，所以阈值为 8 KB，新的初始窗口为 1 KB。

阈值以下执行慢开始，每轮 RTT 成功确认后窗口约翻倍；达到阈值后执行拥塞避免，每轮约增加 1 MSS。四轮变化如下：

因此选 C。A 的 7 KB 未按慢开始增长，B 的 8 KB 少计了一轮，D 的 16 KB 在达到阈值后仍继续翻倍。超时恢复与收到三个重复确认后的恢复处理不能混用。

答案：A。

**基础：**FTP 使用两个用途不同的 TCP 连接。控制连接负责用户登录、文件操作命令和服务器应答，通常在会话期间持续存在；数据连接负责实际文件内容或目录列表的传输。题目问的是“传递 FTP 命令”，因此使用建立在 TCP 之上的控制连接，选 A。

B 虽正确使用 TCP，但数据连接承载的是传输内容，不承载题目所问的控制命令。C、D 都把 FTP 的传输层协议误写成 UDP；FTP 需要利用 TCP 提供的可靠字节流服务。判断时要把“使用什么传输层协议”与“是哪一种 FTP 连接”两项分别核对。客户端发送下载命令与服务器随后传输文件是两个阶段，前者走控制连接，后者走数据连接。

**结论：**该方法不能保证求得最短路径。最短路径要最小化从起点到终点的边权总和，而题中方法只选择当前顶点附近最短的一条边；眼前最短的选择，可能把后续路径带到代价很大的地方。

**反例：**构造三个顶点 A、B、C 的无向图，起点为 A、终点为 C，边权如下，所有权值都非负，也确实存在到目标的路径。

按给定步骤执行：初始路径只有 A；在 A 的未入路径邻接点中，B 的距离 1 小于 C 的距离 2，所以选 B，路径成为 A—B。当前顶点改为 B，此时 A 已在路径中，不再考虑，剩下的候选点 C 通过权 10 的边加入。算法到达 C 后结束，所得路径为 A—B—C，长度 $1+10=11$。

但直接路径 A—C 的长度只有 2。此图从 A 到 C 的简单路径只有 A—C 和 A—B—C，故最短长度为 2，严格小于算法所得的 11，已经足以否定它对所有图都正确。不能因为权值非负就认为任意贪心选择都成立；需要比较从起点出发的累计距离并维护合适的候选状态，不能只比较当前边长。

**（1）基本思想。**链表只能沿 link 向后访问，不能从尾部反向数。可以设置 fast、slow 两个指针，让 fast 先走 k 步，再让二者同步移动，始终保持 k 步距离。fast 到达空指针时，slow 后面连同自身恰好还有 k 个结点，因此 slow 指向倒数第 k 个结点。这个方法不需要保存所有结点，也不需要先计算长度再重新遍历。

**（2）实现步骤。**list 指向不存放有效数据的表头结点，所以两个指针从 list->link 开始。先让 fast 前移 k 次，每次移动前检查是否为空；如果提前为空，说明链表少于 k 个数据结点，直接返回 0。成功建立间隔后，fast、slow 每次各前移一步，直到 fast 为空。输出 slow->data 并返回 1。

例如数据链为 10→20→30→40→50，k=2，fast 先从 10 移到 30，slow 留在 10；同步移动三次后 fast 为空、slow 指向 40，正是倒数第二项。

**（3）C 实现。**题设 k 为正整数，代码同时处理非法 k、空表和空头指针，失败时不输出数据。

#include <stdio.h>
typedef struct Node {
    int data;
    struct Node *link;
} Node;

int kth_from_end(Node *list, int k) {
    if (list == NULL || k <= 0) return 0;
    /* 跳过表头结点，从首个数据结点开始。 */
    Node *fast = list->link, *slow = list->link;
    for (int i = 0; i < k; ++i) {
        if (fast == NULL) return 0;  /* 数据结点数不足 k。 */
        fast = fast->link;
    }
    while (fast != NULL) {  /* 保持 fast 比 slow 领先 k 步。 */
        fast = fast->link;
        slow = slow->link;
    }
    printf("%d\n", slow->data);
    return 1;
}

**正确性与复杂度。**设共有 n 个数据结点，建立间隔后 fast 再移动 $n-k$ 步到空，slow 也移动 $n-k$ 步，停在正数第 $n-k+1$ 个结点，也就是倒数第 k 个。k=1 时得到尾结点，k=n 时得到首元结点，k>n 或空表时返回 0。每个指针至多走 n 步，时间复杂度为 $O(n)$，只使用两个指针和循环变量，额外空间为 $O(1)$，没有改变任何 data 或 link。

**基础与单位。**CPU 用于 I/O 的时间比例可用“每秒处理 I/O 消耗的 CPU 周期数÷CPU 每秒总周期数”计算。CPU 主频为 $500\mathrm{MHz}=5\times10^8$ 周期/s，CPI=5 表示每条指令平均用 5 个周期。传输率按十进制单位换算，$1\mathrm{MB}=10^6\mathrm B$。

**（1）中断方式。**每次传输单位为 32 bit，即 $32/8=4$ B，所以每秒中断次数为 $0.5\times10^6/4=125000$ 次。一次中断有 18 条服务指令，另有相当于 2 条指令的开销，总周期数为 $(18+2)\times5=100$。于是每秒 I/O 占用 $125000\times100=1.25\times10^7$ 个 CPU 周期，比例为

$$\frac{1.25\times10^7}{5\times10^8}\times100\%=2.5\%.$$

也可验算：时钟周期为 2 ns，一次中断占 200 ns；每秒累计 0.025 s，正好是 2.5%。

**（2）DMA 方式。**DMA 控制器直接完成数据块传送，CPU 只做每块的预处理和后处理。数据率为 $5\times10^6$ B/s，每块 5000 B，故每秒块数为 $5\times10^6/5000=1000$。题目给出的每块总开销已是 500 个时钟周期，不应再乘 CPI。每秒 CPU 开销为 $1000\times500=5\times10^5$ 周期，比例为

$$\frac{5\times10^5}{5\times10^8}\times100\%=0.1\%.$$

题设排除了 DMA 与 CPU 的访存冲突，因此不再计算 DMA 数据传送导致的 CPU 等待。DMA 传送整个数据块所需的时间，不等于 CPU 为此忙碌的时间。

先读懂操作数。(R1) 表示寄存器 R1 的内容，这里它是一个主存地址；((R1)) 才表示该地址中的数据。指令要求把 R0 的数据与该主存数据相加，并写回原主存单元。因此 R1 本身不需要更新，R0 也不作为结果寄存器。

**数据通路约束。**MAR 保存主存地址，MDR 在主存数据总线 DB 与 CPU 内总线之间暂存数据；A 保存 ALU 的一个输入，另一个输入来自内总线，运算结果先存 AC。内总线在同一节拍只能有一个数据源输出，不能同时让 R0out、MDRout 有效。下表沿“取地址→读操作数→暂存一项→相加→准备写数据→写内存”的顺序安排，表中未列的控制信号均为 0。

**逐步说明。**C5 的 R1out 把地址送到内总线，MARin 将其锁存。C6 用 MemR 发出主存读命令，读回的数据通过外部数据总线、MDRinE 进入 MDR。C7 再用 MDRout、Ain 将它转存 A。C8 由 R0out 提供另一个加数，Add 选择加法，ACin 保存结果。C9 把 AC 的结果经内总线送 MDR；C10 用 MDRoutE 把结果送外部数据总线，MemW 写入 MAR 指定的单元。MAR 输出始终使能且地址未改，保证写回原位置。

若希望缩短节拍，也可在 C6 主存读取的同时，用 R0out、Ain 把 R0 送 A；下一拍让 MDRout、Add、ACin 有效完成相加，再依次把 AC 送 MDR、写主存，共用 C5～C9。主存读经外部 DB，R0 装 A 经内总线，两条通路不冲突。这种安排与上表功能等价。

**基础：**P 操作申请一个资源，数量不足时阻塞；V 操作归还或增加一个资源，并唤醒相应等待者。需要同时控制“有无可用单元”“有无指定类型数据”和“同一时刻只有一个进程操作缓冲区”。

定义 mutex=1，为缓冲区互斥信号量；empty=N，为初始空单元数；odd=0、even=0，分别记录可供消费者申请的奇数、偶数数量。生产者只在有空单元时放数据，P2 只在有奇数时取数据，P3 只在有偶数时取数据。伪代码如下：

semaphore mutex = 1, empty = N, odd = 0, even = 0;

P1: while (true) {
    x = produce();
    P(empty); P(mutex);
    put(x);
    V(mutex);
    if (x % 2 == 1) V(odd); else V(even);
}

P2: while (true) {
    P(odd); P(mutex);
    x = getodd();
    V(mutex); V(empty);
    countodd();
}

P3: while (true) {
    P(even); P(mutex);
    x = geteven();
    V(mutex); V(empty);
    counteven();
}

**为什么顺序正确。**生产者先 P(empty) 预留空单元，再 P(mutex) 进入临界区；写入后释放互斥锁，并按 x 的奇偶性只通知一种消费者。消费者先 P(odd) 或 P(even) 预留自己要取的数据，再进入临界区；取出后释放锁并 V(empty)，让该空单元重新可用。三个进程的 put/get 都由同一个 mutex 保护，所以不会并发修改缓冲区。

数量条件的 P 必须放在 P(mutex) 前面。否则例如缓冲区满时生产者拿着 mutex 等 empty，消费者又需 mutex 才能取数，双方会僵持。produce、countodd、counteven 不访问共享缓冲区，可放在临界区外以缩短占锁时间。每次放入恰好增加一种数据计数，每次取出恰好释放一个空单元；N=1 时也成立。信号量机制保证同步和互斥，不要求生产者一定生成某种奇偶数。

**先拆地址。**页面大小为 $4\mathrm{KB}=4096\mathrm B=2^{12}\mathrm B=1000\mathrm H$，所以低 12 位，即最后 3 个十六进制数字，是页内偏移；其余高位是页号。

**（1）逐次访问时间。**初始页 0、2 在内存，TLB 为空；先查 TLB，未命中再读内存页表，找到页框后还要实际访问一次数据。

• 2362H：TLB 未命中耗 10 ns，查页表耗 100 ns，发现页 2 存在，再访问数据耗 100 ns，共 $10+100+100=210$ ns。查表后页 2 的映射加入 TLB，且页 2 成为最近使用页。
• 1565H：先查 TLB 与页表，耗 $10+100=110$ ns，发现页 1 不在内存。驻留集固定为 2 且采用局部淘汰，必须从该进程的页 0、2 中选一个；刚使用过页 2，所以 LRU 淘汰页 0，把页 1 装到页框 101H。缺页处理耗 $10^8$ ns，已包括页表与 TLB 更新。随后从原指令重执行，重新查 TLB 命中耗 10 ns，再读数据耗 100 ns。总计 $110+10^8+10+100=100000220$ ns。
• 25A5H：页 2 未被淘汰，其 TLB 表项仍可命中，故耗 $10+100=110$ ns。

不能把第二次访问只算作“检测缺页+缺页处理”：处理结束后尚需重新完成原来的数据访问。

**（2）物理地址。**页 1 使用被换出页 0 的页框 101H，页内偏移在转换时保持不变。物理地址为“页框号×页面大小+偏移”：

$$101\mathrm H\times1000\mathrm H+565\mathrm H=101565\mathrm H.$$

这里拼接的是页框号 101H 与 3 位十六进制偏移 565H，不能误用页 2 的页框 254H。

**（1）子网划分。**IPv4 子网一般不能把全 0 主机号（网络地址）和全 1 主机号（广播地址）分给普通主机，因此保留 h 位主机号时可用地址数为 $2^h-2$。$2^6-2=62<120$，而 $2^7-2=126\ge120$，每个子网至少保留 7 位主机号。

原 /24 有 8 位主机号，借最高的一位作子网号，就得到两个 /25，掩码为 255.255.255.128。划分如下：

每网 126 个可分配地址，即使从中给 R1 的局域网接口分配一个地址，也仍有 125 个地址可供其他主机使用，满足要求。

**（2）R1 路由表。**局域网 1、2 分别从 E1、E2 直接到达；域名服务器与互联网都要先把分组交给相邻路由器 R2，其下一跳是同链路上的 202.118.2.2，从 L0 发出。要求的四类路由为：

域名服务器是一台主机，使用 /32，即 255.255.255.255；互联网目的网络范围无法逐个列出，用 0.0.0.0/0 默认路由。路由器按最长前缀匹配选择：目的地址属于本地局域网时优先命中 /25，目的为 202.118.3.2 时优先命中 /32，其余目的才采用 /0。下一跳应写相邻路由器的地址，不能把远处服务器的地址当成互联网路由的下一跳。

**（3）R2 的聚合路由。**两个 /25 的前 24 位相同，且第 25 位分别是 0、1，恰好覆盖原来的 202.118.1.0/24。因此可合成一条 /24 路由，掩码为 255.255.255.0。R2 到这两个局域网都应先交给 R1，故下一跳为 202.118.2.1，出口为 R2 的 L0：

聚合减少了路由表项数，且所聚合的两个网络在本题中有相同下一跳，转发方向一致。