2018年408真题

题目详解：
首先，我们需要明确栈 $S_1$ 和栈 $S_2$ 的初始状态以及函数 $F()$ 的执行步骤。

初始状态：

• 栈 $S_1$ 中的操作数依次是 $5, 8, 3, 2$（$2$ 在栈顶），即栈从顶到底为 $2, 3, 8, 5$。
• 栈 $S_2$ 中的运算符依次是 $*, -, +$（$+$ 在栈顶），即栈从顶到底为 $+, -, *$。

函数 $F()$ 的执行步骤如下：

1. 从 $S_1$ 中依次弹出两个操作数 $a$ 和 $b$（$a$ 是第一个弹出的，$b$ 是第二个弹出的）。
2. 从 $S_2$ 中弹出一个运算符 $op$。
3. 执行相应的运算 $b \ op \ a$。
4. 将运算结果压入 $S_1$ 中。

调用 $3$ 次 $F()$ 的过程如下：

第一次调用 $F()$：

1. 弹出 $a = 2$ 和 $b = 3$。
2. 弹出 $op = +$。
3. 计算 $3 + 2 = 5$。
4. 将 $5$ 压入 $S_1$。
   此时 $S_1$ 的状态为 $5, 8, 5$（从顶到底）。
   $S_2$ 的状态为 $-, *$。

第二次调用 $F()$：

1. 弹出 $a = 5$ 和 $b = 8$。
2. 弹出 $op = -$。
3. 计算 $8 - 5 = 3$。
4. 将 $3$ 压入 $S_1$。
   此时 $S_1$ 的状态为 $3, 5$（从顶到底）。
   $S_2$ 的状态为 $*$。

第三次调用 $F()$：

1. 弹出 $a = 3$ 和 $b = 5$。
2. 弹出 $op = *$。
3. 计算 $5 * 3 = 15$。
4. 将 $15$ 压入 $S_1$。
   此时 $S_1$ 的状态为 $15$（从顶到底）。
   $S_2$ 的状态为空。

调用 $3$ 次 $F()$ 后，$S_1$ 栈顶保存的值是 $15$。

正确答案：B

题目详解：
初始时，队列 $Q$ 中的元素为 $1, 2, 3, 4, 5, 6$ （ $1$ 在队头），栈 $S$ 为空。我们需要验证每个选项是否可以通过给定的操作序列得到。

选项A： $1, 2, 5, 6, 4, 3$

1. 操作①：出队并输出 $1$ ， $Q$ 变为 $2, 3, 4, 5, 6$ 。

2. 操作①：出队并输出 $2$ ， $Q$ 变为 $3, 4, 5, 6$ 。

3. 操作②：出队并将 $3$ 入栈， $Q$ 变为 $4, 5, 6$ ， $S$ 为 $3$ 。

4. 操作②：出队并将 $4$ 入栈， $Q$ 变为 $5, 6$ ， $S$ 为 $4, 3$ 。

5. 操作①：出队并输出 $5$ ， $Q$ 变为 $6$ 。

6. 操作①：出队并输出 $6$ ， $Q$ 为空。

7. 操作③：出栈并输出 $4$ ， $S$ 为 $3$ 。

8. 操作③：出栈并输出 $3$ ， $S$ 为空。

   输出序列为 $1, 2, 5, 6, 4, 3$ ，与选项A一致。因此，选项A是可以得到的。

选项B： $2, 3, 4, 5, 6, 1$

1. 操作②：出队并将 $1$ 入栈， $Q$ 变为 $2, 3, 4, 5, 6$ ， $S$ 为 $1$ 。

2. 操作①：出队并输出 $2$ ， $Q$ 变为 $3, 4, 5, 6$ 。

3. 操作①：出队并输出 $3$ ， $Q$ 变为 $4, 5, 6$ 。

4. 操作①：出队并输出 $4$ ， $Q$ 变为 $5, 6$ 。

5. 操作①：出队并输出 $5$ ， $Q$ 变为 $6$ 。

6. 操作①：出队并输出 $6$ ， $Q$ 为空。

7. 操作③：出栈并输出 $1$ ， $S$ 为空。

   输出序列为 $2, 3, 4, 5, 6, 1$ ，与选项B一致。因此，选项B是可以得到的。

选项C： $3, 4, 5, 6, 1, 2$

1. 要输出 $3$ 作为第一个元素，必须先将 $1$ 和 $2$ 入栈：

   • 操作②：出队并将 $1$ 入栈， $Q$ 变为 $2, 3, 4, 5, 6$ ， $S$ 为 $1$ 。
   • 操作②：出队并将 $2$ 入栈， $Q$ 变为 $3, 4, 5, 6$ ， $S$ 为 $2, 1$ 。
   • 操作①：出队并输出 $3$ ， $Q$ 变为 $4, 5, 6$ 。

2. 接下来输出 $4, 5, 6$ ：

   • 操作①：出队并输出 $4$ ， $Q$ 变为 $5, 6$ 。
   • 操作①：出队并输出 $5$ ， $Q$ 变为 $6$ 。
   • 操作①：出队并输出 $6$ ， $Q$ 为空。

3. 最后需要输出 $1, 2$ ，但栈 $S$ 的顺序是 $2, 1$ ，因此只能先输出 $2$ 再输出 $1$ ，无法得到 $1, 2$ 的顺序。

   因此，选项C是无法得到的。

选项D： $6, 5, 4, 3, 2, 1$

1. 将所有元素入栈：

   • 操作②：出队并将 $1$ 入栈， $Q$ 变为 $2, 3, 4, 5, 6$ ， $S$ 为 $1$ 。
   • 操作②：出队并将 $2$ 入栈， $Q$ 变为 $3, 4, 5, 6$ ， $S$ 为 $2, 1$ 。
   • 操作②：出队并将 $3$ 入栈， $Q$ 变为 $4, 5, 6$ ， $S$ 为 $3, 2, 1$ 。
   • 操作②：出队并将 $4$ 入栈， $Q$ 变为 $5, 6$ ， $S$ 为 $4, 3, 2, 1$ 。
   • 操作②：出队并将 $5$ 入栈， $Q$ 变为 $6$ ， $S$ 为 $5, 4, 3, 2, 1$ 。
   • 操作②：出队并将 $6$ 入栈， $Q$ 为空， $S$ 为 $6, 5, 4, 3, 2, 1$ 。

2. 依次出栈并输出：

   • 操作③：出栈并输出 $6$ ， $S$ 为 $5, 4, 3, 2, 1$ 。
   • 操作③：出栈并输出 $5$ ， $S$ 为 $4, 3, 2, 1$ 。
   • 操作③：出栈并输出 $4$ ， $S$ 为 $3, 2, 1$ 。
   • 操作③：出栈并输出 $3$ ， $S$ 为 $2, 1$ 。
   • 操作③：出栈并输出 $2$ ， $S$ 为 $1$ 。
   • 操作③：出栈并输出 $1$ ， $S$ 为空。

   输出序列为 $6, 5, 4, 3, 2, 1$ ，与选项D一致。因此，选项D是可以得到的。

综上所述，不能得到的输出序列是选项C。

正确答案：C

题目详解：
对称矩阵 $M$ 的上三角部分（包括对角线）共有 $\frac{n(n+1)}{2}$ 个元素，其中 $n = 12$。因此，上三角部分总共有 $\frac{12 \times 13}{2} = 78$ 个元素。

在行优先存储方式下，上三角部分的元素按行依次存入一维数组 $N$ 中。我们需要计算元素 $m_{6,6}$ 在 $N$ 中的下标。

1. 首先计算前 $5$ 行（$i = 1$ 到 $i = 5$）的元素总数：

   • 第 $1$ 行有 $12$ 个元素（$j = 1$ 到 $j = 12$）。
   • 第 $2$ 行有 $11$ 个元素（$j = 2$ 到 $j = 12$）。
   • ...
   • 第 $5$ 行有 $8$ 个元素（$j = 5$ 到 $j = 12$）。

   前 $5$ 行的元素总数为：
   $12 + 11 + 10 + 9 + 8 = 50$

2. 元素 $m_{6,6}$ 是第 $6$ 行的第 $1$ 个元素（因为 $j$ 从 $6$ 开始），所以它在 $N$ 中的下标为前 $5$ 行的元素总数加上 $0$（因为是第 $1$ 个元素），即 $50 + 0 = 50$。

因此，$m_{6,6}$ 在 $N$ 中的下标是 $50$。

正确答案：A

题目详解：
根据题目描述，这是一棵非空完全二叉树，且所有叶结点均位于同一层，每个非叶结点都有 2 个子结点。这种树的结构是一个满二叉树。

在满二叉树中，叶结点的数量 $k$ 与树的高度 $h$ 满足关系：
$k = 2^{h-1}$
其中 $h$ 是树的高度（根结点的高度为 1）。

满二叉树的总结点数 $N$ 可以通过以下公式计算：
$N = 2^h - 1$

将 $k = 2^{h-1}$ 代入 $N$ 的公式中：
$N = 2 \times 2^{h-1} - 1 = 2k - 1$

因此，T 的结点总数是 $2k - 1$。

正确答案：A

题目详解：
首先，我们需要根据字符出现的频率构建哈夫曼树。步骤如下：

1. 将字符及其频率按升序排列：

   • $d: 2$
   • $b: 3$
   • $f: 4$
   • $a: 6$
   • $c: 8$
   • $e: 10$

2. 每次选择频率最小的两个节点合并，直到形成完整的哈夫曼树：

   • 合并 $d$ 和 $b$，得到新节点 $db: 5$（$2 + 3$）。
   • 合并 $f$ 和 $db$，得到新节点 $fdb: 9$（$4 + 5$）。
   • 合并 $a$ 和 $c$，得到新节点 $ac: 14$（$6 + 8$）。
   • 合并 $fdb$ 和 $e$，得到新节点 $fdbe: 19$（$9 + 10$）。
   • 最后合并 $ac$ 和 $fdbe$，得到根节点 $acfdbe: 33$（$14 + 19$）。

3. 根据哈夫曼树为每个字符分配编码：

   • 从根节点出发，左分支为 $0$，右分支为 $1$。
   • $e$ 的编码为 $11$（出现频率最高，路径最短）。
   • $c$ 的编码为 $01$。
   • $a$ 的编码为 $00$。
   • $f$ 的编码为 $100$。
   • $b$ 的编码为 $1011$。
   • $d$ 的编码为 $1010$。

4. 将编码与选项对比：

   • A 选项中的编码顺序为 $a:00$, $b:1011$, $c:01$, $d:1010$, $e:11$, $f:100$，与我们的结果一致。
   • 其他选项的编码不符合哈夫曼编码规则。

正确答案：A

题目详解：

根据二叉排序树的特性：中序遍历（LNR）得到的是一个递增序列。图中二叉排序树的中序遍历序列为 $x_i, x_3, x_5, x_4, x_2$，可知 $x_3 < x_5 < x_4$。

正确答案: C

题目详解：

拓扑排序每次选取入度为 0 的结点输出，经观察不难发现拓扑序列前两位一定是 1,5 或 5,1（因为只有 1 和 5 的入度均为 0，且其他结点都不满足仅有 1 或仅有 5 作为前驱）。因此 D 显然错误。

正确答案：D

题目详解：
一个 $m$ 阶B树的最小关键字个数可以通过以下方式计算：

1. B树的最小关键字个数公式：对于高度为 $h$ 的 $m$ 阶B树，最小关键字个数为 $2 \cdot \lceil m/2 \rceil^{h-1} - 2$。

2. 题目参数：

   • 阶数 $m = 3$，因此 $\lceil m/2 \rceil = \lceil 3/2 \rceil = 2$。
   • 高度 $h = 5$。

3. 代入计算：
   $2 \cdot 2^{5-1} - 2 = 2 \cdot 2^{4} - 2 = 2 \cdot 16 - 2 = 32 - 2 = 30$
   然而，这个公式计算的是最小关键字个数的下限，更准确的最小关键字个数可以通过递归方式计算：

   • 根结点至少有 $1$ 个关键字。
   • 其他非叶子结点至少有 $\lceil m/2 \rceil - 1 = 1$ 个关键字。
   • 每个非叶子结点（除根外）至少有 $2$ 个子结点。
   • 高度为 $5$ 的B树的最小关键字总数为：
     $1 + 2 \cdot (1 + 2 \cdot (1 + 2 \cdot (1 + 2 \cdot 1))) = 1 + 2 \cdot (1 + 2 \cdot (1 + 2 \cdot 3)) = 1 + 2 \cdot (1 + 2 \cdot 7) = 1 + 2 \cdot 15 = 31$

因此，高度为 $5$ 的 $3$ 阶B树的最小关键字个数为 $31$。

正确答案：B

题目详解：
首先，我们有一个长度为 $7$ 的散列表 $HT$，初始为空。散列函数为 $H(k) = k \% 7$，并使用线性探测再散列法解决冲突。

1. 插入关键字 $22$：

   • 计算散列值：$H(22) = 22 \% 7 = 1$。
   • $HT[1]$ 为空，直接插入 $22$。
   • 查找长度为 $1$。

2. 插入关键字 $43$：

   • 计算散列值：$H(43) = 43 \% 7 = 1$。
   • $HT[1]$ 已被 $22$ 占用，发生冲突。
   • 使用线性探测法，检查下一个位置 $HT[2]$，为空，插入 $43$。
   • 查找长度为 $2$。

3. 插入关键字 $15$：

   • 计算散列值：$H(15) = 15 \% 7 = 1$。
   • $HT[1]$ 被 $22$ 占用，发生冲突。
   • 检查 $HT[2]$，被 $43$ 占用，继续检查 $HT[3]$，为空，插入 $15$。
   • 查找长度为 $3$。

查找成功的平均查找长度（ASL）计算公式为：

$$ASL = \frac{\text{所有关键字的查找长度之和}}{\text{关键字数量}}$$

这里所有关键字的查找长度之和为 $1 + 2 + 3 = 6$，关键字数量为 $3$，因此：

$$ASL = \frac{6}{3} = 2$$

正确答案：C

题目详解：
希尔排序的增量序列决定了每次排序的子序列间隔。我们需要根据给定的排序结果反推出增量。

1. 初始序列：$(8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6)$

2. 第一趟排序结果：$(1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8)$

   • 假设增量为 $d_1$，将初始序列分为 $d_1$ 个子序列，每个子序列进行插入排序。
   • 观察第一趟结果，$1$ 移动到了最前面，说明 $d_1$ 较大。尝试 $d_1 = 5$：
     • 子序列为：$(8, 1, 6)$、$(3, 4, 10)$、$(9, 7)$、$(11, 5)$、$(2, 6)$。
     • 对子序列排序后合并，与第一趟结果一致，因此 $d_1 = 5$。

3. 第二趟排序结果：$(1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9)$

   • 在第一趟结果的基础上，假设增量为 $d_2$。
   • 观察第二趟结果，$2$ 和 $3$ 等元素移动，说明 $d_2$ 较小。尝试 $d_2 = 3$：
     • 子序列为：$(1, 4, 5, 10)$、$(3, 2, 7, 8, 9)$、$(7, 6, 11)$。
     • 对子序列排序后合并，与第二趟结果一致，因此 $d_2 = 3$。

因此，两趟排序采用的增量依次是 $5, 3$。

正确答案：D

题目详解：
大根堆的构建过程是从最后一个非叶子节点开始，依次向上调整，使得每个子树都满足大根堆的性质（父节点的值大于等于子节点的值）。初始序列为 $(6, 1, 5, 9, 8, 4, 7)$。

1. 第一步调整：最后一个非叶子节点是索引 $2$（值为 $5$），比较其子节点 $4$（左）和 $7$（右），$7$ 更大，交换 $5$ 和 $7$，序列变为 $(6, 1, 7, 9, 8, 4, 5)$。

2. 第二步调整：调整索引 $1$（值为 $1$），其子节点为 $9$（左）和 $8$（右），$9$ 更大，交换 $1$ 和 $9$，序列变为 $(6, 9, 7, 1, 8, 4, 5)$。

3. 第三步调整：调整索引 $0$（值为 $6$），其子节点为 $9$（左）和 $7$（右），$9$ 更大，交换 $6$ 和 $9$，序列变为 $(9, 6, 7, 1, 8, 4, 5)$。此时需要检查交换后的子树（$6$ 为根），其子节点为 $1$ 和 $8$，$8$ 更大，交换 $6$ 和 $8$，最终序列变为 $(9, 8, 7, 1, 6, 4, 5)$。

因此，正确的序列变化过程是选项 A 的步骤：
$6, 1, 7, 9, 8, 4, 5 \rightarrow 6, 9, 7, 1, 8, 4, 5 \rightarrow 9, 6, 7, 1, 8, 4, 5 \rightarrow 9, 8, 7, 1, 6, 4, 5$。

正确答案：A

题目详解：
冯·诺依曼结构计算机采用二进制编码表示数据的主要原因包括以下几点：

1. 二进制的运算规则简单（I）：二进制只有 $0$ 和 $1$ 两个数码，其运算规则比十进制简单得多。例如，加法规则仅有 $0 + 0 = 0$、$0 + 1 = 1$、$1 + 0 = 1$ 和 $1 + 1 = 10$（进位），这使得硬件实现更加高效。

2. 制造两个稳态的物理器件较容易（II）：二进制只需要物理器件具有两个稳定的状态（如高电平和低电平、开关的导通和截止等），这种设计在工程上更容易实现，且抗干扰能力强。例如，晶体管可以很容易地表示 $0$ 和 $1$ 两种状态。

3. 便于用逻辑门电路实现算术运算（III）：二进制与逻辑门电路（如与门、或门、非门等）天然契合，可以方便地通过逻辑电路实现算术和逻辑运算。例如，加法器可以通过组合逻辑门直接实现二进制加法。

综上所述，I、II 和 III 都是冯·诺依曼结构计算机采用二进制编码的主要原因。

正确答案：D

题目详解：
首先，我们需要将给定的十六进制机器数转换为对应的十进制值，并计算 $x - y$ 的机器数。

1. 转换 $x$ 的机器数 FFFF FFDFH：

   • 这是一个补码表示的负数。补码转换为原码的方法是：取反加 1。
   • 取反：$\text{FFFF FFDFH}$ 取反得到 $0000 0020H$。
   • 加 1：$0000 0020H + 1 = 0000 0021H$。
   • 转换为十进制：$0000 0021H = 33$，所以 $x = -33$。

2. 转换 $y$ 的机器数 0000 0041H：

   • 这是一个正数，直接转换为十进制：$0000 0041H = 65$，所以 $y = 65$。

3. 计算 $x - y$ 的机器数：

   • $x - y = -33 - 65 = -98$。
   • 将 $-98$ 转换为补码表示：
     • 绝对值的二进制表示：$98 = 62H = 0000 0062H$。
     • 取反：$0000 0062H$ 取反得到 $FFFF FF9DH$。
     • 加 1：$FFFF FF9DH + 1 = FFFF FF9EH$。
   • 因此，$x - y$ 的机器数为 $\text{FFFF FF9EH}$。

综上所述，$x = -33$，$y = 65$，$x - y$ 的机器数为 $\text{FFFF FF9EH}$。

正确答案：C

题目详解：
IEEE 754 单精度浮点数的格式由 1 位符号位 $S$ 、8 位阶码 $E$ 和 23 位尾数 $M$ 组成。规格化数的阶码 $E$ 范围为 $1 \leq E \leq 254$ （全 0 和全 1 有特殊用途），对应的指数 $e$ 计算为 $e = E - 127$ ，因此指数的范围为 $-126 \leq e \leq 127$ 。

规格化数的尾数部分隐含最高位为 1，因此其实际值为 $1.M$ 。最小的规格化正数出现在 $E = 1$ （即 $e = -126$ ）且尾数 $M = 0$ 时，其值为：
$1.0 \times 2^{-126}$

其他选项分析：

• 选项 B $1.0 \times 2^{-127}$ ：对应的阶码 $E = 0$ ，此时表示的是非规格化数或零，不是规格化数。
• 选项 C $1.0 \times 2^{-128}$ ：阶码 $E = -1$ ，超出单精度浮点数的表示范围。
• 选项 D $1.0 \times 2^{-149}$ ：这是最小的非规格化正数，而非规格化数。

因此，最小的规格化正数是 $1.0 \times 2^{-126}$ 。

正确答案：A

题目详解：
在32位计算机中，int类型通常占用4个字节（32位）。题目中采用小端（Little Endian）方式存储数据，即低字节存储在低地址，高字节存储在高地址。

1. 首先分析语句 int i = 0; 的机器代码为 C745FC 00 00 00 00：

   • C745FC 是操作码部分，表示将数据存储到某个地址。
   • 00 00 00 00 是数据部分，表示 i = 0 的32位补码表示。

2. 现在分析 int i = -64; 的机器代码：

   • -64 的32位补码表示：
     • 64的二进制表示为 $00000000\ 00000000\ 00000000\ 01000000$。
     • 取反后为 $11111111\ 11111111\ 11111111\ 10111111$。
     • 加1后得到补码 $11111111\ 11111111\ 11111111\ 11000000$，即十六进制 FF FF FF C0。
   • 由于是小端存储，字节顺序为从低到高，因此数据部分应为 C0 FF FF FF。
   • 完整的机器代码为操作码 C745FC 加上数据部分 C0 FF FF FF，即 C745FC C0 FF FF FF。

3. 对比选项：

   • A选项 C745FC C0 FF FF FF 符合计算结果。
   • B、C、D选项的字节顺序或数据值不正确。

正确答案：A

题目详解：
逻辑右移和算术右移的区别在于对最高位（符号位）的处理方式：

1. 逻辑右移：无论最高位是 $0$ 还是 $1$，右移后最高位补 $0$。右移 $1$ 位时，所有位向右移动一位，最左边补 $0$。

   • 原始机器数：$1101\ 1000$
   • 逻辑右移 $1$ 位后：$0110\ 1100$

2. 算术右移：最高位（符号位）保持不变，右移后最高位补原来的符号位。右移 $1$ 位时，所有位向右移动一位，最左边补原来的符号位 $1$。

   • 原始机器数：$1101\ 1000$
   • 算术右移 $1$ 位后：$1110\ 1100$

因此，逻辑右移 $1$ 位得到 $0110\ 1100$，算术右移 $1$ 位得到 $1110\ 1100$。

正确答案：B

题目详解：
对于一个 $2K \times 1$ 位的DRAM芯片，其总容量为 $2^{11} = 2048$ 个存储单元。为了减少地址引脚数，DRAM通常采用行列地址复用的方式，因此需要将地址分为行地址和列地址两部分。设行数为 $r$，列数为 $c$，则有 $r \times c = 2048$。

为了尽量减少刷新开销，应该尽量减少行数 $r$，因为DRAM的刷新是按行进行的，行数越少，刷新开销越小。因此，我们需要将 $r$ 和 $c$ 的取值尽可能均衡，同时让 $r$ 尽可能小。

将 $2048$ 分解为 $r \times c$ 的形式，有以下几种可能：

• $r = 32$，$c = 64$（$32 \times 64 = 2048$）
• $r = 64$，$c = 32$（$64 \times 32 = 2048$）
• $r = 2048$，$c = 1$（$2048 \times 1 = 2048$）
• $r = 1$，$c = 2048$（$1 \times 2048 = 2048$）

其中，$r = 32$ 和 $r = 64$ 是较优的选择，但为了进一步减少刷新开销，应选择行数 $r$ 更小的方案，即 $r = 32$，$c = 64$。

因此，正确答案是选项C。

正确答案：C

题目详解：
根据题目描述，数组 $A$ 的首地址为 $2000H$，每次循环取一个数组元素时，偏移地址为变址值乘以 $\text{sizeof(double)}$。在大多数系统中，$\text{sizeof(double)}$ 为 $8$ 字节。

设进入循环时变址寄存器的内容为 $x$，则本次循环所取元素的地址为：$2000H + x \times 8$

题目给出本次循环所取元素的地址为 $2100H$，因此可以列出方程：$2000H + x \times 8 = 2100H$

将十六进制转换为十进制计算：$2000H = 8192_{10}$$， 2100H = 8448_{10}$

代入方程：
$8192 + 8x = 8448$
$8x = 8448 - 8192$
$8x = 256$
$x = \frac{256}{8}$
$x = 32$

因此，进入该次循环时变址寄存器的内容是 $32$。

正确答案：B

题目详解：
首先，我们需要理解减法指令的执行过程以及CF（进位/借位标志）和OF（溢出标志）的定义。

1. 减法操作：

   • 指令“sub R1, R2, R3”的功能是 $(R1) - (R2) \rightarrow R3$。
   • 给定的寄存器值为：
     • $(R1) = \text{FFFF FFFFH} = 2^{32} - 1$
     • $(R2) = \text{FFFF FFF0H} = 2^{32} - 16$
   • 计算差值：
     • $(R1) - (R2) = (2^{32} - 1) - (2^{32} - 16) = 15$
     • 结果 $R3 = 15$，即 $\text{0000 000FH}$。

2. CF（进位/借位标志）：

   • CF 在减法中表示借位。如果被减数小于减数，则 $CF = 1$，否则 $CF = 0$。
   • 这里 $(R1) = \text{FFFF FFFFH}$ 和 $(R2) = \text{FFFF FFF0H}$，显然 $(R1) > (R2)$，因此 $CF = 0$。

3. OF（溢出标志）：

   • OF 表示有符号数的溢出。对于减法 $a - b$，OF 的计算公式为：
     • $OF = (a_{n} \land \neg b_{n} \land \neg r_{n}) \lor (\neg a_{n} \land b_{n} \land r_{n})$
     • 其中 $a_{n}$、$b_{n}$ 和 $r_{n}$ 分别是 $a$、$b$ 和结果 $r$ 的最高位（符号位）。
   • 将 $(R1)$ 和 $(R2)$ 视为有符号数：
     • $(R1) = \text{FFFF FFFFH}$ 是 $-1$（符号位为1）。
     • $(R2) = \text{FFFF FFF0H}$ 是 $-16$（符号位为1）。
     • 结果 $R3 = 15$ 是 $+15$（符号位为0）。
   • 计算OF：
     • $a_{n} = 1$，$b_{n} = 1$，$r_{n} = 0$。
     • $OF = (1 \land \neg 1 \land \neg 0) \lor (\neg 1 \land 1 \land 0) = (1 \land 0 \land 1) \lor (0 \land 1 \land 0) = 0 \lor 0 = 0$。

综上，$CF = 0$ 且 $OF = 0$。

正确答案：A

题目详解：
在流水线设计中，CPU 时钟周期的确定需要满足以下条件：时钟周期必须不小于所有流水段中最慢的那个段的总时间（包括功能部件时间和流水段寄存器延时）。具体步骤如下：

1. 首先计算每个功能部件加上流水段寄存器延时的总时间：

   • 部件A：$80\,\text{ps} + 20\,\text{ps} = 100\,\text{ps}$
   • 部件B：$50\,\text{ps} + 20\,\text{ps} = 70\,\text{ps}$
   • 部件C：$50\,\text{ps} + 20\,\text{ps} = 70\,\text{ps}$
   • 部件D：$70\,\text{ps} + 20\,\text{ps} = 90\,\text{ps}$
   • 部件E：$50\,\text{ps} + 20\,\text{ps} = 70\,\text{ps}$

2. 找出所有段中的最大值：

   • 最大值是 $100\,\text{ps}$（来自部件A）。

3. 因此，CPU 时钟周期至少为 $100\,\text{ps}$。

正确答案：D

题目详解：
同步总线数据传输率的提升可以通过以下几种方式实现：

1. 增加总线宽度（I）：总线宽度增加意味着每次传输可以携带更多数据。数据传输率 $R$ 可以表示为 $R = \text{总线宽度} \times \text{总线频率}$。因此，增加总线宽度可以直接提高数据传输率。

2. 提高总线工作频率（II）：总线工作频率的提高会缩短每个时钟周期的时间，从而在单位时间内完成更多数据传输。数据传输率 $R$ 与总线频率成正比。

3. 支持突发传输（III）：突发传输允许在一次地址周期后连续传输多个数据，减少了地址传输的开销，从而有效提高了数据传输率。

4. 采用地址/数据线复用（IV）：这种方式虽然可以减少总线引脚数量，但需要通过分时复用传输地址和数据，增加了控制复杂度，且可能降低数据传输率，因此不会直接提高数据传输率。

综上所述，能够提高同步总线数据传输率的选项是 I、II、III。

正确答案：B

题目详解：
在计算机系统中，外部I/O 中断的处理涉及多个关键机制，下面逐项分析：

选项A：中断控制器通常根据预先设定的中断优先级（如固定优先级或可编程优先级）来决定响应顺序，而不是简单地按照请求的先后次序。例如，$IRQ_0$ 可能比 $IRQ_1$ 具有更高的固定优先级。因此该选项错误。

选项B：CPU 响应中断时，中断隐指令负责完成程序计数器（$PC$）和程序状态字（$PSW$）的保护，而通用寄存器的保护是由中断服务程序通过压栈指令（如 $PUSH$）完成的。因此该选项错误。

选项C：CPU 通过中断允许触发器（如 $IF$ 标志位）控制中断响应。只有当 $IF = 1$（中断允许状态）时，CPU 才会响应可屏蔽中断请求。这是正确的叙述。

选项D：CPU 仅在当前指令执行结束后才会检查中断请求（除非是异常或不可屏蔽中断）。现代流水线架构中，还可能等待流水线排空。立即暂停当前指令的说法不准确，因此该选项错误。

正确答案：C

题目详解：
多任务操作系统是指能够同时管理和执行多个任务的系统。其核心特点和相关需求分析如下：

1. 并发和并行（I）：

   • 并发：指系统通过任务切换在单个 $CPU$ 上交替执行多个任务，宏观上表现为“同时运行”。
   • 并行：指在多 $CPU$ 硬件上真正同时执行多个任务。多任务操作系统通常支持并发，若硬件支持多 $CPU$，则可实现并行。因此，I 正确。

2. 共享资源保护（II）：

   • 多任务环境下，多个任务可能访问同一资源（如内存、文件），需通过同步机制（如信号量、锁）避免冲突，确保数据一致性。因此，II 正确。

3. 多 $CPU$ 硬件需求（III）：

   • 多任务操作系统可在单 $CPU$ 或多 $CPU$ 平台上运行。多 $CPU$ 能提升并行能力，但非必需条件。因此，III 错误。

综上，仅 I 和 II 正确。

正确答案：C

题目详解：
本题考察非抢占式优先级调度，由优先权可知，进程的执行顺序为 P2 → P3 → P1。

P2 的周转时间：1 +15+24= 40μs

P3 的周转时间：18+1+24+1 +36= 80μs

P1 的周转时间：30+1+24 +1 +36+1 +12=105μs

平均周转时间： (40+80+105) /3= 225/3= 75μs, 故选 D。

正确答案：D

题目详解：
仔细阅读两个线程代码可知，threadl 和 thread2 均是对 x 进行加 1 操作，x 初始值为 0，若要使得最终 x = 2，只有先执行 thread1 再执行 thread2，或先执行 thread2 再执行 threadl，故只有 2 种可能，选 B。

题目详解：
首先，我们整理题目中的已知信息：

1. 总资源数： $4$
2. 进程资源需求：
   • $P_1$ 需要 $4$ 个资源，已分配 $2$ 个，还需求 $4 - 2 = 2$ 个。
   • $P_2$ 需要 $3$ 个资源，已分配 $1$ 个，还需求 $3 - 1 = 2$ 个。
   • $P_3$ 需要 $1$ 个资源，已分配 $0$ 个，还需求 $1 - 0 = 1$ 个。
3. 已分配资源总数： $2 (P_1) + 1 (P_2) + 0 (P_3) = 3$ 个。
4. 可用资源数： $4 - 3 = 1$ 个。

接下来，我们尝试找到一个安全序列：

• 第一步：检查当前可用资源 $1$ 是否能满足某个进程的需求：
  • $P_3$ 需要 $1$ 个资源，可以满足。假设执行 $P_3$，释放 $1$ 个资源，此时可用资源变为 $1 + 1 = 2$ 个。
• 第二步：检查剩余进程 $P_1$ 和 $P_2$ 的需求：
  • $P_1$ 需要 $2$ 个资源，$P_2$ 需要 $2$ 个资源。当前可用资源 $2$ 只能满足其中一个进程的需求，但无论选择哪个，另一个进程的需求都无法满足。

因此，系统无法找到一个安全序列，导致系统处于不安全状态。

正确答案：A