2015年计算机408真题

答案：A。

基础概念。 函数每开始一次调用，就把这次调用的参数、返回位置等信息放入一个栈帧。调用栈是“后调用的在上面”，返回时也先处理最上面的调用。

跟踪程序。

1. 首先执行 main，因此 main 的栈帧在栈底。
2. main 调用 S(1)，S(1) 的栈帧压在 main 上面。因为 $1>0$，还不能直接返回，需要计算 S(0)+1。
3. S(1) 再调用 S(0)，S(0) 的栈帧压到最上面。此时栈底到栈顶就是 main→S(1)→S(0)。
4. S(0) 返回 0 后才依次结束 S(1) 和 main。题目问的是调用过程中保存的信息次序，而不是返回次序。

所以选 A。B 把栈顶到栈底当成了所问方向，C、D 则改变了实际调用的先后关系。

答案：B。

思路。 先序遍历是“根、左子树、右子树”。先序标签 a、b、c、d 已固定，所以每一种二叉树形状都能唯一地按先序顺序填入这四个标签；只需数四个结点的不同形状。

设 $T_n$ 为 $n$ 个结点的二叉树形状数，空树也算一种，故 $T_0=1$。确定根后，左子树有 $i$ 个结点，右子树有 $n-1-i$ 个结点，得到

$$T_n=\sum_{i=0}^{n-1}T_iT_{n-1-i}.$$

先算出 $T_1=1$、$T_2=2$、$T_3=5$，于是

$$T_4=T_0T_3+T_1T_2+T_2T_1+T_3T_0=5+2+2+5=14.$$

因此选 B。也可用卡特兰数 $\frac1{5}\binom84=14$ 验算。不要再乘 $4!$：先序序列已经指定，结点标签不能任意排列。

答案：D。

判断依据。 哈夫曼树的每个内部结点权值等于两个孩子权值之和，构造时还必须每次合并当前最小的两个权值。满足“父等于子之和”只是必要条件，还要满足最小权合并规则。

• A：两条路径都经过权值 10，之后分别到叶子 5 和 7，要求它们相加为 10，但 $5+7=12$，矛盾。
• B：根的两个分支权值是 10 和 12，应有根权值 $10+12=22$，与 24 不符。
• C：权值 10 的结点若有权值 10 的孩子，另一个孩子只能为 0；权值 14 的另一个孩子为 3。即使容许零权叶子，0、3 也应先合并，不能先把 0、10 合成 10。
• D：可以取叶权 5、5、6、8，先合并 $5+5=10$，再合并 $6+8=14$，最后 $10+14=24$，恰好得到题给两条路径。

所以只有 D 能由哈夫曼合并过程产生。

答案：D。

先识别排序方向。 中序遍历依次访问左子树、根、右子树。现在中序结果是降序，因此这棵树采用“左边较大、右边较小”的排序规则，与常见的升序二叉搜索树方向相反。

考虑树中的最大关键字。如果它还有左子树，那么左子树中会有比它更大的关键字，与“它最大”矛盾，所以最大结点必定没有左子树，D 正确。

其余判断都用了过强的“一定”：

• A：只有一个结点或两个结点的 AVL 树，其根的度可以为 0 或 1。
• B：最小结点必须没有右子树，但仍可能有左孩子，因此不一定是叶子。
• C：新结点插入后可能引起旋转，最后插入的结点也可能被旋转为内部结点。例如依次插入 3、1、2，最后的 2 可以成为新根。

易错点是直接套用升序树“最大在最右”的结论，忽略题目的降序条件。

答案：D。

DFS 的关键。 深度优先遍历访问一个新顶点后，应先沿它的出边尽可能向深处走；只有没有未访问后继时才回退。邻接顶点的选择顺序可变，但不能任意打乱整段遍历。

从 $v_0$ 出发，第一步有三种选择：

合计 $1+2+2=5$ 种，选 D。特别地，0、1、2、3 不合法：访问 1 时还没有完成它的后继 3，不能先回去访问 2。

答案：C。

区分两种选边范围。 Kruskal 按全图边权从小到大选边，只要不成环就能选；Prim 从指定起点逐步扩大一个已连接顶点集合，每次必须选“集合内到集合外”的最小边。

图中唯一权值 5 的边为 $(V_1,V_4)$，因此两种算法第一步都选它。之后：

• Kruskal 的第二步可从权值 8 的边 $(V_1,V_3)$、$(V_2,V_3)$、$(V_3,V_4)$ 中任选一条，它们都不会与第一条边形成环。
• Prim 此时集合为 $\{V_1,V_4\}$。它的第二步只能选跨越这个集合边界的最小边，即 $(V_1,V_3)$ 或 $(V_3,V_4)$。
• $(V_2,V_3)$ 的两个端点都在集合外，不能把已有树接到新顶点，所以不能作为 Prim 的第二条边。

故选 C。A、D 都能成为 Prim 的第二条边，B 已在第一步选中。

答案：A。

折半查找的限制。 每比较一次，就丢弃一半区间，后面的比较关键字必须仍在尚未丢弃的区间内。因此可把之前比较的值转成目标关键字的上下界。

看 A 的 500→200→450→180：

1. 500 后出现较小的 200，说明目标小于 500，搜索转入左半区。
2. 200 后出现较大的 450，说明目标大于 200，搜索转入右半区。
3. 此时剩余区间内所有关键字都应大于 200；180 已在第二步被排除，不可能再次成为比较对象。

所以 A 不合法。B 可以依次向较小区间缩小；C 对目标依次给出“大于 180、小于 500、大于 200”的限制；D 也能不断缩小到 200 与 500 之间，三者均无矛盾。

不要把比较序列本身要求成单调序列，折半查找可以左右交替收缩。

答案：C。

本题的下标从 0 开始。 模式串为 abaabc，失配前已匹配的五个字符是 abaab；失配位置是主串和模式串的下标 5。

KMP 不让主串下标退回，而是利用已匹配部分的最长相同真前缀和真后缀来移动模式串。abaab 的真前缀为 a、ab、aba、abaa，真后缀为 b、ab、aab、baab，最长相同部分为 ab，长度为 2。

因此已经匹配成功的后缀 ab 可以直接与模式串开头的 ab 对齐，下一次从模式串下标 2 开始试配：

$$i=5,\qquad j=2.$$

选 C。A 把主串也退回，B 没有利用长度为 2 的匹配信息，D 则跳过了尚未比较成功的主串字符。易错点是把“长度 2”理解成模式下标 1，或把本题下标当成从 1 开始。

答案：C。

基础概念。 基数排序不是根据两个元素谁大谁小进行交换，而是逐位把元素放入对应桶，再按桶的顺序收集。设有 $n$ 个元素，关键字共有 $d$ 位，每一趟都必须处理全部 $n$ 个元素，趟数也是 $d$。

因此，不论最初已经有序、逆序还是杂乱，每一位的分配和收集都要进行，移动次数由 $n$、$d$ 及实现方式决定，与初始排列无关。

其余算法会受原始排列影响：

• 直接插入排序：有序时几乎不用后移元素，逆序时需要大量后移。
• 起泡排序：有序时不需要交换，逆序时会发生很多交换。
• 快速排序：划分过程中需要的交换、移动随元素分布而变化。

故选 C。题目问的是“元素移动次数”，不要把它和比较次数、最好时间复杂度混为一谈。

答案：C。

先画出调整位置。 小根堆的根最小。删除根 8 后，先把最后一个元素 12 移到根，再向下调整。剩余数组暂为 12、15、10、21、34、16。

按通常的小根堆下滤算法逐次统计：

1. 根的两个孩子为 15、10，先比较它们，选择较小的 10：第 1 次比较。
2. 再比较待调整值 12 与 10，因 $12>10$，把 10 提到根，12 下移到原来 10 的位置：第 2 次比较。
3. 此时 12 只有一个孩子 16，比较 $12<16$，堆序已满足，停止：第 3 次比较。

最终堆为 10、15、12、21、34、16，故选 C。下标越界判断、赋值和交换不是关键字比较，不计入题目所问次数；单孩子结点也不需要再做“两孩子选小者”的比较。

答案：A。

基础概念。 希尔排序先选一个增量 $d$，把下标相差 $d$ 的元素放在同一组，再分别把各组排好序。随后逐渐缩小增量，最后用 $d=1$ 完成整体排序。

它的标准组内操作是直接插入：从组的第二个元素开始，把当前元素与前面已经排好的元素比较，必要时将较大元素向后移动，再把当前元素放入适当位置。区别只在于移动步长是 $d$，并不是相邻下标的一格。

因此选 A。B 的折半插入需要另用折半定位插入位置；C 的快速排序使用枢轴划分；D 的归并排序把有序子序列合并，均不是希尔排序所采用的标准组内操作。

容易误解的是“希尔排序的组内元素不连续，所以不能用直接插入”。直接插入只需要能按组内顺序访问元素，元素在数组中不必相邻。

答案：A。

从处理器取指过程理解。 CPU 从存储器取出的是二进制指令字，按操作码译码，再控制寄存器、运算器和存储器完成规定操作。能够以这种形式直接取指执行的就是机器语言程序。

逐项判断：

• I 正确：机器语言由处理器支持的机器指令组成，能直接译码执行。
• II 错误：汇编语言使用指令助记符和符号地址，必须先由汇编器转换成机器代码，CPU 不能直接把源代码文字当作指令执行。
• III 错误：硬件描述语言描述电路结构或行为，可以经过综合、实现形成硬件，但其源程序不是普通 CPU 直接执行的机器指令序列。

所以只有 I 符合，选 A。不要因为汇编与机器指令关系很密切，就把“容易翻译成机器语言”和“硬件直接执行”当成同一件事。

答案：B。

使用补码的位权。 8 位补码最高位的权为 $-128$，其余位的权依次为 64、32、16、8、4、2、1。因此数值可写成

$$-128b_7+64b_6+\cdots+2b_1+b_0.$$

要使数最小，先把一个 1 放到符号位，获得 $-128$；余下两个 1 必须放在正权最低的两位，使增加的正数最少。因此编码是

$$10000011_2,\qquad -128+2+1=-125.$$

选 B。A 的 -126 编码为 10000010，只有两个 1，不满足条件；C 的 -32 虽可由 11100000 表示，但大于 -125；D 的 -3 编码含更多的 1，也不符合位数限制。

易错点是把补码按原码的“符号位加绝对值”解释。补码最高位具有负位权，不能先把后七位当成 3，再直接加负号得到 -3。

答案：D。

按浮点运算的几个阶段分别判断。

1. 对阶让较小的阶码向较大的阶码靠拢，同时把对应尾数右移。两操作数阶码本来都能表示，最终阶码取较大的已有值，不会在这一步产生阶码上溢或下溢。I 正确；尾数右移可能损失精度，是另一回事。
2. 尾数相加后若超过规格化范围，需要右规：尾数右移、阶码加一。舍入也可能使尾数进位而再次右规，阶码若已达上限，就可能上溢。II 正确。
3. 相减发生抵消时，尾数可能太小，需要左规：尾数左移、阶码减一。减到下限之外就可能下溢。III 正确。
4. 尾数产生进位并不自动表示浮点结果溢出；只要右规后阶码仍在范围内，结果依然可表示。IV 正确。

四项都成立，选 D。判断浮点溢出应看最终阶码和规格化结果，不能仅看到尾数最高位进位就认定整个结果溢出。

答案：C。

总容量包括数据和管理信息。 题目给出的 4K 字是数据容量，每字 32 位；还需要为每一行存储标记、有效位和回写用的脏位。

逐步计算：

1. 每块含 4 字，即 $4\times4=16$ B，块内偏移需要 $\log_2 16=4$ 位。
2. Cache 可存 4096 字，每行存 4 字，所以行数为 $4096/4=1024$，行号需要 10 位。
3. 地址共 32 位，直接映射标记长度为 $32-10-4=18$ 位。
4. 每行数据为 $4\times32=128$ 位，加 18 位标记、1 位有效位和1位脏位，共 148 位。

总容量为 $1024\times148=148$ Kbit，选 C。A 少算两个状态位，B 只算了其中一个；D 与正确的字段划分不符。直接映射每组只有一行，不需要额外的 LRU 替换状态位。

答案：B。

“至少”表示取最有利的命中情况。 这条指令要取指令、确定变量 x 的地址、读 x、加立即数 3，再把结果写回 x。题目已配置 TLB 和 Cache，各个读操作都可能不访问主存：

• 指令可在 Cache 命中。
• 虚拟地址转换可在 TLB 命中，不必去主存读页表。
• x 的旧值也可在 Cache 命中。
• 立即数 3 在指令中，不需要单独读一个存储单元。

但是 Cache 采用直写方式，更新 x 时必须同时更新主存，而不是只留在 Cache 中。因此即使全部读都命中，也至少有一次主存写入，选 B。

A 忽略直写规则；C、D 对应包含某些读缺失等较差情况，并不是最少次数。注意：TLB 命中解决的是地址翻译，Cache 命中解决的是指令或数据读取，两者作用不同。

答案：B。

先看存储信息所用的器件。 动态 RAM 用电容上的电荷表示数据，电荷会逐渐泄漏，因此即使没有读写请求，也必须周期性补充电荷，这就是刷新。

SDRAM 的全称是同步动态 RAM。“同步”表示它的操作配合时钟，不改变它属于动态 RAM 的事实，所以仍需要刷新，B 正确。

其他选项：

• SRAM 使用稳定的触发器电路保存位值，只要供电正常就能保持状态，不需要这种周期刷新。
• ROM 用于保存固定或较少改动的信息，不依靠会快速泄漏的动态存储电容。
• Flash 是非易失存储器，掉电后仍可保存信息，不需要 DRAM 式的周期刷新。

易错点是因为 SRAM 与 SDRAM 都含字母 S，就把它们都视作静态 RAM。SRAM 中的 S 是 static，SDRAM 中的 S 是 synchronous。

答案：D。

低位交叉编址。 四个存储体由地址最低两位选择，即地址对 4 取余。相邻地址通常落到不同存储体，可以在前一体尚未完成访问时启动后一体，形成交叉访问。

题给序列对应的存储体为：

最后的 8004、8000 连续访问同一个存储体 0，前一次访问可能尚未结束，因此会发生冲突，选 D。

B、C 的两个地址落到不同存储体。A 虽也属于体 0，但请求之间已隔开一轮交叉访问，并不是此序列中的相邻同体冲突。不能只检查“模4相同”，还要结合实际请求次序和存储体的忙闲情况。

答案：C。

同步与异步的区别。 同步总线用统一的时钟约定何时发送、采样和结束数据传输。不同设备可以有不同内部时钟，但不能各自用互不协调的时钟决定同一次总线传输，所以 C 错误，应选 C。

其余三项说明如下：

• A：全互锁要依次确认请求、应答及信号撤销，交互步骤最多，因而在几种异步握手方式中最慢。
• B：非互锁主要依靠预先估计的延迟，不完整确认对方状态；设备速度和延迟变化时较容易出错，可靠性最差。
• D：半同步把时钟控制和等待/握手结合起来，设备可要求等待，但对握手信号的判断仍在规定的时钟时刻进行。

本题问“错误”，不要看到 A 的“最慢”就误以为不合理。通信方式的速度和可靠性不同，全互锁的更多确认恰好用时间换取了更强的协调保障。

答案：B。

平均存取时间由三部分组成： 寻道时间、旋转等待时间、数据传输时间。7200 rpm 表示每分钟 7200 圈，因此一圈的时间为

$$T_{\mathrm{rot}}=\frac{60}{7200}\mathrm{s}=8.333\mathrm{ms}.$$

请求到达时目标扇区的位置可处于一圈内的任意位置，平均只需等待半圈，所以平均旋转等待为 $8.333/2=4.167$ ms。每圈有 1000 个扇区，读一个扇区约需 $8.333/1000=0.00833$ ms。

最后把题给寻道时间 8 ms 加入：

$$T_{\mathrm{avg}}=8+4.167+0.00833\approx12.175\mathrm{ms}\approx12.2\mathrm{ms}.$$

因此选 B。最常见的错误是把平均旋转等待按整圈计算，或完全漏掉旋转等待。传输时间很小，但应先列入公式，再根据数值判断能否近似忽略。

答案：B。

中断 I/O 的分工。 打印机准备好接收一个字符时通知 CPU，CPU 执行中断处理程序，再通过接口端口把字符交给打印机。因此 CPU 仍负责搬运每次的数据。

接口端口通常包括：

• 数据端口：接收要打印的字符，对应 A。
• 状态端口：报告忙、就绪、出错等状态，对应 C。
• 控制端口：接收启动、复位或允许中断等命令，对应 D。

B 的“主存地址”是 DMA 等直接搬运主存数据的方式常用的信息；中断方式下，打印接口不需要拿着主存地址自行取字符，所以本题选 B。

要区分“主存地址”和“端口地址”。CPU 访问接口时当然需要选择哪个端口，但选择 I/O 端口的地址，不等于把待打印数据的主存地址交给打印机。

答案：D。

三类异常的返回位置不同。

所以 D 把所有异常都说成“回到发生异常的指令继续执行”，错误，应选 D。

A、B 描述内部异常的来源与检测：它和当前指令相关，由 CPU 内部检测逻辑识别。

选项 C 的考试口径。 本题把“指令执行过程中”按广义的指令处理过程理解，强调异常与当前指令同步相关。因此按这一口径，C 不作为错误项。它不能被扩张成“所有异常一定在该指令尚未完成时报告”。具体报告时机仍须区分：fault 通常在指令未完成时发现，修复后重试；trap 在引发它的指令执行完成后报告，再从后续应执行的指令继续；abort 则不保证可靠恢复。这个严格时机区别不改变 D 将所有返回行为一概而论的错误。

例如，缺页后必须重试那次未完成的访存；执行完陷阱指令后却通常不能再反复执行它。分清这些例子，就能理解为何 D 不能一概而论。

答案：B。

为什么要保存现场？ 中断处理程序也会使用寄存器。如果把被中断程序的数据覆盖，返回后原程序就无法正确继续，因此要先保存，退出时再恢复。

在通常的中断响应过程里，硬件先保存返回所必需的信息，如 PC 的断点值和相关状态，使 CPU 能跳入中断入口。随后操作系统的软件处理程序把需要使用的通用寄存器内容压入内核栈，处理完成后再恢复。因此本题由操作系统保存的对象是 B。

C、D 不属于逐次中断要保存的通用寄存器现场：

• TLB 是地址转换缓存，可能按地址空间管理策略保留或失效，不是把整个快表当作进程寄存器逐项保存。
• Cache 由硬件维护，保存了主存内容的副本，也不需要每次中断都把全部内容备份。

A 是中断硬件首先需要记录的返回地址；B 才是本题区分的软件保存任务。

答案：C。

抓住“指令已装入指令寄存器”。 这排除了取这条指令时可能发生的缺页，只需看其执行动作会不会产生异常或主动陷入。

• A：DIV 做除法，若除数为 0 等，就会发生算术异常，需要进入异常处理。
• B：INT n 是软件中断指令，执行它就是主动请求进入中断或陷阱处理。
• C：NOT R0 只把寄存器 R0 中的每一位取反，不访存、不做除法，也不是特权操作；没有上述引发内核处理的条件。
• D：MOV 从内存地址 addr 取数据，可能因页面不在主存或访问权限问题产生异常，进入内核处理。

因此选 C。题目问“不可能”，不是问“正常执行时通常是否进入内核”。DIV 和 MOV 在正常条件下也可能不切换，但它们存在发生异常的可能。

答案：D。

先分清就绪和阻塞。 就绪态表示进程已具备运行条件，只是暂时没有 CPU；阻塞态表示它还缺少某个条件，如数据、资源或 I/O 完成，即使给 CPU 也不能继续所等待的动作。

被更高优先级进程抢占时，当前进程并没有失去内存或运行条件，只是 CPU 被调度给了别人，因此从执行态进入就绪态，D 正确。

其他选项不表示这种 CPU 调度造成的转移：

• 执行 P 操作若信号量条件满足，可以继续运行；若不满足，则等待而阻塞，不是就绪。
• 内存申请失败涉及资源条件，等待该资源时进入阻塞，或由程序处理失败返回，不是被抢占而就绪。
• 按通常的同步 I/O 过程，启动 I/O 后要等待完成，进入阻塞态。

可用一句话判断：只缺 CPU 是就绪；还在等别的条件是阻塞。

答案：B。

区分预防、避免和检测。 死锁预防直接破坏死锁的必要条件；死锁避免在每次分配前检查是否安全；死锁检测允许先运行，再判断有没有已经形成的死锁并处理它。

逐项判断：

1. I 错误。按统一顺序申请资源是死锁预防中破坏循环等待的方法，不是所有避免方法都必须施加的限制。
2. II 正确。典型避免方法如银行家算法，需要知道进程最大需求，才能估计剩余资源是否足以让进程依次完成；检测方法主要根据已有分配和当前请求检查，不要求事先声明最大总量。
3. III 正确。避免方法会拒绝可能把系统带入不安全状态的分配；检测方法可能先进行这样的分配，之后再检测是否真的出现死锁。

所以 II、III 正确，选 B。特别注意：不安全状态不等于已经死锁，但为了保证未来仍有安全完成顺序，避免策略也会拒绝不安全分配。

答案：A。

LRU 的规则。 淘汰的是当前内存中“距离上次访问最久”的页面。每访问一次页面，就把它更新为最近使用，不能仅根据第一次装入的时间判断。

下面按“最久未用→最近使用”记录四个页框中的页面：

下一次访问 7 时，它不在内存，需要换出最左边的 2，选 A。选项中的 3 已在访问 5 时被淘汰，不能再作为这次的牺牲页；4、8 的最近访问时间都比 2 更新。

答案：A。

缓冲区的作用。 磁盘按块传输，而程序可能一次只读写少量字节。先把数据暂存在内存，可以让多个小请求合并成一次磁盘访问，也可以重复利用已经读入的数据，减少真正需要访问磁盘的次数。

例如，程序逐字节读取一个 1KB 数据块时，不必每读一个字节都重新读磁盘；一次读入内存后，后续字节直接从缓冲区取得。所以主要目的对应 A。

其余选项：

• B：平均寻道时间与访问的磁道、调度等有关，缓冲区并不直接改变磁头运动速度。
• C：可靠性主要由校验、冗余、持久化等机制保证；仅把数据暂放在内存不自动提高磁盘可靠性。
• D：设备无关性主要由统一接口和 I/O 软件层次实现，不是设置缓冲区本身的主要目的。

注意不要把减少 I/O 次数与缩短每一次物理 I/O 的机械时间混淆。

答案：B。

先求文件内部的逻辑块号。 块大小 1KB=1024B，字节偏移除以 1024 取整就是从 0 开始的逻辑块号。一个索引块能存 $1024/4=256$ 个指针。

1. 偏移 1234 对应逻辑块 $\lfloor1234/1024\rfloor=1$，在直接索引覆盖的 0～9 号块内。索引结点已经在内存，只需读取一个数据块，访问 1 次。
2. 偏移 307400 对应逻辑块 300。直接索引加一级索引共覆盖 $10+256=266$ 块，即块号 0～265；300 已进入二级索引范围。
3. 找到该数据块要依次读二级索引块、它指向的一级索引块、最终数据块，共 3 次。

所以结果为 1、3，选 B。不要再额外读取索引结点，题目明确它已在内存；也不能把“二级索引”误理解成只读两个块，因为最终的数据块本身仍要读取。

答案：C。

两个维度分别表示什么？

• 固定/可变分配：进程获得的页框数量是否允许变化。
• 局部/全局置换：缺页时只能从本进程的页框中选牺牲页，还是可以选择其他进程的页框。

固定分配要求一个进程的页框数保持不变。全局置换却允许它把别的进程的页框拿来装自己的新页，这会增加自己的页框数、减少别人的页框数，与固定分配的定义冲突。因此 C 不能组合。

其他三种组合都有一致的含义：

• 可变+全局：缺页时可以从其他进程取得页框。
• 可变+局部：系统可调整分配量，但某次局部置换仍只在本进程页框中选择。
• 固定+局部：在本进程的固定页框集合中一换一，数量不变。

易错点是把“局部”误解成“永远不能调整页框数”，实际上它限制的是选择牺牲页的范围。

答案：C。

位图的一位对应一个磁盘块。 一个存放位图的盘块有 1024 字节，每字节 8 位，因此能够记录 $1024\times8=8192$ 个磁盘块的使用状态。要定位盘块 409612 对应的位，逐级做除法即可。

1. 在整个位图中，它位于第 $\lfloor409612/8192\rfloor=50$ 个位图盘块，块内余数为 $409612-50\times8192=12$。
2. 位图不是从物理块 0 开始，而是从块 32 开始存放，所以物理盘块号为 $32+50=82$。
3. 块内第 12 位所在的字节号为 $\lfloor12/8\rfloor=1$，在这个字节里的位号为 $12\bmod8=4$。

因此要修改 82 号块中的第 1 号字节，选 C。题目明确从 0 编号：字节 1 实际是该块的第二个字节，不能再加一写成 2。A、B 的盘块定位也少了一块。

答案：C。

先确定磁头方向。 最外侧磁道号为 0，因此“从外侧向内侧移动”表示磁道号增大。SCAN 像电梯一样先处理当前方向上的请求，再反向处理另一侧请求。

当前位置 58，向内侧的请求排序后为 130、180、199；反向后处理 42、15。因此移动路线为

$$58\to130\to180\to199\to42\to15.$$

按各段相加：

$$(130-58)+(180-130)+(199-180)+(199-42)+(42-15) =72+50+19+157+27=325.$$

也可合并为 $(199-58)+(199-15)=325$，选 C。

请求序列只是到达列表，不是实际服务次序；题目统计的是这些请求全部完成时的移动量，处理完最后一个请求 15 后无需再额外走到 0。若把 SCAN 混成循环扫描或按列出的次序逐个访问，就会得到不同结果。

答案：D。

分清协议层次。 POP3 是应用层的邮件接收协议，负责让用户从邮件服务器取回邮件；它需要下层把命令、响应和邮件数据可靠、有序地传送过去，因此使用 TCP。

TCP 向应用程序提供的是面向连接的可靠字节流服务：通信前建立连接，通过序号、确认和重传处理丢失，并保证交付顺序。所以对应 D 的“有连接、可靠”。

其余组合不符合 POP3 所使用的 TCP：

• A 的“无连接、不可靠”是 UDP 的典型基本服务。
• B 不属于 TCP 的服务性质。
• C 虽有连接，却把可靠性否定了，也不符合 TCP。

这里的“连接”说的是传输层连接，不是用户是否已登录邮箱或是否插入网线。可靠传输也不表示网络永远不会故障，而是协议提供差错恢复与有序交付机制。

答案：A。

读编码图时要看跳变的位置。 先按上方虚线把波形分成一个个比特区间，再判断信息由电平、比特边界跳变还是比特中点跳变表示。

编码 1 中，0 保持低电平，1 保持高电平；相邻两个相同比特之间没有必须发生的变化，例如连续的 1 对应连续高电平。这是 NRZ（不归零）编码。NRZI 的信息由边界是否翻转表示，连续多个 1 不会像此图一样始终保持同一电平。

编码 2 的每个比特中间都有跳变：图中 0 的中点为低到高，1 的中点为高到低，跳变方向直接表示数据，是曼彻斯特编码。差分曼彻斯特也有中点跳变，但主要用比特开始处是否跳变表示数据，不能只凭“每位中间有跳变”就选它。

所以编码 1、2 分别为 NRZ、曼彻斯特，选 A。

答案：B。

先算需要同时在途的帧数。 一帧为 1000 字节，即 8000 bit。链路速率为 128000 bit/s，所以帧发送时间

$$T_f=\frac{8000}{128000}=0.0625\mathrm{s}=62.5\mathrm{ms}.$$

单向传播为 250 ms，往返传播为 500 ms。发送第一帧到其确认回来，共需 $62.5+500=562.5$ ms。

不计确认开销，窗口为 $W$ 时利用率为 $\min(1,WT_f/(T_f+2T_p))$。要求至少80%，得到

$$W\ge0.8\times\frac{562.5}{62.5}=7.2,$$

窗口至少为 8 帧。

若用3位序号，常用 GBN 的发送窗口最多 $2^3-1=7$，不足8；用4位时可满足。若采用选择重传，3位窗口上限更小，而4位仍能允许8帧。因此最少4位，选 B。不要直接把“8帧”写成“3位”，可靠滑动窗口还需避免序号回绕后的新旧帧混淆。

答案：B。

CSMA/CD 的工作过程。 发送前先监听信道，空闲时开始发送；发送过程中继续检测是否有碰撞，一旦碰撞就停止、发送强化碰撞信号，并经过随机退避再尝试。

逐项判断：

• A 正确，CD 就是“碰撞检测”，要求边发边检测。
• B 错误。无线发送端自身信号很强，而且可能存在隐藏站，难以像有线共享以太网那样可靠地边发边检测碰撞；无线局域网通常采用 CSMA/CA，即碰撞避免。
• C 正确。最远两站的碰撞可能需要一个往返传播时间才能被发送者发现，因此帧发送时长不能太短，需要结合跨距和速率规定最小帧长。
• D 正确。当传播延迟趋近 0 时，等待和检测碰撞造成的相对浪费越来越小，理想化利用率可趋近100%。

本题选错误项 B。不要把 CD 的 detection 与 CA 的 avoidance 混为同一种机制。

答案：A。

交换机怎样转发？ 以太网交换机依据帧中的目的 MAC 地址查转发表，并把帧送到相应端口；它工作在数据链路层，相当于把多个网桥端口集成起来，所以 A 正确。

检查其他选项：

• B 错误。交换机把不同端口上的共享以太网段分开，不再让一处碰撞传播到所有端口，因而各端口隔离冲突域。
• C 错误。普通交换机仍会转发广播帧，未经 VLAN 划分的端口通常属于同一个广播域，而不是每端口一个广播域。
• D 错误。需要网络层协议转换或跨子网路由的互联，不能仅凭链路层的 MAC 转发实现；普通交换机可以连接多个以太网段，但不因此具备这些网络层功能。

易错点是把“隔离冲突域”和“隔离广播域”当成同一句话。网桥或普通交换机可以实现前者，后者通常要由路由或 VLAN 等机制来划分。

答案：C。

最长前缀匹配分两步：先找全部匹配项，再选择最具体的一项。 目的地址为 169.96.40.5，查看题给三个网段：

三项都匹配，默认路由 /0 也可作为兜底，但应选择前缀长度最大的 /27。它对应接口 E3，因此选 C。

A、B 不是完全不匹配，而是不如 /27 具体；D 的默认路由只有在找不到更具体匹配时才用。不能按照路由表出现的先后顺序停在第一项，也不能只比较前三个十进制地址段。

答案：A。

实际发送窗口受两种窗口共同限制： 拥塞窗口 cwnd 反映网络允许发送多少，接收窗口 rwnd 反映对端缓冲区还能装多少，实际取两者的较小值。

本题采用教材中传统的慢开始默认模型：连接建立后初始拥塞窗口为1个 MSS，即1KB；按传输轮次统计，每轮内发送该轮窗口允许的数据，在轮末根据这些数据的确认更新窗口。题面没有另给初始窗口数值，所以本题答案是在这一考试约定下计算的，不能推广为所有实际 TCP 实现都必须从1个 MSS开始。

慢开始阈值为32KB，前四轮仍处于慢开始阶段，发送量为：

四轮后 cwnd 可增到16KB，但接收方没有取走任何数据，rwnd 已降为1KB，所以实际发送窗口为 $\min(16,1)=1$ KB，选 A。

确认报文说明数据已收到，不能把接收缓冲区中的数据自动清空。B、C、D 都忽略或错误计算了接收窗口的约束。

答案：C。

按 HTTP 报文各行的职责判断。

• GET /index.html HTTP/1.1 是请求行，表示请求服务器上的路径 /index.html，所以 A 正确。
• Host: www.test.edu.cn 指定请求目标主机，结合路径得到所请求的资源，B 符合题意。
• Connection: Close 明确要求这次交互后关闭连接。HTTP/1.1 虽通常允许持续连接，但这个字段已经要求关闭，因此 C 的“使用持续连接”错误。
• Cookie: 123456 表示浏览器把已持有的站点 Cookie 随请求送出，按本题语境说明此前与该站点有过访问交互，D 正确。

因此选 C。不要只看到 HTTP/1.1 就直接认定必为持续连接；具体首部可以改变默认连接行为。另外，Cookie 字段传的是浏览器保存的状态标识，不是本次下载页面的正文。

1. 算法的基本设计思想。 判断两个整数是否应视为重复，只看它们的绝对值。题目保证 $|data|\le n$，因此可以开一个下标为 0～n 的标记数组 seen；seen[k] 表示绝对值 k 是否已经保留过。这样每个结点只需一次数组查询，避免对每个结点再扫描整个链表。

2. 单链表结点的数据类型定义。 使用图示的带头结点链表。下面采用 C 语言，约定数据结点由 malloc 分配，所以删除时使用 free；成功返回1，输入或内存分配失败返回0。

#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *link;
} Node;

3. 算法实现、过程与正确性。

int removeRepeatedAbs(Node *head, int n) {
    if (head == NULL || n < 0) return 0;

    unsigned char *seen = calloc((size_t)n + 1, sizeof(*seen));
    if (seen == NULL) return 0;  // 尚未改变链表

    Node *prev = head;          // 当前结点的前驱
    Node *cur = head->link;     // 第一个数据结点

    while (cur != NULL) {
        int key = cur->data < 0 ? -cur->data : cur->data;
        if (seen[key]) {
            prev->link = cur->link; // 越过重复结点
            free(cur);
            cur = prev->link;      // 前驱不动，继续检查新后继
        } else {
            seen[key] = 1;
            prev = cur;
            cur = cur->link;
        }
    }
    free(seen);
    return 1;
}

题设的绝对值上限保证 key 在数组范围内；用 int 型正整数 n 表示该上限时，INT_MIN 不属于允许的数据范围。

过程示例。 对 21→−15→−15→−7→15，依次标记21、15，删除第二个−15，标记7，再删除最后一个15，得到21→−15→−7。最后的15虽然与−15符号不同，但绝对值已经出现，因此也应删除。如果后面再出现7，也应删除，因为它与−7绝对值相同。数据0同样可以用seen[0]记录。

为什么正确？ 每次循环开始，已处理部分恰好保留每种绝对值的第一次出现，标记数组记录这些值。遇到新值时保留并标记，不会漏掉第一次；遇到已标记值时删去的是后续出现，不会删掉代表结点。指针始终继续向后推进，因此结束时全部结点都已正确处理。

4. 时间复杂度、空间复杂度与边界。 扫描 m 个结点是 $O(m)$，初始化 n+1 个标记是 $O(n)$，完整时间 $O(m+n)$、辅助空间 $O(n)$；若只统计已初始化标记数组之后的扫描，则为 $O(m)$。空链表、连续重复结点和末尾重复均由循环正确处理。删除时不能同时把前驱向后移，否则会跳过新的后继；也不能在释放 cur 后再读取 cur 的成员。

（1）写邻接矩阵。 行、列按顶点0、1、2、3、4排列。有边就填1，无边填0；没有自环，所以主对角线为0。图为无向图，边0—1需要同时填 $A_{01}=A_{10}=1$，其余边同理。

各顶点的邻接点为：0连1、2、4；1连0、3、4；2连0、3；3连1、2、4；4连0、1、3。因此

$$A=\begin{bmatrix} 0&1&1&0&1\\ 1&0&0&1&1\\ 1&0&0&1&0\\ 0&1&1&0&1\\ 1&1&0&1&0 \end{bmatrix}.$$

（2）矩阵相乘与元素含义。 矩阵平方不是把每个元素分别平方，而是行与列相乘后求和：

$$(A^2)_{ij}=\sum_{k=0}^{4}A_{ik}A_{kj}.$$

每一项为1，就表示有一条 $i\to k\to j$ 的两步行走。计算得到

$$A^2=\begin{bmatrix} 3&1&0&3&1\\ 1&3&2&1&2\\ 0&2&2&0&2\\ 3&1&0&3&1\\ 1&2&2&1&3 \end{bmatrix}.$$

例如 $(A^2)_{03}$ 把0行与3列相乘，得到 $0+1+1+0+1=3$，对应0→1→3、0→2→3、0→4→3三条长度为2的行走。主对角线 $(A^2)_{00}=3$ 则对应从0走到其三个邻接点后各返回0。

（3）一般矩阵幂。 $(B^m)_{ij}$ 表示从 i 到 j、长度恰好为 m 的行走条数。因为乘一次 B 就相当于把已有行走再接一条边，按中间顶点求和会数出所有可能的连接方式。非零表示至少有一条这样的行走。

行走允许重复顶点或边，因此不能无条件称为“简单路径条数”；它也不直接给出两点的最短距离。

（1）程序员可见寄存器与暂存器。 程序员可见的是 R0～R3 和 PC：通用寄存器保存指令可操作的数据，PC决定下一条取指位置。MAR、MDR、IR、T、SR是实现取指或执行所需的内部工作部件，通常不作为本题指令直接指定的通用操作数。

单总线一次只能由一个源驱动数据。ALU却可能需要两个操作数，因此先把一个数经总线存入T，T的输出保持在ALU的A端，再让另一个数经MUX送B端。否则两个寄存器不能在同一根总线上同时提供两个不同数。

（2）操作选择位数。 k种不同操作至少需要 $\lceil\log_2k\rceil$ 位编码，因为 b 位最多区分 $2^b$ 种情况。ALU有7种操作，2位只有4种，不够，故需3位；SR有3种操作，1位只有2种，不够，故需2位。

（3）SRout的作用。 它控制SR与总线之间的三态门。有效时，SR的数据送总线；无效时，输出呈高阻态，相当于暂时断开，避免它与其他寄存器同时驱动总线。它不是选择移位方向，移位方向由SRop决定。

（4）控制端点。 ①是SRout，②是SRop，③是ALUop，⑤是Tin，⑧是MUXop，它们接收控制部件发出的控制信号。④、⑥、⑦、⑨属于要连接的数据路径，不能当成操作选择信号。

（5）补齐数据连线。 需要⑥→⑨，让内部总线作为MUX的另一个数据输入；还需⑦→④，让MUX输出送到ALU的B端。结合原图已有的T→ALU A端、ALU→SR以及SR经三态门→总线，就能形成完整运算和写回通路。

（6）常数2的原因。 主存按字节编址，每条指令16位，占2B，因此顺序执行时应计算 $PC+2$。MUX选择常数2，ALU与暂存的PC相加，就能形成下一条指令地址。若错误地加1，只会移动一个字节，落在当前指令中间。

（1）最大指令数。 R0～R3共有4个寄存器，需要2位编号；每个操作数字段还需1位寻址方式，所以每字段共3位。三个字段占9位，16位指令字剩下7位作操作码，因此最多定义 $2^7=128$ 条指令。

（2）逐字段编码。 每个操作数字段按“寻址方式位+两位寄存器号”组成。寄存器直接方式为0，间接方式为1，所以R1对应001、R2对应010、R3对应011，(R1)对应101。字段次序为OP、目的操作数、源操作数1、源操作数2，单地址或二地址不用的尾部字段填0。

括号表示“寄存器内容作为内存地址再取数”，所以改变的是寻址方式位，寄存器编号本身仍为01。

（3）控制信号。 先把每条微操作对应到要完成的数据动作：

（4）执行周期。 只统计执行阶段，不包括取指阶段，按题给微操作组合与单总线限制安排：

因此sub至少4个周期。inc R1按图示方式先把R1送入运算路径，经ALU加1存SR，再用下一个总线时隙把SR写回R1，至少2个周期。读取结果、计算结果和写回结果有先后依赖，不能为了减少周期让不同源同时驱动单总线。

先把限制转为信号量。 对每个信箱，都要区分“有没有邮件可取”“有没有空位可放”和“能否独占修改信箱”。前两个是计数条件，最后一个是互斥条件。

P操作表示申请一个许可，资源不足时等待；V操作表示释放或增加一个许可。完整过程如下：

CoBegin
A:
    while TRUE:
        P(fullA)       // 先确认自己的信箱有邮件
        P(mutexA)
        从A信箱取一封邮件
        V(mutexA)
        V(emptyA)      // 取出邮件产生一个空位

        回答并生成发给B的新邮件

        P(emptyB)      // 先确认对方信箱有空位
        P(mutexB)
        将新邮件放入B信箱
        V(mutexB)
        V(fullB)       // 放入邮件产生一个可取项目
B:
    while TRUE:
        P(fullB)
        P(mutexB)
        从B信箱取一封邮件
        V(mutexB)
        V(emptyB)

        回答并生成发给A的新邮件

        P(emptyA)
        P(mutexA)
        将新邮件放入A信箱
        V(mutexA)
        V(fullA)
CoEnd

为什么能同步？ A取邮件前消耗fullA，A信箱为空时就阻塞；A给B放邮件前消耗emptyB，B信箱满时就阻塞。取出后增加相应empty，放入后增加相应full，另一方就能继续。B完全对称。

为什么还要互斥？ A从A信箱取邮件的同时，B可能向A信箱放邮件，两者都修改同一信箱的队列或计数，需要mutexA保护；B信箱同理。

关键顺序。 先等待full/empty，再获取mutex，避免拿着信箱锁等待对方操作。每次只在短暂修改信箱时持有一个锁，回答问题的耗时过程不应占住信箱锁。初始邮件不是0，所以不能把fullA、fullB都错误地初始化为0；两信箱容量M、N也不能互换。

先分清三个地址字段。 虚拟地址共有32位，由10位页目录号、10位页表索引、12位页内偏移组成。前两段定位页表项，最后一段定位页面内部的字节。

（1）页面与虚拟空间。 按字节编址，12位页内偏移能区分 $2^{12}=4096$ 个字节，所以页大小与页框大小均为4096B。虚页号共 $10+10=20$ 位，虚拟地址空间包含 $2^{20}$ 页；再乘4096B，就是 $2^{32}$ B。

（2）页表占用。 本题按完整覆盖整个虚拟地址空间的页表容量计算，页目录的1024个目录项各对应一张二级页表；这是第（2）问采用的默认建表约定。

1. 页目录有 $2^{10}=1024$ 个目录项，每项4B，共4096B，正好1页。
2. 每个二级页表也有1024项，大小也是4096B，即1页。
3. 完整覆盖全部虚拟页时，1024个目录项分别对应一个二级页表，因此需要1024个二级页表。
4. 加页目录，共 $1+1024=1025$ 页，占 $1025\times4096=4198400$ B。

因此，本题第（2）问的结果为1025页。若讨论实际操作系统按需创建页表，只创建了r张二级页表时，占用才是1+r页；这属于不同的建表范围，不能据此改写本题完整覆盖的容量结果。不要只算1024而漏掉页目录本身。

（3）访问几个二级页表。 页目录号是地址高10位，可用右移22位求出：

$$01000000_H\gg22=4,\qquad01112048_H\gg22=4.$$

两地址页目录号相同，所以都进入同一个二级页表，答案是1个。二级索引分别为0和112H，实际读取的是这个表中的不同页表项；“读两个页表项”不等于“访问两个二级页表”。

（1）DHCP地址范围与Discover。 /24掩码为255.255.255.0，网络地址是111.123.15.0，广播地址是111.123.15.255，两者不能分配给普通主机。可用主机地址为.1～.254，其中.1路由器、.2 DHCP服务器、.3 WWW服务器、.4主机1已经静态占用。

因此最大的动态地址范围为111.123.15.5～111.123.15.254，共250个地址。主机尚未取得IP时，Discover分组使用源IP 0.0.0.0、目的IP 255.255.255.255，以本地广播寻找DHCP服务器；不要误把已知子网广播地址当成Discover必用的目的地址。

（2）先找网关MAC，再发外网分组。 发往Internet的IP目的地址不在本子网，下一跳是路由器的内网接口111.123.15.1。ARP表为空时，主机先发送ARP请求询问这个IP对应的MAC，因此第一个以太网帧的目的MAC为广播FF-FF-FF-FF-FF-FF。

得到ARP应答后，实际装载外网IP分组的以太网帧目的MAC为网关的00-a1-a1-a1-a1-a1。IP层目的地址仍是外网服务器，不能因为以太网帧先交给网关，就把IP目的地址也改成网关地址。外网服务器的MAC也不会作为本局域网这一跳的目的MAC。

（3）错误网关的影响。 主机1为111.123.15.4，WWW服务器为111.123.15.3；两者与/24掩码相与，都得到111.123.15.0。属于同一子网时可以直接ARP获取对方MAC，经交换机通信，不用默认网关，所以WWW可访问。

Internet目的地址属于其他子网，需要通过默认网关转发。主机1却把网关配置成111.123.15.2，这个地址是DHCP服务器，并不是连接Internet的路由器接口.1，不能完成外网转发，所以Internet不可访问。判断网关错误的后果时，应分别检查本地通信和跨子网通信，不要把所有网络访问都判为失败。