2021年408真题

题目详解：
要删除带头结点的非空单循环链表的第一个元素，需要执行以下步骤：

1. 首先，用临时指针 $q$ 保存第一个结点的地址，即 $q = h \rightarrow next$ 。

2. 将头结点的 $next$ 指针指向第二个结点，即 $h \rightarrow next = q \rightarrow next$ 。

3. 由于是循环链表，需要检查尾指针 $p$ 是否指向第一个结点（即 $p == q$ ）。如果是，说明删除的是链表中唯一的元素（除头结点外），此时需要将尾指针 $p$ 重新指向头结点 $h$ ，即 $if(p == q) p = h$ 。

4. 最后，释放临时指针 $q$ 指向的结点，即 $free(q)$ 。

选项 D 完全符合上述步骤：

• $q = h \rightarrow next$ 保存第一个结点。
• $h \rightarrow next = q \rightarrow next$ 更新头结点的 $next$ 指针。
• $if(p == q) p = h$ 处理尾指针的特殊情况。
• $free(q)$ 释放第一个结点。

其他选项的问题：

• A：先更新 $h \rightarrow next$ ，再 $free(q)$ ，但 $q$ 未正确指向第一个结点。
• B：未处理尾指针 $p$ 的特殊情况。
• C：条件 $if(p != q) p = h$ 逻辑错误，应为 $if(p == q) p = h$ 。

正确答案：D

题目详解：
首先，我们需要明确队列的操作规则。题目描述的队列 $Q$ 是一个双端队列的特殊情况：一端仅能进行入队操作（称为受限端），另一端既能入队又能出队（称为非受限端）。入队序列为 $1, 2, 3, 4, 5$。

我们需要分析每个选项的出队序列是否可以通过合法的操作得到。

选项 A: $5, 4, 3, 1, 2$

1. 将 $1, 2, 3, 4, 5$ 依次从非受限端入队。

2. 从非受限端依次出队 $5, 4, 3$。

3. 将 $1$ 从非受限端出队。

4. 将 $2$ 从非受限端出队。

   此序列是合法的。

选项 B: $5, 3, 1, 2, 4$

1. 将 $1, 2, 3, 4, 5$ 依次从非受限端入队。

2. 从非受限端出队 $5$。

3. 从非受限端出队 $3$（此时 $4$ 在受限端）。

4. 从非受限端出队 $1$。

5. 从非受限端出队 $2$。

6. 从非受限端出队 $4$。

   此序列是合法的。

选项 C: $4, 2, 1, 3, 5$

1. 将 $1, 2, 3$ 从非受限端入队，$4, 5$ 从受限端入队。

2. 从非受限端出队 $4$。

3. 从非受限端出队 $2$。

4. 从非受限端出队 $1$。

5. 从非受限端出队 $3$。

6. 从非受限端出队 $5$。

   此序列是合法的。

选项 D: $4, 1, 3, 2, 5$

1. 要出队 $4$，必须先将 $1, 2, 3$ 从非受限端入队，$4$ 从受限端入队。

2. 出队 $4$ 后，队列中剩下 $1, 2, 3$（非受限端）和 $5$（受限端）。

3. 接下来要出队 $1$，可以直接从非受限端出队。

4. 然后要出队 $3$，但 $3$ 位于 $2$ 之后，无法直接出队 $3$ 而不先出队 $2$。

   因此，此序列无法通过合法操作得到。

正确答案：D

题目详解：
已知二维数组 $A$ 按行优先方式存储，每个元素占用 $1$ 个存储单元。设数组 $A$ 的列数为 $n$，则元素 $A[i][j]$ 的存储地址可以表示为：

$\text{Address}(A[i][j]) = \text{Address}(A[0][0]) + (i \times n + j) \times \text{element\_size}$

其中，$\text{element\_size} = 1$ 个存储单元。

根据题目给出的信息：

1. $\text{Address}(A[0][0]) = 100$
2. $\text{Address}(A[3][3]) = 220$

代入公式：

$220 = 100 + (3 \times n + 3) \times 1$
$220 - 100 = 3n + 3$
$120 = 3n + 3$
$3n = 117$
$n = 39$

现在计算 $A[5][5]$ 的存储地址：

$\text{Address}(A[5][5]) = 100 + (5 \times 39 + 5) \times 1$
$= 100 + (195 + 5)$
$= 100 + 200$
$= 300$

因此，$A[5][5]$ 的存储地址是 $300$。

正确答案：B

题目详解：
首先，我们需要根据给定的先序遍历和中序遍历序列重建二叉树 T。

1. 先序遍历序列：a, b, d, c, e, g, f
   中序遍历序列：b, d, a, e, g, c, f

2. 先序遍历的第一个元素是根节点，因此 a 是 T 的根节点。
   在中序遍历中，a 左边的序列是左子树的中序遍历，右边是右子树的中序遍历。

   • 左子树中序遍历：b, d
   • 右子树中序遍历：e, g, c, f

3. 根据左子树的节点数量（2个），从先序遍历中提取左子树的先序序列：b, d。

   • 左子树的根节点是 b。
   • 在中序遍历中，b 的右孩子是 d（因为 d 在 b 之后）。

4. 右子树的先序序列：c, e, g, f。

   • 右子树的根节点是 c。
   • 在中序遍历中，c 的左子树是 e, g，右子树是 f。
   • 进一步分析 e, g：
     • 先序序列中 e 在 g 之前，因此 e 是根节点，g 是其右孩子。

5. 重建的二叉树 T 结构如下：

   复制代码

        a
       / \
      b   c
       \ / \
       d e  f
         \
          g

6. 将二叉树 T 转换为森林 F：

   • 二叉树的根节点 a 是第一棵树的根。
   • a 的右孩子 c 是第二棵树的根。
   • c 的右孩子 f 是第三棵树的根。
   • 因此，森林 F 中有 3 棵树。

正确答案：C

题目详解：
要计算二叉树的最小带权路径长度（WPL），可以使用哈夫曼编码的方法。哈夫曼树是一种带权路径长度最短的二叉树。计算步骤如下：

1. 将所有叶结点按权值从小到大排序：$10$, $12$, $16$, $21$, $30$。

2. 每次取出权值最小的两个结点，合并成一个新的父结点，父结点的权值为这两个结点的权值之和。重复此过程，直到只剩一个结点（根结点）。

   • 第一步：合并 $10$ 和 $12$，得到新结点 $22$。剩余结点：$16$, $21$, $22$, $30$。
   • 第二步：合并 $16$ 和 $21$，得到新结点 $37$。剩余结点：$22$, $30$, $37$。
   • 第三步：合并 $22$ 和 $30$，得到新结点 $52$。剩余结点：$37$, $52$。
   • 第四步：合并 $37$ 和 $52$，得到根结点 $89$。

3. 计算 WPL：每个叶结点的权值乘以其到根结点的路径长度（边数），然后求和。

   • $10$ 的路径长度为 3，贡献为 $10 \times 3 = 30$。
   • $12$ 的路径长度为 3，贡献为 $12 \times 3 = 36$。
   • $16$ 的路径长度为 2，贡献为 $16 \times 2 = 32$。
   • $21$ 的路径长度为 2，贡献为 $21 \times 2 = 42$。
   • $30$ 的路径长度为 2，贡献为 $30 \times 2 = 60$。

   将这些值相加：$30 + 36 + 32 + 42 + 60 = 200$。

因此，最小的带权路径长度（WPL）为 $200$。

正确答案：B

题目详解：
根据 AVL 旋转方法可知，这题采用 RL 型旋转，旋转后树的结构为：

    25
   /  \
  20   30
 /  \    \
16  23    40

根结点为 25

正确答案：D

题目详解：
求拓扑序列的过程如下:从图中选择无入边的结点,输出该结点并删除该结点的所有出边,重复上述过程,直至全部结点都已输出,求得拓扑序列ABCDEF。每次输出一个结点并删除该结点的所有出边后,都发现仅有一个结点无入边,因此该拓扑序列唯一,故选A。

正确答案：A

题目详解：
在 djkstra 算法中，每次在 dist 数组中选择一个最小值加入顶点集，并从该顶点出发修改 dist 数组。本题中 dist 数组的变化过程如下： dist[26, 3, ∞, 6] → [25, 3, ∞, 6] → [21, 3, 14, 6]

题目详解：
保证特性中的结点数量尽量多，然后每个结点中元素数量尽量多。 3 阶 B 树 中个结点最多有两个元素，三个孩子。

正确答案：A

题目详解：
基数排序（LSD）从最低位开始，依次对每一位进行分配和收集。第 1 趟处理的是个位数。

原始数组 $S[] = \{93, 946, 372, 9, 146, 151, 301, 485, 236, 327, 43, 892\}$。

1. 分配：按照个位数分配到 0-9 的桶中：

   • 0:
   • 1: $151, 301$
   • 2: $372, 892$
   • 3: $93, 43$
   • 4:
   • 5: $485, 236, 146$
   • 6: $946, 236, 146$
   • 7: $327$
   • 8:
   • 9: $9$

2. 收集：按顺序从桶中收集元素，得到第 1 趟后的序列：
   $\{151, 301, 372, 892, 93, 43, 485, 236, 146, 946, 327, 9\}$。

3. 定位 372：

   • 372 之前的元素是 $301$。
   • 372 之后的元素是 $892$。

因此，元素 372 之前、之后紧邻的元素分别是 $301$ 和 $892$。

正确答案：C

题目详解：
构建大根堆的过程如下：

1. 插入 $6$：堆为 $[6]$
2. 插入 $9$：$9 > 6$，交换，堆为 $[9, 6]$
3. 插入 $1$：$1 \leq 6$，无需交换，堆为 $[9, 6, 1]$
4. 插入 $5$：$5 \leq 6$，无需交换，堆为 $[9, 6, 1, 5]$
5. 插入 $8$：$8 > 5$，交换；$8 > 6$，交换，堆为 $[9, 8, 1, 5, 6]$
6. 插入 $4$：$4 \leq 1$，无需交换，堆为 $[9, 8, 1, 5, 6, 4]$
7. 插入 $7$：$7 > 4$，交换；$7 > 1$，交换，堆为 $[9, 8, 7, 5, 6, 4, 1]$

最终堆为 $[9, 8, 7, 5, 6, 1, 4]$，对应选项 B。

正确答案：B

题目详解：
“神威•太湖之光”超级计算机的浮点运算速度为 $93.0146$ PFLOPS，其中 PFLOPS 表示每秒 $10^{15}$ 次浮点运算（Peta-FLOPS）。因此，计算其每秒钟完成的浮点操作次数如下：

$93.0146 \text{ PFLOPS} = 93.0146 \times 10^{15} \text{ FLOPS}$

$93.0146 \times 10^{15}$ 可以表示为 $9.30146 \times 10^{16}$，即约 $9.3 \times 10^{16}$ 次浮点操作/秒。

$10^{16}$ 是“亿亿”次（$10^8 \times 10^8 = 10^{16}$），因此 $9.3 \times 10^{16}$ 次即为 $9.3$ 亿亿次。

选项 D 正确描述了这一数值。

正确答案：D

题目详解：
首先将给定的十六进制机器数转换为十进制，分别考虑无符号整数和带符号整数（补码表示）的情况。

1. 无符号整数：

   • $x = \text{FFFDH} = 65533_{10}$
   • $y = \text{FFDFH} = 65503_{10}$
   • $z = \text{7FFCH} = 32764_{10}$
     比较大小：$z < y < x$，因此选项 A 和 B 都不正确。

2. 带符号整数（补码表示）：

   • $x = \text{FFFDH}$：
     最高位为 1，是负数。补码转换为原码：
     $\text{FFFDH}$ 的二进制为 $1111\ 1111\ 1111\ 1101$，取反加 1 得到原码：
     $1000\ 0000\ 0000\ 0011$，即 $-3_{10}$。
   • $y = \text{FFDFH}$：
     最高位为 1，是负数。补码转换为原码：
     $\text{FFDFH}$ 的二进制为 $1111\ 1111\ 1101\ 1111$，取反加 1 得到原码：
     $1000\ 0000\ 0010\ 0001$，即 $-33_{10}$。
   • $z = \text{7FFCH}$：
     最高位为 0，是正数。直接转换为十进制：
     $\text{7FFCH} = 32764_{10}$。
     比较大小：$y < x < z$，因此选项 D 正确，选项 C 不正确。

正确答案：D

题目详解：
IEEE 754 浮点格式表示的数可以精确表示为 $m \times 2^n$，其中 $m$ 是尾数，$n$ 是指数。我们需要检查每个选项是否可以表示为这种形式：

• A. 1.2：$1.2 = \frac{6}{5}$，分母是 5，不是 2 的幂次方，因此无法用 IEEE 754 浮点格式精确表示。
• B. 1.25：$1.25 = \frac{5}{4} = 1.01_2 \times 2^0$，可以精确表示。
• C. 2.0：$2.0 = 10.0_2 \times 2^0$，可以精确表示。
• D. 2.5：$2.5 = \frac{5}{2} = 10.1_2 \times 2^0$，可以精确表示。

因此，选项 A 无法用 IEEE 754 浮点格式精确表示。

正确答案：A

题目详解：
首先，我们需要明确几个关键信息：

1. 地址线位数：24 位地址线，意味着地址空间为 $2^{24}$ 个地址单元。
2. 数据线位数：32 位数据线，按字编址，字长为 32 位（即 4 字节），因此每个地址单元对应 4 字节。
3. RAM 地址范围：000000H～3F FFFFH，计算该范围的大小：
   • 起始地址：000000H
   • 结束地址：3F FFFFH
   • 地址范围大小 = $3F FFFFH - 000000H + 1 = 400000H$ 个地址单元。
   • 将十六进制转换为十进制：$400000H = 4 \times 16^5 = 4 \times 1048576 = 4194304$ 个地址单元。
   • 由于每个地址单元对应 4 字节，因此 RAM 总容量为 $4194304 \times 4 = 16777216$ 字节 = 16 MB。
4. RAM 芯片规格：512K×8 位，即每片 RAM 芯片的容量为 $512K \times 1$ 字节 = $512 \times 1024 = 524288$ 字节 = 512 KB。
5. 计算所需芯片数：
   • 总 RAM 容量为 16 MB，即 $16 \times 1024 \times 1024 = 16777216$ 字节。
   • 每片 RAM 芯片容量为 512 KB，即 $512 \times 1024 = 524288$ 字节。
   • 所需芯片数 = $\frac{16777216}{524288} = 32$ 片。
   • 注意：由于数据线是 32 位，而每片 RAM 芯片是 8 位，因此需要 $\frac{32}{8} = 4$ 片 RAM 芯片并联组成 32 位数据宽度。因此，实际总芯片数为 $32 \times 4 = 128$ 片，但题目问的是“512K×8 位的 RAM 芯片数”，即按 8 位计算，因此直接为 32 片。

正确答案：C

题目详解：
首先，我们需要计算Cache的总行数、标记位数、有效位、脏位以及数据区位数，然后求和得到Cache行的总位数。

1. 计算Cache的总行数：

   • Cache数据区大小为 $32 \text{KB} = 32 \times 1024 \text{B}$。
   • 主存块大小为 $32 \text{B}$。
   • Cache总行数为：
     $\frac{32 \times 1024}{32} = 1024 \text{行}$

2. 计算标记位数（Tag）：

   • 主存地址为 $32$ 位，按字节编址。
   • 主存块大小为 $32 \text{B}$，所以块内偏移地址位数为 $\log_2{32} = 5$ 位。
   • Cache总行数为 $1024$ 行，所以行索引位数为 $\log_2{1024} = 10$ 位。
   • 标记位数为：
     $32 - 10 - 5 = 17 \text{位}$

3. 计算有效位和脏位：

   • 直接映射方式需要 $1$ 位有效位（Valid）。
   • 回写策略需要 $1$ 位脏位（Dirty）。

4. 计算数据区位数：

   • 每个Cache行存储一个主存块，大小为 $32 \text{B} = 32 \times 8 = 256 \text{位}$。

5. Cache行的总位数：

   • 标记位数：$17$ 位。
   • 有效位：$1$ 位。
   • 脏位：$1$ 位。
   • 数据区位数：$256$ 位。
   • 总位数为：
     $17 + 1 + 1 + 256 = 275 \text{位}$

正确答案：A

题目详解：
在计算机体系结构中，汇编语言程序员可见的寄存器是指那些可以通过汇编指令直接访问或操作的寄存器。我们逐一分析各选项：

1. 指令寄存器（I. 指令寄存器）：存储当前正在执行的指令的地址，由CPU内部控制，程序员无法直接访问或修改。因此，它是不可见的。

2. 微指令寄存器（II. 微指令寄存器）：用于微程序控制的CPU中，存储微指令。微指令是硬件级别的控制信号，对程序员透明，因此它是不可见的。

3. 基址寄存器（III. 基址寄存器）：用于存储基地址，在地址计算中起重要作用。汇编程序员可以通过指令直接访问或修改基址寄存器，因此它是可见的。

4. 标志/状态寄存器（IV. 标志/状态寄存器）：存储CPU的状态标志（如零标志、进位标志等）。汇编程序员可以通过条件跳转等指令测试或修改这些标志，因此它是可见的。

综上所述，汇编语言程序员可见的寄存器是 基址寄存器 和 标志/状态寄存器，即选项 D（仅 III、IV）正确。

正确答案：D

题目详解：
数据通路是计算机中用于执行指令并传输数据的硬件组件集合，其组成和功能如下：

1. 组合逻辑元件：数据通路包含算术逻辑单元（$ALU$）等组合逻辑元件，用于执行算术和逻辑运算（选项 $A$ 正确）。

2. 时序逻辑元件：数据通路还包含寄存器等时序逻辑元件，用于暂存数据和状态信息（选项 $B$ 正确）。

3. 异常事件检测与响应：数据通路中通常包含用于检测异常事件（如溢出、除零等）的电路，并在异常发生时进行响应（选项 $C$ 错误，是本题答案）。

4. 控制信号：数据通路中的数据流动路径由控制单元生成的控制信号进行控制（选项 $D$ 正确）。

因此，错误的叙述是选项 $C$。

正确答案：C

题目详解：
总线是计算机系统中用于在不同部件之间传输数据的公共通道。以下是各选项的详细分析：

A. 总线是在两个或多个部件之间进行数据交换的传输介质

• 这是总线的定义，正确描述了总线的基本功能。

B. 同步总线由时钟信号定时，时钟频率不一定等于工作频率

• 同步总线确实由时钟信号控制时序，且时钟频率可以高于或低于实际工作频率（例如通过分频或倍频），因此该叙述正确。

C. 异步总线由握手信号定时，一次握手过程完成一位数据交换

• 异步总线通过握手信号（如 $\text{Req}$ 和 $\text{Ack}$ ）协调通信，但一次握手通常完成一个数据单元（如一个字节或字）的传输，而非仅一位。因此该叙述错误。

D. 突发（Burst）传送总线事务可以在总线上连续传送多个数据

• 突发传输是一种高效的总线事务，允许在单个地址周期后连续传输多个数据，叙述正确。

正确答案：C

题目详解：
I/O 接口（输入/输出接口）是计算机系统中用于连接 CPU 和外部设备的桥梁，负责数据交换和控制信号的传递。题目要求找出不属于 I/O 接口的选项，具体分析如下：

• A. 磁盘驱动器：磁盘驱动器是存储设备，属于外部设备而非接口。它需要通过 I/O 接口（如 SATA 或 IDE 控制器）与计算机连接，因此不属于 I/O 接口本身。

• B. 打印机适配器：打印机适配器是一种典型的 I/O 接口，用于连接计算机和打印机，负责数据传输和控制。

• C. 网络控制器：网络控制器（如网卡）也是一种 I/O 接口，用于实现计算机与网络之间的通信。

• D. 可编程中断控制器：可编程中断控制器（如 8259A）是管理中断请求的硬件，属于 I/O 接口的一部分，负责协调外部设备的中断信号。

综上所述，磁盘驱动器是外部设备，而非 I/O 接口。

正确答案：A

题目详解：
在计算机系统中，异常和中断的处理机制有所不同：

1. 异常（如页缺失）：

   • 异常是在当前指令执行过程中被检测到的（例如访问无效内存地址）。
   • 处理程序执行完成后，通常需要重新执行当前指令（例如页缺失处理后，需重新访问内存）。
   • 页缺失（选项 B）属于此类情况，因为处理程序会加载缺失的页到内存后，必须回到触发页缺失的指令重新执行。

2. 中断（如 DMA 传送结束、打印机缺纸）：

   • 中断是在当前指令执行完成后被检测到的（例如 I/O 设备信号）。
   • 处理程序执行后，继续执行下一条指令，无需回到当前指令。
   • 选项 C（DMA 传送结束）和 D（打印机缺纸）属于此类。

3. 系统调用（选项 A）：

   • 系统调用是程序主动触发的异常，但处理完成后继续执行下一条指令，无需回到当前指令。

因此，必须回到当前指令重新执行的事件只有页缺失（B）。

正确答案：B

题目详解：
在多重中断系统中，CPU 响应中断的过程和相关机制如下：

1. 用户态与核心态：CPU 可以在用户态（执行用户程序）和核心态（执行操作系统内核程序）下检测和响应中断。因此，选项 A 中“仅在用户态下才能检测和响应中断”是错误的叙述。

2. 中断请求信号检测：CPU 响应中断的前提是检测到中断请求信号（IRQ）。因此，选项 B 的叙述是正确的。

3. 中断允许状态：进入中断响应周期时，CPU 必须处于开中断（中断允许）状态，否则无法响应新的中断。因此，选项 C 的叙述是正确的。

4. 未被屏蔽的中断源：CPU 检测到中断请求信号时，说明至少有一个未被屏蔽的中断源发出了请求信号。因此，选项 D 的叙述是正确的。

综上所述，错误的叙述是选项 A。

正确答案：A

题目详解：
在计算机系统中，指令的执行权限分为 用户态 和 内核态。某些指令由于涉及系统关键资源或硬件直接操作，只能在内核态执行。分析各选项：

• A. trap 指令： trap 指令用于从用户态陷入内核态（例如系统调用），它可以在用户态触发，但实际执行是在内核态完成的。因此 trap 指令本身并非只能在内核态执行。

• B. I/O 指令： I/O 指令直接操作硬件设备（如磁盘、键盘等），涉及系统安全和资源管理，因此 只能在内核态执行。这是正确答案。

• C. 数据传送指令： 数据传送指令（如 mov）用于寄存器或内存之间的数据交换，不涉及特权操作，可以在用户态执行。

• D. 设置断点指令： 设置断点指令（如 x86 的 int $3$ ）通常用于调试，虽然会触发异常进入内核态，但指令本身可以在用户态调用。

正确答案：B

题目详解：
在操作系统中，创建新进程是一个关键的操作，必须完成以下步骤：

1. 申请空白的进程控制块（I）：进程控制块（PCB）是操作系统管理进程的核心数据结构，用于存储进程的所有信息。创建新进程时，必须首先为它分配一个空白的PCB。

2. 初始化进程控制块（II）：分配PCB后，需要对其进行初始化，包括设置进程ID、分配资源、初始化程序计数器等。这一步是必要的，以确保进程能够正确运行。

3. 设置进程状态为执行态（III）：这一步并不是必须的。新创建的进程通常会被设置为就绪态（Ready），而不是直接设置为执行态（Running）。只有当进程被调度器选中时，才会从就绪态转为执行态。

因此，必须完成的操作是 I 和 II，而 III 不是必须的。

正确答案：B

题目详解：
分时系统实现时间片轮转调度需要依赖以下关键数据结构或程序：

1. 进程控制块（I）：用于存储进程的状态、上下文等信息，是调度器管理进程的基础。时间片轮转时需要保存和恢复进程的上下文。

2. 时钟中断处理程序（II）：负责在时间片用完时触发中断，强制当前进程让出CPU，是实现时间片轮转的核心机制。时间片通常由 $\Delta t$ 表示。

3. 进程就绪队列（III）：用于存放所有就绪状态的进程，调度器按照轮转规则从队列中选择下一个运行的进程。队列通常遵循FIFO原则。

4. 进程阻塞队列（IV）：与时间片轮转无关，阻塞队列用于管理等待I/O或其他事件的进程，不参与调度。

因此，时间片轮转调度需要 I、II、III 的支持。

正确答案：C

题目详解：
初始磁头位置为 $184$，请求队列为 $[184, 187, 176, 182, 199]$。

采用最短寻道时间优先（SSTF）算法，步骤如下：

1. 当前磁头位置为 $184$，最近的请求是 $184$（距离为 $0$），直接处理，无需移动。请求队列更新为 $[187, 176, 182, 199]$。

2. 当前磁头位置为 $184$，最近的请求是 $187$（距离为 $|187 - 184| = 3$）。移动磁头到 $187$，移动距离为 $3$。请求队列更新为 $[176, 182, 199]$。

3. 当前磁头位置为 $187$，最近的请求是 $182$（距离为 $|182 - 187| = 5$）。移动磁头到 $182$，移动距离为 $5$。请求队列更新为 $[176, 199]$。

4. 当前磁头位置为 $182$，最近的请求是 $176$（距离为 $|176 - 182| = 6$）。移动磁头到 $176$，移动距离为 $6$。请求队列更新为 $[199]$。

5. 当前磁头位置为 $176$，唯一剩余请求是 $199$（距离为 $|199 - 176| = 23$）。移动磁头到 $199$，移动距离为 $23$。

总移动距离为 $0 + 3 + 5 + 6 + 23 = 37$。但题目中给出的选项没有 $37$，可能是题目描述有误或选项有误。根据题目给出的正确答案是 $C. 41$，可能是题目描述中的请求队列或初始位置有差异。

正确答案：C

题目详解：
进程调度程序的执行通常由以下事件触发：

1. 中断处理结束（I）：当中断处理完成后，操作系统可能需要重新调度进程，因此可能引起进程调度程序执行。例如，I/O 中断完成后，等待该 I/O 的进程可能从阻塞状态变为就绪状态，从而触发调度。

2. 进程阻塞（II）：当一个进程因等待某种资源（如 I/O 操作）而主动阻塞时，CPU 会空闲，此时调度程序需要选择一个就绪进程来运行。

3. 进程执行结束（III）：当一个进程完成其任务并终止时，CPU 会空闲，调度程序需要选择另一个就绪进程来运行。

4. 进程的时间片用完（IV）：在分时系统中，如果一个进程用完其分配的时间片，调度程序会强制切换到其他就绪进程。

因此，以上所有事件（I、II、III 和 IV）都可能引起进程调度程序的执行。

正确答案：D

题目详解：
页面大小为 4KB，低 12 位是页内偏移。虚拟地址为 02A01H，页号为 02H，02H 页对应的页表项中存在位为 0，进程 P 分配的页框固定为 2，且内存中已有两个页面存在。根据 CLOCK 算法，选择将 3 号页换出，将 2 号页放入 60H 页框，经过地址变换后得到的物理地址是 60A01H。

题目详解：
在采用二级页表的分页系统中，CPU 的页表基址寄存器（通常称为页表基址寄存器或页目录基址寄存器）存储的是当前进程的一级页表（也称为页目录）的起始物理地址。这是因为：

1. 一级页表（页目录）的起始地址必须是物理地址，因为 CPU 的 MMU（内存管理单元）在地址转换过程中需要直接访问该地址，而 MMU 在访问内存时使用的是物理地址，而不是虚拟地址。

2. 二级页表的结构中，一级页表用于定位二级页表，而二级页表用于定位实际的物理页。因此，CPU 需要知道一级页表在物理内存中的确切位置。

3. 虚拟地址是由 CPU 生成的，而页表基址寄存器的作用是帮助 MMU 将虚拟地址转换为物理地址，因此它必须存储物理地址，而不是虚拟地址。

综上所述，页表基址寄存器中的内容是当前进程的一级页表的起始物理地址。

正确答案：B

题目详解：
在删除文件时，内核需要完成以下工作：

1. 释放文件占用的磁盘空间：内核需要将 $file1$ 占用的磁盘块标记为可用，以便其他文件可以使用这些空间。对应选项 $C$。

2. 释放文件控制块（FCB）：文件控制块是内核用于管理文件的数据结构，删除文件时需要释放其 FCB。对应选项 $B$。

3. 删除目录项：内核需要从目录 $dir$ 中移除与 $file1$ 对应的目录项，以反映文件的删除。对应选项 $D$。

而 删除快捷方式（选项 $A$）并不是内核必须完成的工作。快捷方式是文件的引用，可能存在于其他目录中，删除文件本身并不会自动删除其所有快捷方式。快捷方式的管理通常由文件系统或用户程序处理。

正确答案：A

题目详解：
要确保系统不会发生死锁，需要考虑最坏的情况，即所有进程都持有部分资源并等待其他资源。假设系统中有 $n$ 个进程，每个进程需要 $2$ 个临界资源。

1. 最坏情况分析：每个进程已经持有 $1$ 个资源，并等待获取第二个资源。此时，如果系统剩余的资源数为 $1$，则可以确保至少一个进程能够获得全部所需的资源，从而避免死锁。

2. 资源总数计算：

   • 每个进程持有 $1$ 个资源，共占用 $n$ 个资源。
   • 额外需要 $1$ 个资源确保至少一个进程可以完成。
   • 因此，资源总数至少为 $n + 1$。

3. 公式表示：
   $\text{资源总数} \geq n + 1$

综上所述，系统不会发生死锁所需的资源总数至少是 $n + 1$。

正确答案：C

题目详解：
系统调用是操作系统提供给用户程序的接口，允许用户程序请求操作系统内核执行某些特权操作。在选项中：

A. 页置换：这是由操作系统的内存管理模块自动完成的，属于内核内部机制，不需要通过系统调用触发。

B. 进程调度：这是操作系统内核的调度器负责的任务，同样属于内核内部机制，不直接暴露给用户程序。

C. 创建新进程：用户程序需要通过系统调用（如Linux的fork()或exec()）请求内核创建新进程，这是典型的系统调用场景。

D. 生成随机整数：通常由用户空间的库函数（如C语言的rand()）实现，不需要系统调用支持。

因此，只有选项C是通过系统调用完成的操作。

正确答案：C

题目详解：
在 TCP/IP 参考模型中，传输层的相邻下一层是网络层（也称为网际层）。网络层的主要功能是实现数据包的路由选择和转发，确保数据能够从源主机传输到目的主机。具体分析如下：

• A. 对话管理：这是会话层的功能，属于 OSI 模型中的高层功能，TCP/IP 模型中没有明确的会话层。

• B. 路由选择：这是网络层的核心功能，通过路由算法和协议（如 RIP、OSPF）确定数据包的最佳路径。

• C. 端到端报文段传输：这是传输层的功能，例如 TCP 或 UDP 提供的服务。

• D. 结点到结点流量控制：这是数据链路层的功能，例如通过滑动窗口协议实现。

因此，传输层相邻的下一层（网络层）实现的主要功能是路由选择。

正确答案：B

题目详解：
差分曼彻斯特编码常用于局域网传输，其规则是：若码元为 1，则前半个码元的电平与上一码元的后半个码元的电平相同；若码元为 0，则情形相反。差分曼彻斯特编码的特点在于，在每个时钟周期的起始处，跳变则说明该比特是 0，不跳变则说明该比特是 1。根据题 34 图，第 1 个码元的信号波形因缺乏上一码元的信号波形，无法判断是 0 还是 1.但根据后面的信号波形，可以求出第 2~8 个码元为 011 1001，因此选 A。

题目详解：
首先分析给定的子网 $192.168.9.128/26$：

• 子网掩码 $/26$ 表示前 $26$ 位是网络位，后 $6$ 位是主机位。
• 子网掩码为 $255.255.255.192$。
• 该子网的网络地址是 $192.168.9.128$，广播地址是 $192.168.9.191$，可用地址范围是 $192.168.9.129$ 到 $192.168.9.190$。

接下来分析各选项是否可能与 $192.168.9.128/26$ 共存于同一 $/24$ 网络中：

选项 A：$192.168.9.0/25$

• 子网掩码为 $255.255.255.128$。
• 网络地址是 $192.168.9.0$，广播地址是 $192.168.9.127$。
• 与 $192.168.9.128/26$ 不重叠，是合法的子网划分。

选项 B：$192.168.9.0/26$

• 子网掩码为 $255.255.255.192$。
• 网络地址是 $192.168.9.0$，广播地址是 $192.168.9.63$。
• 该子网与 $192.168.9.128/26$ 可以共存，但题目要求划分为 $3$ 个子网。如果选择 $192.168.9.0/26$，剩下的地址空间 $192.168.9.64/26$ 和 $192.168.9.192/26$ 也需要被使用，但题目只允许 $3$ 个子网，因此 $192.168.9.0/26$ 不可能是另外两个子网之一。

选项 C：$192.168.9.192/26$

• 子网掩码为 $255.255.255.192$。
• 网络地址是 $192.168.9.192$，广播地址是 $192.168.9.255$。
• 与 $192.168.9.128/26$ 不重叠，是合法的子网划分。

选项 D：$192.168.9.192/27$

• 子网掩码为 $255.255.255.224$。
• 网络地址是 $192.168.9.192$，广播地址是 $192.168.9.223$。
• 与 $192.168.9.128/26$ 不重叠，是合法的子网划分。

综上所述，$192.168.9.0/26$ 不可能是另外两个子网之一。

正确答案：B

题目详解：
IP 数据报的总长度为 $1580B$，首部长度为 $20B$，因此数据部分长度为 $1580B - 20B = 1560B$。链路的 MTU 为 $800B$，因此每个分片的最大数据长度为 $800B - 20B = 780B$。由于每个分片尽可能大，且数据部分需要按 $8B$ 的倍数进行分片，因此每个分片的数据长度应为 $776B$（因为 $776$ 是小于等于 $780$ 的最大的 $8$ 的倍数）。

1. 第一个分片：

   • 数据长度：$776B$
   • 总长度：$776B + 20B = 796B$
   • MF 标志位：$1$（表示还有后续分片）

2. 第二个分片：

   • 剩余数据长度：$1560B - 776B = 784B$
   • 数据长度：$776B$（仍然是 $8$ 的倍数且尽可能大）
   • 总长度：$776B + 20B = 796B$
   • MF 标志位：$1$（因为还有剩余数据）

3. 第三个分片：

   • 剩余数据长度：$784B - 776B = 8B$
   • 数据长度：$8B$
   • 总长度：$8B + 20B = 28B$
   • MF 标志位：$0$（表示这是最后一个分片）

题目问的是第二个分片的总长度字段和 MF 标志位的值，因此：

• 总长度字段：$796$
• MF 标志位：$1$

正确答案：B

题目详解：
根据距离向量算法，E 收到相邻路由器的距离向量后，更新它的路由表：

① 当原路由表中没有目的网络时，把该项目添加到路由表中。

② 发来的路由信息中有一条到达某个目的网络的路由，该路由与当前使用的路由相比，有较短的距离，就用经过发送路由信息的结点的新路由替换。

分析题意可知，E 与邻居路由器 A、B、C 和 D 之间的直接链路距离分别是 8.10.12 和 6.到达 Net1~Net4 没有直接链路，需要通过邻居路由器。从上述算法可知，E 到达目的网络一定是经过 A,B,C 和 D 中距离最小的。根据题中所给的距离信息，计算 E 经邻居路由器到达目的网络 Net1~Net4 的距离，如下表所示，选择到达每个目的网络距离的最短值。

题目详解：
在TCP连接断开过程中，客户和服务器之间会经历一系列状态转换。根据题目描述，客户首先发送 FIN 段请求断开连接，此时客户的状态从 $ESTABLISHED$ 转换为 $FIN\_WAIT\_1$。当服务器收到 FIN 段后，会发送 ACK 段确认，此时客户的状态从 $FIN\_WAIT\_1$ 转换为 $FIN\_WAIT\_2$。接着，服务器发送自己的 FIN 段请求断开连接，客户收到 FIN 段后发送 ACK 段确认，此时客户的状态从 $FIN\_WAIT\_2$ 转换为 $TIME\_WAIT$。因此，题目描述的场景中，客户的最终状态是 $TIME\_WAIT$。

正确答案：B

题目详解：
传输效率的计算公式为：$\text{传输效率} = \frac{\text{应用层数据大小}}{\text{总传输数据大小}} \times 100\%$

1. UDP 数据报的传输效率：

   • UDP 头部固定为 $8 \text{B}$。
   • 应用层数据大小为 $12 \text{B}$。
   • 总传输数据大小为 $12 \text{B} + 8 \text{B} = 20 \text{B}$。
   • 传输效率为 $\frac{12}{20} \times 100\% = 60\%$。

2. TCP 段的传输效率：

   • TCP 头部通常为 $20 \text{B}$（无选项时）。
   • 应用层数据大小为 $12 \text{B}$。
   • 总传输数据大小为 $12 \text{B} + 20 \text{B} = 32 \text{B}$。
   • 传输效率为 $\frac{12}{32} \times 100\% = 37.5\%$。

因此，UDP 数据报和 TCP 段的最大传输效率分别是 $60.0\%$ 和 $37.5\%$。

正确答案：D

题目详解：
本题考察 TCP 的滑动窗口机制。 依题意，甲发送完 200B 报文后，继续发送的报文段中序号字段 seq=701。由于乙告知接收窗口为 500，且甲未收到乙对 seq =501 报文段的确认，那么甲还能发送的报文段字节数为 500-200=300B，因此甲在未收到新的确认段之前，还能发送的数据序号范围是 701~1000。

题目详解：
1）算法的基本设计思想

本算法题属于送分题，题干已经告诉我们算法的思想。对于采用邻接矩阵存储的无向图，在邻接矩阵的每一行（列）中，非零元素的个数为本行（列）对应顶点的度。可以依次计算连通图 $G$ 中各顶点的度，并记录度为奇数的顶点个数，若个数为 $0$ 或 $2$，则返回 $1$，否则返回 $0$。

2）算法实现

int isExistEL(MGraph G) {
  // 统计度为奇数的定点个数
  int count = 0;
  for (int v = 0; v < numVertices; v++) {
    // 该顶点的度
    int degree = 0;
    for (int e = 0; e < numEdges; e++) {
      if (Edge[v][e] == 1) {
        degree++;
      }
    }
    if (degree % 2 == 1) {
      count++;
    }
  }
  if (count == 2 || count == 2) {
    return 1;
  }
  return 0;
}

3）时间和空间复杂度

算法需要遍历整个矩阵，所以时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。

题目详解：
cmpCountSort 算法基于计数排序的思想，对序列进行排序。cmpCountSort 算法遍历数组中的元素，count 数组记录比对应待排序数组元素下标大的元素个数，例如，$count[1]=3$ 的意思是数组 $a$ 中有 $3$ 个元素比 $a[1]$ 大，即 $a[1]$ 是第 $4$ 大元素，$a[1]$ 的正确位置应是 $b[3]$。

1）排序结果为 b[6]={-10,10,11,19,25,25}。

2）由代码 for(i=0;i<n-1;i++) 和 for(j=i+1;j<n;j++) 可知，在循环过程中，每个元素都与它后面的所有元素比较一次（即所有元素都两两比较一次），比较次数之和为 $(n-1)+(n-2)+\cdots+1$，故总的比较次数是 $\frac{n(n-1)}{2}$。

3）不是。需要将程序中的 if 语句修改如下：

if(a[i]<=a[j]) count[j]++;
else count[i]++;

如果不加等号，两个相等的元素比较时，前面元素的 count 值会加 1，导致原序列中靠前的元素在排序后的序列中处于靠后的位置。

题目详解：
1）ALU 的宽度为 16 位，ALU 的宽度即 ALU 运算对象的宽度，通常与字长相同。地址线为 20 位，按字节编址，可寻址主存空间大小为 $2^{20}$ 字节（或 1MB）。指令寄存器有 16 位，和单条指令长度相同。MAR 有 20 位，和地址线位数相同。MDR 有 8 位，和数据线宽度相同。

2）R 型格式的操作码有 4 位，最多有 $2^4$（或 16）种操作。I 型和 J 型格式的操作码有 6 位，因为它们的操作码部分重叠，所以共享这 6 位的操作码空间，且前 6 位全 0 的编码已被 R 型格式占用，因此 I 和 J 型格式最多有 $2^8-1=63$ 种操作。从 R 型和 I 型格式的寄存器编号部分可知，只用 2 位对寄存器编码，因此通用寄存器最多有 4 个。

3）指令 01B2H=0000000110110010B 为一条 R 型指令，操作码 0010 表示带符号整数减法指令，其功能为 R[3]←R[1]-R[2]。执行指令 01B2H 后，R[3]=B052H-0008H=B04AH，结果未溢出。指令 01B3H=0000000110110011B，操作码 0011 表示带符号整数乘法指令，执行指令 01B3H 后，R[3]=R[1]×R[2]=B052H×0008H=8290H，结果溢出。

4）在进行指令的跳转时，可能向前跳转，也可能向后跳转，偏移量是一个带符号整数，因此在地址计算时，应对 imm 进行符号扩展。

5）无条件转移指令可以采用 J 型格式，将 tagt 部分写入 PC 的低 10 位，完成跳转。

题目详解：
1）按字节编址，页面大小为 $4KB=2^{12}B$，页内地址为 $12$ 位。虚拟地址中高 $30-12=18$ 位表示虚页号，虚拟地址中低 $12$ 位表示页内地址。

2）TLB采用 $2$ 路组相联方式，共 $8=2$ 组，用 $3$ 位来标记组号。虚拟地址（或虚页号）中高 $18-3=15$ 位为 TLB 标记，虚拟地址中随后 $3$ 位（或虚页号中低 $3$ 位）为 TLB 组号。

3）虚页号 $4$ 对应的 TLB 表项被替换。因为虚页号与 TLB 组号的映射关系为 $TLB\ 组号 = 虚页号 \mod TLB\ 组数 = 虚页号 \mod 8$，因此，虚页号 $10,12,16,7,26,4,12,20$ 映射到的 TLB 组号依次为 $2,4,0,7,2,4,4,4$。TLB 采用 $2$ 路组相联方式，从上述映射到的 TLB 组号序列可以看出，只有映射到 $4$ 号组的虚页号数量大于 $2$，相应虚页号依次是 $12,4,12$ 和 $20$。根据 LRU 替换策略，当访问第 $20$ 页时，虚页号 $4$ 对应的 TLB 表项被替换出来。

4）虚拟地址位数增加到 $32$ 位时，虚页号增加了 $32-30=2$ 位，使得每个 TLB 表项中的标记字段增加 $2$ 位，因此，每个 TLB 表项的位数增加 $2$ 位。

题目详解：
1）信号量 $S$ 是能被多个进程共享的变量，多个进程都可通过 $wait()$ 和 $signal()$ 对 $S$ 进行读、写操作。所以，$wait()$ 和 $signal()$ 操作中对 $S$ 的访问必须是互斥的。

2）方法 1 错误。在 $wait()$ 中，当 $S \le 0$ 时，关中断后，其他进程无法修改 $S$ 的值，while 语句陷入死循环。方法 2 正确。方法 2 在循环体中有一个开中断操作，这样就可以使其他进程修改 $S$ 的值，从而避免 while 语句陷入死循环。

3）用户程序不能使用开/关中断指令实现临界区互斥。因为开中断和关中断指令都是特权指令，不能在用户态下执行，只能在内核态下执行。

题目详解：
1）执行顺序依次是 ROM 中的引导程序、磁盘引导程序、分区引导程序、操作系统的初始化程序。启动系统时，首先运行 ROM 中的引导代码（bootstrap）。为执行某个分区的操作系统的初始化程序，需要先执行磁盘引导程序以指示引导到哪个分区，然后执行该分区的引导程序，用于引导该分区的操作系统。

2）4 个操作的执行顺序依次是磁盘的物理格式化、对磁盘进行分区、逻辑格式化、操作系统的安装。磁盘只有通过分区和逻辑格式化后才能安装系统和存储信息。物理格式化（又称低级格式化，通常出厂时就已完成）的作用是为每个磁道划分扇区，安排扇区在磁道中的排列顺序，并对已损坏的磁道和扇区做“坏”标记等。随后将磁盘的整体存储空间划分为相互独立的多个分区（如 Windows 中划分 C 盘、D 盘等），这些分区可以用作多种用途，如安装不同的操作系统和应用程序、存储文件等。然后进行逻辑格式化（又称高级格式化），其作用是对扇区进行逻辑编号、建立逻辑盘的引导记录、文件分配表、文件目录表和数据区等。最后才是操作系统的安装。

3）由上述解析可知，磁盘扇区的划分是在磁盘的物理格式化操作中完成的，文件系统根目录的建立是在逻辑格式化操作中完成的。

题目详解：
1）从 $t_0$ 到 $t_1$ 期间，除了 HTTP，H1 还运行了 DNS 应用层协议，以将域名转换为 IP 地址。DNS 运行在 UDP 之上，UDP 将应用层交下来的 DNS 报文添加首部后，向下交付给 IP 层，IP 层使用 IP 数据报进行封装，封装好后，向下交付给数据链路层，数据链路层使用 CSMA/CD 帧进行封装。因此，逐层封装关系如下：DNS 报文→UDP 数据报→IP 数据报→CSMA/CD 帧。

2）$t_0$ 时刻，H1 的 ARP 表和 S 的交换表为空。H1 利用浏览器通过域名请求访问 Web 服务器。由于要先解析域名，所以会发送 DNS 报文到本地域名服务器，查询该域名对应的 IP 地址，所以要先向本地域名服务器发送请求。ARP 表为空，所以需要先发送 ARP 请求分组，查询本地域名服务器对应的 MAC 地址。这些帧的目的 MAC 地址均是 FF-FF-FF-FF-FF-FF。S 接收到这个帧，在交换表中记录下 MAC 地址为 00-11-22-33-44-cc，位于端口 4，然后广播该帧。当本地域名服务器接收到 ARP 请求后，向 H1 发送响应 ARP 分组。S 接收到这个帧，在交换表中记录下 MAC 地址为 00-11-22-33-44-bb 位于端口 1，然后把该帧从端口 4 发送出去。

得到了域名对应的 IP 地址，发现不在本局域网中，需要通过路由表转发。

H1 的 ARP 表中并没有路由器对应的 MAC 地址，因此需要先发送 ARP 请求分组，查询路由器对应的 MAC 地址。这些帧的目的 MAC 地址均是 FF-FF-FF-FF-FF-FF。S 接收到这个帧，广播该帧。当路由器收到 ARP 请求后，向 H1 发送响应 ARP 分组。S 接收到这个帧，在交换表中记录下 MAC 地址为 00-11-22-33-44-aa，位于端口 2，然后把该帧从端口 4 发送出去。现在，H1 能把数据发送给路由器了。在整个过程中，并没有涉及 H2，H2 没有主动发送数据。所以 S 并不会记录下 H2 的 MAC 地址和端口，所以 S 在 $t_1$ 时刻的交换表如下表所示。

3）H2 至少会接收到 2 个和此次 Web 访问相关的帧。接收到的均是封装 ARP 查询报文的以太网帧；这些帧的目的 MAC 地址均是 FF-FF-FF-FF-FF-FF。