2009年408真题

题目详解：
为了解决计算机主机与打印机之间速度不匹配的问题，通常采用缓冲区的机制。主机将需要打印的数据依次写入缓冲区，而打印机则从缓冲区中依次取出数据进行打印。这种工作方式需要遵循 先进先出（FIFO） 的原则，即先进入缓冲区的数据会先被打印机取出。

• 栈（A） 的逻辑结构是 后进先出（LIFO），不符合题目要求。
• 队列（B） 的逻辑结构是 先进先出（FIFO），完全符合题目中缓冲区的需求。
• 树（C） 和 图（D） 是更复杂的非线性数据结构，不适合这种顺序处理数据的场景。

因此，该缓冲区的逻辑结构应该是 队列。

正确答案：B

题目详解：
栈 $S$ 的操作遵循后进先出（LIFO）原则，而队列 $Q$ 的操作遵循先进先出（FIFO）原则。题目中元素 $a, b, c, d, e, f, g$ 依次进入栈 $S$，每个元素出栈后立即进入队列 $Q$，最终队列 $Q$ 的出队顺序为 $b, d, c, f, e, a, g$。我们需要根据这一顺序推断栈 $S$ 的容量至少是多少。

1. 初始状态：栈 $S$ 和队列 $Q$ 均为空。
2. 元素依次入栈 $S$ 的顺序为 $a, b, c, d, e, f, g$。
3. 出栈顺序即为队列 $Q$ 的入队顺序，最终队列 $Q$ 的出队顺序为 $b, d, c, f, e, a, g$。

根据队列的FIFO特性，队列 $Q$ 的出队顺序即为入队顺序，因此栈 $S$ 的出栈顺序也是 $b, d, c, f, e, a, g$。我们需要模拟栈 $S$ 的入栈和出栈过程，并记录栈的最大深度。

具体步骤如下：

• 入栈 $a$，栈内容：$[a]$，当前深度：$1$。
• 入栈 $b$，栈内容：$[a, b]$，当前深度：$2$。
• 出栈 $b$ 并进入队列 $Q$，栈内容：$[a]$，当前深度：$1$。
• 入栈 $c$，栈内容：$[a, c]$，当前深度：$2$。
• 入栈 $d$，栈内容：$[a, c, d]$，当前深度：$3$。
• 出栈 $d$ 并进入队列 $Q$，栈内容：$[a, c]$，当前深度：$2$。
• 出栈 $c$ 并进入队列 $Q$，栈内容：$[a]$，当前深度：$1$。
• 入栈 $e$，栈内容：$[a, e]$，当前深度：$2$。
• 入栈 $f$，栈内容：$[a, e, f]$，当前深度：$3$。
• 出栈 $f$ 并进入队列 $Q$，栈内容：$[a, e]$，当前深度：$2$。
• 出栈 $e$ 并进入队列 $Q$，栈内容：$[a]$，当前深度：$1$。
• 出栈 $a$ 并进入队列 $Q$，栈内容：$[]$，当前深度：$0$。
• 入栈 $g$，栈内容：$[g]$，当前深度：$1$。
• 出栈 $g$ 并进入队列 $Q$，栈内容：$[]$，当前深度：$0$。

在上述过程中，栈 $S$ 的最大深度为 $3$（例如在入栈 $d$ 和 $f$ 时）。因此，栈 $S$ 的容量至少需要 $3$ 才能满足操作需求。

正确答案：C

题目详解：
分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍历的方式是 RNL。本题考查的遍历方法并不是二叉树的 3 种基本遍历方式，对于考生而言，重要的是要掌握遍历的思想。

题目详解：
根据 AVL的定义有，任意结点的左、右子树高度差的绝对值不超过 1。而其余 3 个 选项均可以找到不符合该条件的结点。在做题过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进行判断。

题目详解：
一棵完全二叉树的第 $6$ 层有 $8$ 个叶结点，这意味着第 $6$ 层不是最后一层，因为如果第 $6$ 层是最后一层，那么它的所有结点都应该是叶结点。因此，这棵树至少有 $7$ 层。

1. 计算第 $6$ 层的总结点数：

   • 第 $6$ 层最多有 $2^{6-1} = 32$ 个结点。
   • 已知第 $6$ 层有 $8$ 个叶结点，因此第 $6$ 层有 $32 - 8 = 24$ 个非叶结点。

2. 计算第 $7$ 层的结点数：

   • 每个第 $6$ 层的非叶结点会对应第 $7$ 层的 $2$ 个子结点。
   • 因此，第 $7$ 层最多有 $24 \times 2 = 48$ 个结点。

3. 计算总结点数：

   • 前 $5$ 层的结点总数为 $2^5 - 1 = 31$ 个。
   • 第 $6$ 层的结点数为 $32$ 个。
   • 第 $7$ 层的结点数为 $48$ 个。
   • 因此，总结点数最多为 $31 + 32 + 48 = 111$ 个。

正确答案：C

题目详解：
将森林转换为二叉树的过程遵循“左孩子右兄弟”的规则。具体转换步骤如下：

1. 对于森林中的每棵树，树的根结点作为二叉树的根结点。
2. 树中某结点的第一个孩子（最左边的孩子）作为该结点在二叉树中的左孩子。
3. 树中某结点的兄弟结点作为该结点在二叉树中的右孩子。

根据题目描述，在二叉树中结点 $u$ 是结点 $v$ 的父结点的父结点（即 $u$ 是 $v$ 的“祖父结点”），我们需要分析在原来的森林中 $u$ 和 $v$ 可能的关系：

• 情况 I（父子关系）：
  在森林中，$u$ 是 $v$ 的祖父结点（即 $u$ 是 $v$ 的父结点的父结点），这是一种父子关系的延伸。因此，$u$ 和 $v$ 可以是父子关系。

• 情况 II（兄弟关系）：
  在森林中，$u$ 和 $v$ 可能是兄弟关系。例如，$u$ 的父结点和 $v$ 的父结点是同一个结点，且 $u$ 是 $v$ 的父结点的父结点，这意味着 $u$ 和 $v$ 的父结点是兄弟关系，而 $u$ 和 $v$ 本身是兄弟关系。

• 情况 III（$u$ 的父结点与 $v$ 的父结点是兄弟关系）：
  这种情况在森林中并不直接导致 $u$ 是 $v$ 的祖父结点。因此，这种情况不满足题目条件。

综上所述，$u$ 和 $v$ 可能的关系是 I 和 II。

正确答案：B

题目详解：
对于无向连通图的特性分析如下：

I. 所有顶点的度之和为偶数：在无向图中，每条边会贡献 $2$ 个度（一个给边的每个端点），因此所有顶点的度之和等于 $2 \times \text{边数}$ ，必然是偶数。这一叙述是正确的。

II. 边数大于顶点个数减 1：无向连通图的边数至少为 $n - 1$ （例如树的情况），但边数可以大于 $n - 1$ （例如带环的图）。因此“边数大于顶点个数减 1”并不总是成立，这一叙述是错误的。

III. 至少有一个顶点的度为 1：无向连通图中不一定存在度为 1 的顶点，例如环状图中所有顶点的度均为 $2$ 。这一叙述是错误的。

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

正确答案：A

题目详解：
$m$ 阶B树的定义要求如下：

1. 根结点子树数量：根结点最多有 $m$ 棵子树（即最多 $m-1$ 个关键字），因此选项A符合定义。

2. 叶结点层级：所有叶结点必须位于同一层上，这是B树平衡性的体现，因此选项B符合定义。

3. 关键字排列：每个结点内部的关键字必须按照升序或降序排列，因此选项C符合定义。

4. 叶结点指针链接：B树的叶结点之间没有通过指针链接的特性，这是B+树的特点。因此选项D不符合B树的定义。

正确答案：D

题目详解：
初始小根堆的树形结构如下：

        5
       /   \
      8     12
     / \    / \
    19 28 20 15
   /
  22

插入关键字 $3$ 后，首先将 $3$ 放在堆的末尾，即成为 $19$ 的右孩子：

        5
       /   \
      8     12
     / \    / \
    19 28 20 15
   / \
  22  3

接下来进行堆调整（从下往上调整）：

1. 比较 $3$ 和其父节点 $19$，由于 $3 < 19$，交换两者：

        5
       /   \
      8     12
     / \    / \
    3  28 20 15
   / \
  22 19

2. 继续比较 $3$ 和其新的父节点 $8$，由于 $3 < 8$，交换两者：

        5
       /   \
      3     12
     / \    / \
    8  28 20 15
   / \
  22 19

3. 最后比较 $3$ 和其新的父节点 $5$，由于 $3 < 5$，交换两者：

        3
       /   \
      5     12
     / \    / \
    8  28 20 15
   / \
  22 19

调整后的小根堆序列为：$3, 5, 12, 8, 28, 20, 15, 22, 19$。

正确答案：A

题目详解：
给定的数据元素序列为：$11，12，13，7，8，9，23$，这是第二趟排序后的结果。我们需要分析每个排序算法在第二趟排序后可能产生的序列特征，从而确定正确的排序算法。

1. 冒泡排序（A选项）：

   • 冒泡排序每一趟会将最大的元素“冒泡”到当前未排序部分的末尾。
   • 第二趟排序后，序列中至少最后两个元素是有序的（即最大的两个元素在末尾）。
   • 但给定的序列中，$23$ 不在末尾，且前三个元素 $11，12，13$ 已经有序，这与冒泡排序的特征不符。
   • 因此，排除冒泡排序。

2. 插入排序（B选项）：

   • 插入排序每次将一个元素插入到已排序部分的适当位置。
   • 第二趟排序后，前三个元素 $11，12，13$ 已经有序，后续元素未排序。
   • 给定的序列符合插入排序的特征：前三个元素有序，后续元素未排序。
   • 因此，插入排序是可能的。

3. 选择排序（C选项）：

   • 选择排序每一趟选择未排序部分的最小元素，放到已排序部分的末尾。
   • 第二趟排序后，前两个元素是整个序列中最小的两个元素，且有序。
   • 但给定的序列中，前三个元素 $11，12，13$ 有序，且 $7$ 和 $8$ 未出现在前两位，这与选择排序的特征不符。
   • 因此，排除选择排序。

4. 二路归并排序（D选项）：

   • 二路归并排序每次将相邻的两个子序列合并为一个有序序列。
   • 第二趟排序后，序列会被划分为长度为 $4$ 的有序子序列。
   • 但给定的序列中，前三个元素有序，后续元素无序，这与二路归并排序的特征不符。
   • 因此，排除二路归并排序。

综上所述，只有 插入排序 符合给定的序列特征。

正确答案：B

题目详解：
在冯·诺依曼体系结构的计算机中，指令和数据都是以二进制形式存储在存储器中的。CPU 需要通过某种机制来区分当前从存储器中读取的是指令还是数据。这个区分的关键在于 指令周期的不同阶段。

指令周期分为以下几个主要阶段：

1. 取指阶段（Fetch）：CPU 从存储器中读取指令。此时，存储器中的二进制代码被视为 指令。
2. 执行阶段（Execute）：CPU 可能需要从存储器中读取操作数（数据）。此时，存储器中的二进制代码被视为 数据。

因此，CPU 是根据当前所处的 指令周期阶段 来区分二进制代码是指令还是数据的。具体来说：

• 在 取指阶段，从 程序计数器（PC） 指向的地址读取的内容被视为 指令。
• 在 执行阶段，从其他地址（如通过寻址方式计算出的地址）读取的内容被视为 数据。

其他选项的分析：

• A. 指令操作码的译码结果：这是在指令执行阶段的行为，无法用于初始区分。
• B. 指令和数据的寻址方式：寻址方式只是获取地址的方法，无法区分内容类型。
• D. 指令和数据所在的存储单元：指令和数据可能存储在相同的存储单元（如自修改代码），无法作为区分依据。

正确答案：C

题目详解：
首先，我们需要明确变量在内存中的表示方式以及运算过程中的类型转换规则。

1. 变量类型及初始值：

   • $x$ 是 $\text{int}$ 型（32位），初始值为 $127$。
   • $y$ 是 $\text{short}$ 型（16位），初始值为 $-9$。
   • $z$ 是 $\text{int}$ 型（32位），通过 $z = x + y$ 计算得到。

2. 数值的二进制和十六进制表示：

   • $x = 127$ 的二进制表示为 $00000000\ 00000000\ 00000000\ 01111111$，对应的十六进制为 $0000007FH$。
   • $y = -9$ 的二进制表示（16位补码）为 $11111111\ 11110111$，对应的十六进制为 $FFF7H$。

3. 运算过程中的类型转换：

   • 在计算 $z = x + y$ 时，$y$ 是 $\text{short}$ 型，需要先进行符号扩展转换为 $\text{int}$ 型。
   • $y$ 扩展为 32 位后为 $11111111\ 11111111\ 11111111\ 11110111$，对应的十六进制为 $FFFFFFF7H$。

4. 计算 $z = x + y$：

   • $x$ 的 32 位值为 $0000007FH$。
   • $y$ 的 32 位值为 $FFFFFFF7H$。
   • 相加结果为 $0000007FH + FFFFFFF7H = 00000076H$（进位溢出部分被忽略）。

5. 最终结果：

   • $x$ 的值不变，仍为 $0000007FH$。
   • $y$ 的值不变，仍为 $FFF7H$（16位表示）。
   • $z$ 的值为 $00000076H$。

综上所述，正确答案是 D。

正确答案：D

题目详解：
首先，我们需要将 $X$ 和 $Y$ 表示为浮点数格式。浮点数的阶码和尾数均采用补码表示，且位数分别为 $5$ 位（含 $2$ 位符号位）和 $7$ 位（含 $2$ 位符号位）。

1. 表示 $X$ 和 $Y$：

   • $X = 2^7 \times \frac{29}{32}$：
     • 阶码 $E_X = 7$，补码表示为 $00111$（$5$ 位，含 $2$ 位符号位）。
     • 尾数 $M_X = \frac{29}{32}$，补码表示为 $0011101$（$7$ 位，含 $2$ 位符号位）。
   • $Y = 2^5 \times \frac{5}{8}$：
     • 阶码 $E_Y = 5$，补码表示为 $00101$。
     • 尾数 $M_Y = \frac{5}{8}$，补码表示为 $0010100$。

2. 对阶：

   • 阶差 $\Delta E = E_X - E_Y = 7 - 5 = 2$。
   • 将 $Y$ 的阶码调整为 $7$，尾数右移 $2$ 位：
     • 新的尾数 $M_Y' = \frac{5}{8} \times 2^{-2} = \frac{5}{32}$，补码表示为 $0000101$。

3. 尾数相加：

   • $M_X + M_Y' = \frac{29}{32} + \frac{5}{32} = \frac{34}{32} = 1.0625$。
   • 尾数补码表示为 $0100010$（$7$ 位，含 $2$ 位符号位）。

4. 规格化：

   • 尾数 $1.0625$ 需要右规，阶码加 $1$：
     • 新的阶码 $E = 7 + 1 = 8$，补码表示为 $01000$。
     • 新的尾数 $M = \frac{1.0625}{2} = 0.53125$，补码表示为 $0010001$。

5. 判溢出：

   • 阶码 $01000$ 的值为 $8$，超过了 $5$ 位补码表示的范围（$-16$ 到 $15$ 中的 $15$ 是最大正数，但阶码 $8$ 未超过 $15$，但题目中阶码含 $2$ 位符号位，实际阶码数值位为 $3$ 位，最大阶码为 $7$）。
   • 因此，阶码 $8$ 超过了 $3$ 位数值位能表示的最大正数 $7$，发生上溢。

正确答案：D

题目详解：
首先，我们需要理解题目中的几个关键信息：

1. Cache 共有 16 块，采用 2 路组相联映射方式（即每组 2 块）。因此，Cache 的组数为：
   $\text{组数} = \frac{\text{Cache 总块数}}{\text{每组块数}} = \frac{16}{2} = 8 \text{ 组}$

2. 每个主存块大小为 32B，按字节编址。因此，主存地址可以分为以下几个部分：

   • 块内地址：由于每个块有 32B，块内地址需要 $\log_2{32} = 5$ 位。
   • 组号：由于有 8 组，组号需要 $\log_2{8} = 3$ 位。
   • 标记位：主存地址的剩余部分为标记位。

3. 主存 129 号单元的地址计算：

   • 首先，将 129 转换为二进制：$129_{10} = 10000001_2$。
   • 主存地址的划分如下：
     • 块内地址：取低 5 位，即 $00001_2$。
     • 组号：接下来的 3 位，即 $000_2$。
     • 标记位：剩余的高位，即 $100_2$。
   • 但是，这里需要重新计算，因为 129 除以块大小 32 的商为块号，余数为块内偏移：
     $\text{块号} = \left\lfloor \frac{129}{32} \right\rfloor = 4$
     $\text{块内偏移} = 129 \mod 32 = 1$
   • 然后，块号 4 映射到 Cache 的组号：
     $\text{组号} = \text{块号} \mod \text{组数} = 4 \mod 8 = 4$

因此，主存 129 号单元所在主存块应装入到的 Cache 组号是 4。

正确答案：C

题目详解：
首先计算主存的总容量和各部分容量：

• 主存总容量为 $64KB$，其中 $ROM$ 区为 $4KB$，$RAM$ 区为 $64KB - 4KB = 60KB$。

1. 计算 $ROM$ 芯片数：

   • $ROM$ 区总容量为 $4KB$，按字节编址，即 $4K \times 8$ 位。
   • 使用的 $ROM$ 芯片规格为 $2K \times 8$ 位。
   • 需要的 $ROM$ 芯片数为：
     $\frac{4K \times 8}{2K \times 8} = \frac{4}{2} = 2 \text{ 片}$

2. 计算 $RAM$ 芯片数：

   • $RAM$ 区总容量为 $60KB$，即 $60K \times 8$ 位。
   • 使用的 $RAM$ 芯片规格为 $4K \times 4$ 位。
   • 由于每个 $RAM$ 芯片只能提供 $4$ 位数据，而主存按字节编址（$8$ 位），因此需要将两个 $4K \times 4$ 位芯片组合成一个 $4K \times 8$ 位的存储单元。
   • 需要的 $RAM$ 芯片数为：
     $\frac{60K \times 8}{4K \times 8} \times 2 = \frac{60}{4} \times 2 = 15 \times 2 = 30 \text{ 片}$

综上所述，需要的 $ROM$ 芯片数为 $2$ 片，$RAM$ 芯片数为 $30$ 片。

正确答案：D

题目详解：
转移指令采用相对寻址，目标地址的计算公式为：

$\text{目标地址} = \text{当前PC值} + \text{相对位移量}$

1. 转移指令所在主存地址为 $2000H$，指令由两个字节组成（操作码字段和相对位移量字段），因此：

   • 取操作码字段时，PC 自动加 1，此时 $\text{PC} = 2000H + 1 = 2001H$。
   • 取相对位移量字段时，PC 再次自动加 1，此时 $\text{PC} = 2001H + 1 = 2002H$。

2. 相对位移量字段的内容为 $06H$，这是一个 8 位有符号数，需要将其符号扩展为 16 位。由于 $06H$ 的最高位为 0，扩展后仍为 $0006H$。

3. 目标地址计算：
   $\text{目标地址} = \text{当前PC值} + \text{相对位移量} = 2002H + 0006H = 2008H$。

正确答案：C

题目详解：
RISC（精简指令集计算机）和CISC（复杂指令集计算机）是两种不同的指令集架构设计哲学，主要区别如下：

1. 微程序控制器：RISC 通常采用硬布线控制器 而非微程序控制器，因为硬布线控制器速度更快，更适合RISC 的简单指令集。因此，选项A 是错误的。CISC 才普遍采用微程序控制器。

2. 指令执行周期：RISC 的设计目标是简化指令，使大多数指令可以在一个时钟周期 内完成（选项B 正确）。

3. 通用寄存器数量：RISC 为了减少访存操作，通常会设置较多的通用寄存器（选项C 正确）。

4. 指令集复杂度：RISC 的指令数、寻址方式和指令格式种类比CISC 少（选项D 正确），这是RISC 的核心特征。

正确答案：A

题目详解：
在指令流水线中，CPU 的时钟周期由流水线中最慢的功能段（即瓶颈段）决定。这是因为所有功能段必须在同一个时钟周期内完成工作，而时钟周期需要足够长以适应最慢的功能段。

给定的四个功能段的时间分别为 $90ns$ 、 $80ns$ 、 $70ns$ 和 $60ns$ 。其中最慢的功能段时间为 $90ns$ ，因此 CPU 的时钟周期至少需要 $90ns$ 才能确保所有功能段都能完成操作。

正确答案：A

题目详解：
微程序控制器和硬布线控制器是两种不同的控制器实现方式，其特点对比如下：

1. 指令执行速度：

   • 微程序控制器通过执行微程序（存储在控制存储器中的微指令序列）来控制指令的执行，需要多次访问控制存储器，因此执行速度较慢。
   • 硬布线控制器通过组合逻辑电路直接生成控制信号，无需访问控制存储器，因此执行速度更快。

2. 修改和扩展性：

   • 微程序控制器的指令功能可以通过修改微程序（即修改控制存储器中的内容）来实现，因此修改和扩展较为容易。
   • 硬布线控制器的控制逻辑直接由硬件电路实现，若需修改或扩展指令功能，必须重新设计和布线硬件电路，因此修改和扩展难度较大。

综上所述，硬布线控制器的特点是 指令执行速度快，指令功能的修改和扩展难。

正确答案：D

题目详解：
总线带宽的计算公式为：
$\text{总线带宽} = \frac{\text{传输数据量}}{\text{时间}}$

根据题目描述：

1. 一个总线周期并行传输 $4B$ 信息。
2. 一个总线周期占用 $2$ 个时钟周期。
3. 总线时钟频率为 $10MHz$，即时钟周期为 $\frac{1}{10MHz} = 0.1\mu s$。

因此，一个总线周期的时间为：
$2 \times 0.1\mu s = 0.2\mu s$

总线带宽为：
$\frac{4B}{0.2\mu s} = \frac{4B}{0.2 \times 10^{-6}s} = 20 \times 10^{6}B/s = 20MB/s$

正确答案：B

题目详解：
Cache 的命中率是指程序执行过程中访问 Cache 命中的次数占总访存次数的比例。计算公式为：

$\text{命中率} = \frac{\text{总访存次数} - \text{缺失次数}}{\text{总访存次数}} \times 100\%$

根据题目描述，总访存次数为 $1000$ 次，缺失次数为 $50$ 次。因此，命中率为：

$\text{命中率} = \frac{1000 - 50}{1000} \times 100\% = \frac{950}{1000} \times 100\% = 95\%$

正确答案：D

题目详解：
外部中断是由 CPU 外部的事件引发的中断，通常与硬件设备相关。以下是各选项的分析：

• A. 键盘输入：键盘输入是由外部设备（键盘）触发的中断，属于外部中断。当用户按下键盘时，键盘控制器会向 CPU 发送中断信号，因此这是正确选项。

• B. 除数为 0：除数为 0 是 CPU 在执行除法指令时检测到的异常，属于内部中断（或称为陷阱），而非外部中断。

• C. 浮点数运算下溢：浮点数运算下溢是 CPU 在执行浮点运算时检测到的异常，属于内部中断，与外部设备无关。

• D. 访存缺页：访存缺页是内存管理单元（MMU）在地址转换时检测到的异常，属于内部中断，由操作系统处理，与外部设备无关。

因此，只有 A. 键盘输入 是能引起外部中断的事件。

正确答案：A

题目详解：
在单处理机系统中，并行性受到限制，因为只有一个中央处理单元（CPU）。我们需要分析每个选项的可行性：

1. I. 进程与进程：在单处理机系统中，进程不能真正并行执行，只能通过时间片轮转等方式实现并发（伪并行）。因此，进程与进程不能并行。

2. II. 处理机与设备：处理机（CPU）可以和外设并行工作，例如CPU进行计算的同时，磁盘可以进行I/O操作。这是典型的并行场景。

3. III. 处理机与通道：通道是一种专门用于管理I/O操作的硬件，可以独立于CPU工作。因此，处理机与通道可以并行。

4. IV. 设备与设备：不同的外设（如磁盘和打印机）可以同时工作，因此设备与设备可以并行。

综上所述，能够并行的是 II、III 和 IV。

正确答案：D

题目详解：
在高响应比优先调度算法中，响应比（$Response\ Ratio$）的计算公式为：

$Response\ Ratio = \frac{Waiting\ Time + Execution\ Time}{Execution\ Time}$

其中：

• $Waiting\ Time$ 是进程的等待时间
• $Execution\ Time$ 是进程的执行时间

该算法通过计算每个进程的响应比，优先调度响应比高的进程。由于响应比同时考虑了等待时间和执行时间，因此能够兼顾长进程和短进程的需求：

1. 对于短进程，$Execution\ Time$ 较小，响应比会较大，容易被优先调度
2. 对于长进程，随着 $Waiting\ Time$ 的增加，响应比也会逐渐增大，避免长时间饥饿

其他选项分析：

• A. 时间片轮转：仅考虑时间片轮转，不考虑等待时间和执行时间
• B. 短进程优先：仅考虑执行时间，可能导致长进程饥饿
• C. 先来先服务：仅考虑到达顺序，不考虑等待时间和执行时间

正确答案：D

题目详解：
要确定系统可能发生死锁的最小 $K$ 值，我们需要分析死锁发生的条件。死锁的四个必要条件是：

1. 互斥条件
2. 占有并等待
3. 非抢占条件
4. 循环等待条件

在本题中，打印机是互斥资源，每个进程最多需要 $3$ 台打印机。假设每个进程已经占用了 $2$ 台打印机，此时每个进程还需要 $1$ 台打印机才能完成任务。如果此时系统中剩余的打印机数量不足，即所有进程都无法继续执行，就会发生死锁。

设系统中有 $8$ 台打印机，$K$ 个进程。每个进程占用 $2$ 台打印机时，总共占用了 $2K$ 台打印机。此时剩余的打印机数量为 $8 - 2K$。为了发生死锁，剩余的打印机数量必须小于 $K$（因为每个进程还需要 $1$ 台打印机），即：

$$8 - 2K < K$$

$$8 < 3K$$

$$K > \frac{8}{3}$$

$$K \geq 3$$

但是，当 $K = 3$ 时，剩余打印机数量为 $8 - 2 \times 3 = 2$，可以满足其中两个进程的需求，因此不会发生死锁。当 $K = 4$ 时，剩余打印机数量为 $8 - 2 \times 4 = 0$，所有进程都无法继续执行，此时会发生死锁。

因此，$K$ 的最小值是 $4$。

正确答案：C

题目详解：
在分区分配内存管理方式中，主要采用 界地址保护 作为内存保护措施。界地址保护通过为每个分区分配一个 基地址（Base） 和 界限地址（Limit） 来实现。具体原理如下：

1. 基地址（Base）：表示分区的起始物理地址。
2. 界限地址（Limit）：表示分区的长度或最大偏移量。

当程序访问内存时，硬件会检查访问的地址是否满足：

$$\text{Base} \leq \text{访问地址} \leq \text{Base} + \text{Limit}$$

如果条件不成立，则触发越界中断，防止程序访问其他分区的内存空间。

其他选项（B、C、D）描述的保护措施（如程序代码保护、数据保护、栈保护）通常由编译器和操作系统共同实现，但不是分区分配内存管理方式的核心保护机制。

正确答案：A

题目详解：
在分段存储管理系统中，地址长度为 $32$ 位，其中段号占 $8$ 位，那么剩余的位数用于表示段内偏移量（即段长）。计算方式如下：

1. 总地址长度：$32$ 位
2. 段号占用位数：$8$ 位
3. 段内偏移量位数：$32 - 8 = 24$ 位

最大段长由段内偏移量的位数决定，因为段内偏移量的位数决定了可以寻址的最大范围。因此，最大段长为 $2^{24}$ 字节（B）。

正确答案是 C。

题目详解：
文件物理结构的选择取决于随机访问和文件扩展的需求。我们逐一分析各选项：

1. 连续结构（A）：

   • 文件存储在连续的磁盘块中。
   • 随机访问效率高（$O(1)$ 时间）。
   • 但文件扩展困难，可能导致外部碎片。

2. 索引结构（B）：

   • 通过索引块记录文件的所有磁盘块地址。
   • 随机访问效率高（通过索引直接定位，$O(1)$ 时间）。
   • 文件扩展容易（只需分配新块并更新索引）。
   • 是最佳选择。

3. 链式结构且磁盘块变长（D）：

   • 通过指针链接磁盘块，块长度可变。
   • 随机访问效率低（$O(n)$ 时间）。
   • 文件扩展容易，但随机访问性能差。

4. 链式结构且磁盘块定长（C）：

   • 通过指针链接固定长度的磁盘块。
   • 随机访问效率低（$O(n)$ 时间）。
   • 文件扩展容易，但随机访问性能差。

综上所述，索引结构同时满足随机访问高效和文件扩展便捷的需求。

正确答案：B

题目详解：
SCAN 调度（电梯调度）算法的基本思想是磁头沿一个方向移动，依次处理经过的所有磁道请求，直到到达磁盘的一端（即没有更多请求为止），然后掉头反向移动，继续处理请求。具体步骤如下：

1. 初始磁头位置：第 $105$ 道，方向为磁道序号增加（向外）。
2. 请求序列：$35, 45, 12, 68, 110, 180, 170, 195$。
3. 磁头向外移动时，会依次访问大于 $105$ 的请求，按从小到大的顺序处理：
   • 访问 $110$（第一个大于 $105$ 的请求）。
   • 接着访问 $170$、$180$、$195$（按顺序）。
4. 到达磁盘最外端后，磁头掉头向内移动，依次访问小于 $105$ 的请求，按从大到小的顺序处理：
   • 访问 $68$（当前未处理的最大小于 $105$ 的请求）。
   • 接着访问 $45$、$35$、$12$（按顺序）。
5. 最终访问序列为：$110, 170, 180, 195, 68, 45, 35, 12$。

正确答案：A

题目详解：
在文件系统中，文件的访问控制信息通常存储在 $\text{文件控制块 (File Control Block, FCB)}$ 中。$\text{FCB}$ 是操作系统为每个文件维护的一个数据结构，用于存储文件的元数据，包括：

• 文件权限信息（如读、写、执行权限）
• 文件所有者
• 文件大小
• 文件创建和修改时间
• 文件存储位置（如磁盘块指针）

其他选项的分析：

• $\text{文件分配表 (File Allocation Table, FAT)}$：主要用于记录文件占用的磁盘块信息，不存储访问控制信息。
• $\text{用户口令表}$：存储用户认证信息，与文件访问控制无关。
• $\text{系统注册表}$：是 Windows 操作系统存储系统配置信息的数据库，不直接管理文件访问控制。

因此，文件访问控制信息最合理的存储位置是 $\text{文件控制块}$。

正确答案：A

题目详解：
在文件系统中，引用计数值（reference count）用于跟踪指向同一文件实体的链接数量。以下是详细分析：

1. 初始状态：

   • 文件 $F1$ 的引用计数值为 $1$（仅 $F1$ 本身指向该 inode）。

2. 创建符号链接（软链接）$F2$：

   • 符号链接 $F2$ 是一个独立的文件，其内容是 $F1$ 的路径名。
   • $F2$ 的创建不会影响 $F1$ 的引用计数值。
   • 此时 $F1$ 的引用计数值仍为 $1$，$F2$ 的引用计数值不直接关联到 $F1$ 的 inode。

3. 创建硬链接 $F3$：

   • 硬链接 $F3$ 直接指向 $F1$ 的 inode。
   • 硬链接会增加 $F1$ 的引用计数值。
   • 此时 $F1$ 和 $F3$ 共享同一个 inode，引用计数值变为 $2$。

4. 删除 $F1$：

   • 删除 $F1$ 会将其引用计数值减 $1$（从 $2$ 变为 $1$）。
   • 由于 $F3$ 仍指向该 inode，inode 不会被释放。
   • 符号链接 $F2$ 不受影响，因为它是一个独立的文件，但 $F2$ 指向的路径 $F1$ 已失效，因此 $F2$ 的引用计数值为 $1$（仅 $F2$ 自身）。
   • $F3$ 的引用计数值为 $1$（仅 $F3$ 自身指向 inode）。

最终状态：

• $F2$ 的引用计数值为 $1$（符号链接自身的计数）。
• $F3$ 的引用计数值为 $1$（硬链接指向的 inode 计数）。

正确答案：B

题目详解：
在操作系统中，当程序员使用系统调用来打开I/O设备时，通常使用 逻辑设备名 而不是物理设备名或设备号。这是因为：

1. 逻辑设备名（Logical Device Name）是一个抽象的用户友好名称，例如 /dev/ttyS0（串口设备）或 /dev/sda（磁盘设备）。它隐藏了底层硬件的具体细节，提供了统一的访问接口。

2. 物理设备名（Physical Device Name）直接对应硬件的物理地址或标识，例如总线地址或端口号。程序员通常不需要直接操作物理设备名，因为这依赖于硬件细节。

3. 主设备号（Major Device Number）和 从设备号（Minor Device Number）是操作系统内核用于管理设备的内部标识符。主设备号标识设备驱动程序，从设备号标识具体的设备实例。这些编号由内核使用，程序员通常不直接使用。

使用逻辑设备名的好处是：

• 提供设备独立性，程序可以在不同硬件配置上运行而无需修改。
• 简化了设备访问，程序员无需关心底层硬件的具体实现。

因此，正确答案是 A. 逻辑设备名。

题目详解：
在OSI（Open Systems Interconnection）参考模型中，共有7个层次，从下到上依次为：

1. 物理层（Physical Layer）
2. 数据链路层（Data Link Layer）
3. 网络层（Network Layer）
4. 传输层（Transport Layer）
5. 会话层（Session Layer）
6. 表示层（Presentation Layer）
7. 应用层（Application Layer）

• 物理层 负责比特流的传输。
• 数据链路层 负责帧的传输和错误检测，提供点到点的服务。
• 网络层 负责数据包的路由和转发，提供主机到主机的服务。
• 传输层 是第一个提供 端到端（End-to-End）服务的层次，负责数据的可靠传输和流量控制，例如TCP和UDP协议。
• 会话层 负责建立、管理和终止会话。
• 表示层 负责数据格式转换和加密解密。
• 应用层 为用户提供网络服务接口。

因此，自下而上第一个提供端到端服务的层次是 传输层。

正确答案：B

题目详解：
根据奈奎斯特公式，在无噪声情况下，通信链路的最高数据传输速率 $R$ 可以通过以下公式计算：

$R = 2B \log_2 V$

其中：

• $B$ 是链路的带宽，题目中为 $3 \text{kHz}$。
• $V$ 是调制电平数，即每个符号可以表示的不同状态数。

题目中采用 4 个相位，每个相位有 4 种振幅，因此调制电平数 $V$ 为：
$V = 4 \times 4 = 16$

将 $B = 3 \text{kHz}$ 和 $V = 16$ 代入奈奎斯特公式：
$R = 2 \times 3 \text{kHz} \times \log_2 16$
$\log_2 16 = 4$
$R = 6 \text{kHz} \times 4 = 24 \text{kbps}$

因此，该通信链路的最大数据传输速率为 $24 \text{kbps}$。

正确答案：B

题目详解：
在后退 $N$ 帧协议(GBN)中，发送方维护一个窗口，窗口内的帧可以被连续发送。当某个帧的确认未被收到且计时器超时时，发送方会重发该帧及其后续所有已发送但未被确认的帧。

题目中，发送方已经发送了编号为 $0 \sim 7$ 的帧，共 $8$ 个帧。收到的确认帧是 $0$、$2$ 和 $3$ 号帧。这里需要注意以下几点：

1. 确认帧 $0$ 表示 $0$ 号帧及其之前的所有帧已被正确接收，因此 $1$ 号帧的确认隐含在 $0$ 号帧的确认中。
2. 确认帧 $2$ 和 $3$ 表示 $2$ 号和 $3$ 号帧已被正确接收，但 $4$ 号及之后的帧未被确认。

因此，发送方需要重发未被确认的最小编号帧及其后续所有已发送的帧。未被确认的最小编号帧是 $4$ 号帧（因为 $0 \sim 3$ 号帧已被确认），所以需要重发 $4$、$5$、$6$ 和 $7$ 号帧，共 $4$ 个帧。

正确答案：C

题目详解：
以太网交换机在数据链路层（OSI 模型的第 2 层）工作，它根据 MAC 地址（物理地址）进行转发决策。当交换机接收到一个数据帧时，它会检查帧中的 $目的 MAC 地址$，并根据自己的 $MAC 地址表$ 决定将帧转发到哪个端口。因此，交换机进行转发决策时使用的是 $目的物理地址$。

选项分析：

• A. 目的物理地址：正确，交换机根据 $目的 MAC 地址$ 进行转发。
• B. 目的IP 地址：错误，IP 地址是网络层（第 3 层）的概念，交换机不处理 IP 地址。
• C. 源物理地址：错误，交换机虽然会学习 $源 MAC 地址$ 并更新 $MAC 地址表$，但不用于转发决策。
• D. 源IP 地址：错误，交换机不处理 IP 地址。

正确答案：A

题目详解：
在CSMA/CD协议中，为了保证冲突检测，最小数据帧的传输时间必须大于等于信号在最远两个站点之间往返传播的时间。设最远两个站点之间的距离为 $d$，信号传播速度为 $v$，传输速率为 $R$，最小数据帧长度为 $L$。

原始条件满足：

$$\frac{L}{R} \geq \frac{2d}{v}$$

当最小数据帧长度减少 $\Delta L = 800 \text{bit}$ 时，新的最小数据帧长度为 $L' = L - 800$。为了维持冲突检测的条件，新的距离 $d'$ 必须满足：

$$\frac{L - 800}{R} \geq \frac{2d'}{v}$$

将原始条件代入，可以得到：

$$\frac{L}{R} - \frac{800}{R} \geq \frac{2d'}{v}$$

由于原始条件中 $\frac{L}{R} = \frac{2d}{v}$，代入后得到：

$$\frac{2d}{v} - \frac{800}{R} \geq \frac{2d'}{v}$$

整理不等式：

$$d' \leq d - \frac{800 \cdot v}{2R}$$

将已知数值代入：

• $R = 1 \text{Gbps} = 10^9 \text{bit/s}$
• $v = 200000 \text{km/s} = 2 \times 10^8 \text{m/s}$

计算距离变化量：

$$\Delta d = \frac{800 \cdot v}{2R} = \frac{800 \cdot 2 \times 10^8}{2 \times 10^9} = \frac{1600 \times 10^8}{2 \times 10^9} = 80 \text{m}$$

因此，最远两个站点之间的距离至少需要减少 $80 \text{m}$。

正确答案：D

题目详解：
主机甲向主机乙发送了两个连续的 TCP 段，它们的有效载荷分别为 $300B$ 和 $500B$。第一个段的序列号为 $200$。

1. 第一个 TCP 段的序列号为 $200$，有效载荷为 $300B$，因此该段的数据范围是 $200$ 到 $499$（$200 + 300 - 1$）。
2. 第二个 TCP 段的序列号为 $500$（即前一个段的序列号加上前一个段的有效载荷：$200 + 300$），有效载荷为 $500B$，因此该段的数据范围是 $500$ 到 $999$（$500 + 500 - 1$）。
3. 主机乙正确接收到两个段后，期望接收的下一个序列号是最后一个成功接收的字节的下一个字节，即 $1000$（$500 + 500$ 或 $200 + 300 + 500$）。
4. 因此，主机乙发送给主机甲的确认序列号是 $1000$。

正确答案：D

题目详解：
当拥塞窗口为 $16KB$ 时发生超时，TCP 会进入慢启动状态，并将拥塞窗口重置为 $1KB$，同时将慢启动阈值（ssthresh）设置为当前拥塞窗口的一半，即 $8KB$。

接下来的传输过程如下：

1. 第1个RTT：

   • 拥塞窗口 $cwnd = 1KB$。
   • 发送 $1$ 个 TCP 段（$1KB$）。
   • 成功接收确认后，$cwnd$ 翻倍为 $2KB$。

2. 第2个RTT：

   • 拥塞窗口 $cwnd = 2KB$。
   • 发送 $2$ 个 TCP 段（$2KB$）。
   • 成功接收确认后，$cwnd$ 翻倍为 $4KB$。

3. 第3个RTT：

   • 拥塞窗口 $cwnd = 4KB$。
   • 发送 $4$ 个 TCP 段（$4KB$）。
   • 成功接收确认后，$cwnd$ 翻倍为 $8KB$。

4. 第4个RTT：

   • 此时 $cwnd = 8KB$，达到慢启动阈值 $ssthresh = 8KB$，TCP 进入拥塞避免阶段。
   • 在拥塞避免阶段，每收到一个确认，$cwnd$ 增加 $\frac{1}{cwnd}$，即每 RTT 增加 $1KB$。
   • 发送 $8$ 个 TCP 段（$8KB$）。
   • 成功接收确认后，$cwnd$ 增加 $1KB$，变为 $9KB$。

因此，当第 4 个 RTT 时间内发送的所有 TCP 段都得到肯定应答时，拥塞窗口大小是 $9KB$。

正确答案：C

题目详解：
FTP（File Transfer Protocol，文件传输协议）使用两种不同的连接来完成文件传输任务：

1. 控制连接：用于在FTP 客户和服务器之间传递FTP 命令和响应。这种连接建立在 $TCP$ 之上，因为 $TCP$ 提供可靠的、面向连接的服务，确保命令和响应的准确传递。控制连接默认使用端口 $21$ 。

2. 数据连接：用于实际传输文件数据。这种连接也建立在 $TCP$ 之上，但它是临时的，仅在传输数据时建立，传输完成后关闭。数据连接默认使用端口 $20$ 。

题目问的是“传递FTP 命令时使用的连接”，因此正确答案是建立在 $TCP$ 之上的控制连接。

正确答案：A

题目详解：
该方法不一定能（或不能）求得最短路径。

举例说明：

1. 图（1）
   • 设初始顶点为1，目标顶点为4。
   • 实际最短路径长度为2，但利用给定方法求得的路径长度为3，结果并非最短路径。

2. 图（2）
   • 设初始顶点为1，目标顶点为3。
   • 利用给定方法甚至无法求出顶点1到顶点3的路径。

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

问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第 k 个结点的位置。算法的基本设计思想：定义两个指针变量 p 和 q，初始时均指向头结点的下一个结点（链表的第一个结点）。p 指针沿链表移动，当 p 指针移动到第 k 个结点时，q 指针开始与 p 指针同步移动；当 p 指针移动到最后一个结点时，q 指针所指示结点为倒数第 k 个结点。以上过程对链表仅进行一遍扫描。

2）算法的详细实现步骤：

1. count=0，p 和 q 指向链表表头结点的下一个结点；
2. 若 p 为空，转 5；
3. 若 count 等于 k，则 q 指向下一个结点；否则，count=count+l;
4. p 指向下一个结点，转 2：
5. 若 count 等于 k，则查找成功，输出该结点的 data 域的值，返回 1；否则，说明 k 值超过了线性表的长度，查找失败，返回 0；
6. 算法结束。

3）算法实现

int FindElement(Node *head, int k) {
  Node *p1 = head;
  Node *p2 = head;
  for (int i = 0; i < k; i++) {
    p1 = p1->link;
    if (p1 == NULL) {
      return 0;
    }
  }
  // p1 != NULL
  while (p1 != NULL) {
    p1 = p1->link;
    p2 = p2->link;
  }
  printf("%d\n", p2->data);
  return 1;
}

提示：算法程序题，如果能够写出数据结构类型定义，正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。

【评分说明】① 若所给出的算法采用一遍扫描方式就能得到止确结果，可给满分 15 分：若采用两遍或多遍扫描才能得到正确结果的，最高给 10 分；若采用递归算法得到正确结果的，最高给 10 分；若实现算法的空间复杂度过高（使用了大小与 k 有关的辅助数组），但结果正确，最高给 10 分；若实现的算法的空间复杂度过高（使用了大小与 k 有关的辅助数组），但结果正确，最高给 10 分。

②若在算法基本思想描述和算法步骤描述中因文学表达没有非常清晰地反映出算法的思路，但在算法实现中能够清晰看出算法思想和步骤且正确，按照 () 的标准给分。

③若考生的答案中算法基本思想描述、算法步骤描述或算法实现中部分正确，可酌情给分。

题目详解：
1）按题意，外设每秒传送 0.5MB，中断时每次传送 4B。中断方式下，CPU 每次用于数据传送的时钟周期为 5×18+5×2 = 100。（2 分）

为达到外设 0.5MB/s 的数据传输率，外设每秒申请的中断次数为 0.5MB/4B = 125000。（1 分）

1s 内用于中断的开销为 100×125000 = 12500000 = 12.5M 个时钟周期。（1 分）

CPU 用于外设 I/O 的时间占整个 CPU 时间的百分比为 12.5M/500M = 2.5%。（1 分）

2）当外设数据传输率提高到 5MB/s 时，改用 DMA 方式传送，每次 DMA 传送 5000B，1s 内需产生的 DMA 次数为 5MB/5000B=1000。（1 分）

CPU 用于 DMA 处理的总开销为 1000×500 = 500000 = 0.5M 个时钟周期。（1 分）

CPU 用于外设 I/O 的时间占整个 CPU 时间的百分比为 0.5M/500M = 0.1%。（1 分）

【评分说明】如果考生只给出正确的计算结果，未给出计算过程，每个给 2 分。

题目详解：
题干已给出取值和译码阶段每个节拍的功能和有效控制信号，我们应以弄清楚取指阶段中数据通路的信息流动作为突破口，读懂每个节拍的功能和有效控制信号。然后应用到解题思路中，包括划分执行步骤、确定完成的功能、需要的控制信号。

先分析题干中提供的示例（本部分解题时不做要求）：

取指令的功能是根据 PC 的内容所指主存地址，取出指令代码，经过 MDR，最终送至 R。这部分和后面的指令执行阶段的取操作数、存运算结果的方法是相通的。

C1: (PC)→MAR

在读写存储器前，必须先将地址（这里为 PC）送至 MAR。

C2: M(MAR)→MDR, (PC)+1→PC

读写的数据必须经过 DR，指令取出后 PC 自增 1。

C3: (MDR)→IR

然后将读到 MDR 中指令代码送至 IR 进行后续操作。

指令 “ADD(R1),R0” 的操作数一个在主存中，一个在寄存器中，运算结果在主存中。根据指令功能，要读出 R1 的内容所指的主存单元，必须先将 R1 的内容送至 MAR，即 (R1)→MAR。而读出的数据必须经过 MDR，即 M(MAR)→MDR。

因此，将 R1 的内容所指主存单元的数据读出到 MDR 的节拍安排如下：

C5: (R1)→MAR

C6: M(MAR)→MDR

ALU 一端是寄存器 A，MDR 或 R0 中必须有一个先写入 A 中，如 MDR。

C7: (MDR)→A

然后执行加法操作，并将结果送入寄存器 AC。

C8: (A)+(R0)→AC

之后将加法结果写回到 R1 的内容所指主存单元，注意 MAR 中的内容没有改变。

C9: (AC)→MDR

C10: (MDR)→M(MAR)

有效控制信号的安排并不难，只需看数据是流入还是流出，如流入寄存器 X 就是 Xin，流出寄存器 X 就是 Xout。还需注意其他特殊控制信号，如 PC+1、Add 等。

于是得到参考答案如下：

本题答案不唯一：

题目详解：
互斥资源：缓冲区只能互斥访问，因此设置互斥信号量 mutex。

同步问题：$P_1$、$P_2$ 因为奇数的放置与取用而同步，设同步信号量 odd；$P_1$、$P_3$ 因为偶数的放置与取用而同步，设置同步信号量 even；$P_1$、$P_2$、$P_3$因为共享缓冲区，设同步信号量 empty, 初值为 N。程序如下：

semaphore mutex=1;
semaphore odd=0, even=0;
semaphore empty=N;

P1() {
    while (true) {
        x = produce();   // 生成一个数
        P(empty);        // 判断缓冲区是否有空单元
        P(mutex);        // 缓冲区是否被占用
        put();
        V(mutex);        // 释放缓冲区
        if (x % 2 == 0)
            V(even);     // 如果是偶数，向 P3 发出信号
        else
            V(odd);      // 如果是奇数，向 P2 发出信号
    }
}

P2() {
    while (true) {
        P(odd);          // 收到 P1 发来的信号，已产生一个奇数
        P(mutex);        // 缓冲区是否被占用
        getodd();
        V(mutex);        // 释放缓冲区
        V(empty);        // 向 P1 发信号，多出一个空单元
        countodd();
    }
}

P3() {
    while (true) {
        P(even);         // 收到 P1 发来的信号，已产生一个偶数
        P(mutex);        // 缓冲区是否被占用
        geteven();
        V(mutex);        // 释放缓冲区
        V(empty);        // 向 P1 发信号，多出一个空单元
        counteven();
    }
}