2023年408真题

题目详解：
顺序存储的有序表是指元素在内存中连续存储，并且按照一定的顺序（如升序或降序）排列。我们需要分析每个选项的操作在顺序存储的有序表中的平均时间复杂度：

A. 查找包含指定值元素的算法：由于表是有序的，可以使用二分查找，其时间复杂度为 $O(\log n)$ ，不是 $O(1)$ 。

B. 插入包含指定值元素的算法：插入操作需要找到合适的位置（时间复杂度为 $O(\log n)$ 或 $O(n)$ ），并移动后续元素（最坏情况下需要移动 $O(n)$ 个元素），因此平均时间复杂度为 $O(n)$ ，不是 $O(1)$ 。

C. 删除第 $i$ （1≤ $i$ ≤ $n$ ）个元素的算法：删除操作需要移动后续元素（最坏情况下需要移动 $O(n)$ 个元素），因此平均时间复杂度为 $O(n)$ ，不是 $O(1)$ 。

D. 获取第 $i$ （1≤ $i$ ≤ $n$ ）个元素的算法：顺序存储的有序表支持随机访问，可以直接通过下标 $i$ 获取元素，时间复杂度为 $O(1)$ 。

正确答案：D

题目详解：
在双向链表中插入一个新结点 $s$ 到结点 $p$ 之后，需要正确调整前驱和后继指针。初始状态下，$p$ 的后继结点为 $q$（即 $q = p \rightarrow \text{next}$）。插入操作分为以下步骤：

1. 首先执行 $s \rightarrow \text{next} = p \rightarrow \text{next}$，将 $s$ 的后继指向 $q$。
2. 然后执行 $p \rightarrow \text{next} = s$，将 $p$ 的后继指向 $s$。

此时，还需要调整 $s$ 的前驱指针和 $q$ 的前驱指针：

3. 执行 $s \rightarrow \text{prev} = s \rightarrow \text{next} \rightarrow \text{prev}$，即 $s \rightarrow \text{prev} = q \rightarrow \text{prev}$，将 $s$ 的前驱指向 $p$（因为 $q \rightarrow \text{prev}$ 原本指向 $p$）。
4. 最后执行 $s \rightarrow \text{next} \rightarrow \text{prev} = s$，即 $q \rightarrow \text{prev} = s$，将 $q$ 的前驱指向 $s$。

因此，完整的语句序列为：
$s \rightarrow \text{next} = p \rightarrow \text{next};$
$p \rightarrow \text{next} = s;$
$s \rightarrow \text{prev} = s \rightarrow \text{next} \rightarrow \text{prev};$
$s \rightarrow \text{next} \rightarrow \text{prev} = s;$

对应选项 C 的描述。

正确答案：C

题目详解：
稀疏矩阵的三元组表存储结构通常需要存储以下信息：

1. 每个非零元素的行下标 $i$
2. 每个非零元素的列下标 $j$
3. 非零元素的值 $v$

此外，为了完整描述稀疏矩阵的结构，还需要保存矩阵的总行数和总列数。这是因为：

• 矩阵的总行数 $rows$ 和总列数 $cols$ 定义了矩阵的维度，是稀疏矩阵的基本属性。
• 非零元素的行数和列数可以通过遍历三元组表统计得到，无需额外存储。

因此，题目中需要保存的数据是：

I. M 的行数（必须保存）
III. M 的列数（必须保存）

而 II 和 IV 是非必要信息，因为它们可以从三元组表中推导出来。

正确答案：A

题目详解：
首先，我们需要理解哈夫曼编码的构造过程以及加权平均长度的计算方法。哈夫曼编码是一种用于无损数据压缩的贪心算法，通过为出现频次高的字符分配较短的编码，为出现频次低的字符分配较长的编码，从而达到压缩数据的目的。加权平均长度是指所有字符的编码长度乘以其出现频次的总和，再除以总频次。

给定字符集 $S$ 中各字符的出现频次为 $3, 4, 5, 6, 8, 10$。总频次为：

$$3 + 4 + 5 + 6 + 8 + 10 = 36$$

接下来，我们按照哈夫曼编码的步骤构造编码树：

1. 将频次从小到大排序：$3, 4, 5, 6, 8, 10$。
2. 取出频次最小的两个节点 $3$ 和 $4$，合并为一个新节点 $7$（$3 + 4$），此时剩余的节点为 $5, 6, 7, 8, 10$。
3. 取出频次最小的两个节点 $5$ 和 $6$，合并为一个新节点 $11$（$5 + 6$），此时剩余的节点为 $7, 8, 10, 11$。
4. 取出频次最小的两个节点 $7$ 和 $8$，合并为一个新节点 $15$（$7 + 8$），此时剩余的节点为 $10, 11, 15$。
5. 取出频次最小的两个节点 $10$ 和 $11$，合并为一个新节点 $21$（$10 + 11$），此时剩余的节点为 $15, 21$。
6. 最后合并 $15$ 和 $21$，得到根节点 $36$（$15 + 21$）。

构造的哈夫曼树如下：

• 频次为 $3$ 和 $4$ 的字符编码长度为 $3$。
• 频次为 $5$ 和 $6$ 的字符编码长度为 $3$。
• 频次为 $8$ 的字符编码长度为 $2$。
• 频次为 $10$ 的字符编码长度为 $2$。

因此，加权平均长度的计算如下：

$$\text{加权平均长度} = \frac{(3 \times 3) + (4 \times 3) + (5 \times 3) + (6 \times 3) + (8 \times 2) + (10 \times 2)}{36} = \frac{9 + 12 + 15 + 18 + 16 + 20}{36} = \frac{90}{36} = 2.5$$

正确答案：B

题目详解：
如下图所示。对于后序序列 fdbeca，a 为树节点的根，因此在序号 1 中，a 首先进行绘制。同时，a 节点的左子树有 4 个节点，右子树有 1 个节点，因此 fdbe 属于左子树，c 节点属于右子树，所以我们在序号 2 的树中，填充 c。a 结点左子树的后序遍历序列为 fdbe，代表 e 为左子树的根节点，因此在序号 3 的树中，填充 e。同理 e 节点的左子树有两个节点，右子树有一个节点，因此 fdb 属于左子树，e 属于右子树，在序号 4 的树中，我们填写 b。e 的左子树的后序遍历序列为 fd，则 d 为子树的根节点，因此在序号 5 的树中，我们填充 d，最后在序号 6 的图中，填充 f。先序序列为 a，e，d，f，b，c。本题答案选 A。

题目详解：
题目中给出的图 $G$ 是一个无向连通图，且各边的权值均为 1。我们需要找到一个算法，能够求出从某顶点到其余各顶点的最短路径。

1. 普里姆（Prim）算法：该算法用于求解最小生成树（MST），其目标是找到连接所有顶点的边权值之和最小的树。虽然最小生成树可能包含某些最短路径，但它并不保证计算从某个特定顶点到其他所有顶点的最短路径。因此，Prim 算法不满足题目要求。

2. 克鲁斯卡尔（Kruskal）算法：该算法同样用于求解最小生成树，通过按边权值从小到大排序并选择不形成环的边来构建 MST。与 Prim 算法类似，Kruskal 算法也不保证计算从某个特定顶点到其他所有顶点的最短路径。因此，Kruskal 算法不满足题目要求。

3. 图的广度优先搜索算法（BFS）：在边权值均为 1 的无向图中，BFS 能够有效地计算从某个顶点到其他所有顶点的最短路径。因为 BFS 按层次遍历图，第一次访问某个顶点时的路径长度即为最短路径长度。因此，BFS 满足题目要求。

综上所述，仅 III（BFS） 能够保证求出从某顶点到其余各顶点的最短路径。

正确答案：B

题目详解：

逐项分析：

① 插入操作可能增加树的高度：正确 。

当插入关键字导致根结点发生分裂时，会生成新的根结点，从而使整个B树的高度增加1。例如，在插入操作中，如果从下至上的分裂过程一直传递到根结点，就会发生这种情况。

② 删除操作一定会导致叶结点的变化：正确。

• 如果删除的关键字位于叶结点：直接删除该关键字，该叶结点必然发生变化（关键字减少）。若删除后关键字数低于下限，可能引发合并或借用，但叶结点一定变化。
• 如果删除的关键字位于非叶结点：通常会用其直接后继（或前驱）关键字（该关键字必位于叶结点）来替换被删除关键字，然后删除那个叶结点中的关键字。因此，最终总会导致某个叶结点发生变化。
• 综上，无论删除何处关键字，最终都会引起叶结点的变化。

③ 查找某关键字一定是要查找到叶结点：错误

B树中所有结点（包括内部结点）都可以存储关键字。若查找的关键字恰好位于某个内部结点，则查找过程会在该结点结束，而不会继续向下到叶结点。

④ 插入的新关键字最终位于叶结点中：错误

插入操作总是从叶结点开始，但过程中可能发生分裂和关键字上溢。例如，当插入导致结点分裂时，中间关键字会上溢到父结点。如果上溢持续到根结点，新关键字可能最终位于内部结点甚至根结点。因此，新关键字不一定最终留在叶结点。

正确答案：B

题目详解：
折半查找的最大比较次数可以通过计算有序顺序表的判定树高度来确定。判定树的高度 $h$ 与元素个数 $n$ 的关系满足：

$h = \lceil \log_2{(n + 1)} \rceil$

题目中 $n = 600$，因此：

$h = \lceil \log_2{601} \rceil$

计算 $\log_2{601}$：

$2^9 = 512$

$2^{10} = 1024$

因为 $512 < 601 < 1024$，所以 $\log_2{601}$ 的值介于 9 和 10 之间，向上取整后得到 $h = 10$。

因此，关键字间的比较次数最多是 10 次。

正确答案：B

题目详解：
首先，我们有一个长度为 5 的散列表 $HT$，初始为空。散列函数为 $H(k) = (k + 4) \% 5$。我们依次插入关键字序列 $2022, 12, 25$，然后删除关键字 $25$，最后计算查找失败的平均查找长度（ASL）。

1. 计算每个关键字的散列值：

   • $H(2022) = (2022 + 4) \% 5 = 2026 \% 5 = 1$
   • $H(12) = (12 + 4) \% 5 = 16 \% 5 = 1$
   • $H(25) = (25 + 4) \% 5 = 29 \% 5 = 4$

2. 插入关键字到散列表：

   • 插入 $2022$：$HT[1] = 2022$
   • 插入 $12$：$HT[1]$ 已被占用，线性探查下一个位置 $HT[2]$，插入 $HT[2] = 12$
   • 插入 $25$：$HT[4]$ 为空，直接插入 $HT[4] = 25$

3. 删除关键字 $25$：

   • 删除 $HT[4]$ 中的 $25$，标记 $HT[4]$ 为“已删除”（DEL）。

4. 计算查找失败的平均查找长度（ASL）：

   • 查找失败时，需要探查直到遇到空位置或遍历整个表。
   • 对于每个可能的散列值 $i$（$0 \leq i \leq 4$），计算查找失败的探查次数：
     • $i = 0$：探查 $HT[0]$（空），探查次数为 $1$
     • $i = 1$：探查 $HT[1]$（$2022$）→ $HT[2]$（$12$）→ $HT[3]$（空），探查次数为 $3$
     • $i = 2$：探查 $HT[2]$（$12$）→ $HT[3]$（空），探查次数为 $2$
     • $i = 3$：探查 $HT[3]$（空），探查次数为 $1$
     • $i = 4$：探查 $HT[4]$（DEL）→ $HT[0]$（空），探查次数为 $2$
   • 平均查找长度 $ASL = \frac{1 + 3 + 2 + 1 + 2}{5} = \frac{9}{5} = 1.8$

正确答案：C

题目详解：
排序算法的稳定性是指在排序过程中，相等的元素在排序前后的相对位置是否保持不变。若算法保持相等元素的相对位置，则称该算法是稳定的；否则，称其为不稳定的。以下是题目中涉及的排序算法的稳定性分析：

1. 希尔排序（I）：希尔排序是插入排序的改进版本，通过分组插入排序实现。由于分组过程中可能改变相等元素的相对位置，因此希尔排序是 不稳定的。

2. 归并排序（II）：归并排序在合并两个有序子序列时，若遇到相等元素，通常会优先保留左边子序列的元素，因此归并排序是 稳定的。

3. 快速排序（III）：快速排序的分区过程中，可能将相等的元素交换到不同的位置，因此快速排序是 不稳定的。

4. 堆排序（IV）：堆排序在调整堆结构时，可能破坏相等元素的相对顺序，因此堆排序是 不稳定的。

5. 基数排序（V）：基数排序按位排序时，若使用的子排序算法是稳定的（如计数排序），则基数排序也是 稳定的。

综上所述，不稳定的排序算法是 I（希尔排序）、III（快速排序）、IV（堆排序），对应选项 C。

正确答案：C

题目详解：
在快速排序算法中，一次划分的过程是将序列分为两部分，其中枢轴（pivot）左边的元素都小于等于枢轴，右边的元素都大于等于枢轴。枢轴的选择通常是序列的第一个元素、最后一个元素或随机元素，具体取决于实现方式。根据题目给出的划分结果：

$68, 11, 70, 23, 80, 77, 48, 81, 93, 88$

我们需要找到一个元素，使得其左边的所有元素都小于等于它，右边的所有元素都大于等于它。观察序列：

• 对于选项 A（11），其左边的元素是 68，$68 > 11$，不满足左边元素小于等于枢轴的条件。
• 对于选项 B（70），其左边的元素是 68 和 11，$11 < 70$ 但 $68 < 70$，但右边的 23 比 70 小，不满足右边元素大于等于枢轴的条件。
• 对于选项 C（80），其左边的元素是 68, 11, 70, 23，其中 70 和 23 都小于 80，但右边的 77 和 48 都比 80 小，不满足右边元素大于等于枢轴的条件。
• 对于选项 D（81），其左边的元素是 68, 11, 70, 23, 80, 77, 48，都小于等于 81，右边的元素是 93, 88，都大于等于 81，满足划分条件。

因此，该次划分的枢轴是 81。

正确答案：D

题目详解：
程序 P 在机器 M 上的指令执行速度（即每秒执行的指令数，单位为 GIPS）可以通过以下公式计算：

指令执行速度 = $\frac{主频}{CPI}$

其中：

• 主频 = $1.5 \text{GHz} = 1.5 \times 10^9 \text{Hz}$
• CPI（每条指令的平均时钟周期数）= $1.2$

代入公式：

指令执行速度 = $\frac{1.5 \times 10^9}{1.2} = 1.25 \times 10^9 \text{IPS} = 1.25 \text{GIPS}$

接下来计算用户 CPU 时间：

用户 CPU 时间 = $\frac{\text{指令条数} \times \text{CPI}}{\text{主频}}$

其中：

• 指令条数 = $5 \times 10^5$
• CPI = $1.2$
• 主频 = $1.5 \times 10^9 \text{Hz}$

代入公式：

用户 CPU 时间 = $\frac{5 \times 10^5 \times 1.2}{1.5 \times 10^9} = \frac{6 \times 10^5}{1.5 \times 10^9} = 0.4 \times 10^{-3} \text{秒} = 0.4 \text{ms}$

因此，程序 P 在机器 M 上的指令执行速度为 $1.25 \text{GIPS}$，用户 CPU 时间为 $0.4 \text{ms}$。

正确答案：C

题目详解：
首先，我们需要明确几个概念：

1. short 型变量：在大多数系统中，short 类型占用 2 个字节（16 位），表示的范围是 -32 768 到 32 767。
2. 机器数：机器数是指数值在计算机中的二进制表示形式，通常使用补码表示有符号整数。
3. 十六进制表示：题目中的选项是十六进制（H 表示十六进制），我们需要将补码转换为十六进制。

现在，我们来计算 x = -8 190 的机器数。

步骤 1：确定绝对值的二进制表示

• 首先，取 x 的绝对值：$| -8 190 | = 8 190$。
• 将 8 190 转换为二进制：
  • 8 190 ÷ 2 = 4 095 余 0
  • 4 095 ÷ 2 = 2 047 余 1
  • 2 047 ÷ 2 = 1 023 余 1
  • 1 023 ÷ 2 = 511 余 1
  • 511 ÷ 2 = 255 余 1
  • 255 ÷ 2 = 127 余 1
  • 127 ÷ 2 = 63 余 1
  • 63 ÷ 2 = 31 余 1
  • 31 ÷ 2 = 15 余 1
  • 15 ÷ 2 = 7 余 1
  • 7 ÷ 2 = 3 余 1
  • 3 ÷ 2 = 1 余 1
  • 1 ÷ 2 = 0 余 1
  • 将余数倒序排列，得到 8 190 的二进制表示为：$11111111111110_2$（共 14 位，前面补两个 0 凑齐 16 位：$0011111111111110_2$）。

步骤 2：求补码

• 负数的补码是其绝对值的二进制表示取反后加 1。
• 取反 $0011111111111110_2$：
  • 取反后：$1100000000000001_2$。
• 加 1：
  • $1100000000000001_2 + 1 = 1100000000000010_2$。

步骤 3：转换为十六进制

• 将补码 $1100000000000010_2$ 转换为十六进制：
  • 每 4 位一组：
    • $1100$ 对应 $C$
    • $0000$ 对应 $0$
    • $0000$ 对应 $0$
    • $0010$ 对应 $2$
  • 组合起来是 $C002H$，但选项中没有这个答案，说明可能在取反时直接对 16 位取反。
• 重新计算：
  • 8 190 的 16 位二进制是 $0001111111111110_2$。
  • 取反：$1110000000000001_2$。
  • 加 1：$1110000000000010_2$。
  • 转换为十六进制：
    • $1110$ 对应 $E$
    • $0000$ 对应 $0$
    • $0000$ 对应 $0$
    • $0010$ 对应 $2$
  • 组合起来是 $E002H$，与选项 A 一致。

正确答案：A

题目详解：
IEEE 754 单精度浮点数格式由 3 部分组成：

• 符号位 $S$（1 位）
• 阶码 $E$（8 位）
• 尾数 $M$（23 位）

给定的机器数为 8020 0000H，转换为二进制为：
$1000\ 0000\ 0010\ 0000\ 0000\ 0000\ 0000\ 0000$

1. 符号位 $S$：
   最高位为 $1$，表示负数。

2. 阶码 $E$：
   接下来的 8 位为 $0000\ 0000$，即 $E = 0$。

3. 尾数 $M$：
   剩余的 23 位为 $010\ 0000\ 0000\ 0000\ 0000\ 0000$，即 $M = 0.01_2$（二进制小数）。

对于 IEEE 754 单精度浮点数：

• 当 $E = 0$ 时，表示非规格化数，其值为：
  $x = (-1)^S \times 2^{-126} \times M$

代入数值：
$x = (-1)^1 \times 2^{-126} \times 0.01_2$
$0.01_2 = 2^{-2}$，因此：
$x = -1 \times 2^{-126} \times 2^{-2} = -2^{-128}$

正确答案：A

题目详解：
首先，计算机的 CPU 有 30 根地址线，按字节编址，因此可寻址的存储空间大小为：
$2^{30} = 1 \text{GB}$。

根据题目要求，RAM 区和 ROM 区所分配的空间大小比为 3:1，因此：

• RAM 区的大小为 $\frac{3}{4} \times 1 \text{GB} = 768 \text{MB}$。
• ROM 区的大小为 $\frac{1}{4} \times 1 \text{GB} = 256 \text{MB}$。

由于 RAM 在连续低地址区，ROM 在连续高地址区，因此：

• RAM 的地址范围是 $0000 0000H$ 到 $2FFF FFFFH$（$768 \text{MB} = 768 \times 1024 \times 1024 = 805,306,368$ 字节，转换为十六进制为 $3000 0000H - 1 = 2FFF FFFFH$）。
• ROM 的地址范围是 $3000 0000H$ 到 $3FFF FFFFH$（$256 \text{MB} = 256 \times 1024 \times 1024 = 268,435,456$ 字节，转换为十六进制为 $4000 0000H - 1 = 3FFF FFFFH$）。

因此，ROM 的地址范围是 $3000 0000H$ 到 $3FFF FFFFH$，对应选项 C。

正确答案：C

题目详解：
在计算机中，溢出标志 $OF$ 和借位标志 $CF$ 用于指示算术运算的结果是否超出了数据类型的表示范围。对于有符号整数运算，$OF$ 表示有符号溢出；对于无符号整数运算，$CF$ 表示无符号借位。

1. 计算 $x - y$ 的二进制补码表示：

   • 当 $x = 10$，$y = -20$ 时，$x - y = 10 - (-20) = 30$。
   • 假设 $x$ 和 $y$ 是 8 位有符号整数（范围为 $-128$ 到 $127$），则：
     • $x = 10$ 的二进制补码表示为 $00001010$。
     • $y = -20$ 的二进制补码表示为 $11101100$。
     • $x - y$ 的二进制补码表示为 $00001010 - 11101100$，相当于 $00001010 + 00010100$（因为减去负数等于加上其绝对值），结果为 $00011110$（即 $30$）。

2. 判断溢出标志 $OF$：

   • $OF$ 在有符号运算中表示结果是否超出有符号数的表示范围。
   • 计算 $10 - (-20) = 30$，结果 $30$ 在 8 位有符号数的范围内（$-128 \leq 30 \leq 127$），因此 $OF = 0$。

3. 判断借位标志 $CF$：

   • $CF$ 在无符号运算中表示是否需要借位。
   • 将 $x$ 和 $y$ 视为无符号数：
     • $x = 10$ 的无符号表示为 $00001010$。
     • $y = -20$ 的无符号表示为 $11101100$（即 $236$）。
     • 计算 $10 - 236$，由于 $10 < 236$，需要借位，因此 $CF = 1$。

综上所述，当 $x = 10$，$y = -20$ 时，执行 $x - y$ 指令得到的 $OF$ 和 $CF$ 分别为 $0$ 和 $1$。

正确答案：B

题目详解：
在计算机体系结构中，CPU 需要通过某种方式确定操作数的实际位置或获取操作数的方式。题目描述的情况涉及以下关键点：

1. 地址码指向通用寄存器：指令中的一个地址码字段指定了某个通用寄存器（编号为 $R_i$），该寄存器可能存储：

   • 操作数本身（直接值）
   • 操作数的地址（间接指向内存或其他位置）

2. 区分依据：CPU 需要明确当前使用的是寄存器中的值还是寄存器指向的地址。这一逻辑由 操作数的寻址方式 决定。寻址方式是指令集架构（ISA）中预先定义的规则，例如：

   • 寄存器直接寻址：寄存器 $R_i$ 的内容是操作数。
   • 寄存器间接寻址：寄存器 $R_i$ 的内容是操作数的地址。

3. 其他选项分析：

   • B 选项（编码方式）：与操作数的表示格式（如补码、浮点编码）相关，与地址解析无关。
   • C 选项（寄存器编号）：编号仅标识寄存器，无法区分内容用途。
   • D 选项（寄存器内容）：内容本身无法自我表明是值还是地址，需依赖寻址方式解释。

因此，CPU 通过指令中 寻址方式字段 的设定来区分寄存器内容的用途。

正确答案：A

题目详解：
在数据通路中，元件可以分为两类：

1. 操作元件（组合逻辑元件）：这类元件不存储状态，其输出仅依赖于当前的输入，执行特定的逻辑或算术操作。常见的操作元件包括：

   • 算术逻辑部件（ALU）：执行算术和逻辑运算，属于典型的组合逻辑元件。
   • 多路选择器（MUX）：根据选择信号从多个输入中选择一个输出，也是组合逻辑元件。

2. 状态元件（时序逻辑元件）：这类元件具有存储功能，其输出依赖于当前状态和输入，通常由时钟信号控制。常见的状态元件包括：

   • 通用寄存器组（GPRs）：用于存储临时数据，属于时序逻辑元件。
   • 程序计数器（PC）：存储下一条指令的地址，属于时序逻辑元件。

根据题目描述，操作元件是 I（ALU） 和 IV（MUX），因此正确答案是 B. 仅 I、IV。

正确答案：B

题目详解：
流水线执行过程如下（每行代表一个时钟周期，列表示流水段）：

分析数据冒险和阻塞情况：

1. I2 依赖 I1：$I2$ 需要 $s2$ 的值，而 $s2$ 由 $I1$ 在 执行 阶段计算。$I1$ 的写回在周期 5，但 $I2$ 的译码/取数在周期 3，此时 $s2$ 还未准备好。通过 转发技术 可以从 $I1$ 的 执行 阶段（周期 3）直接转发结果给 $I2$ 的 译码/取数 阶段，因此 不需要阻塞。

2. I3 依赖 I2：$I3$ 需要 $s3$ 的值，而 $s3$ 由 $I2$ 在 访存 阶段（周期 5）从内存加载。$I3$ 的 译码/取数 阶段在周期 4，此时 $s3$ 还未准备好。即使使用转发技术，也无法在周期 4 获得 $s3$ 的值（因为 $I2$ 的访存阶段还未完成），因此 必须阻塞 1 个周期，等待 $I2$ 完成访存。

3. I4 依赖 I3：$I4$ 需要 $t2$ 的值，而 $t2$ 可能被 $I3$ 的 分支 修改。由于 $I3$ 是分支指令，其执行结果在周期 5 确定。$I4$ 的 译码/取数 阶段在周期 5，此时 $I3$ 的执行结果还未写回。即使使用转发技术，也无法在周期 5 获得 $t2$ 的值（因为 $I3$ 的执行阶段还未完成），因此 必须阻塞 1 个周期，等待 $I3$ 完成执行。

综上，发生阻塞的指令是 $I3$ 和 $I4$。

正确答案：C

题目详解：
首先，我们需要计算读取一个主存块（32B）所需的时间。具体步骤如下：

1. 总线传输数据量：

   • 总线宽度为 $64b$，即每次可以传输 $8B$ 的数据。
   • 主存块大小为 $32B$，因此需要传输的次数为：
     $\frac{32B}{8B} = 4 \text{ 次}$

2. 总线传输时间：

   • 总线时钟频率为 $1GHz$，即时钟周期为：
     $\frac{1}{1GHz} = 1ns$
   • 每次传输需要一个时钟周期，因此 $4$ 次传输需要的时间为：
     $4 \times 1ns = 4ns$

3. 主存准备数据时间：

   • 主存每次准备 $64b$ 数据需要 $6ns$。
   • 由于主存块大小为 $32B$，每次准备 $8B$，因此需要准备 $4$ 次，总时间为：
     $4 \times 6ns = 24ns$

4. 总时间计算：

   • 读取一个主存块的总时间是主存准备数据时间和总线传输时间之和：
     $24ns + 4ns = 28ns$
   • 但题目中给出的选项没有 $28ns$，最接近的是 $32ns$，可能是题目设定主存准备时间和总线传输时间不能完全重叠，因此总时间为 $32ns$。

正确答案：D

题目详解：
在计算机系统中，硬件与异常/中断的关系如下：

• 选项A：CPU 在执行一条指令过程中可以检测到异常事件（如除零、缺页等）。异常是同步的，通常由当前执行的指令触发，因此该叙述正确。

• 选项B：CPU 通常在执行完一条指令的末尾检查中断请求信号（如外部设备的中断）。中断是异步的，与当前指令无关，因此该叙述正确。

• 选项C：当开中断（即中断允许标志 $IF = 1$）时，CPU 检测到中断请求后会进行中断响应（如保存现场、跳转到中断处理程序等），因此该叙述正确。

• 选项D：外部设备通过中断控制器（如 $8259A$）向 CPU 发送的是 中断请求信号（如 $INTR$），而 中断结束信号（$EOI$）是由 CPU 或中断控制器发送给外部设备的，用于通知中断处理完成。因此该叙述错误。

正确答案：D

题目详解：
在计算机系统中，I/O 控制方式主要有查询方式、中断方式和 DMA 方式三种。以下是各选项的详细分析：

A. 查询方式：CPU 需要不断执行查询程序，检查 I/O 设备的状态，直到设备准备好才进行数据传输。这种方式下，CPU 利用率较低，因为 CPU 需要一直轮询设备状态。因此，选项 A 的描述是正确的。

B. 中断方式：当 I/O 设备准备好数据传输时，会向 CPU 发送中断信号，CPU 暂停当前任务，转而执行中断服务程序完成数据传输。这种方式避免了 CPU 的轮询等待，提高了效率。因此，选项 B 的描述是正确的。

C. DMA 方式：DMA（Direct Memory Access）方式下，数据传输由 DMA 控制器直接管理，不需要 CPU 介入。DMA 控制器负责在内存和 I/O 设备之间直接传输数据，仅在传输开始和结束时通知 CPU。因此，选项 C 中“通过 CPU 执行 DMA 传送程序”是错误的描述。

D. 高速设备的 I/O 方式：对于 SSD、网络适配器等高速设备，如果采用中断方式或查询方式，CPU 的负担会过重，因此通常采用 DMA 方式以提高效率。因此，选项 D 的描述是正确的。

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

正确答案：C

题目详解：
微内核操作系统与宏内核操作系统相比，具有以下主要特征：

1. 性能：微内核由于将许多功能移到用户空间，内核与外部的通信需要通过消息传递，这会引入一定的性能开销，因此性能通常不如宏内核（即 I. 较好的性能 不符合微内核的特点）。

2. 可靠性：微内核的设计将核心功能最小化，大部分服务运行在用户空间，单个服务的故障不会导致整个系统崩溃，因此具有 II. 较高的可靠性。

3. 安全性：微内核的权限分离和最小特权原则减少了攻击面，使得系统具有 III. 较高的安全性。

4. 可扩展性：微内核的模块化设计使得新功能可以动态添加或移除，无需修改内核代码，因此具有 IV. 较强的可扩展性。

综上所述，微内核操作系统具有 II、III、IV 特征。

正确答案：D

题目详解：
在操作系统内核中，中断向量表（Interrupt Vector Table, IVT）是一种用于存储中断处理程序入口地址的数据结构。中断向量表需要满足以下关键特性：

1. 快速访问：当硬件中断发生时，CPU需要根据中断号快速定位到对应的中断处理程序。这就要求中断向量表必须支持 $O(1)$ 时间复杂度的随机访问。

2. 固定大小：中断向量表的大小通常是固定的，因为中断号的范围是预先定义的（例如，x86架构中有256个中断向量）。

3. 连续存储：中断向量表的每一项（即中断处理程序的入口地址）通常是等长的，且需要连续存储以便通过下标直接计算地址偏移量。

数组（Array）是最适合实现中断向量表的数据结构，因为它：

• 支持 $O(1)$ 的随机访问；
• 内存布局连续，可以通过基地址 $+$ 偏移量直接定位元素；
• 大小固定，与中断向量表的特性完全匹配。

其他数据结构不满足需求：

• 队列（B）：不支持随机访问，且操作受限；
• 单向链表（C）和双向链表（D）：访问时间复杂度为 $O(n)$，无法满足快速响应的要求。

正确答案：A

题目详解：
首先计算物理内存中的总页框数。物理内存大小为 $16GB$，页大小为 $4KB$，因此页框数为：

$$\text{页框数} = \frac{\text{物理内存大小}}{\text{页大小}} = \frac{16 \times 1024 \times 1024 \times 1024 \text{B}}{4 \times 1024 \text{B}} = 4 \times 1024 \times 1024 = 4,194,304$$

位图使用一个二进制位（bit）表示一个页框的空闲状态，因此位图的总大小为：

$$\text{位图大小} = \frac{\text{页框数}}{8} \text{B} = \frac{4,194,304}{8} \text{B} = 524,288 \text{B}$$

将字节转换为更常用的单位：

$$524,288 \text{B} = 512 \text{KB}$$

因此，位图所占空间的大小是 $512KB$。

正确答案：C

题目详解：
CPU 的工作状态分为内核态（Kernel Mode）和用户态（User Mode）。以下是对每个选项的分析：

• A. 阻塞进程：
  当进程被阻塞时，通常是由运行态转为阻塞态，此时 CPU 可能会切换到另一个进程，但这一操作本身不会导致 CPU 从内核态转为用户态。阻塞操作通常发生在内核态。

• B. 执行 CPU 调度：
  CPU 调度是操作系统内核的核心功能，由调度器在内核态完成。调度完成后，CPU 会切换到用户态运行新调度的进程，但“执行 CPU 调度”这一动作本身是内核态的操作，不会直接导致状态切换。

• C. 唤醒进程：
  唤醒进程是由内核完成的，通常发生在内核态。唤醒后，进程可能被加入就绪队列，但唤醒操作本身不会直接导致 CPU 从内核态转为用户态。

• D. 执行系统调用：
  系统调用是用户程序通过接口请求内核服务的过程。调用时，CPU 从用户态进入内核态；当系统调用完成后，CPU 会从内核态返回到用户态。因此，系统调用完成时会导致 CPU 从内核态转为用户态。

正确答案：D

题目详解：
线程由执行态变为就绪态通常发生在以下情况：

1. 时间片用完：操作系统的时间片轮转调度会导致当前线程让出 CPU。
2. 主动出让 CPU：线程通过调用如 $yield()$ 等方法主动放弃 CPU 使用权。
3. 被更高优先级线程抢占：如果有更高优先级的线程变为就绪态，当前线程可能会被抢占。

选项分析：

• A. 键盘输入：属于 I/O 操作，通常会导致线程进入阻塞态，而非就绪态。
• B. 缺页异常：属于硬件中断或异常，线程会进入阻塞态等待页面调入。
• C. 主动出让 CPU：线程主动放弃 CPU 后，会进入就绪态等待下次调度。
• D. 执行信号量的 $wait()$ 操作：如果信号量不可用，线程会进入阻塞态。

因此，主动出让 CPU 是导致线程由执行态变为就绪态的直接原因。

正确答案：C

题目详解：
虚拟内存管理是现代操作系统的重要特性，关于进程虚拟地址空间的叙述分析如下：

A. 正确。每个进程都有自己独立的虚拟地址空间，这是虚拟内存管理的基本特征，不同进程的相同虚拟地址会被映射到不同的物理地址。

B. 正确。C 语言中的 malloc() 函数返回的是进程虚拟地址空间中的地址，这个地址在被实际访问时才会通过页表映射到物理内存。

C. 正确。操作系统通常会对代码段（存放程序指令）设置只读权限，而对数据段（存放变量等）设置读写权限，这是内存保护的重要机制。

D. 错误。虚拟地址空间的大小主要由 CPU 的寻址能力决定，例如 32 位系统的虚拟地址空间是 $2^{32} = 4GB$，64 位系统则大得多。它与内存和硬盘的大小无直接关系，硬盘只是用作虚拟内存的交换空间。

正确答案：D

题目详解：
具体的调度表如下图所示。周转时间 = 完成时间 - 到达时间，进程 1 的周转时间为 115ms-0ms=115ms，进程 2 的周转时间为 75ms-20ms=55ms，进程 3 的周转时间为 43ms- 30ms=13ms。平均周转时间为 (115+55+13)/3=61ms。所以该题的答案为 B 选项。

正确答案：B

题目详解：
在操作系统中，进程 R 和 S 共享数据 $data$，这意味着它们访问的是同一块物理内存。以下是关键概念的分析：

1. 页号（$p1$ 和 $p2$）：页号是虚拟地址空间中的逻辑页编号。不同进程的虚拟地址空间是独立的，因此 $data$ 在进程 R 和 S 中的页号 $p1$ 和 $p2$ 不一定相同。例如，进程 R 可能将 $data$ 放在其虚拟地址空间的第 5 页，而进程 S 可能将其放在第 10 页。

2. 页框号（$f1$ 和 $f2$）：页框号是物理内存中的实际页框编号。由于 $data$ 是共享的，两个进程的页表会映射到同一个物理页框，因此 $f1$ 和 $f2$ 一定相同。例如，$data$ 可能存储在物理内存的第 20 页框中，因此 $f1 = f2 = 20$。

综上所述：

• $p1$ 和 $p2$ 不一定相等（因为虚拟地址空间独立）。
• $f1$ 和 $f2$ 一定相等（因为共享同一物理页框）。

正确答案：C

题目详解：
当进程 $P$ 关闭文件 $F$ 时，文件系统需要完成以下操作：

1. 释放 $F$ 的索引节点所占的内存空间：索引节点（inode）是文件系统用于管理文件元数据的数据结构。当文件被打开时，其索引节点会被加载到内存中以供快速访问。当文件关闭时，这部分内存空间需要被释放，以便系统可以重新利用它。

2. 其他选项分析：

   • 选项 A：删除目录文件中 $F$ 的目录项是不正确的，因为关闭文件并不会删除文件本身，只是释放相关资源。
   • 选项 C：释放 $F$ 的索引节点所占的外存空间也是不正确的，因为关闭文件并不会删除文件的外存数据，索引节点的外存空间仍然保留。
   • 选项 D：将文件磁盘索引结点中的链接计数减 1 通常是在删除硬链接时进行的操作，而不是关闭文件时的操作。

因此，文件系统在关闭文件时主要需要释放索引节点所占的内存空间。

正确答案：B

题目详解：
设备分配是操作系统资源管理的重要环节，需要考虑以下因素：

1. 设备的类型（I）：不同类型的设备（如打印机、磁盘、网络设备等）具有不同的特性和使用方式，分配时需明确设备类型以满足任务需求。例如，打印任务必须分配打印机而非磁盘设备。

2. 设备的访问权限（II）：操作系统需检查进程是否具备访问该设备的权限，防止未授权访问。例如，普通用户可能无权直接访问高优先级设备。

3. 设备的占用状态（III）：分配前需检查设备是否空闲。若设备已被占用，需等待或选择其他可用设备。例如，打印机忙碌时需排队或分配其他空闲打印机。

4. 逻辑设备与物理设备的映射关系（IV）：用户程序通过逻辑设备名（如/dev/printer）请求设备，操作系统需将其映射到实际物理设备（如Printer1或Printer2），这种灵活性便于资源管理和负载均衡。

综上，设备分配需全面考虑上述四个因素，因此正确答案为 $D$ 。

正确答案：D

题目详解：

1. 发送阶段

• 第 1 个分组：$0 \rightarrow 0.08$ ms 发送完。

• …

• 第 1000 个分组：$79.92 \rightarrow 80$ ms 发送完。

  因此，最后 1 位比特离开 H1 的时刻为 $t_1 = \textbf{80 ms}$。

2. H1 → R 传播
   单向传播时延 $T_p = 0.01$ ms
   $t_2 = t_1 + T_p = \textbf{80.01 ms}$

3. R 转发（序列化）
   路由器必须将该分组重新发送一次，耗时仍为 $T_s = 0.08$ ms
   $t_3 = t_2 + T_s = \textbf{80.09 ms}$

4. R → H2 传播
   再次经过链路传播时延 $T_p = 0.01$ ms
   $t_4 = t_3 + T_p = \textbf{80.10 ms}$

正确答案：D

题目详解：
根据奈奎斯特定理，无噪声理想信道的最大数据传输速率 $R$ 可以通过以下公式计算：

$$R = 2B \log_2 V$$

其中：

• $B$ 是信道带宽，题目中给出 $B = 4 \text{ MHz}$。
• $V$ 是调制电平数，即 QAM 调制方案中的状态数。
• $R$ 是最大数据传输速率，题目中给出 $R = 48 \text{ Mb/s}$。

将已知数值代入公式：

$$48 = 2 \times 4 \times \log_2 V$$

简化方程：

$$48 = 8 \log_2 V$$

两边同时除以 8：

$$\log_2 V = 6$$

通过指数运算求解 $V$：

$$V = 2^6 = 64$$

因此，该信道采用的 QAM 调制方案是 QAM–64。

正确答案：C

题目详解：
信道利用率 $U$ 的计算公式为：$U = \frac{T_{\text{data}}}{T_{\text{data}} + T_{\text{prop}} + T_{\text{ack}}}$
其中：

• $T_{\text{data}}$ 是发送一帧数据的时间
• $T_{\text{prop}}$ 是传播时延
• $T_{\text{ack}}$ 是确认时延

对于停止–等待协议（$U_1$），每次只能发送一帧并等待确认，信道利用率为： $U_1 = \frac{T_{\text{data}}}{T_{\text{data}} + 2T_{\text{prop}}}$ （忽略 $T_{\text{ack}}$ 因为确认帧长度被忽略）

对于 GBN 协议（$U_2$），发送窗口大小为 $W_{\text{GBN}} = 2^n - 1 = 7$（$n = 3$ 比特），信道利用率为： $U_2 = \frac{W_{\text{GBN}} \cdot T_{\text{data}}}{T_{\text{data}} + 2T_{\text{prop}}} = \frac{7T_{\text{data}}}{T_{\text{data}} + 2T_{\text{prop}}}$

对于 SR 协议（$U_3$），发送窗口和接收窗口相等，最大窗口大小为 $W_{\text{SR}} = 2^{n-1} = 4$，信道利用率为： $U_3 = \frac{W_{\text{SR}} \cdot T_{\text{data}}}{T_{\text{data}} + 2T_{\text{prop}}} = \frac{4T_{\text{data}}}{T_{\text{data}} + 2T_{\text{prop}}}$

比较 $U_1$、$U_2$ 和 $U_3$：

• $U_1 = \frac{T_{\text{data}}}{T_{\text{data}} + 2T_{\text{prop}}}$
• $U_3 = \frac{4T_{\text{data}}}{T_{\text{data}} + 2T_{\text{prop}}}$
• $U_2 = \frac{7T_{\text{data}}}{T_{\text{data}} + 2T_{\text{prop}}}$

显然 $U_1 \leq U_3 \leq U_2$，因此正确答案是 B。

正确答案：B

题目详解：
在以太网中，二进制指数退避算法用于确定冲突后重发的等待时间。具体步骤如下：

1. 基本时间单位是争用时间片，即 $51.2 \mu s$。
2. 第 $k$ 次冲突后的退避时间从 $0$ 到 $2^k - 1$ 个时间片中随机选择。
3. 最大退避次数限制为 $10$ 次，即 $k \leq 10$。
4. 题目中发生了连续 $4$ 次冲突，因此 $k = 4$。
5. 最大退避时间为 $(2^4 - 1) \times 51.2 \mu s = 15 \times 51.2 \mu s = 768 \mu s$。

因此，最长的等待时间是 $768 \mu s$。

正确答案：C

题目详解：
CRC校验的原理是将数据比特串 $D$ 与生成多项式 $G$ 进行模2除法，若余数为0，则传输未发生错误。生成多项式 $G(X) = X^4 + X + 1$ 对应的二进制为 $G = 10011$。

步骤如下：

1. 在数据比特串后补 $4$ 个0（因为生成多项式的最高次为4），得到被除数 $D'$。
2. 用 $G$ 对 $D'$ 进行模2除法，检查余数是否为0。

对于选项D $1\ 0111\ 1100$：

1. 补0后得到 $D' = 101111100\ 0000$。
2. 进行模2除法：
   • $1011111000000 \div 10011$：
     • 第一步：$1011111000000 \oplus 1001100000000 = 0010011000000$
     • 第二步：$0010011000000 \oplus 0000000000000 = 0010011000000$
     • 第三步：$0010011000000 \oplus 001001100000 = 0000000000000$
   • 余数为0，说明传输未发生错误。

其他选项的余数均不为0，因此只有选项D满足条件。

正确答案：D

题目详解：
当 IP 分组经过 网络地址转换（Network Address Translation, NAT）转发时，会发生源 IP 地址转换：NAT 会将源 IP 地址从私有 IP 地址（在局域网内使用的 IP 地址）转换为公共 IP 地 址（在互联网上可路由的 IP 地址）。这是为了隐藏内部网络的真实 IP 地址，使其在公共网络 上不可见。同时给定 IP 地址段为 192.168.0.34/30，它表示一个有 30 位网络前缀的子网。根据 CIDR 表示法，30 表示子网掩码为 255.255.255.252。在这个子网中，可用的 IP 地址如下，网 络地址：192.168.0.32，第一个可用地址：192.168.0.33，最后一个可用地址：192.168.0.34，广 播地址：192.168.0.35。可以分配的源地址为 192.168.0.33 和 192.168.0.34，因为选项中只有 192.163.0.33，所以本题正确答案为选项 A。

正确答案：A

题目详解：

1. 首先，根据给定的 IP 地址 $168.16.84.24/20$，我们需要确定子网掩码。$/20$ 表示前 20 位是网络位，子网掩码为 $255.255.240.0$。

2. 计算子网地址：

   • 将 IP 地址 $168.16.84.24$ 转换为二进制形式：
     $168.16.0101\ 0100.24$。
   • 子网掩码 $255.255.240.0$ 的二进制形式为：
     $11111111.11111111.11110000.00000000$。
   • 进行按位与运算，得到子网地址：
     $168.16.0101\ 0000.0$，即 $168.16.80.0$。

3. 确定子网范围：

   • 最小可分配 IP 地址是子网地址加 1，即 $168.16.80.1$。
   • 最大可分配 IP 地址是子网的广播地址减 1。广播地址的计算方法是将主机位全部置 1：
     $168.16.0101\ 1111.11111111$，即 $168.16.95.255$。
   • 因此，最大可分配 IP 地址为 $168.16.95.254$。

4. 综上所述，最小可分配 IP 地址是 $168.16.80.1$，最大可分配 IP 地址是 $168.16.95.254$。

正确答案：B

题目详解：
关于 IPv4 和 IPv6 的叙述分析如下：

I. IPv6 地址空间是 IPv4 地址空间的 96 倍

• IPv4 地址长度为 $32$ 位，地址空间为 $2^{32}$。
• IPv6 地址长度为 $128$ 位，地址空间为 $2^{128}$。
• IPv6 地址空间是 IPv4 的 $\frac{2^{128}}{2^{32}} = 2^{96}$ 倍，即 $2^{96}$ 倍，而非简单的 96 倍。因此叙述 错误。

II. IPv4 首部和 IPv6 的基本首部的长度均可变

• IPv4 首部长度可变（因为有选项字段），但 IPv6 的基本首部长度固定为 $40$ 字节。因此叙述 错误。

III. IPv4 向 IPv6 过渡可以采用双协议栈和隧道技术

• 双协议栈（Dual Stack）和隧道技术（Tunneling）是 IPv4 向 IPv6 过渡的两种主要技术，叙述 正确。

IV. IPv6 首部的 Hop Limit 等价于 IPv4 首部的 TTL 字段

• IPv6 的 Hop Limit 字段与 IPv4 的 TTL（Time To Live）字段功能相同，均用于限制数据包的生存跳数，叙述 正确。

综上，正确的叙述是 III 和 IV，对应选项 D。

正确答案：D

题目详解：
1）采用邻接矩阵表示有向图时，一行中 1 的个数为该行对应顶点的出度，一列中 1 的个数为该列对应顶点的入度。使用一个初值为 0 的计数器记录 $K$ 顶点的个数。对图 $G$ 的每个顶点，根据邻接矩阵计算其出度 $outdegree$ 和入度 $indegree$。若 $outdegree - indegree > 0$，则输出该顶点且计数器加 1。最后返回计数器的值。

2）算法实现

int printVertices(MGraph G) {
    // K 顶点的个数
    int count = 0;
    for (int v = 0; v < numVertices; v++) {
        // v 顶点的入度和出度
        int indegree = 0;
        int outdegree = 0;
        // 统计出度
        for (int i = 0; i < numVertices; i++) {
            outdegree += G.Edge[v][i];
        }
        // 统计入度
        for (int i = 0; i < numVertices; i++) {
            indegree += G.Edge[i][v];
        }
        if (outdegree > indegree) {
            printf("%s ", G.VerticesList[v]);
            count++;
        }
    }
    return count;
}

题目详解：
1）该题的关键字序列可生成 3 个初始归并段，分别是：

• 37，51，63，92，94，99
• 14，15，23，31，48，56，60，90，166
• 8，17，43，100

2）最大值为 $n$，最小值为 $m$。

题目详解：
1）数组 $a$ 分布在 2 个页面中。缺页异常次数为 2。两个页故障地址分别是 $0042\,2000H$、$0042\,3000H$。

2）该程序段的数据访问没有时间局部性。因为每个数组元素仅访问 1 次。

3）虚拟地址中低 5 位 ($A_4$~$A_0$) 用作块内地址；低 11 位虚拟地址中高 6 位 ($A_{10}$~$A_5$) 用作 Cache 组号。$a[1][0]$ 的虚拟地址为 $0042\,2000H + 1 \times 64 \times 4 + 0 \times 4 = 0042\,2100H$。$a[1][0]$ 所在主存块对应的 Cache 组号为 $001000B = 8$。