2010年计算机408真题

答案：D。

**思路：**栈只能弹出栈顶元素，而且本题额外禁止连续三次出栈。用“入”表示压栈、“出”表示弹栈，逐项构造操作即可判断，不应只检查普通的栈序列合法性。

A 可按：入 abcd，出 dc，入 e，出 eb，入 f，出 fa；B 可按：入 abc，出 cb，入 d，出 da，入 e、出 e，入 f、出 f；C 可按：入 ab、出 b，入 c、出 ca，入 de、出 e，入 f、出 fd。三种操作都没有连续三次出栈。D 要先出 a，再出 f，必须先把剩余 bcdef 全部压栈；f 弹出后已无新元素可入栈，只能连续弹出 e、d、c、b。这五次退栈无法插入一次进栈来打断，违反限制，故选 D。

答案：C。

**基础：**这是输出受限的双端队列：入队可选两端，出队只在固定一端进行。题目规定 a～e 全部入队后才出队，所以把允许出队的一端记为左端，最终队列从左到右就必须等于给定出队序列。

后入元素只能加在已有序列最左或最右。A 可先放 a，再把 b 放左端、cde 放右端，得到 bacde。B 可依次把 b 放 a 左边、c 放右边、d 放左边、e 放右边，得到 dbace。D 可依次把 bc 放左边、d 放右边、e 放左边，得到 ecbad。对 C 的 dbcae 逆向删除最后入队的元素：e 在右端，可删；d 在左端，可删；剩 bca 中 c 位于内部，不可能是当时最后从两端加入的元素。因此 C 不可能。

答案：D。

**基础：**后序遍历顺序为“左子树、右子树、根”。线索化只利用原来的空孩子指针：空左指针指向后序前驱，空右指针指向后序后继；原本存在的实线孩子关系必须保留。四图的实线形状相同：a 的左右孩子是 b、c，b 的右孩子是 d，因此后序序列为 d、b、c、a。

据此，d 是第一项，空左指针为 Null，空右指针应指向 b；b 的空左指针应指向 d；c 的空左、空右指针分别应指向 b、a。图 D 恰好满足这些线索。A 把 b 的前驱指向 a、d 的后继指向 c；B 把 b 的前驱写为 Null、c 的后继写为 Null；C 把 d 的后继指向 c、c 的后继写为 Null，均与上述序列不符，选 D。

答案：C。

**步骤：**先按二叉排序树规则找插入位置：$48>24$，进入右子树；$48<53$，进入左子树；$48>37$，所以插为 37 的右孩子。此时结点 24 的左子树高度为 1、右子树高度为 3，成为从新结点向上遇到的第一个失衡结点。

插入路径从 24 向右，再从 53 向左，属于 RL 型，需先对 53 右旋，再对 24 左旋。调整后 37 成为新根，左子树根为 24（其左孩子仍为 13），右子树根为 53（左右孩子分别为 48、90）。所以 37 的左、右孩子是 24、53，选 C。A 错把孙结点 13 当成直接左孩子；B 错把 48 当成直接右孩子；D 的 90 也是 53 的孩子，不是 37 的孩子。

答案：B。

**基础：**树中结点的“度”是它的孩子数，叶结点度为 0。把所有结点的孩子数相加，每条父子边恰好被统计一次，所以度数总和等于边数；一棵有 n 个结点的非空树恰有 n−1 条边。

题中边数为 $20\times4+10\times3+1\times2+10\times1=80+30+2+10=122$，因此总结点数为 $122+1=123$。非叶结点共 $20+10+1+10=41$ 个，叶结点数为 $123-41=82$，选 B。A 的 41 是非叶结点数，D 的 122 是边数，C 的 113 不满足结点数与边数关系。也可直接代入 $n_0=1+\sum_{i\ge1}(i-1)n_i=1+3\times20+2\times10+1=82$，度为 1 的结点不增加该式中的叶数贡献。

答案：A。

**基础：**哈夫曼构造每次选当前权值最小的两棵树合并，产生一个有两个孩子的新根，其权值为两者之和。它保证最小带权路径长度，不要求最后一层从左到右排满，所以“不一定是完全二叉树”，A 是错误项。

例如不同权值 1、2、4、8，依次合并为 3、7、15，最终一侧只有叶 8，另一侧还包含较深的 1、2，不符合完全二叉树形状。B 正确，因为每次合并恰有两个孩子，不会产生度为 1 的结点；C 正确，因为最初最小的两个权值首先合并，必成为兄弟。

D 也正确：设某层非叶结点权值为 u，下一层结点权值为 v。若后者是前者的孩子，v 不超过父权值；若不属于其子树，假设 v>u，互换两棵子树会使权 u 的整棵子树加深一层、权 v 的整棵子树变浅一层，带权路径长度变化为 u−v<0，违背哈夫曼树的最优性。所以必有 u≥v。不能把“每个非叶结点有两个孩子”误认为“完全二叉树”。

答案：C。

**思路：**题目要的是“任意分布这些边都保证连通”，不是“存在一个连通图”。因此应先找不连通图最多能有多少边，再多加一条。按无向简单图的通常约定，不计自环和重边。

要让不连通图边数尽量多，各连通分量内部应都是完全图，并把顶点尽量集中到一个分量。7 个顶点分成 6 个与 1 个时，最多有 $\binom62+\binom12=15$ 条边：6 个顶点两两相连，另一个是孤立点。其他拆分如 5+2 只有 $10+1=11$ 条边，更多分量只会减少上限。因此 16 条边已经不可能保持不连通，选 C。A 的 6 条边可构成连通树，却也可围绕部分顶点分布；B 的 15 有孤立点反例；D 的 21 是完全图边数，足够但不是最少。

答案：B。

**基础：**拓扑序列要求每条有向边的起点排在终点前面。图中边为 a→b、a→c、a→e、b→c、c→d、e→d。只有 a 初始入度为 0，所以 a 必须第一个；b 要在 c 前，c、e 都要在 d 前，因此 d 必须最后。

剩下只需在中间排列 b、c、e，满足 b 在 c 前。可逐一列出三种：a、b、c、e、d；a、b、e、c、d；a、e、b、c、d。等价地，b、c 的次序固定，e 可插在 b 前、b 与 c 之间、c 后，恰有 3 种。选 B。A 的 4 多算了违反 b→c 等约束的排列；C 的 2 漏掉一处合法插入；D 的 1 误以为所有顶点的次序都被确定。注意图中虽有 a→c，但它不会增加 b、c、e 的新约束。

答案：B。

**基础：**折半查找每次与区间中间元素比较，再把可能范围缩小到左半或右半；若元素不存在，必须一直缩小到空区间才可宣布失败。16 个元素不代表最多只比较 $\log_2 16=4$ 次，因为还可能留下最后一个候选元素需要比较。

用下标 0～15、中点向下取整，查找一个大于全部元素的关键字，依次比较下标 7、11、13、14、15，共 5 次，然后 low 超过 high，查找失败。一般最大次数为 $\lfloor\log_2 n\rfloor+1$，n=16 得 5，选 B。A 的 4 少计了最后一个单元素区间；C 的 6、D 的 7 超过折半判定树的最大比较深度。这里计的是与关键字的比较，退出循环的边界判断不再计为一次关键字比较。

答案：D。

**思路：**快速排序每次用枢轴划分出左右两个分区，再分别排序。左右分区形成的子问题已经由划分结果决定，先递归左边还是右边，或先处理较长还是较短的分区，都只是改变处理先后，不会让某个子问题消失，因此递归次数与分区处理顺序无关，选 D。

A 不对：初始数据的排列会影响枢轴位置。例如采用首元素作枢轴时，已排序数据可能反复形成长度 0 与 n−1 的分区，使递归链很深；较均衡的划分则形成较浅的递归树。B、C 把处理顺序与递归次数混淆。某些经过尾递归消除的实现先处理短分区，可降低同时占用的栈空间，但这不意味着普通递归快排的待处理子问题数会减少。要区分递归次数、递归深度和运行时间。

答案：A。

**步骤：**按从左到右扫描、相邻逆序就交换的冒泡排序模拟。第一趟中 2、12、16 已有序；遇到 88>5，交换为 2、12、16、5、88、10；再因 88>10 交换，得到题目的 2、12、16、5、10、88。第二趟把 16 依次与 5、10 交换，得到 2、12、5、10、16、88；第三趟把 12 移到 5、10 后面，得到 2、5、10、12、16、88。

三趟分别把当前最大值 88、16、12 固定在末尾，故 A 可能。B 希尔排序按间隔分组插入，不能解释这组逐趟相邻交换结果；C 二路归并第一趟应得到有序相邻对，末尾 10、88 虽有序，但中间 16、5 无序；D 基数排序按数位分配收集，第一趟结果不符合按个位排序的次序。

答案：D。

**基础：**CPU 执行时间可写为 $T=I\times\mathrm{CPI}\times T_{\rm clk}=I\times\mathrm{CPI}/f$，I 为执行的指令数，CPI 为每条指令平均周期数，f 为时钟频率。要缩短时间，可减少分子中的工作量或增加分母中的执行频率。

I 提高频率，在其他条件相同时缩短每个周期，能缩短时间；II 优化数据通路，例如减少操作所需节拍、缓解结构冲突，可降低 CPI，也能缩短时间；III 编译优化可消除冗余计算、减少指令数或采用更合适的指令，同样能缩短时间。三项都是可能有效的措施，选 D。A、B、C 各遗漏了一项。题目问“能”采取的优化方向，不要求在任何实际设计中它们都毫无代价地提高性能。

答案：B。

**基础：**8 位补码表示范围为 $-2^7\le x\le2^7-1$，即 −128～127。若十六进制最高位为 1，可把其无符号值减 256 得到有符号值：FEH=254−256=−2，F2H=242−256=−14，90H=144−256=−112，F8H=248−256=−8。

分别计算四个数学乘积：A 为 $(-2)\times(-14)=28$；B 为 $(-14)\times(-112)=1568$；C 为 $(-2)\times(-8)=16$；D 为 $(-14)\times(-8)=112$。只有 B 超过最大正数 127，所以存入 8 位寄存器时发生溢出，选 B。不能只看截断后低 8 位“还能装进寄存器”就认为无溢出；溢出的定义是完整数学结果无法由目标位宽正确表示。

答案：B。

**逐式判断：**IEEE 754 单精度有 24 位有效二进制精度，785 是很小的整数，可精确转换成 float，再转换回 int 仍为 785，I 为真。f 约为 1567.8，强制转 int 会向零截断成 1567，再转 float 得 1567.0，与原 f 不同，II 为假。

double 的有效精度与指数范围均包含 float 的全部有限值，f→double 可精确保留已有的浮点值，再转回 float 仍是同一值，III 为真。d 约为 $1.5\times10^{100}$，f 相对它太小，做 d+f 时 f 在对阶与舍入中丢失，结果仍为 d；再减 d 得 0，而 f 非 0，IV 为假。故仅 I、III 为真，选 B。A、C 含错误的 II，D 含错误的 IV。浮点运算不总满足实数代数中的抵消律。

答案：D。

**基础：**一片 2K×4 位芯片有 2K 个地址，但每个地址只有 4 位。要组成每地址 8 位的存储器，需两片并联作位扩展；这两片使用同一组地址，共同提供低 4 位与高 4 位。位扩展不会把地址范围变成 4K。

总共需 $8K/2K=4$ 组，每组覆盖 $2K=2048=0800\mathrm H$ 个连续地址。四组区间依次为 0000H～07FFH、0800H～0FFFH、1000H～17FFH、1800H～1FFFH。地址 0B1FH 落在第二组，组内偏移为 $0B1F\mathrm H-0800\mathrm H=031F\mathrm H$，故所在芯片映射范围的最小地址为 0800H，选 D。A 属于第一组，B、C 不是按 2K 容量对齐的组边界。

答案：A。

**逐项判断：**I 正确，通常的 RAM 断电后丢失信息，ROM 则可在断电后保存信息。II 也正确，“随机存取”指按地址直接访问任意单元，而不是必须顺序经过前面的单元；ROM 的只读性质不妨碍它随机读取。

III 错误，Cache 要随程序访存不断装入新块、更新内容，ROM 无法承担这种频繁改写的数据缓存；典型 Cache 使用 SRAM。IV 错误，DRAM 依靠电容电荷保存数据，需要刷新，但 SRAM 不需要，ROM 也不需要。于是仅 I、II 正确，选 A。B、D 包含错误的 III，C、D 包含错误的 IV。要区分随机访问、可读写、易失性与刷新这几个独立概念，“RAM”这个名称不等于“只有它可随机访问”。

答案：D。

**基础：**TLB 缓存当前有效的虚页到物理页框映射，Cache 缓存主存数据，Page 命中表示所访问页面已经在内存。系统换出页面时需使相应 TLB 表项失效，不能继续把旧映射当成有效转换。

A 的三者都未命中可以发生：页面未驻留，因而没有有效 TLB 映射，所需数据也不在 Cache。B 可以发生：映射没有留在 TLB 中，但页面仍在内存，查页表后所需数据恰好在 Cache。C 也可以发生：映射在 TLB 中，页面在内存，而所需主存块未装入 Cache。D 不可能，因为 TLB 命中已意味着存在有效的驻留页映射，与 Page 未命中矛盾，Cache 命中也不能挽救这个矛盾，故选 D。

答案：B。

基础：“程序员可见”指寄存器是体系结构层面可感知或影响的机器状态，不要求它一定像通用寄存器一样能用普通数据传送指令任意读写。PC 保存指令执行位置，转移、调用、返回等指令会改变它，汇编程序必须依赖它组织控制流，因此 PC 可见，选 B。

A 的 MAR 暂存内部访存地址，C 的 MDR 暂存内部读写数据，D 的 IR 暂存当前指令，这些通常由 CPU 内部控制信号驱动，汇编程序不能直接把它们当作操作数指定，属于实现层面的寄存器。不要因为 PC 的自动加 1 是硬件完成的，就认为它对程序员不可见；也不要因为 CPU 内部确实存在 MAR、MDR、IR，就认为指令集必须开放它们。

答案：A。

**基础：**流水线阻塞意味着某条指令暂时不能进入下一阶段，需要等待。数据旁路又称转发，它把前面指令已生成但尚未写回寄存器的结果，直接送给后面依赖该结果的指令，从而减少等待，是缓解阻塞的措施，A 本身不会引起阻塞。

B 数据相关可能使后一条指令在前一条结果产生前无法执行，例如紧接着使用一次加载的结果。C 条件转移的方向或目标尚未确定时，后续取指可能需要等待或在预测失败后清空，属于控制相关。D 资源冲突是两条指令同时需要同一硬件资源但不能同时使用，也可能暂停一条指令。因此本题选 A。转发不保证消除所有数据相关阻塞，但不能把用于解决相关问题的措施当成阻塞来源。

答案：D。

**思路：**每个选项要求“全部缩写都是总线标准”，只需找出混入的非总线项即可排除。D 中 ISA 为工业标准体系结构总线，EISA 为其扩展标准，PCI 为外围组件互连总线，PCI Express 为采用串行链路的互连标准，四项都符合，选 D。

A 虽有 PCI、USB、EISA，但 CRT 是阴极射线管，属于显示器相关技术，不是总线标准。B 中 ISA、VESA、EISA 可对应总线标准，但 CPI 是每条指令平均时钟周期数，是性能分析参数。C 中 RAM 是随机存取存储器，MIPS 通常表示每秒百万条指令的性能指标，均不能当作总线标准；SCSI 即使属于接口/总线标准，也不能让整个选项成立。遇到缩写题要核对所有项目，不能看到一两个熟悉总线名就选。

答案：A。

**基础：**需要区分中断响应阶段与中断服务程序阶段。中断响应时，硬件通常已关中断并保存断点（返回地址），然后进入服务程序；服务程序还要保存可能被自己改写的通用寄存器等现场。单级中断不允许服务期间嵌套新的中断，应在处理与恢复完成后再开中断。

所以服务程序依次执行 I 保护现场、V 处理中断事件、VI 恢复现场、II 开中断、VII 中断返回，选 A。B 把关中断列入程序又缺少恢复现场；C、D 把保存断点当成服务程序步骤，同时缺少完整的保护现场或开中断环节，不符合题目采用的处理流程。保存断点与保护现场不是同一件事：前者记录返回到哪条指令，后者保留原程序的寄存器工作状态。

答案：D。

**步骤：**每帧像素数为 $1600\times1200=1920000$，每像素 24 bit，所以一帧需 $1920000\times24=46080000$ bit。帧频 85 Hz 表示每秒读取 85 帧，屏幕刷新需带宽 $46080000\times85=3916800000$ bit/s，即 3916.8 Mbps。

题目规定显存总带宽只有 50% 用来刷新屏幕，设总带宽为 B，应满足 $0.5B\ge3916.8$ Mbps，故 $B\ge7833.6$ Mbps，约为 7834 Mbps，选 D。A、B、C 的数值都不足以满足刷新量及一半带宽的约束。尤其 24 的单位是“位”而非“字节”，若先换算成 3 B 算出字节率，最终仍须乘 8 才能与 Mbps 选项比较；剩余的 50% 带宽不能计入屏幕刷新可用量。

答案：A。

**基础：**应用程序在用户态运行，不能直接任意操作内核和硬件。当它需要创建进程、打开文件、读取设备等操作系统服务时，通过系统调用进入内核，由内核检查参数、权限并执行服务。因此操作系统直接提供给应用程序的编程接口是 A“系统调用”。

B 中断是 CPU 转入相应处理程序的事件和机制，可由设备产生，不等同于应用程序请求服务的一组接口。C 库函数是程序库提供的接口，有些库函数会封装系统调用，有些完全在用户态完成，例如部分数学函数，因此不能把库函数整体称为操作系统接口。D 原语通常指内核中实现特定操作、不能被打断的基本过程，并不直接开放给一般应用程序。系统调用可由库包装，但二者层次不同。

答案：C。

**基础：**进程是程序的一次执行活动，创建进程需要建立进程控制块、分配必要资源并加入系统管理。按题目采用的通常操作系统流程，用户登录成功需要创建其会话或命令解释等相关进程，I 会导致创建进程；启动一个新程序执行需要建立其运行实体，III 也会导致创建进程。

II 设备分配是为已经存在的进程提供 I/O 资源，改变的是资源占用关系，不需要另建进程，所以不属于创建进程的典型触发操作。因此仅 I、III 正确，选 C。A、B、D 都错误包含了 II；A、B 还各漏掉一项。判断时要区分“建立一个新的执行实体”与“给现有执行实体增加资源”，系统活动有变化并不必然表示创建了新进程。

答案：B。

**基础：**采用记录型计数信号量的通常定义，P 操作先减 1，若结果为负则阻塞申请者；V 操作增加 1 并在必要时唤醒等待者。信号量非负时表示剩余可用资源数，负数的绝对值表示等待进程数。

初值为 3 说明资源总共有 3 个，当前值为 1>0，意味着还有 1 个可申请资源、2 个已经分配；因为仍有资源可用，不存在因该信号量等待的进程，即 $M=1,N=0$，选 B。A 的“0、1”应对应资源耗尽且有等待者；C 的“1、2”把已经占用的 2 个资源误当作等待进程数；D 的“2、0”把已分配数当作可用数。初值减当前值在无等待时可表示已用数量，不能直接当作等待数量。

答案：A。

**思路：**动态优先级调度通常适当照顾等待较久或频繁进行 I/O 的进程，避免某个持续计算的进程长期占据处理机。进程用完一个完整时间片，说明它本次持续使用 CPU，可降低优先级，使其他就绪进程得到运行机会，A 是合理时机。

B 刚完成 I/O 的进程往往需尽快处理数据，适当提高或维持优先级有利于交互响应和 CPU、设备重叠工作。C 长期处于就绪队列的进程已等待很久，应通过老化等措施提高优先级，降低反而会加重饥饿。D 从就绪转为运行只是被调度的结果，尚未反映它此次占用了多少 CPU，不适合仅因状态转换而降级。题目问典型合理策略，具体系统的优先级数值方向虽可不同，“降低优先级”始终指减少被优先调度的机会。

答案：D。

**基础：**这段代码是两进程 Peterson 算法。flag[i]=TRUE 表示 Pi 想进入临界区；turn 指定当双方都想进入时，应优先让哪一方通过。若只有 P0 申请，flag[1] 为假，P0 无需等待，P1 同理。

若双方都申请，两个 flag 都为真，turn 最终只能为 0 或 1。turn=0 时 P1 的等待条件成立而 P0 可进入；turn=1 时相反，因此不能同时进入，互斥成立。进入者退出后把自己的 flag 清零，等待者即可通过；即使退出者立即再次申请，它也先把 turn 设为对方，使已等待的对方优先，因而不会被无限次越过，不会饥饿。按题目抽象的共享变量原子读写、顺序一致执行模型，选 D。A、B 否定互斥，C 错判饥饿；真实并行代码还需符合语言内存模型的同步保证。

答案：B。

**基础：**最佳适配每次选择“能够容纳申请量的最小空闲分区”，以尽量减少该次分配的剩余空间。它不等于把所有空闲空间合成一个分区，也不会跨越已占用区域合并。

释放后两个空闲区之间隔着仍占用的 30 MB，不能合并。8 MB 应选较小的 10 MB 分区，剩 2 MB；6 MB 不能装入 2 MB，只能选 15 MB，剩 9 MB。所以最大空闲分区为 9 MB，选 B。A 的 7 MB 对应先把 8 放入 15 的错误选择；C、D 是分配尚未完成时的旧空闲区大小。

答案：B。

**基础：**二级页表把完整页表拆成可装入一个页面的若干二级页表，页目录中的每一项指向一张二级页表。页内偏移只用于定位数据字节，不决定目录项数量；这里需算每张二级页表最多管理多少个逻辑页。

页面大小 $2^{10}$ B，页表项大小 2 B，所以一页最多存 $2^{10}/2=512=2^9$ 个页表项，能映射 512 个逻辑页。逻辑空间共有 $2^{16}$ 页，覆盖它至少需要 $2^{16}/2^9=2^7=128$ 张二级页表，也就需要 128 个页目录项，选 B。A 的 64 少一半；C 的 256、D 的 512 均不是最少数，其中 512 是单张二级页表的项数。相应逻辑地址可分为 7 位目录号、9 位页号、10 位页内偏移，共 26 位。

答案：C。

**基础：**直接地址项直接指向数据块；一级间接项指向一个保存数据块地址的索引块；二级间接项先指向一级索引地址的集合，再经下一层索引块到达数据块。磁盘块 256 B，每个地址项 4 B，所以一个索引块可存 $256/4=64$ 个地址。

4 个直接项可管理 4 个数据块；2 个一级间接项可管理 $2\times64=128$ 个数据块；1 个二级间接项可管理 $64\times64=4096$ 个数据块。总数据块数 $4+128+4096=4228$，最大文件数据长度为 $4228\times256=1082368$ B=$1057$ KB，选 C，其中 $1\mathrm{KB}=1024\mathrm B$。A 的 33 KB 只包含直接和一级间接部分；B 少算了二级间接覆盖量；D 大幅超过给定索引容量。索引块本身是管理开销，不计入文件的数据长度。

答案：C。

**基础：**当前工作目录为进程提供相对路径的查找起点。若文件经常位于某个目录下，先把它设为当前目录，再使用短的相对路径，就可以从该目录直接查找，而不必每次由根目录沿绝对路径逐层检索。因此主要目的为加快文件检索，选 C。

例如当前目录是 /home/u/work，打开 data.txt 可直接检索 work 中的目录项；使用绝对路径则要从根目录依次解析 home、u、work、data.txt。A 节省外存空间、B 节省内存空间不是设置查找起点的主要目标，目录和文件仍需存储。D 文件读写速度主要与数据块布局、磁盘/缓存性能等因素相关；当前目录帮助更快找到文件，但不会直接提高找到后的数据传输速度。文件检索与文件数据读写是两个阶段。

答案：B。

**思路：**键盘输入从硬件到应用层需要经过设备服务流程。按键产生输入信息后，键盘控制器通知 CPU，操作系统的键盘中断处理程序读取设备数据并存入输入缓冲区，后续上层程序再获取字符。因此首先获得键盘输入信息的是 B“中断处理程序”。

D 用户登录程序确实最终使用用户名与口令，但它处于设备处理之后，不是直接最先读取设备数据的程序。A 命令解释程序通常处理用户登录后输入的命令，也依赖系统提供的输入服务。C 系统调用服务程序可处理应用提出的读请求，却不能替代键盘输入到达时首先运行的设备中断处理。题目中的“本地”“通过键盘”和“首先”共同提示要从 I/O 设备事件的处理顺序判断，而不是只关注登录功能的执行者。

答案：C。

**基础：**网络体系结构描述网络功能如何分层，以及同层实体按哪些协议相互通信。它需要规定 A 网络层次、B 每层使用的协议、D 每层必须完成的功能，否则各系统无法知道职责如何划分、报文如何解释与交互。

C 协议的内部实现细节则不属于体系结构必须规定的内容。例如协议可以规定某种确认报文格式及发送时机，但一个实现用数组保存状态、另一个用链表保存状态，或采用不同语言、线程模型，只要外部行为遵守协议即可互通。因此本题选 C。理解时可区分协议的“可观察规则”与实现者的“内部做法”：前者需要统一，后者通常允许不同。网络分层的目的之一正是让不同实现能够通过相同接口和协议配合。

答案：C。

**步骤：**分组总长 1000 B，其中头部 20 B，所以每组承载文件数据 $1000-20=980$ B。文件共需 $980000/980=1000$ 个分组。每条链路速率为 $100\mathrm{Mbps}=10^8$ bit/s，发送一个完整分组需 $t=1000\times8/10^8=80\,\mu s=0.08$ ms。

图中最短路径是 H1→左上路由器→右上路由器→H2，共 3 段链路。“存储转发”要求路由器收完整组才能发送，因此第一组到 H2 要 3t；之后各链路可流水工作，每隔 t 又到达一组。总时间为 $3t+(1000-1)t=1002\times0.08=80.16$ ms，选 C。A 的 80 ms 只计一条链路发送全部分组，B 少计一个流水延迟，D 对应 4 段链路的较长路径。分组拆装和传播时延按题设忽略。

答案：D。

**基础：**RIP 用跳数度量到目的网络的距离，合法可达距离最多为 15，16 被保留表示“无穷大”，即不可达。邻居发来的距离矢量中 <net1,16> 是在通告 R2 当前认为 net1 不可达，而不是它有一条恰好 16 跳的可用路径。

R1 若尝试经 R2 到 net1，需要把邻居通告距离加 1；但对不可达值应继续按无穷大处理，不能把 17 当作更长的有效路由。所以能得出的结论是 D“R1 不能经过 R2 到达 net1”。A 无法从邻居通告推出 R2 经 R1 的路径；B 把 16 当成可达跳数；C 同样把不可达值加 1 后误当有效路由。D 只说明不能走 R2，并不排除 R1 通过另一个邻居到达 net1。

答案：C。

**基础：**按本题使用的历史 ICMP 报文分类，源点抑制报文用于网络拥塞时通知源主机降低发送速率。路由器缺少缓冲空间、因拥塞丢弃分组，可向原分组的源主机发出该报文，请它减少后续流量，故选 C。

A 路由重定向用于通知主机存在更合适的下一跳或路由，与因拥塞请求减速不同。B 目的不可达用于报告目的网络、主机、端口等无法到达，拥塞丢弃不等同于目的不可达。D 超时报文通常对应 IP 生存时间耗尽或分片重组超时，不是本题的拥塞原因。源点抑制属于已经弃用的历史机制，现代网络主要由传输层等机制处理拥塞，不应由这道历史试题推导出现代路由器仍应发送该报文。

答案：B。

**步骤：**最后一个掩码字节 248 的二进制为 11111000，前面三个字节均为 255，因此总共有 $24+5=29$ 个网络位，即 /29。原地址空间是 /24，所以从原来的 8 位主机号中借出 5 位作子网号，可得到 $2^5=32$ 个等长子网。

每个子网剩 3 位主机号，共有 $2^3=8$ 个地址，扣除网络地址和广播地址，可分配给普通主机的地址为 $8-2=6$ 个，选 B。A 的 32、8 没有扣除两个保留地址；C、D 把子网位与主机位的数量颠倒。第一个子网为 192.168.5.0/29，其可用地址 .1～.6、广播 .7；后续网络地址每次增加 8。子网数量按现行允许全 0、全 1 子网的口径不再减 2。

答案：D。

**基础：**广播域是一个广播帧能够扩散到的范围。普通路由器在网络层连接不同网络，不转发链路层广播帧，能把一个网络中的广播限制在其广播域内，从而抑制广播风暴向其他网络扩散，IV 正确。

I 中继器与 II 集线器工作在物理层，主要再生或转发信号，不检查广播地址，也不能划分广播域。III 普通网桥在链路层可以按目的 MAC 过滤单播、划分冲突域，但遇到广播帧仍会向其他端口转发，不能依靠它隔离广播域。于是只有 IV 符合，选 D。A 选了两个物理层设备；B、C 都误把网桥当成广播域边界。某些二层设备可配置额外的环路控制或广播限速功能，但题目比较的是这些设备的基本转发作用。

答案：A。

**基础：**TCP 发送窗口同时受拥塞窗口 cwnd 和接收方通告窗口 rwnd 约束，可在途的总字节数不超过两者的较小值。计算“还可发送”的量时，还须扣除已经发出但尚未确认的数据，不能把新的窗口全部当作空余空间。

甲连续发了两个最大段，每段 1000 B，共发 2000 B。收到第一个段的确认后，第一个段的 1000 B 退出在途集合，第二个段的 1000 B 仍未确认。通告 rwnd=2000 B，cwnd 原为 4000 B且此处没有拥塞事件，因此约束来自接收窗口，可再发送 $\min(\mathrm{cwnd},2000)-1000=1000$ B，选 A。B 的 2000 未扣除第二段；C 的 3000 只看拥塞窗口；D 的 4000 同时忽略接收窗口与在途数据。

答案：A。

**基础：**递归查询把“继续查出最终答案”的任务交给被询问服务器：它若不知道答案，就向下一层服务器代查，最后把结果逐级返回。迭代查询则可能只返回下一台应询问的服务器，让原查询者继续发新的请求。

按题目采用的递归链，用户主机向本地域名服务器发一条请求；本地没有缓存，向下一层域名服务器发一条递归请求，后续查询由收到请求的服务器继续承担，本地等待最终结果。因此用户主机、本地域名服务器各发一条请求，选 A。B 的“一条、多条”通常对应用户对本地递归、本地向外迭代的组合；C、D 都错误认为用户需要自行发送多次查询。这里统计的是这两台设备各自发出的请求数，不是整条递归链中所有服务器请求的总数。

**（1）构造散列表。**装填因子 $\alpha=n/m$，n 为已有关键字数、m 为表长。本题 $n=7,\alpha=0.7$，故 $m=7/0.7=10$，数组下标为 0～9。注意散列函数仍是题目指定的 $(3\times\mathrm{key})\bmod7$，不能把它改成 mod 10；只有线性探测到数组末尾后，回绕使用表长 10。

按给定顺序插入，初始散列地址分别为 0、3、6、5、5、6、0。地址已占用就试下一个单元，直到找到空单元：

最终散列表为：

**（2）平均查找长度。**查找成功时，从关键字的初始地址沿同一探测序列寻找，比较次数与表中插入探测次数一致。七个已存关键字被等概率查找时，

$$ASL_s=\frac{1+1+1+1+3+3+2}{7}=\frac{12}{7}\approx1.714.$$

查找失败时，要一直探测到空单元才知道关键字不存在，找到空单元的那一次也计入探测长度。由于散列函数 mod 7，初始地址只可能为 0～6，按这些散列地址等概率计算：

所以 $ASL_f=(3+2+1+2+1+5+4)/7=18/7\approx2.571$。虽然表长为 10，7～9 可以被冲突探测访问，但不能成为该散列函数的初始地址，因此失败查找平均的分母不能误用 10。

**（1）基本思想。**把数组分成 A、B 两段：A 是下标 0～p−1 的前 p 项，B 是下标 p～n−1 的后 n−p 项。循环左移的目标正是把 AB 变成 BA，且保持 A、B 各段内部原来的次序。

使用三次原地反转：先反转 A，再反转 B，得到 $A^{\rm R}B^{\rm R}$；最后反转整个数组，段的先后次序互换、各段内部又反转一次，于是得到 BA。反转时只需用一个临时变量不断交换两端元素。

例如 [1,2,3,4,5,6,7] 左移 p=3：前段反转后为 [3,2,1,4,5,6,7]；后段反转后为 [3,2,1,7,6,5,4]；整体反转后为 [4,5,6,7,1,2,3]，符合题意。

**（2）C 实现。**下标区间均为闭区间，循环中两个指针逐步向中间靠拢。

static void reverse(int r[], int left, int right) {
    while (left < right) {
        int t = r[left];
        r[left++] = r[right];
        r[right--] = t;
    }
}

void rotate_left(int r[], int n, int p) {
    /* 按题设，n > 1 且 0 < p < n。 */
    reverse(r, 0, p - 1);  /* 反转前 p 项 A。 */
    reverse(r, p, n - 1);  /* 反转后 n-p 项 B。 */
    reverse(r, 0, n - 1);  /* 整体反转，得到 BA。 */
}

**（3）正确性与复杂度。**前两次反转不改变两段中的元素集合，整体反转把 B 搬到前面、A 搬到后面，又将各段内部次序恢复，恰好得到 $(x_p,\ldots,x_{n-1},x_0,\ldots,x_{p-1})$。三次反转处理的区间长度之和为 $p+(n-p)+n=2n$，时间复杂度为 $O(n)$；只有一个交换临时变量及下标，额外空间为 $O(1)$。在一般数组上必须移动线性数量的元素，这一复杂度已足够高效。p=1 或 p=n−1 时某一段只有一个元素，反转循环不执行，算法仍正确。

**（1）字段容量与寄存器位数。**OP 占第 15～12 位，共 4 位，因此最多有 $2^4=16$ 种操作码，即 16 条不同指令。Rs、Rd 各占 3 位，可以指定 $2^3=8$ 个通用寄存器。

MAR 的宽度取决于地址数。主存容量为 $128\mathrm{KB}=2^{17}$ B，每个字为 16 bit=2 B，按字编址，共有 $2^{17}/2=2^{16}$ 个字地址，故 MAR 至少需 16 位。MDR 每次保存一个 16 位字，也至少需 16 位。不能因容量为 128 KB 就把按字编址的地址位数错算为 17 位。

**（2）相对转移范围。**相对寻址的有效目标是 $(PC)+(Rn)$，这里偏移量存于通用寄存器 Rn，而非指令中 3 位寄存器号字段。16 位补码偏移可取 −32768～32767，所以相对于执行转移时的 PC，目标位移范围为 $[PC-32768,PC+32767]$，单位是字地址。主存地址宽度也是 16 位，若按 16 位地址运算取低 16 位，偏移的 65536 种值可覆盖 0000H～FFFFH 的整个地址空间；超出边界的算术和按该地址宽度回绕解释。

**（3）编码与执行。**源操作数 (R4) 是寄存器间接寻址，Ms=001、Rs=100；目的 (R5)+ 是寄存器间接自增，Md=010、Rd=101。加法 OP=0010，将字段按题设从高到低拼接：

OP   | Ms  | Rs  | Md  | Rd
0010 | 001 | 100 | 010 | 101
= 0010 0011 0001 0101 = 2315H

R4 中的 1234H 是源地址，不是加数；R5 中的 5678H 是本次目的地址。先取源数据 $M[1234\mathrm H]=5678\mathrm H$，取目的原数据 $M[5678\mathrm H]=1234\mathrm H$，相加为 $5678\mathrm H+1234\mathrm H=68AC\mathrm H$，写回原目的地址 5678H。自增寻址在使用该地址后使 R5 增加一个字地址，得到 5679H，而不是增加 2。

所以由该加法与寻址操作改变的通用寄存器为 R5，改变的数据单元为 5678H；源寄存器与源数据均不改变。

（1）Cache 总容量。$256\mathrm{MB}=2^{28}$ B，按字节编址，因此主存地址为 28 位。每行 64 B=$2^6$ B，需要 6 位块内偏移；共 8 行=$2^3$ 行，直接映射需要 3 位行号；剩下的 $28-6-3=19$ 位为标记。地址结构为“19 位标记、3 位行号、6 位偏移”。

每行除 $64\times8=512$ bit 数据外，还需 19 bit 标记和 1 bit 有效位；有效位用于判断该行是否存有有效块，不能遗漏。按题意不计一致性及替换控制位，总容量为

$$8\times(512+19+1)=4256\mathrm{bit}=532\mathrm B.$$

其中纯数据容量为 512 B，另有 20 B 管理信息。

**（2）两个元素的映射。**int 占 4 B，二维数组按行优先存储，一行 256 项，因此

$$\operatorname{addr}(a[i][j])=320+(256i+j)\times4.$$

主存块号为 $\lfloor\operatorname{addr}/64\rfloor$，Cache 行号为“块号 mod 8”。

**（3）访问命中率及速度。**按数组尚未装入数据 Cache 的首次遍历口径分析，i、j、sum 都在寄存器中，指令与数据 Cache 又分离，因此只需统计对 a 的 65536 次数据访问。

程序 A 按行访问，与物理连续次序一致。首地址 $320=5\times64$ 恰好按块对齐，每个块含 $64/4=16$ 个 int；访问每块首项时未命中并装入整块，其后 15 项命中。共有 $65536/16=4096$ 次未命中，命中率为 $(65536-4096)/65536=15/16=93.75\%$。

程序 B 按列访问，相邻访问地址相差一行，即 $256\times4=1024$ B，相差 16 个主存块。16 是 Cache 行数 8 的倍数，因此同一列的各行元素映射到同一 Cache 行，后一个不断替换前一个。到下一列时，上一次保留的是最后一行的数据，又从第 0 行开始，仍全部冲突未命中，命中率为 0。

两个程序计算次数相同，而 A 利用了一次装入整块的空间局部性，减少了访主存次数，所以执行时间更短。题面未明确初始 Cache 内容，以上精确命中率采用通常的冷启动口径；已有初始缓存可能影响少量首次访问，不改变两种遍历的局部性比较。

**（1）空闲块管理。**使用位示图，每个磁盘块对应 1 bit。$16384=2^{14}$ 个块需要 16384 bit，即 $16384/8=2048$ B=2 KB，恰好符合内存限制。可约定 0 为空闲、1 为已分配。分配块时寻找一个 0 位并置 1，释放块时把对应位清 0；第 b 块对应第 $\lfloor b/8\rfloor$ 个字节中的第 $b\bmod8$ 位。位值约定也可反过来，但分配和释放必须一致。

**（2）读四个扇区的平均时间。**一次磁盘读取需要寻道、旋转等待和数据传输。本题按请求端点回绕的考试约定计算：沿磁道号增大的方向服务完当前方向上的请求后，直接回到最小待服务磁道，再继续向大号方向服务。访问次序是 100→120→30→50→90；从 120 回到 30 时不服务沿途请求，但磁头移动仍耗时。

相邻磁道平均移动 1 ms，所以寻道时间 $T_s=170\times1=170$ ms。转速 6000 转/min=100 转/s，一圈 $T_r=1/100$ s=10 ms。随机扇区平均需等待半圈，四次旋转等待共 $4\times10/2=20$ ms。每道 100 个扇区，读一个扇区传输时间 $10/100=0.1$ ms，四个共 0.4 ms。因此总平均时间为

$$T=T_s+T_{\rm rotation}+T_{\rm transfer}=170+20+0.4=190.4\mathrm{ms}.$$

随机分布的扇区位置使旋转等待采用平均值，不能确定每一次具体等待值。

**术语与适用范围。**题面把该策略称为 CSCAN，本题数值答案采用上面的请求端点回绕约定；这种行为在严格区分术语的教材中称为 C-LOOK。若某教材把 C-SCAN 定义为先走到物理最大磁道、再回到 0 号道，则需另给最大磁道号 T。该模型下寻道距离为 $(T-100)+T+90=2T-10$ 道，总平均时间为 $2T+10.4$ ms。这里说明两个定义的边界，本题作答采用请求端点模型，结果为 190.4 ms。

**（3）Flash 的调度。**在题设只考虑随机访问与调度开销的模型中，可以用先来先服务 FCFS。Flash 没有机械磁头，也没有盘片旋转，因此无需按磁道号排序来减少寻道和旋转等待。FCFS 按请求到达顺序处理，省去磁道排序及循环扫描管理的开销，也保证先到者先服务。实际设备还有内部并行、写入擦除等因素，但题设没有提供这些参数，不据此额外设计调度算法。

**（1）页号与偏移。**逻辑地址空间 64 KB=$2^{16}$ B，所以逻辑地址为 16 位。页面大小 1 KB=$2^{10}$ B=400H，低 10 位为页内偏移、高 6 位为页号。对 17CAH 作除法：

$$17CA\mathrm H=5\times400\mathrm H+3CA\mathrm H.$$

因此页号为 5，偏移为 3CAH（十进制 970，小于 1024）。当前只装入页 0～3，访问页 5 会缺页；它是该进程允许的六页 0～5 中的合法页面。

**（2）FIFO。**固定分配局部置换意味着只可从该进程已经分到的四个页框中选一个，不能临时增加页框。FIFO 看装入时刻，不看访问位：页 0、3、2、1 的装入时刻分别为 130、160、200、230，页 0 最早，应淘汰。把页 5 装入页 0 原占的页框 7，页内偏移不变，物理地址为

$$7\times400\mathrm H+3CA\mathrm H=1C00\mathrm H+3CA\mathrm H=1FCA\mathrm H.$$

**（3）CLOCK。**访问位为 1 表示近期访问过，扫描时给它第二次机会并清 0；访问位为 0 才立即作为替换对象。指针初始指向页框 2，按图顺时针依次为 2→4→7→9→2。

没有题设中的新访问插入扫描，第一圈把四个访问位全部清 0，第二圈首先遇到页框 2，于是页 5 放入该页框。物理地址为 $2\times400\mathrm H+3CA\mathrm H=0800\mathrm H+3CA\mathrm H=0BCA\mathrm H$。FIFO 与 CLOCK 得到不同结果，是因为前者按装入先后，后者按访问位与当前指针位置选择。

**（1）碰撞检测时间。**信号从甲到乙的单程传播时延为 $\tau=d/v=2/200000$ s=$10\,\mu s$。这里的传播时间只由距离和信号传播速度决定，不用数据发送速率 10 Mbps 来求。

以两台中较早开始发送的时刻为 0。若甲乙同时发送，它们的信号虽然在电缆中途更早相遇，但两端要在对方信号传播到本端时才检测到碰撞，所以两台均检测到冲突的最短时间是 $\tau=10\,\mu s$。

若乙在甲的信号即将到达前才开始发送，设乙开始时刻为 $\delta<\tau$，乙约在时刻 $\tau$ 检测到甲的信号，甲则需等到乙的信号在 $\delta+\tau$ 到达后才检测到。两台都检测完成的时刻为 $\delta+\tau$，当 $\delta$ 接近 $\tau$ 时接近 $2\tau=20\,\mu s$。因此通常以往返传播时延 20 μs 作为最坏情况上界。最短 10 μs，最长按题目计为 20 μs；不能把信号在电缆中途相遇的时间当成两端检测时间。

**（2）有效数据率。**题目采用停等方式，甲要发完整数据帧、等它传播到乙；乙收完整帧后立即发确认帧，再等确认传播回甲。一次周期只允许完成一个数据帧，因此时间组成如下：

标准最长以太网帧 1518 B 包含 14 B 首部、1500 B 有效载荷和 4 B 帧校验，因此有效数据只计 1500 B。按题设忽略前导码，并按收到后立即发送的规则计算，

$$R_{\rm effective}=\frac{1500\times8}{1.2856\times10^{-3}}\approx9.334\times10^6\mathrm{bit/s}=9.334\mathrm{Mbps}.$$

分母仍需包含首部、校验与确认帧的发送开销；若把 1518 B 全部计为有效数据，或省去确认发送与往返传播，就会高估有效数据率。