2020年408真题

题目详解：
上三角矩阵按列优先存储，先存储仅 1 个元素的第一列，再存储有 2 个元素的第二列，以此类推。加 7,2 位于左下角，对应右上角的元素为加 2, 7 , 在加 2,7 之前存有

• 第 1 列：1
• 第 2 列：2
• ……
• 第 6 列：6
• 第 7 列：1

前面共存有 1 + 2 + 3 + 4 + 5 + 6 + 1 = 2 2 个 元 素（数组下标范围为 0〜21）, 注意数组下标 从 0 开始，故加工 7 在数组 N 中的下标为 2 2 , 即加 7,2 在数组 N 中的下标为 22。

正确答案：C

题目详解：
我们需要根据给定的操作序列 Push, Push, Pop, Push, Pop, Push, Push, Pop 来模拟栈的操作过程，并确定最终的出栈序列。初始时栈 $S$ 为空，入栈序列为 $a$, $b$, $c$, $d$, $e$。

1. 第一个操作 Push：将 $a$ 入栈，栈 $S$ 的状态为 $[a]$。
2. 第二个操作 Push：将 $b$ 入栈，栈 $S$ 的状态为 $[a, b]$。
3. 第三个操作 Pop：弹出栈顶元素 $b$，出栈序列为 $[b]$，栈 $S$ 的状态为 $[a]$。
4. 第四个操作 Push：将 $c$ 入栈，栈 $S$ 的状态为 $[a, c]$。
5. 第五个操作 Pop：弹出栈顶元素 $c$，出栈序列为 $[b, c]$，栈 $S$ 的状态为 $[a]$。
6. 第六个操作 Push：将 $d$ 入栈，栈 $S$ 的状态为 $[a, d]$。
7. 第七个操作 Push：将 $e$ 入栈，栈 $S$ 的状态为 $[a, d, e]$。
8. 第八个操作 Pop：弹出栈顶元素 $e$，出栈序列为 $[b, c, e]$，栈 $S$ 的状态为 $[a, d]$。

因此，最终的出栈序列是 $b$, $c$, $e$，对应选项 D。

正确答案：D

题目详解：
对于一棵高度为 $h$ 的二叉树，若采用顺序存储结构（即数组存储），为了保证能够存储所有可能的结点，需要的存储单元数量至少为 $2^h - 1$ 个。这是因为：

1. 顺序存储结构是按照完全二叉树的形式存储的，即使二叉树不是完全二叉树，也需要预留空间来保证逻辑结构的正确性。
2. 高度为 $h$ 的完全二叉树的最大结点数为 $2^h - 1$。

题目中给出二叉树的高度为 $5$，因此至少需要的存储单元数量为：

$$2^5 - 1 = 32 - 1 = 31$$

虽然题目中说明二叉树只有 $10$ 个结点，但顺序存储结构必须按照最坏情况（即完全二叉树）分配空间，因此至少需要 $31$ 个存储单元。

正确答案：A

题目详解：
本题考察的是森林的遍历， 森林 F 的先根遍历序列对应其二叉树 T 的先序遍历序列，森林 F 的中根遍历序列对应其二叉树 T 的中序遍历序列。即 T 的先序遍历序列为 a,b,c,d,e,f，中序遍历序列为 b,a,d,f,e,c。根据二叉树 T 的先序序列和中序序列可以唯一确定它的结构，构造过程如下：

可以得到二叉树 T 的后序序列为 b,f,e,d,c,a。

正确答案：C

题目详解：
选项 B 生成二叉排序树的过程如下，显然 B 选项错误：

题目详解：
在图的深度优先搜索（DFS）算法中，递归调用的顺序和顶点访问的顺序会影响最终的输出序列。原DFS算法在进入递归前输出顶点信息，而修改后的算法在退出递归前输出顶点信息。这种修改会导致顶点的输出顺序与递归的返回顺序一致，即后递归的顶点先输出。

对于有向无环图（DAG），拓扑排序是将顶点排成线性序列，使得对于图中的每一条有向边 $(u, v)$，$u$ 在序列中总是位于 $v$ 的前面。而逆拓扑排序则是将顶点排成线性序列，使得对于每一条有向边 $(u, v)$，$u$ 在序列中总是位于 $v$ 的后面。

修改后的DFS算法在退出递归前输出顶点，相当于按照递归返回的逆序输出顶点。这种顺序正好满足逆拓扑排序的定义，即对于任何边 $(u, v)$，$u$ 的输出总是在 $v$ 之后。因此，输出的顶点序列是 $G$ 的逆拓扑有序序列。

正确答案：B

题目详解：
Kruskal算法：按权值递增顺序依次选取$n-1$条边，并保证这$n-1$条边不构成回路。初始构造一个仅含$n$个顶点的森林；第一步，选取权值最小的边$(b,f)$加入最小生成树；第二步，剩余边中权值最小的边为$(b,d)$，加入最小生成树；第二步操作后权值最小的边$(d,f)$不能选，因为会与之前已选取的边形成回路；接下来依次选取权值$9$、$10$、$11$对应的边加入最小生成树，此时$6$个顶点形成了一棵树，最小生成树构造完成。按照上述过程，加到最小生成树的边依次为$(b,f)$、$(b,d)$、$(a,e)$、$(c,e)$、$(b,e)$。其生成过程如下所示。

题目详解：
在 AOE（Activity On Edge）网中，关键路径的确定和工程进度的估算是一个重要问题。以下是各选项的详细分析：

• 选项A：关键路径是从原点到汇点边数最多的一条路径。
  这是错误的。关键路径的定义与边数无关，而是与路径的总时间（即路径长度）有关。关键路径是完成工程所需时间最长的路径，而不是边数最多的路径。

• 选项B：关键路径是从原点到汇点路径长度最长的路径。
  这是正确的。关键路径的定义就是从起点（原点）到终点（汇点）具有最长路径长度的路径。这条路径的总时间决定了整个工程的最短完成时间。

• 选项C：增加任一关键活动的时间不会延长工程的工期。
  这是错误的。关键活动位于关键路径上，其时间的增加会直接导致关键路径的总时间增加，从而延长整个工程的工期。

• 选项D：缩短任一关键活动的时间将会缩短工程的工期。
  这是不完全正确的。虽然缩短关键活动的时间可能缩短工期，但如果存在多条关键路径，仅缩短其中一条关键路径上的活动时间可能不会影响整体工期，因为其他关键路径的总时间仍然不变。

综上所述，正确的叙述是 B。

正确答案：B

题目详解：
关于大根堆（至少含 2 个元素）的各个叙述分析如下：

I. 可以将堆视为一棵完全二叉树

• 堆在逻辑上是一棵完全二叉树，这是堆的基本性质之一。因此该叙述正确。

II. 可以采用顺序存储方式保存堆

• 完全二叉树通常采用顺序存储（数组）方式保存，堆作为完全二叉树自然可以采用顺序存储。因此该叙述正确。

III. 可以将堆视为一棵二叉排序树

• 堆和二叉排序树的性质不同：堆只要求父节点的值大于（或小于）子节点的值，而二叉排序树要求左子树所有节点小于根节点，右子树所有节点大于根节点。因此堆不一定是二叉排序树。该叙述错误。

IV. 堆中的次大值一定在根的下一层

• 在大根堆中，根节点是最大值，次大值可能是根的直接左孩子或右孩子（均在根的下一层），或者在更深的层中（但此时根的下一层必须有一个节点是次大值，否则违反堆的性质）。因此该叙述正确。

综上所述，正确的叙述是 I、II 和 IV。

正确答案：C

题目详解：
在4阶B树中，每个节点最多有3个关键字和4个子节点。插入过程如下：

1. 插入5：根节点为 $[5]$。
2. 插入6：根节点为 $[5, 6]$。
3. 插入9：根节点为 $[5, 6, 9]$。
4. 插入13：此时根节点 $[5, 6, 9, 13]$ 超过限制，需要分裂。中间关键字 $9$ 提升为新的根节点，左右子节点分别为 $[5, 6]$ 和 $[13]$。根节点为 $[9]$。
5. 插入8：插入到左子节点 $[5, 6, 8]$。
6. 插入2：插入到左子节点 $[2, 5, 6, 8]$，超过限制，分裂为 $[2, 5]$ 和 $[8]$，中间关键字 $6$ 提升到根节点。根节点为 $[6, 9]$。
7. 插入12：插入到右子节点 $[12, 13]$。
8. 插入15：插入到右子节点 $[12, 13, 15]$，超过限制，分裂为 $[12]$ 和 $[15]$，中间关键字 $13$ 提升到根节点。根节点为 $[6, 9, 13]$，超过限制，分裂为 $[6, 9]$ 和 $[13]$，中间关键字 $9$ 提升为新的根节点。最终根节点为 $[9]$，但题目问的是插入过程中根节点的关键字，在插入15之前，根节点为 $[6, 9]$。

正确答案是B。

题目详解：
直接插入排序和简单选择排序在大部分元素已有序的数组中的效率差异可以从以下几个方面分析：

1. 比较次数：

   • 直接插入排序在数组大部分有序时，每次插入操作只需比较少数元素即可找到正确位置，比较次数接近 $O(n)$。
   • 简单选择排序无论数组是否有序，每次都需要遍历剩余未排序部分找到最小（或最大）元素，比较次数固定为 $O(n^2)$。
   • 因此，I 是正确的。

2. 辅助空间：

   • 直接插入排序和简单选择排序都是原地排序算法，辅助空间复杂度均为 $O(1)$。
   • 因此，II 是错误的。

3. 移动次数：

   • 直接插入排序在插入元素时可能需要移动较多元素以腾出位置，移动次数与数组的有序程度相关，最坏情况下为 $O(n^2)$。
   • 简单选择排序每次交换仅需移动两个元素，移动次数固定为 $O(n)$。
   • 因此，III 是错误的。

综上所述，只有 I 是正确的。

正确答案：A

题目详解：
在计算机体系结构中，机器字长是指CPU一次能处理的二进制数据的位数。各部件与机器字长的关系如下：

1. ALU (算术逻辑单元)：是CPU的核心部件，负责执行算术和逻辑运算。ALU的位数 $n$ 必须与机器字长相同，因为它需要处理CPU一次能处理的完整数据。因此 I 正确。

2. 指令寄存器：用于存储当前正在执行的指令。其位数 $m$ 不一定与机器字长相同，而是由指令格式决定。例如，在变长指令集架构中，指令长度可能不等于机器字长。因此 II 错误。

3. 通用寄存器：用于存储操作数和中间结果，其位数 $k$ 通常与机器字长相同，以便高效处理数据。因此 III 正确。

4. 浮点寄存器：专门用于浮点运算，其位数 $p$ 通常与浮点数的标准格式（如IEEE 754）相关，可能大于机器字长（例如64位浮点数在32位机器上）。因此 IV 错误。

综上，只有 I (ALU) 和 III (通用寄存器) 的位数一定与机器字长相同。

正确答案：B

题目详解：
C800 0000H = 1100 1000 0000 0000 0000 0000 0000 0000

将其转换为对应的 float 或 int：

1. 为 float 型时，尾数隐藏最高位 1，数符为 1 表示负数，阶码 $10010000 = 2^{7} + 2^{4} = 128 + 16$，再减去偏置值 127 得到 17，算出 x 值为 $-2^{17}$。
2. 为 int 型时，带符号补码，为负数，数值部分取反加 1，得 $011 1000 0000 0000 0000 0000 0000 0000$，算出 x 值为 $-7 \times 2^{27}$。

正确答案：A

题目详解：
在按字节编址、采用小端方式的 32 位计算机中，结构体变量的存储分配如下：

1. 结构体 record 包含两个成员：

   • short x1：占用 $2$ 个字节。
   • int x2：占用 $4$ 个字节。

2. 由于采用边界对齐方式，int x2 的起始地址必须是 $4$ 的倍数。因此，结构体的存储布局如下：

   • short x1 占据地址 $2020\,FE00H$ 和 $2020\,FE01H$。
   • 为了对齐，$2020\,FE02H$ 和 $2020\,FE03H$ 会被填充（padding）。
   • int x2 从 $2020\,FE04H$ 开始，占据 $2020\,FE04H$ 到 $2020\,FE07H$。

3. 小端方式存储 int x2 的机器数 $1234\,0000H$ 时，低位字节存储在低地址：

   • $2020\,FE04H$：$00H$
   • $2020\,FE05H$：$00H$
   • $2020\,FE06H$：$34H$
   • $2020\,FE07H$：$12H$

4. 因此，$34H$ 所在的存储单元地址是 $2020\,FE06H$。

正确答案：D

题目详解：
TLB (Translation Lookaside Buffer) 和 Cache 是计算机系统中两种重要的高速缓存组件，但它们的设计和功能有所不同：

1. 命中率与程序局部性：

   • TLB 和 Cache 的命中率都与程序的局部性原理有关。TLB 利用的是地址访问的时空局部性，而 Cache 利用的是数据访问的时空局部性。因此，选项 A 是正确的。

2. 缺失后的访问行为：

   • 当 TLB 缺失时，需要查询页表（可能位于主存或 Cache 中）来获取地址转换信息。
   • 当 Cache 缺失时，需要访问主存来获取数据。
   • 因此，选项 B 是正确的。

3. 缺失处理的实现方式：

   • TLB 和 Cache 的缺失处理通常都可以由硬件实现（如 MMU 或 Cache 控制器）。因此，选项 C 是正确的。

4. 存储介质：

   • TLB 通常由 SRAM 组成，因为 SRAM 速度快，适合高频访问。
   • Cache 也通常由 SRAM 组成，同样是为了追求高速访问。
   • DRAM 一般用于主存，而不是 TLB 或 Cache。因此，选项 D 是错误的。

正确答案：D

题目详解：
首先，指令字长为 16 位，操作码位数和寻址方式位数固定。指令系统有 48 条指令，因此操作码位数 $n$ 需要满足 $2^n \geq 48$。计算得 $n = 6$（因为 $2^6 = 64 \geq 48$）。

支持 4 种寻址方式，因此寻址方式位数 $m$ 需要满足 $2^m \geq 4$，即 $m = 2$。

单地址指令的指令格式为：
$\text{操作码（6 位）} + \text{寻址方式（2 位）} + \text{地址码（8 位）}$。

直接寻址方式下，地址码部分直接表示操作数的地址，因此地址码的位数决定了可寻址范围。地址码为 8 位，无符号表示时的范围为 $0$ 到 $2^8 - 1$，即 $0$ 到 $255$。

正确答案：A

题目详解：
在计算机体系结构中，CPI（Cycles Per Instruction）表示执行一条指令所需的平均时钟周期数。不同类型的处理器设计会影响 CPI 的值。

1. 单周期 CPU（I）：每条指令在一个时钟周期内完成，因此 CPI 恒为 $1$ 。这是理想情况，但时钟周期长度由最慢的指令决定，效率较低。

2. 多周期 CPU（II）：每条指令被分解为多个阶段，每个阶段占用一个时钟周期。不同指令的周期数可能不同，因此 CPI 通常大于 $1$ ，具体取决于指令混合。

3. 基本流水线 CPU（III）：理想情况下，流水线可以做到每个时钟周期完成一条指令（CPI = $1$ ），尽管实际中可能因为流水线冲突（如数据冒险、控制冒险等）导致 CPI 略高于 $1$ 。

4. 超标量流水线 CPU（IV）：通过并行执行多条指令，理想情况下 CPI 可以小于 $1$ （如 $0.5$ 表示每个周期执行两条指令），但在题目中 CPI 为 $1$ 并非其理想情况。

综上所述，单周期 CPU 和 基本流水线 CPU 在理想情况下 CPI 为 $1$ ，因此正确答案是 B. 仅 I、III 。

正确答案：B

题目详解：
自陷（Trap）是计算机系统中一种特殊的异常或中断机制，其特点如下：

1. 自陷的本质：自陷是由程序主动触发的异常，通常通过执行特定的陷阱指令（如 $\text{INT}$、$\text{SYSCALL}$ 等）或由硬件检测到特定条件（如断点、单步调试）产生。因此，自陷是内部事件，而非选项A所述的“外部中断事件”。外部中断通常由硬件设备触发（如I/O完成）。

2. 自陷的用途：

   • 程序调试（选项B）：通过设置断点（触发 $\text{TRAP}$）或单步执行（每执行一条指令触发一次自陷）实现调试功能。
   • 系统调用：用户程序通过陷阱指令（如 $\text{INT 0x80}$）请求操作系统服务。

3. 自陷的处理流程：

   • 自陷发生后，CPU会保存当前上下文，并跳转到操作系统内核的预设处理程序执行（选项C正确）。
   • 处理完成后，CPU会恢复上下文，并返回到陷阱指令的下一条指令继续执行（选项D正确）。

4. 关键错误点：

   • 选项A的错误在于混淆了“自陷”与“外部中断”的来源。自陷是内部触发的同步事件，而外部中断是异步事件，由外设发起。

正确答案：A

题目详解：
QPI 总线的带宽计算步骤如下：

1. 时钟频率：QPI 时钟频率为 $2.4 \text{GHz}$，即每秒 $2.4 \times 10^9$ 个时钟周期。

2. 每次传输的数据量：每个 QPI 数据包有 $80$ 位信息，分 $2$ 个时钟周期传送，每个时钟周期传递 $2$ 次。因此，每次传输的数据量为：
   $\frac{80 \text{位}}{2 \text{时钟周期}} \times 2 \text{次} = 80 \text{位} = 10 \text{B}$
   （因为 $8 \text{位} = 1 \text{B}$）

3. 每秒传送次数：每秒的时钟周期数为 $2.4 \times 10^9$，每个时钟周期传输 $2$ 次，因此每秒传送次数为：
   $2.4 \times 10^9 \times 2 = 4.8 \times 10^9 \text{次}$

4. 总线带宽：根据公式 $\text{带宽} = \text{每秒传送次数} \times \text{每次传输的数据量}$，代入数值：
   $\text{带宽} = 4.8 \times 10^9 \times 10 \text{B} = 48 \times 10^9 \text{Bps} = 48 \text{GBps}$
   但是题目中给出的带宽公式为 $\text{每秒传送次数} \times 2 \text{B} \times 2$，这里需要重新理解题意。实际上，每次传输的 $80$ 位信息中，有效数据是 $16 \text{位} \times 2 = 32 \text{位} = 4 \text{B}$，因此每次传输的有效数据量为 $4 \text{B}$。

   重新计算带宽：
   $\text{带宽} = 4.8 \times 10^9 \times 4 \text{B} = 19.2 \times 10^9 \text{Bps} = 19.2 \text{GBps}$

因此，正确答案是 $19.2 \text{GBps}$。

正确答案：C

题目详解：
外部中断是指由 CPU 外部设备或事件引发的中断，通常与当前执行的指令无关。我们需要分析每个选项是否属于外部中断：

I. 访存时缺页：这是由 CPU 执行访存指令时触发的异常（内部中断），属于 内部中断事件，因为它是当前指令执行过程中产生的。

II. 定时器到时：这是由外部定时器硬件触发的信号，属于 外部中断事件，因为它与 CPU 当前执行的指令无关。

III. 网络数据包到达：这是由网卡等外部设备触发的信号，属于 外部中断事件，因为它是由外部设备引发的。

因此，仅 II 和 III 属于外部中断事件。

正确答案：C

题目详解：
不可屏蔽中断（NMI）和可屏蔽中断是外部中断的两种类型，它们的特性和处理方式有所不同：

1. 不可屏蔽中断（NMI）：

   • NMI 的优先级高于可屏蔽中断，且不受 CPU 关中断状态的影响。即使 CPU 处于关中断状态（即 $\text{IF} = 0$），也能响应 NMI 请求。因此选项 A 和 C 是正确的。

2. 可屏蔽中断：

   • 可屏蔽中断的响应需要满足两个条件：中断请求信号有效（$\text{IRQ} = 1$）且 CPU 处于开中断状态（$\text{IF} = 1$）。如果 CPU 处于关中断状态，即使中断请求信号有效，也不会立即响应。因此选项 B 是错误的。
   • 可屏蔽中断的处理优先级可以通过中断屏蔽字（$\text{IMR}$）动态调整，因此选项 D 是正确的。

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

正确答案：B

题目详解：
在周期挪用（Cycle Stealing）DMA 方式下，DMA 控制器和 CPU 交替使用总线。具体分析如下：

1. 选项 A：I/O 接口的数据缓冲寄存器为 $32$ 位（即 $4$ 字节），每次准备好 $32$ 位数据后，DMA 控制器会发出一次总线请求以传输数据。因此，对于 $512$ 字节的数据块，需要传输 $\frac{512}{4} = 128$ 次。此叙述正确。

2. 选项 B：在周期挪用 DMA 方式中，DMA 控制器的总线优先级高于 CPU，以确保数据能够及时传输。此叙述正确。

3. 选项 C：周期挪用 DMA 方式的特点是 DMA 控制器和 CPU 交替使用总线，因此 CPU 仍然可以访问主存，只是可能会被 DMA 控制器暂时“挪用”总线周期。此叙述错误。

4. 选项 D：数据块传送结束时，DMA 控制器会通过中断通知 CPU 传输完成。此叙述正确。

正确答案：C

题目详解：
在多进程共享同一个文件 $F$ 时，操作系统的文件管理机制如下：

1. 打开方式：进程可以以多种方式（如读、写、读写等）打开文件 $F$，因此选项 A 错误。

2. 系统打开文件表：系统打开文件表是全局的，每个文件 $F$ 在其中仅有一个表项，用于存储文件的属性（如 inode、文件大小等）。因此选项 B 正确。

3. 用户打开文件表：每个进程的用户打开文件表中关于 $F$ 的表项是独立的，可能包含不同的文件偏移量、打开模式等信息，因此选项 C 错误。

4. 关闭文件：当一个进程关闭文件 $F$ 时，系统仅减少该文件的引用计数，直到所有进程都关闭 $F$ 后，才会删除其在系统打开文件表中的表项。因此选项 D 错误。

正确答案：B

题目详解：
在磁盘存储空间分配方式中，题目要求支持 文件长度可变 和 随机访问 的特性。我们逐一分析各选项：

• A. 索引分配：
  索引分配通过为每个文件建立一个 索引块，其中存储了该文件的所有物理块指针。这种方式允许文件长度动态变化（只需扩展索引块），并且支持随机访问（通过索引直接定位任意块）。因此，索引分配满足题目要求。

• B. 链接分配：
  链接分配通过 链表 结构存储文件块，每个块包含指向下一个块的指针。虽然支持文件长度可变，但无法直接随机访问（必须从头遍历链表），因此不满足题目要求。

• C. 连续分配：
  连续分配要求文件占用 连续的物理块。虽然支持随机访问（通过偏移量计算），但文件长度固定后难以动态扩展（容易产生碎片），因此不满足题目要求。

• D. 动态分区分配：
  动态分区分配是内存管理技术，与磁盘文件分配无关，属于干扰项。

综上，只有 索引分配 同时满足 文件长度可变 和 随机访问 的需求。

正确答案：A

题目详解：
在计算机系统中，中断处理涉及多个操作，其中部分由硬件完成，部分由操作系统完成。具体分析如下：

1. 保存被中断程序的中断点（I）：
   这一操作通常由硬件自动完成，当发生中断时，硬件会将当前程序计数器（PC）的值（即中断点）压入栈中，以便后续恢复执行。

2. 提供中断服务（II）：
   这是操作系统的核心职责之一。操作系统需要根据中断类型调用相应的中断服务程序（ISR）来处理中断。

3. 保存中断屏蔽字（IV）：
   这一操作由操作系统完成。中断屏蔽字用于记录当前中断的屏蔽状态，操作系统需要在处理中断前保存其值，以便后续恢复。

4. 初始化中断向量表（III）：
   这是操作系统的初始化任务之一。中断向量表是一个存储中断服务程序入口地址的数据结构，操作系统在启动时负责初始化它。

综上所述，由操作系统完成的操作是 II（提供中断服务）、III（初始化中断向量表）和 IV（保存中断屏蔽字）。因此，正确答案是 D。

正确答案：D

题目详解：
多级反馈队列调度算法（Multilevel Feedback Queue Scheduling）是一种复杂的进程调度算法，其设计需要考虑以下关键因素：

1. 就绪队列的数量（I）：该算法需要设置多个就绪队列，通常队列数量是预先定义的，例如 $Q_1, Q_2, \ldots, Q_n$。每个队列具有不同的优先级或时间片大小。

2. 就绪队列的优先级（II）：不同队列的优先级通常不同，例如 $Q_1$ 的优先级高于 $Q_2$，依此类推。高优先级队列中的进程会被优先调度。

3. 各就绪队列的调度算法（III）：每个队列可以采用不同的调度策略，例如高优先级队列可能使用时间片轮转（Round Robin），而低优先级队列可能使用先来先服务（FCFS）。

4. 进程在就绪队列间的迁移条件（IV）：进程会根据其执行情况动态迁移队列。例如，若进程在一个时间片内未完成，则可能被降级到低优先级队列；反之，若进程自愿放弃CPU（如I/O操作），则可能被升级到高优先级队列。

综上所述，多级反馈队列调度算法的设计需要全面考虑以上四个因素，因此正确答案是 D. I、II、III 和 IV。

题目详解：
首先求出需求矩阵：

由 Allocation 得知当前 Available 为 (1,0)。由需求矩阵可知，初始只能满足 P2 的需求，选 项 A 错误。P2 释放资源后 Available 变为 (3,1)，此时仅能满足 P1 的需求，选 项 C 错误。 P1 释放资源后 Available 变为 (5,4)，可以满足 P 3 的需求，得到的安全序列为 P2, Pl, P3, 选项 B 正确，选项 D 错误。

题目详解：
在请求分页系统中，有效（平均）访存时间（Effective Memory Access Time, EMAT）的计算公式为：

$EMAT = (1 - p) \times t_{memory} + p \times (t_{page\_fault} + t_{disk} + t_{memory})$

其中：

• $p$ 表示缺页率（I），即访问页面时发生缺页的概率。
• $t_{memory}$ 表示内存访问时间（III），即访问内存中页面的时间。
• $t_{page\_fault}$ 表示执行缺页处理程序的 CPU 时间（IV），即处理缺页异常所需的 CPU 时间。
• $t_{disk}$ 表示磁盘读写时间（II），即从磁盘读取页面到内存的时间。

因此，缺页率（I）、磁盘读写时间（II）、内存访问时间（III）和执行缺页处理程序的 CPU 时间（IV）均会影响有效访存时间。

正确答案：D

题目详解：
在操作系统中，父进程和子进程之间的关系和特性如下：

1. 并发执行（A选项）：父进程和子进程可以并发执行，这是多进程系统的基本特性。父进程通过 fork() 系统调用创建子进程后，两者可以独立运行。

2. 虚拟地址空间（B选项）：父进程和子进程 不共享 虚拟地址空间。虽然子进程在创建时会继承父进程的地址空间副本（通过写时复制技术优化），但它们是独立的。因此，B选项是错误的。

3. 进程控制块（C选项）：每个进程都有自己独立的进程控制块（PCB），用于存储进程的状态、寄存器、PID等信息。父进程和子进程的PCB是不同的。

4. 临界资源（D选项）：临界资源是同一时刻只能被一个进程访问的资源。父进程和子进程作为独立进程，不能同时使用同一临界资源，需要通过同步机制（如互斥锁）协调访问。

正确答案：B

题目详解：
设备独立性是指用户程序与物理设备之间的独立性，即用户程序不需要直接依赖于特定的物理设备。系统通过逻辑设备名和物理设备之间的映射关系来实现这一特性。具体分析如下：

• A选项：正确。具备设备独立性的系统允许用户使用文件名（逻辑设备名）来访问物理设备，而无需关心具体的物理设备细节。

• B选项：正确。用户程序通过逻辑设备名访问物理设备，系统负责将逻辑设备名映射到实际的物理设备。

• C选项：正确。为了实现设备独立性，系统需要维护逻辑设备与物理设备之间的映射关系，通常由操作系统管理。

• D选项：错误。设备独立性的核心优势在于更换物理设备时，用户程序无需修改，只需更新逻辑设备与物理设备之间的映射关系即可。

正确答案：D

题目详解：
该题目考察的是文件系统中文件数量的上限计算。关键点在于理解索引结点号的位数决定了文件数量的上限。

1. 目录项结构：

   • 每个目录项长度为 $64$ 字节。
   • 其中 $4$ 字节存放索引结点号，$60$ 字节存放文件名。

2. 文件数量上限的决定因素：

   • 文件数量的上限由索引结点号的位数决定，因为每个文件需要一个唯一的索引结点号。
   • 索引结点号占用 $4$ 字节，即 $4 \times 8 = 32$ 位。
   • 因此，索引结点号可以表示的唯一数量为 $2^{32}$。

3. 文件名的限制：

   • 文件名占用 $60$ 字节，但文件名的长度和内容不影响文件数量的上限，因为文件数量由索引结点号的唯一性决定。

综上所述，该文件系统能创建的文件数量的上限为 $2^{32}$。

正确答案：B

题目详解：
临界区互斥机制必须遵循以下准则：

1. 互斥性（I）： $两个进程不能同时进入临界区$ 。这是临界区最基本的特性，确保共享资源在同一时间只能被一个进程访问。

2. 空闲让进（II）： $允许进程访问空闲的临界资源$ 。当临界区没有被占用时，任何请求进入临界区的进程应该能够立即进入。

3. 有限等待（III）： $进程等待进入临界区的时间是有限的$ 。避免进程无限期等待，确保系统不会出现死锁或饥饿现象。

4. 让权等待（IV）： $不能进入临界区的执行态进程立即放弃 CPU$ 。这一准则并非必须遵循，虽然它可以提高 CPU 利用率，但并不是互斥机制的基本要求。

综上，必须遵循的准则是 I、II、III，因此正确答案是 C。

正确答案：C

题目详解：
协议由语法、语义和时序（又称同步）三部分组成。语法规定了通信双方彼此“如何讲”， 即规定了传输数据的格式。语义规定了通信双方彼此“讲什么”，规定了所要完成的功能， 如通信双方要发出什么控制信息、执行的动作和返回的应答。时序规定了信息交流的次序。 由图可知发送方与接收方依次交换信息，体现了协议三要素中的时序要素。

题目详解：
在虚电路网络中，以下是对各选项的详细分析：

A. 可以确保数据分组传输顺序：虚电路网络通过预先建立的路径传输数据，所有分组沿着同一路径传输，因此可以保证分组的顺序。该叙述正确。

B. 需要为每条虚电路预分配带宽：虚电路网络在建立虚电路时并不需要预分配带宽，而是采用统计复用方式共享网络资源。预分配带宽是电路交换的特点，因此该叙述错误。

C. 建立虚电路时需要进行路由选择：在虚电路建立阶段，网络需要确定一条从源到目的的路径，即进行路由选择。该叙述正确。

D. 依据虚电路号（VCID）进行数据分组转发：虚电路网络中的每个分组携带虚电路号（VCID），交换机根据VCID查找转发表进行转发。该叙述正确。

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

正确答案：B

题目详解：
网络层设备路由器可以隔离广播域和冲突域；链路层设备普通交换机只能隔离冲突域；物 理层设备集线器、中继器既不能隔离冲突域又不能隔离广播域。因此，题中共有 2 个广播 域、4 个冲突域。

题目详解：
在停-等协议中，最大信道利用率 $U$ 可以通过以下公式计算：

$U = \frac{T_{data}}{T_{data} + T_{ack} + 2T_{prop}}$

其中：

• $T_{data}$ 是发送数据帧的时间，
• $T_{ack}$ 是发送确认帧的时间，
• $T_{prop}$ 是单向传播延时。

首先计算 $T_{data}$ 和 $T_{ack}$：

• 数据帧和确认帧的长度均为 $1000B$（即 $8000$ 比特），
• 数据传输速率为 $10kbps$（即 $10000$ bps），
• 因此 $T_{data} = T_{ack} = \frac{8000}{10000} = 0.8$ 秒。

单向传播延时 $T_{prop}$ 为 $200ms$（即 $0.2$ 秒）。

将数值代入公式：

$U = \frac{0.8}{0.8 + 0.8 + 2 \times 0.2} = \frac{0.8}{0.8 + 0.8 + 0.4} = \frac{0.8}{2.0} = 0.4$

因此，最大信道利用率为 $40\%$。

正确答案：D

题目详解：
为了尽量避免碰撞，IEEE 802.11规定，所有站在完成发送后，必须等待一段很短的时间（继续 监听）才能发送下一帧。这段时间称为帧间间隔（InterFrame Space, IFS）。帧间间隔的长 短取决于该站要发送的帧的类型。IEEE 802.11 使 用 3 种帧间间隔：

• DIFS（分布式协调 IFS）：最长的 IFS , 优先级最低，用于异步帧竞争访问的时延。
• PIFS（点协调 IFS）：中等长度的 IFS , 优先级居中，在 PC F 操作中使用。
• SIFS（短 IFS）：最短的 IFS , 优先级最高，用于需要立即响应的操作。

网络中的控制帧及所接收数据的确认帧都采用 SIFS 作为发送之前的等待时延。当结点要发 送数据帧时，载波监听到信道空闲时，需等待 DIFS 后发送 RTS 预约信道，图中 IFS1 对应 的是帧间间隔 DIFS，时间最长，图中 IFS2、IFS3、IFS4 对应 SIFS。

题目详解：
TCP 拥塞控制采用慢启动和拥塞避免算法。题目中拥塞窗口从 $8KB$ 增长到 $32KB$ 的过程分为两个阶段：

1. 慢启动阶段：拥塞窗口从 $8KB$ 开始，每经过一个 $RTT$ 窗口大小翻倍，直到达到慢启动阈值（ssthresh）。假设初始阈值为 $16KB$（题目未明确给出，但通常慢启动阈值初始值较高），则过程如下：

   • $8KB \rightarrow 16KB$：经过 $1$ 个 $RTT$（$2ms$）。
   • 达到 $16KB$ 后进入拥塞避免阶段。

2. 拥塞避免阶段：拥塞窗口每经过一个 $RTT$ 增加 $1MSS$（$1KB$），直到达到 $32KB$：

   • $16KB \rightarrow 17KB \rightarrow 18KB \rightarrow \cdots \rightarrow 32KB$。
   • 窗口从 $16KB$ 增长到 $32KB$ 需要增加 $16KB$，每次增加 $1KB$，因此需要 $16$ 个 $RTT$（$16 \times 2ms = 32ms$）。

但题目中初始窗口为 $8KB$，且未说明慢启动阈值，更合理的分析是直接计算从 $8KB$ 到 $32KB$ 的线性增长（拥塞避免阶段）：

• 窗口从 $8KB$ 增长到 $32KB$ 需要增加 $24KB$，每次增加 $1KB$，因此需要 $24$ 个 $RTT$（$24 \times 2ms = 48ms$）。

因此，最长时间为 $48ms$。

正确答案：D

题目详解：
在 TCP 连接中，序号（Sequence Number）用于标识发送的数据字节流。建立连接时，主机甲发送的 SYN 段中的序号为 $1000$，这是一个初始序号（ISN）。断开连接时，主机甲发送的 FIN 段中的序号为 $5001$。FIN 段会占用一个序号，因此实际应用层数据的最后一个字节的序号为 $5000$。

计算甲向乙发送的应用层数据的字节数，公式为：
$\text{应用层数据字节数} = \text{最后一个字节的序号} - \text{初始序号}$
$\text{应用层数据字节数} = 5000 - 1000 = 4000$

因此，甲向乙已经发送的应用层数据的字节数为 $4000$。

正确答案：C

题目详解：
题中 RTT 均为局域网内主机（主机 H、本地域名服务器）访 问 Internet 上各服务器的往返 时间，且忽略其他时延，因此主机 H 向本地域名服务器的查询时延忽略不计。最短时间： 本地主机中有该域名到 IP 地址对应的记录，因此不需要 DNS 查询时延，直接和 www.abc.com服务器建立 TCP 连接再进行资源访问，TCP 连接建立需要 1 个 RTT，接着发 送访问请求并收到服务器资源响应需要 1 个 RTT，共计 2 个 RTT，即 20ms；最长时间：本 地主机递归查询本地域名服务器（延时忽略），本地服务器依次迭代查询根域名服务器、com 顶级域名服务器、abc.com 域名服务器，共 3 个 RTT，查询到 IP 地址后，将该映射返回给 主机 H，主机 H 和 www.abc.com服务器建立 TCP 连接再进行资源访问，共 2 个 RTT，因 此最长时间需要 3+2=5 个 RTT，即 50ms。

题目详解：
分析，由 $D = |a-b|+|b-c|+|c-a| \ge 0$ 得：

① 当 $a = b = c$ 时，距离最小。

② 其余情况。不失一般性，假设观察下面的数轴：

$L_1 = |a-b|$，$L_2 = |b-c|$，$L_3 = |c-a|$，$D = |a-b| + |b-c| + |c-a| = L_1 + L_2 + L_3 = 2L_3$

由 $D$ 的表达式可知，事实上决定 $D$ 大小的关键是 $a$ 和 $c$ 之间的距离，于是问题就可以简化为每次固定 $c$ 找一个 $a$ 使得 $L_3 = |c-a|$ 最小。

1）算法的基本设计思想

• 使用 $D_{min}$ 记录所有已处理过的三元组的最小距离，初值为一个足够大的整数。
• 集合 $S_1$、$S_2$ 和 $S_3$，分别保存在数组 $A$、$B$、$C$ 中。数组的下标变量 $i = j = k = 0$，当 $i < |S_1|$、$j < |S_2|$ 且 $k < |S_3|$ 时（$|S|$ 表示集合 $S$ 中的元素个数），循环执行以下过程：
  • 计算（$A[i]$，$B[j]$，$C[j]$）的距离 $D$；（计算 $D$）
  • 若 $D < D_{min}$，则 $D_{min} = D$；（更新 $D$)
  • 将 $A[i]$，$B[i]$，$C[j]$ 中的最小值的下标 $+1$；（对照分析：最小值为 $a$，最大值为 $c$，这里 $c$ 不变而更新 $a$，试图寻找更小距离 $D$）
• 输出 $D_{min}$，结束。

2）算法实现

void solve(int S1[], int n1, int S2[], int n2, int S3[], int n3) {
  int i = 0, j = 0, k = 0;
  int res = INT32_MAX;
  while (i < n1 && j < n2 && k < n3) {
    int a = S1[i], b = S2[j], c = S3[k];
    int D = abs(a-b) + abs(b-c) + abs(a-c);
    res = min(res, D);
    int v = min3(a, b, c);
    if (v == a) {
      i++;
    } else if (v == b) {
      j++;
    } else {
      k++;
    }
  }
  return res;
}

3）设 $n = |S_1| + |S_2| + |S_3|$，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

题目详解：

1. 使用一棵二叉树保存字符集中各字符的编码，每个编码对应于从根开始到达某叶结点的一条路径，路径长度等于编码位数，路径到达的叶结点中保存该编码对应的字符。

2. 从左至右依次扫描0/1串中的各位。从根开始，根据串中当前位沿当前结点的左子指针或右子指针下移，直到移动到叶结点时为止。输出叶结点中保存的字符。然后从根开始重复这个过程，直到扫描到0/1串结束，译码完成。

3. 二叉树既可用于保存各字符的编码，又可用于检测编码是否具有前缀特性。判定编码是否具有前缀特性的过程，也是构建二叉树的过程。初始时，二叉树中仅含有根结点，其左子指针和右子指针均为空。

依次读入每个编码$C$，建立/寻找从根开始对应于该编码的一条路径，过程如下：

对每个编码，从左至右扫描$C$的各位，根据$C$的当前位（0或1）沿结点的指针（左子指针或右子指针）向下移动。当遇到空指针时，创建新结点，让空指针指向该新结点并继续移动。沿指针移动的过程中，可能遇到三种情况：

• 若遇到了叶结点（非根），则表明不具有前缀特性，返回。
• 若在处理$C$的所有位的过程中，均没有创建新结点，则表明不具有前缀特性，返回。
• 若在处理$C$的最后一个编码位时创建了新结点，则继续验证下一个编码。

若所有编码均通过验证，则编码具有前缀特性。

题目详解：

1. 乘法运算可以通过加法和移位来实现。编译器可以将乘法运算转换为一个循环代码段，在循环代码段中通过比较、加法和移位等指令实现乘法运算。

2. 控制逻辑的作用是控制循环次数，控制加法和移位操作。

3. ①最长，③最短。对于①，需要用循环代码段（即软件）实现乘法操作，因而需要反复执行很多条指令，而每条指令都需要取指令、译码、取数、执行并保存结果，所以执行时间很长；对于②和③，都只需用一条乘法指令实现乘法操作，不过②中的乘法指令需要多个时钟周期才能完成，而③中的乘法指令可以在一个时钟周期内完成，所以③的执行时间最短。

4. 当 $n=32$，$x=2^{31}-1$，$y=2$ 时，带符号整数和无符号整数乘法指令得到的64位乘积都是 00000000 FFFF FFFEH。int 型的表示范围为 $[-2^{31},2^{31}-1]$，故函数 imul() 的结果溢出；unsigned int 型的表示范围为 $[0,2^{32}-1]$，故函数 umul() 的结果不溢出。对于无符号整数乘法，若乘积高 $n$ 位全为 $0$，即使低 $n$ 位全为 $1$ 也正好是 $2^{32}-1$，不溢出，否则溢出。

题目详解：
1）主存块大小为 $64B=2^6$ 字节，所以主存地址低 6 位为块内地址，Cache 组数为 $32KB/(64B×8) = 64 = 2^6$，故主存地址中间 6 位为 Cache 组号，主存地址中高 $32-6-6 =20$ 位为标记，采用 8 路组相联映射，故每行中的 LRU 位占 3 位，采用直写方式，故没有修改位。

2）$0080\,00C0H = 0000\,0000\,1000\,0000\,0000\,0000\,1100\,0000B$，主存地址的低 6 位为块内地址，为全 0，故 s 位于一个主存块的开始处，占 $1024×4B/64B=64$ 个主存块：在执行程序段的过程中，每个主存块中的 $64B/4B=16$ 个数组元素依次读、写 1 次，因而对每个主存块，总是第一次访问缺失，此时会将整个主存块调入 Cache，之后每次都命中。综上，数组 s 的数据 Cache 访问缺失次数为 64 次。

3）$0001\,0003H = 0000\,0000\,0000\,0001\,0000\,0000\,0000\,0011B$，根据主存地址划分可知，组索引为 0，故该地址所在主存块被映射到指令 Cache 的第 0 组；因为 Cache 初始为空，所有 Cache 行的有效位均为 0，所以 Cache 访问缺失。此时，将该主存块取出后存入指令 Cache 的第 0 组的任意一行，并将主存地址高 20 位（$00010H$）填入该行标记字段，设置有效位，修改 LRU 位，最后根据块内地址 $000011B$ 从该行中取出相应的内容。

题目详解：
本题要求实现操作的先后顺序，没有互斥关系，是一个简单的同步问题。本题虽然有5个操作，但是只有4个同步关系，因此分别设置信号量$SAC$、$SBC$、$SCE$和$SDE$对应4个同步关系。

semaphore SAC = 0; // 实现 A 是 C 的前驱关系
semaphore SBC = 0; // 实现 B 是 C 的前驱关系
semaphore SCE = 0; // 实现 C 是 E 的前驱关系
semaphore SDE = 0; // 实现 D 是 E 的前驱关系

A() {
  操作A;
  V(SAC);
}

B() {
  操作B;
  V(SBC);
}

C() {
  P(SAC);
  P(SBC);
  操作C;
  V(SCE);
}

D() {
  操作D;
  V(SDE);
}

E() {
  P(SCE);
  P(SDE);
  操作E;
}

题目详解：
1） ①页面大小 = $2^{12}$B = 4096B = 4KB。每个数组元素 4B，每个页面可以存放 4KB/4B = 1024 个数组元素，正好是数组的一行，数组 $a$ 按行优先方式存放。10800000H 的虚页号为 10800H，因此 $a[0]$ 行存放在虚页号为 10800H 的页面中，$a[1]$ 行存放在页号为 10801H 的页面中。$a[1][2]$ 的虚拟地址为 10801000H + 4 × 2 = 10801008H。

②转换为二进制 0001 0000 1000 0000 0001 0000 0000 1000，根据虚拟地址结构可知，对应的页目录号为 042H，页号为 001H。

③进程的页目录表起始地址为 00201000H，每个页目录项长 4B，因此 042H 号页目录项的物理地址是 00201000H + 4 × 42H = 00201108H。

④页目录项存放的页框号为 00301H，二级页表的起始地址为 00301000H，因此 $a[1][2]$ 所在页的页号为 001H，每个页表项 4B，对应的页表项物理地址是 00301000H + 001H × 4 = 00301004H。

2） 根据数组的随机存取特点，数组 $a$ 在虚拟地址空间中所占的区域必须连续，由于数组 $a$ 不止占用一页，相邻逻辑页在物理上不一定相邻，因此数组 $a$ 在物理地址空间中所占的区域可以不连续。

3） 由 1）可知每个页面正好可以存放一整行的数组元素，“按行优先方式存放”意味着数组的同一行的所有元素都存放在同一个页面中，同一列的各个元素都存放在不同的页面中，因此数组 $a$ 按行遍历的局部性较好。

题目详解：
1）两个子网使用了相同的网段，且路由器开启了 NAT 功能，加上题干给出了 NAT 表的结构，因此需要配置 NAT 表。路由器 R2 开启 NAT 服务，当路由器 R2 从 WAN 口收到 H2 或 H3 发来的数据时，根据 NAT 表发送给 Web 服务器的对应端口。外网 IP 地址应该为路由器的外端 IP 地址，内网 IP 地址应该为 Web 服务器的地址，Web 服务器的默认端口为 80，因此内网端口号固定为 80，当其他网络的主机访问 Web 服务器时，默认访问的端口应该也是 80，但是访问的目的 IP 是路由器的 IP 地址，因此 NAT 表中的外部端口最好也统一为 80。题目中并未要求对 H1 进行访问，因此 H1 的 NAT 表项可以不写。R2 的 NAT 表配置如下：

2）由于启用了 NAT 服务，H2 发送的 IP 的源 IP 地址应该是 H2 的内网地址，目的地址应该是 R2 的外网 IP 地址，源 IP 地址是 $192.168.1.2$，目的 IP 地址是 $203.10.2.2$。R3 转发后，将 IP 的源 IP 地址改为 R3 的外网 IP 地址，目的 IP 地址仍然不变，源 IP 地址是 $203.10.2.6$，目的 IP 地址是 $203.10.2.2$。R2 转发后，将 IP 的目的 IP 地址改为 Web 服务器的内网地址，源地址仍然不变，源 IP 地址是 $203.10.2.6$，目的 IP 地址是 $192.168.1.2$。