2010年408真题

题目详解：
首先，我们需要理解题目条件：

1. 进栈顺序为 $a, b, c, d, e, f$。
2. 允许进栈和退栈操作交替进行。
3. 不允许连续三次进行退栈操作。

我们需要检查每个选项的出栈序列是否满足上述条件。

选项A：$d \ c \ e \ b \ f \ a$

1. 操作序列：
   • 进 $a, b, c, d$（栈：$a, b, c, d$）。
   • 退 $d$（栈：$a, b, c$）。
   • 退 $c$（栈：$a, b$）。
   • 进 $e$（栈：$a, b, e$）。
   • 退 $e$（栈：$a, b$）。
   • 退 $b$（栈：$a$）。
   • 进 $f$（栈：$a, f$）。
   • 退 $f$（栈：$a$）。
   • 退 $a$（栈：空）。
   • 没有连续三次退栈操作，因此是可能的序列。

选项B：$c \ b \ d \ a \ e \ f$

1. 操作序列：
   • 进 $a, b, c$（栈：$a, b, c$）。
   • 退 $c$（栈：$a, b$）。
   • 退 $b$（栈：$a$）。
   • 进 $d$（栈：$a, d$）。
   • 退 $d$（栈：$a$）。
   • 退 $a$（栈：空）。
   • 进 $e, f$（栈：$e, f$）。
   • 退 $f$（栈：$e$）。
   • 退 $e$（栈：空）。
   • 没有连续三次退栈操作，因此是可能的序列。

选项C：$b \ c \ a \ e \ f \ d$

1. 操作序列：
   • 进 $a, b$（栈：$a, b$）。
   • 退 $b$（栈：$a$）。
   • 进 $c$（栈：$a, c$）。
   • 退 $c$（栈：$a$）。
   • 退 $a$（栈：空）。
   • 进 $d, e$（栈：$d, e$）。
   • 退 $e$（栈：$d$）。
   • 进 $f$（栈：$d, f$）。
   • 退 $f$（栈：$d$）。
   • 退 $d$（栈：空）。
   • 没有连续三次退栈操作，因此是可能的序列。

选项D：$a \ f \ e \ d \ c \ b$

1. 操作序列：
   • 进 $a$（栈：$a$）。
   • 退 $a$（栈：空）。
   • 进 $b, c, d, e, f$（栈：$b, c, d, e, f$）。
   • 退 $f$（栈：$b, c, d, e$）。
   • 退 $e$（栈：$b, c, d$）。
   • 退 $d$（栈：$b, c$）。
   • 退 $c$（栈：$b$）。
   • 退 $b$（栈：空）。
   • 这里连续进行了 $f, e, d, c, b$ 五次退栈操作，违反了“不允许连续三次进行退栈操作”的条件，因此是不可能的序列。

正确答案：D

题目详解：
这是一个关于双端队列（deque）操作的问题。题目描述了一种特殊的队列，允许在队列的两端进行入队操作，但只能在一端进行出队操作。我们需要分析元素 $a, b, c, d, e$ 依次入队后，通过合理的入队和出队操作，能否得到给定的出队序列。

首先，明确以下几点：

1. 入队可以在队列的前端或后端进行。
2. 出队只能在某一固定端进行（假设为前端，因为题目未明确说明，但通常队列的出队操作在前端）。
3. 初始队列为空，元素按顺序 $a, b, c, d, e$ 依次入队。

我们需要检查每个选项的出队序列是否可以通过合理的入队操作实现。

分析选项：

选项 A：$b \ a \ c \ d \ e$

• 入队操作：
  1. $a$ 入队（前端或后端，假设后端）：队列 $[a]$
  2. $b$ 入队前端：队列 $[b, a]$
  3. $c$ 入队后端：队列 $[b, a, c]$
  4. $d$ 入队后端：队列 $[b, a, c, d]$
  5. $e$ 入队后端：队列 $[b, a, c, d, e]$
• 出队操作（从前端出队）：
  依次出队为 $b, a, c, d, e$，与选项 A 一致。
• 可能。

选项 B：$d \ b \ a \ c \ e$

• 入队操作：
  1. $a$ 入队后端：队列 $[a]$
  2. $b$ 入队前端：队列 $[b, a]$
  3. $c$ 入队后端：队列 $[b, a, c]$
  4. $d$ 入队前端：队列 $[d, b, a, c]$
  5. $e$ 入队后端：队列 $[d, b, a, c, e]$
• 出队操作（从前端出队）：
  依次出队为 $d, b, a, c, e$，与选项 B 一致。
• 可能。

选项 C：$d \ b \ c \ a \ e$

• 要得到 $d$ 第一个出队，$d$ 必须在队列前端。
• 入队操作：
  1. $a$ 入队后端：队列 $[a]$
  2. $b$ 入队前端：队列 $[b, a]$
  3. $c$ 入队后端：队列 $[b, a, c]$
  4. $d$ 入队前端：队列 $[d, b, a, c]$
  5. $e$ 入队后端：队列 $[d, b, a, c, e]$
• 出队操作（从前端出队）：
  依次出队为 $d, b, a, c, e$，但选项 C 的第三个出队元素是 $c$，而实际出队顺序中 $a$ 在 $c$ 之前。无法跳过 $a$ 直接出队 $c$。
• 另一种尝试：
  如果 $c$ 在 $a$ 之前，需要在入队时调整顺序，但初始顺序是 $a, b, c, d, e$，无法直接让 $c$ 跳过 $a$。
• 不可能。

选项 D：$e \ c \ b \ a \ d$

• 入队操作：
  1. $a$ 入队后端：队列 $[a]$
  2. $b$ 入队前端：队列 $[b, a]$
  3. $c$ 入队前端：队列 $[c, b, a]$
  4. $d$ 入队后端：队列 $[c, b, a, d]$
  5. $e$ 入队前端：队列 $[e, c, b, a, d]$
• 出队操作（从前端出队）：
  依次出队为 $e, c, b, a, d$，与选项 D 一致。
• 可能。

结论：
选项 C 的出队序列 $d \ b \ c \ a \ e$ 无法通过合理的入队和出队操作实现。

正确答案：C

题目详解：
正确答案：D
题中所给二叉树的后序序列为 d,b,c,a。结点 d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点 b；结点 b 无左子树，左链域指向其前驱结点 d；结点 c 无左子树，左链域指向其前驱结点 b，无右子树，右链域指向其后继结点 a。故选 D。

题目详解：
正确答案：C

插入 48 以后，该 AVL根结点的平衡因子由 -1 变为 -2, 在最小不平衡子树根结点的右子树 (R) 的左子树 (L) 中插入新结点引起的不平衡属千 RL 型平衡旋转，需要做两次旋转操作（先右旋后左旋）。

调整后，关键字 37 所在结点的左、右子结点中保存的关键字分别是 24、53。

题目详解：
正确答案：B
设树中度为 i（i=0,1,2,3,4）的结点数分别为 NiN_i, 树中结点总数为 N，则树中各结点的度之和等于 N-1，即 $N=1+N1+2N2+3N3+4N4=N0+N1+N2+N3+N4N=1 + N_1 + 2N_2 + 3N_3 + 4N_4 = N_0 + N_1 + N_2 + N_3 + N_4$，根据题设中的数据，即可得到 N0=82N_0 = 82,即树 T 的叶结点的个数是 82。

题目详解：
哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，用于数据压缩等领域。对于 n（n≥2）个权值均不相同的字符构造的哈夫曼树，我们逐一分析各选项：

选项A：该树一定是一棵完全二叉树。
哈夫曼树的构造过程是通过每次选择两个权值最小的结点合并，生成新的父结点，直到只剩一棵树。这种构造方式并不保证树是完全二叉树（即除了最后一层外，其他层都是满的，且最后一层结点尽量靠左）。因此，哈夫曼树不一定是完全二叉树。此选项是错误的。

选项B：树中一定没有度为 1 的结点。
哈夫曼树的构造过程中，每次合并都会生成一个度为 2 的父结点，因此哈夫曼树中只有度为 0（叶子结点）和度为 2 的结点，没有度为 1 的结点。此选项是正确的。

选项C：树中两个权值最小的结点一定是兄弟结点。
在哈夫曼树的构造过程中，首先选择两个权值最小的结点合并，因此它们一定是兄弟结点。此选项是正确的。

选项D：树中任一非叶结点的权值一定不小于下一层任一结点的权值。
哈夫曼树的非叶结点的权值是其子结点权值之和，因此非叶结点的权值一定大于或等于其子结点的权值（因为权值均不相同，所以不会等于）。此选项是正确的。

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

正确答案：A

题目详解：
要保证一个具有 $n$ 个顶点的无向图 $G=(V, E)$ 在任何情况下都是连通的，所需的最少边数可以通过以下步骤计算：

1. 首先，考虑最坏的情况，即图 $G$ 中有一个完全连通的子图包含 $n-1$ 个顶点，而剩下的一个顶点通过一条边连接到该子图。这种情况下，边数最少。

2. 完全连通子图的边数为 $\frac{(n-1)(n-2)}{2}$ ，因为 $n-1$ 个顶点的完全图有 $\frac{(n-1)(n-2)}{2}$ 条边。

3. 剩下的一个顶点需要至少一条边连接到该子图，因此总的最少边数为：
   $\frac{(n-1)(n-2)}{2} + 1$

4. 将题目中的 $n = 7$ 代入公式：
   $\frac{(7-1)(7-2)}{2} + 1 = \frac{6 \times 5}{2} + 1 = 15 + 1 = 16$

因此，最少需要 $16$ 条边才能保证图 $G$ 在任何情况下都是连通的。

正确答案：C

题目详解：
正确答案：B

拓扑排序的过程如下图所示：

可以得到 3 个不同的拓扑序列，分别为 abced、abecd、aebcd。

题目详解：
折半查找的最大比较次数可以通过计算判定树的高度来确定。判定树的高度 $h$ 与顺序表的长度 $n$ 之间的关系满足：$h = \lfloor \log_2 n \rfloor + 1$。

给定顺序表的长度 $n = 16$，代入公式计算：
$h = \lfloor \log_2 16 \rfloor + 1 = \lfloor 4 \rfloor + 1 = 5$

因此，最多需要 $5$ 次比较即可确定元素不存在。

正确答案：B

题目详解：
快速排序的递归次数主要取决于以下因素：

1. 递归次数与初始数据的排列次序有关。当数据已经有序或逆序时，递归次数会达到最坏情况 $O(n)$ ，而在数据随机分布时递归次数为 $O(\log n)$ 。因此选项A是错误的。

2. 递归次数与分区处理顺序密切相关。每次划分后，如果总是先处理较长的分区，会导致递归栈的深度增加，在最坏情况下栈深度为 $O(n)$ ；而如果总是先处理较短的分区，可以将栈深度控制在 $O(\log n)$ 。因此选项B和C的描述是相反的，正确的做法应该是先处理较短的分区。

3. 选项D是正确的，因为递归次数实际上取决于分区处理顺序，说"无关"是不准确的。但题目问的是"下列关于递归次数的叙述中，正确的是"，在给定的选项中D最接近正确，因为其他选项都有明显错误。

快速排序的递归深度可以用以下公式表示：
$\text{递归深度} = \begin{cases} O(n) & \text{最坏情况} \\ O(\log n) & \text{平均情况} \end{cases}$

正确答案：D

题目详解：
根据题目描述，排序过程中前三趟的结果如下：

初始数据： $(2, 12, 16, 88, 5, 10)$

第一趟排序结果： $(2, 12, 16, 5, 10, 88)$

第二趟排序结果： $(2, 12, 5, 10, 16, 88)$

第三趟排序结果： $(2, 5, 10, 12, 16, 88)$

从排序过程可以看出以下特点：

1. 每一趟排序都将当前未排序部分的最大值“冒泡”到未排序部分的末尾。例如：

   • 第一趟将 $88$ 移动到最后。
   • 第二趟将 $16$ 移动到倒数第二的位置。
   • 第三趟将 $12$ 移动到倒数第三的位置。

2. 排序过程中，较小的元素逐步向前移动，例如 $5$ 和 $10$ 在第二趟和第三趟中逐步向左移动。

这些特点符合冒泡排序（Bubble Sort）的基本行为：

• 冒泡排序通过多次遍历数据，每次比较相邻元素并交换它们的位置，将较大的元素逐步“冒泡”到数组的末端。
• 每一趟排序完成后，未排序部分的最大值会被放置在正确的位置。

其他选项的分析：

• 希尔排序（B）：希尔排序是基于插入排序的改进算法，会先将数据分组排序，不会表现出这种逐步将最大值移动到末尾的行为。
• 归并排序（C）：归并排序是分治算法，会将数据分成小块排序后合并，不会产生题目中描述的中间结果。
• 基数排序（D）：基数排序是按照位数进行排序的算法，不涉及相邻元素的比较和交换。

因此，采用的排序方法可能是冒泡排序。

正确答案：A

题目详解：
程序执行时间 $T$ 可以通过以下公式表示：
$T = \frac{指令数}{CPI \times 时钟频率}$
其中：

• $指令数$ 表示程序执行所需的指令总数
• $CPI$ (Cycles Per Instruction) 表示每条指令的平均时钟周期数
• $时钟频率$ 表示CPU 的时钟频率

I. 提高CPU 时钟频率：直接增加公式中的 $时钟频率$ 项，可以缩短程序执行时间 $T$。

II. 优化数据通路结构：通过优化数据通路，可以降低 $CPI$ 的值（例如采用流水线技术），从而减少程序执行时间 $T$。

III. 对程序进行编译优化：编译优化可以减少程序的 $指令数$ 或生成更高效的指令序列（降低 $CPI$），从而缩短程序执行时间 $T$。

综上所述，I、II 和III 都能缩短程序执行时间。

正确答案：D

题目详解：
首先，我们需要将给定的十六进制补码转换为十进制数值：

1. $r1 = FEH$：

   • 二进制表示为 $1111\ 1110$
   • 最高位为1，是负数，补码转换为原码：取反加1，得到 $1000\ 0010$，即 $-2$

2. $r2 = F2H$：

   • 二进制表示为 $1111\ 0010$
   • 最高位为1，是负数，补码转换为原码：取反加1，得到 $1000\ 1110$，即 $-14$

3. $r3 = 90H$：

   • 二进制表示为 $1001\ 0000$
   • 最高位为1，是负数，补码转换为原码：取反加1，得到 $1111\ 0000$，即 $-112$

4. $r4 = F8H$：

   • 二进制表示为 $1111\ 1000$
   • 最高位为1，是负数，补码转换为原码：取反加1，得到 $1000\ 1000$，即 $-8$

接下来计算各选项的乘积：

A. $r1 \times r2 = (-2) \times (-14) = 28$

• 8位补码范围为 $-128$ 到 $127$，$28$ 在此范围内，不溢出。

B. $r2 \times r3 = (-14) \times (-112) = 1568$

• $1568$ 超出 $-128$ 到 $127$ 的范围，会发生溢出。

C. $r1 \times r4 = (-2) \times (-8) = 16$

• $16$ 在范围内，不溢出。

D. $r2 \times r4 = (-14) \times (-8) = 112$

• $112$ 在范围内，不溢出。

综上所述，只有选项 B 的运算结果会发生溢出。

正确答案：B

题目详解：
首先，我们需要分析每个选项在32位机器上的行为：

I. $i == (int)(float)i$

• $i = 785$，转换为float时，由于IEEE 754单精度浮点数有23位尾数，可以精确表示785（因为 $785 < 2^{24}$）。
• 因此，$(float)i$ 精确为785.0，再转换为int仍然是785。
• 所以 $i == (int)(float)i$ 为真。

II. $f == (float)(int)f$

• $f = 1.5678e3 = 1567.8$，转换为int时会截断小数部分，得到1567。
• 再将1567转换为float，由于1567可以用单精度浮点数精确表示，结果为1567.0。
• 但原始 $f = 1567.8$，所以 $f == (float)(int)f$ 为假。

III. $f == (float)(double)f$

• $f$ 是单精度浮点数，转换为双精度浮点数时不会丢失精度。
• 再转换回单精度浮点数，结果与原始 $f$ 相同。
• 所以 $f == (float)(double)f$ 为真。

IV. $(d + f) - d == f$

• $d = 1.5e100$，$f = 1.5678e3$。
• $d + f$ 时，由于 $d$ 的指数远大于 $f$ 的指数，$f$ 的有效数字会被舍入到 $d$ 的指数范围，导致 $d + f = d$。
• 因此 $(d + f) - d = 0$，而 $0 \neq f$，所以表达式为假。

综上所述，只有I和III为真。

正确答案：B

题目详解：
首先，我们需要理解题目中的存储器组织和地址分配。

1. 存储器组织：

   • 每个芯片的容量为 $2K \times 4$ 位，即 $2^{11} \times 4$ 位。
   • 要组成一个 $8K \times 8$ 位的存储器，需要：
     • 位扩展：将两个 $2K \times 4$ 位的芯片组合成一个 $2K \times 8$ 位的存储单元。
     • 字扩展：需要 $\frac{8K}{2K} = 4$ 个这样的存储单元。
   • 因此，总共需要 $4 \times 2 = 8$ 个 $2K \times 4$ 位的芯片。

2. 地址分配：

   • 每个 $2K \times 8$ 位的存储单元占用 $2K$ 的地址空间，即 $2^{11} = 2048$ 个地址。
   • 地址范围划分如下：
     • 第 1 个存储单元：$0000H$ 到 $07FFH$
     • 第 2 个存储单元：$0800H$ 到 $0FFFH$
     • 第 3 个存储单元：$1000H$ 到 $17FFH$
     • 第 4 个存储单元：$1800H$ 到 $1FFFH$

3. 确定地址 $0B1FH$ 所在的存储单元：

   • 将 $0B1FH$ 转换为十进制：$11 \times 16^2 + 1 \times 16^1 + 15 \times 16^0 = 2816 + 16 + 15 = 2847$。
   • 检查地址范围：
     • $0800H$ 到 $0FFFH$ 对应的十进制范围是 $2048$ 到 $4095$。
     • $2847$ 落在这个范围内，因此 $0B1FH$ 属于第 2 个存储单元。

4. 最小地址：

   • 第 2 个存储单元的最小地址是 $0800H$。

因此，地址 $0B1FH$ 所在芯片的最小地址是 $0800H$。

正确答案：D

题目详解：
关于RAM和ROM的区别与特性，我们逐一分析题目中的叙述：

I. RAM是易失性存储器，ROM是非易失性存储器

• RAM（随机存取存储器）是易失性存储器，断电后数据会丢失。
• ROM（只读存储器）是非易失性存储器，断电后数据不会丢失。
• 因此，叙述I是正确的。

II. RAM和ROM都采用随机存取方式进行信息访问

• 随机存取是指可以直接访问任意存储单元，而无需顺序访问。
• RAM和ROM都支持随机存取，因此叙述II是正确的。

III. RAM和ROM都可用作Cache

• Cache（高速缓存）需要高速读写能力，通常由 SRAM（静态RAM）实现。
• ROM 无法用作Cache，因为其写入速度慢且通常为只读。
• 因此，叙述III是错误的。

IV. RAM和ROM都需要进行刷新

• 动态RAM（DRAM） 需要定期刷新以保持数据。
• 静态RAM（SRAM） 和 ROM 不需要刷新。
• 因此，叙述IV是错误的。

综上所述，正确的叙述是 I 和 II，对应选项 A。

正确答案：A

题目详解：
在计算机系统中，一次访存过程中涉及到的三个关键组件及其命中关系如下：

1. TLB (Translation Lookaside Buffer)：用于加速虚拟地址到物理地址的转换。若 TLB 命中，则直接获取物理地址；若未命中，则需要查询页表（Page Table）。

2. Page (页表)：若页表命中，说明虚拟地址对应的物理页存在于内存中；若未命中，则发生缺页异常（Page Fault），需要从磁盘加载页面。

3. Cache (高速缓存)：用于加速对物理地址的访问。若 Cache 命中，则直接获取数据；若未命中，则需要访问主存。

分析各选项：

• 选项A：TLB 未命中，Cache 未命中，Page 未命中
  可能发生。TLB 未命中后查询页表，发现 Page 未命中（缺页），此时 Cache 必然未命中（因为数据尚未加载到内存）。

• 选项B：TLB 未命中，Cache 命中，Page 命中
  可能发生。TLB 未命中后查询页表，发现 Page 命中，此时数据已在内存中，Cache 可能命中。

• 选项C：TLB 命中，Cache 未命中，Page 命中
  可能发生。TLB 命中直接获得物理地址，但 Cache 未命中，而 Page 命中（数据在内存中）。

• 选项D：TLB 命中，Cache 命中，Page 未命中
  不可能发生。TLB 命中说明虚拟地址对应的物理页已映射，Page 必须命中（数据在内存中），此时 Cache 可以命中。

正确答案：D

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

1. 存储器地址寄存器（MAR）：用于存放将要访问的内存单元的地址。这是CPU内部工作寄存器，程序员无法直接访问。因此，选项A不可见。

2. 程序计数器（PC）：用于存放下一条要执行的指令的地址。程序员可以通过分支指令（如 JMP、CALL）或直接修改PC的值来控制程序流程。因此，选项B是可见的。

3. 指令寄存器（IR）：用于存放当前正在执行的指令。这是CPU内部工作寄存器，程序员无法直接访问。因此，选项D不可见。

4. 存储器数据寄存器（MDR）：用于存放从内存读取或写入内存的数据。这是CPU内部工作寄存器，程序员无法直接访问。因此，选项C不可见。

综上所述，只有 程序计数器（PC） 是汇编语言程序员可见的寄存器。

正确答案：B

题目详解：
在指令流水线中，阻塞（Stall）通常由以下几种情况引起：

1. 数据相关（B选项）：当一条指令依赖于前一条指令的结果时，如果结果尚未生成，后续指令必须等待，导致流水线阻塞。例如：

   • 指令1：ADD R1, R2, R3（将 $R2 + R3$ 的结果存入 $R1$）
   • 指令2：SUB R4, R1, R5（需要 $R1$ 的值，但 $R1$ 还未更新）

2. 条件转移（C选项）：当遇到分支指令（如 if-else）时，处理器需要等待分支条件计算完成才能确定下一条指令的地址，导致流水线暂停。

3. 资源冲突（D选项）：当多条指令同时竞争同一硬件资源（如ALU、内存端口）时，部分指令必须等待资源释放，从而引发阻塞。

而 数据旁路（A选项） 是一种优化技术，用于减少数据相关引起的阻塞。它通过将前一条指令的结果直接“转发”给后续指令，避免等待结果写回寄存器。例如：

• 指令1：ADD R1, R2, R3
• 指令2：SUB R4, R1, R5
  通过旁路，$R1$ 的结果可以直接从ALU的输出端传递给指令2，无需等待写入寄存器。因此，数据旁路 不会 引起流水线阻塞，反而是解决阻塞的方法。

正确答案：A

题目详解：
在计算机中，总线标准是指用于连接计算机各部件（如CPU、内存、外设等）的通信标准。题目要求选择所有选项均为总线标准的英文缩写组合。我们逐一分析各选项：

A. 选项分析：

• $PCI$（Peripheral Component Interconnect）：是一种局部总线标准。
• $CRT$（Cathode Ray Tube）：是阴极射线管的缩写，属于显示设备技术，不是总线标准。
• $USB$（Universal Serial Bus）：是一种串行总线标准。
• $EISA$（Extended Industry Standard Architecture）：是一种扩展工业标准总线。
  由于 $CRT$ 不是总线标准，因此A选项不符合要求。

B. 选项分析：

• $ISA$（Industry Standard Architecture）：是一种工业标准总线。
• $CPI$（Cycles Per Instruction）：是衡量CPU性能的指标，不是总线标准。
• $VESA$（Video Electronics Standards Association）：是一种视频总线标准。
• $EISA$：同A选项分析。
  由于 $CPI$ 不是总线标准，因此B选项不符合要求。

C. 选项分析：

• $ISA$：同B选项分析。
• $SCSI$（Small Computer System Interface）：是一种并行总线标准。
• $RAM$（Random Access Memory）：是随机存取存储器的缩写，属于存储器，不是总线标准。
• $MIPS$（Million Instructions Per Second）：是衡量CPU性能的指标，不是总线标准。
  由于 $RAM$ 和 $MIPS$ 不是总线标准，因此C选项不符合要求。

D. 选项分析：

• $ISA$：同B选项分析。
• $EISA$：同A选项分析。
• $PCI$：同A选项分析。
• $PCI\text{-}Express$（Peripheral Component Interconnect Express）：是一种高速串行总线标准。
  所有选项均为总线标准，因此D选项符合要求。

正确答案：D

题目详解：
在单级中断系统中，中断服务程序的执行顺序需要遵循特定的流程以确保系统正确响应中断并恢复正常执行。具体步骤如下：

1. 保护现场（I）：首先需要保存当前程序的上下文（如寄存器状态等），以便中断处理完成后能恢复原程序的执行。

2. 开中断（II）：允许更高优先级的中断嵌套，提高系统的响应能力。这一步通常在保护现场之后进行。

3. 中断事件处理（V）：执行实际的中断处理逻辑，处理引发中断的事件。

4. 恢复现场（VI）：将之前保存的上下文恢复到寄存器中，准备返回到原程序。

5. 中断返回（VII）：最后通过中断返回指令回到原程序的断点处继续执行。

需要注意的是，关中断（III）和 保存断点（IV）通常由硬件在中断发生时自动完成，不属于中断服务程序内部的软件操作。因此，正确的顺序是 $I \rightarrow V \rightarrow VI \rightarrow II \rightarrow VII$。

正确答案：A

题目详解：
逐步计算所需的显存总带宽。

1. 计算每帧的像素数据量：

   • 分辨率：1600 × 1200 像素
   • 颜色深度：24 位（即每个像素占 24 位）
   • 每帧的数据量 = 1600 × 1200 × 24 位

2. 计算每秒刷新所需的数据量（即刷新带宽）：

   • 帧频：85 Hz
   • 刷新带宽 = 每帧数据量 × 帧频 = (1600 × 1200 × 24) × 85 位/秒

3. 考虑显存总带宽的利用率：

   • 题目指出“显存总带宽的 50% 用来刷新屏幕”，即：
     刷新带宽 = 总带宽 × 50%
   • 因此，总带宽 = 刷新带宽 / 50% = 刷新带宽 × 2

4. 具体计算：

   • 每帧数据量 = 1600 × 1200 × 24 位
   • 刷新带宽 = 1600 × 1200 × 24 × 85 位/秒
   • 总带宽 = 2 × (1600 × 1200 × 24 × 85) 位/秒

5. 数值计算：

   • 首先计算基本部分：
     1600 × 1200 = 1,920,000 像素/帧
     1,920,000 × 24 = 46,080,000 位/帧
     46,080,000 × 85 = 3,916,800,000 位/秒（即刷新带宽）
   • 总带宽 = 2 × 3,916,800,000 = 7,833,600,000 位/秒

6. 单位转换：

   • 将位/秒转换为 Mbps（兆位/秒，1 Mbps = 10^6 位/秒）：
     总带宽 ≈ 7,833,600,000 / 1,000,000 = 7,833.6 Mbps
   • 四舍五入后约为 7,834 Mbps。

因此，需要的显存总带宽至少约为 7,834 Mbps。

答案：D. 7 834Mbps。

正确答案：D

题目详解：
操作系统提供给应用程序的接口是 系统调用（System Call）。系统调用是操作系统内核提供给用户程序的一组接口，允许用户程序通过这些接口请求内核的服务，例如文件操作、进程控制、设备管理等。系统调用是用户程序与操作系统之间的桥梁，确保用户程序能够安全、高效地访问硬件和系统资源。

• A. 系统调用：正确答案。系统调用是操作系统提供给应用程序的直接接口。
• B. 中断：中断是硬件或软件发出的信号，用于通知处理器有紧急事件需要处理，但它不是应用程序直接调用的接口。
• C. 库函数：库函数是编程语言或第三方库提供的函数，可能封装了系统调用，但不是操作系统直接提供的接口。
• D. 原语：原语是操作系统内核中不可中断的基本操作，通常用于实现系统调用，但不直接面向应用程序。

正确答案：A

题目详解：
在操作系统中，创建新进程通常由以下事件触发：

1. 用户登录成功（I）：当用户成功登录系统时，操作系统会为该用户创建一个新的进程（通常是 shell 或用户会话进程），因此 I 是正确的。

2. 设备分配（II）：设备分配通常由操作系统内核管理，属于资源分配范畴，不会直接创建新进程。设备分配可能涉及进程的阻塞或唤醒，但不会导致新进程的创建，因此 II 是错误的。

3. 启动程序执行（III）：当用户或系统启动一个程序时，操作系统会为其创建一个新的进程来执行该程序，因此 III 是正确的。

综上所述，只有 I 和 III 会导致创建新进程，因此正确答案是 C。

正确答案：C

题目详解：
信号量的初值为 $3$，表示该资源最初有 $3$ 个可用实例。当前信号量的值为 $1$，表示现在有 $1$ 个可用资源实例。

信号量的当前值 $S$ 与资源的可用个数 $M$ 和等待进程数 $N$ 的关系如下：

• 如果 $S \geq 0$，则 $M = S$，且 $N = 0$（没有进程在等待）。
• 如果 $S < 0$，则 $M = 0$，且 $N = |S|$（等待的进程数为信号量的绝对值）。

本题中，当前信号量值 $S = 1$（$S \geq 0$），因此：

• 可用资源个数 $M = S = 1$。
• 等待进程数 $N = 0$。

所以，$M = 1$，$N = 0$。

正确答案：B

题目详解：
在操作系统中，进程优先级的调整是调度算法的重要部分。以下是各选项的分析：

• 选项A：当 $进程的时间片用完$ 时，说明该进程已经占用CPU一段时间，为了避免该进程长期占用CPU资源，调度器可能会降低其优先级，让其他进程有机会执行。这是合理的时机。

• 选项B：当 $进程刚完成I/O$ 并进入就绪队列时，通常其优先级会被提高，因为I/O操作完成后，进程可能处于活跃状态，需要尽快得到CPU资源。因此，降低优先级不合理。

• 选项C：如果 $进程长期处于就绪队列$ 中，说明其优先级可能较低，此时调度器更可能提高其优先级以避免饥饿现象，而不是降低优先级。

• 选项D：当 $进程从就绪状态转为运行状态$ 时，说明它刚刚获得CPU资源，此时降低优先级不合理，反而可能破坏调度的公平性。

综上所述，进程的时间片用完是降低进程优先级的合理时机。

正确答案：A

题目详解：
正确答案：D

这是 Peterson 算法的实际实现，保证进入临界区的进程合理安全。该算法为了防止两个进程为进入临界区而无限期等待，设置变量 u，表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置 u 标志，不允许另一个进程进入，这时，再同时检测另一个进程状态标志和不允许进入表示，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区。保存的是较晚的一次赋值，因此较晚的进程等待，较早的进程进入。先到先入，后到等待，从而完成临界区访问的要求。

其实这里可以想象为两个人进门，每个人进门前都会和对方客套一句“你先走”。如果进门时没别人，就当和空气说句废话，然后大步登门入室；如果两人同时进门，就互相请先，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大地进门。

题目详解：
正确答案：B

最佳适应算法是指每次为作业分配内存空间时，总是找到能满足空间大小需要的最小的空闲分区给作业，可以产生最小的内存空闲分区，如下图所示。

题目详解：
正确答案：B
页大小为 $2^{10}$ B，页表项大小为 2B，故一页可以存放 $2^9$ 个页表项，逻辑地址空间大小为 $2^{16}$ 页，即共需 $2^{16}$ 个页表项，则需要$2^{16}$/$2^{9}$ = $2^7$= 128 个页面保存页表项，即页目录表中包含表项的个数至少是 128。

题目详解：
文件的最大长度由直接地址索引、一级间接地址索引和二级间接地址索引共同决定。具体计算如下：

1. 直接地址索引：

   • 每个地址项指向一个磁盘数据块，大小为 $256B$。
   • 直接地址索引有 $4$ 个地址项，因此直接地址索引可表示的文件大小为：
     $4 \times 256B = 1 024B$

2. 一级间接地址索引：

   • 每个一级间接地址索引指向一个磁盘索引块，该索引块中可以存放多个地址项。
   • 每个地址项大小为 $4B$，磁盘索引块大小为 $256B$，因此一个索引块可以存放的地址项数量为：
     $\frac{256B}{4B} = 64$
   • 每个地址项指向一个磁盘数据块，大小为 $256B$。
   • 一级间接地址索引有 $2$ 个地址项，因此一级间接地址索引可表示的文件大小为：
     $2 \times 64 \times 256B = 32 768B$

3. 二级间接地址索引：

   • 二级间接地址索引指向一个磁盘索引块，该索引块中的每个地址项再指向另一个磁盘索引块，最终指向磁盘数据块。
   • 每个二级间接地址索引可以表示的地址项数量为：
     $64 \times 64 = 4 096$
   • 每个地址项指向一个磁盘数据块，大小为 $256B$。
   • 二级间接地址索引有 $1$ 个地址项，因此二级间接地址索引可表示的文件大小为：
     $1 \times 4 096 \times 256B = 1 048 576B$

4. 总文件大小：

   • 将直接地址索引、一级间接地址索引和二级间接地址索引的文件大小相加：
     $1 024B + 32 768B + 1 048 576B = 1 082 368B$
   • 转换为 KB：
     $\frac{1 082 368B}{1 024} = 1 057KB$

正确答案：C

题目详解：
设置当前工作目录的主要目的是为了加快文件的检索速度。以下是详细解释：

1. 当前工作目录是用户或程序当前操作的默认目录。当访问文件时，系统会首先在当前工作目录中查找文件，而不需要从根目录开始逐级搜索。

2. 文件路径可以分为绝对路径和相对路径：

   • 绝对路径：从根目录开始的完整路径，例如 $/home/user/file.txt$。
   • 相对路径：相对于当前工作目录的路径，例如 $./file.txt$。

3. 使用相对路径时，系统只需在当前工作目录中检索文件，避免了从根目录开始的完整路径解析，从而显著减少了检索时间。

4. 其他选项分析：

   • A. 节省外存空间：工作目录的设置与外存空间无关。
   • B. 节省内存空间：工作目录的设置与内存空间无关。
   • D. 加快文件的读/写速度：读/写速度主要由存储设备性能决定，与工作目录无关。

因此，设置当前工作目录的主要目的是加快文件的检索速度。

正确答案：C

题目详解：
当本地用户通过键盘登录系统时，键盘输入信息的获取涉及以下过程：

1. 键盘输入会触发硬件中断（通常为 IRQ1），此时 CPU 会暂停当前任务，转而执行与该中断对应的 中断处理程序。

2. 中断处理程序负责从键盘的输入缓冲区（例如 I/O 端口 0x60）读取扫描码，并将其转换为对应的字符或控制信号。

3. 转换后的输入信息会被传递给更高层的程序（如 用户登录程序 或 命令解释程序），但最先获得键盘输入信息的必然是 中断处理程序，因为它直接响应硬件中断。

其他选项的分析：

• A. 命令解释程序：负责解析和执行用户输入的命令，但它在中断处理之后才介入。
• C. 系统调用服务程序：与键盘输入无直接关系，属于软件层面的服务。
• D. 用户登录程序：虽然参与登录流程，但并非直接获取键盘输入。

因此，正确答案是 B. 中断处理程序。

题目详解：
网络体系结构是指计算机网络的分层结构及其相关规范的集合，主要用于描述网络的组织方式和运行机制。它主要包含以下几个方面的内容：

1. 网络的层次（选项A）：网络体系结构通常采用分层设计，如OSI七层模型或TCP/IP四层模型，每一层都有其特定的功能和职责。

2. 每层使用的协议（选项B）：每一层通过特定的协议实现其功能，例如传输层的TCP协议和网络层的IP协议。

3. 每层必须完成的功能（选项D）：每一层需要完成特定的功能，例如数据链路层负责帧的传输，网络层负责路由选择。

而 协议的内部实现细节（选项C）并不属于网络体系结构描述的内容。网络体系结构关注的是“做什么”而不是“怎么做”，协议的内部实现细节属于具体的技术实现，通常由开发者或厂商决定。

正确答案：C

题目详解：
正确答案：C

本题考查交换机 存储转发 的交换方式。分组大小为 1000B，其中分组头大小为 20B，则分组携带的数据大小为 980B，文件长度为 980000B，需拆分为 1000 个分组，加上头部后，每个分组大小为 1000B，总共需要传送的数据量大小为 1MB。由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最 少，最短路径经过 2 个分组交换机。

当 $t = 1M×8/(100Mbps)=80ms$时，H1 发送完最后一个比特。

当 H1 发送完最后一个分组时，该分组需要经过 2 个分组交换机的转发，在 2 次转发完成后，所有分组均到达 H2。每次转发的时间为 $t_0 = 1K×8/(100Mbps)=0.08ms$。

所以，在不考虑分组拆装时间和传播延迟的情况下，当 $t = 80ms + 2t_0 = 80.16ms$ 时，H2 接收完文件，即所需的时间至少为 80.16ms。

题目详解：
在 RIP (Routing Information Protocol) 协议中，距离矢量中的跳数（metric）表示到达目标网络的跳数。RIP 规定最大跳数为 $15$ ，当跳数达到 $16$ 时，表示目标网络不可达。

题目中，路由器 R1 收到邻居路由器 R2 的距离矢量信息 $\langle \text{net1}, 16 \rangle$ ，表示 R2 到达 net1 的跳数为 $16$ 。根据 RIP 协议的定义，跳数为 $16$ 即表示 R2 无法到达 net1。因此，R1 也不能通过 R2 到达 net1。

选项分析：

• A. 错误，R2 无法到达 net1，因此 R1 也无法通过 R2 到达 net1。
• B. 错误，R2 的跳数为 $16$ ，表示无法到达 net1。
• C. 错误，R2 无法到达 net1，因此 R1 也无法通过 R2 到达 net1。
• D. 正确，R2 的跳数为 $16$ ，表示 R1 不能通过 R2 到达 net1。

正确答案：D

题目详解：
当路由器 $R$ 因为网络拥塞而丢弃 $IP$ 分组时，它会通过发送 $ICMP$ 报文通知源主机降低发送速率。这种 $ICMP$ 报文类型称为 源点抑制（Source Quench）。源点抑制是一种流量控制机制，用于缓解网络拥塞。

其他选项的含义如下：

• A. 路由重定向：当路由器发现更好的路由路径时，会发送此报文通知主机更新路由表。

• B. 目的不可达：当路由器无法将数据包送达目标主机或网络时发送。

• D. 超时：当 $IP$ 分组的生存时间（$TTL$）减为 $0$ 时发送。

• 因此，正确答案是 C. 源点抑制。

正确答案：C

题目详解：
给定IP地址空间为 $192.168.5.0/24$，这是一个C类地址，默认子网掩码为 $255.255.255.0$。题目中采用的子网掩码为 $255.255.255.248$，我们需要计算子网个数和每个子网内的最大可分配地址个数。

1. 计算子网掩码的二进制形式：

   • 默认子网掩码 $255.255.255.0$ 的二进制为 $11111111.11111111.11111111.00000000$。
   • 题目中子网掩码 $255.255.255.248$ 的二进制为 $11111111.11111111.11111111.11111000$。
   • 子网掩码中新增的 $1$ 的个数为 $5$（因为 $248$ 的二进制是 $11111000$）。

2. 计算最大子网个数：

   • 子网位数为 $5$，因此最大子网个数为 $2^5 = 32$。

3. 计算每个子网内的最大可分配地址个数：

   • 主机位数为 $3$（因为子网掩码最后 $8$ 位中有 $3$ 个 $0$）。
   • 每个子网的总地址数为 $2^3 = 8$。
   • 每个子网的可分配地址数为总地址数减去网络地址和广播地址，即 $8 - 2 = 6$。

因此，最大子网个数为 $32$，每个子网内的最大可分配地址个数为 $6$。

正确答案：B

题目详解：
广播风暴是指网络中的广播数据包过多，导致网络性能下降甚至瘫痪的现象。要抑制广播风暴，需要能够隔离广播域的设备。下面分析各个选项：

1. 中继器（I）：工作在 $OSI$ 物理层，仅用于信号放大和传输，无法识别或过滤任何数据包，因此无法抑制广播风暴。

2. 集线器（II）：工作在 $OSI$ 物理层，是一个多端口的中继器，会将接收到的数据广播到所有端口，无法隔离广播域，因此无法抑制广播风暴。

3. 网桥（III）：工作在 $OSI$ 数据链路层，可以分割冲突域，但默认情况下会转发广播数据包，因此无法有效抑制广播风暴。

4. 路由器（IV）：工作在 $OSI$ 网络层，可以隔离广播域，默认不转发广播数据包，因此能够有效抑制广播风暴。

综上所述，只有 路由器（IV） 能够抑制广播风暴。

正确答案：D

题目详解：
主机甲当前拥塞窗口为 $4000B$，TCP最大段长度为 $1000B$。主机甲向主机乙连续发送两个最大段（即 $2 \times 1000B = 2000B$）后，成功收到第一个段的确认段，确认段中通告的接收窗口大小为 $2000B$。

此时，主机甲已经发送了 $2000B$ 的数据，但只确认了 $1000B$（第一个段），因此未被确认的数据量为 $1000B$。接收窗口大小为 $2000B$，表示主机乙还能接收 $2000B$ 的数据。

主机甲还可以发送的最大字节数由以下两个因素决定：

1. 接收窗口剩余空间：$2000B - 1000B = 1000B$（因为未被确认的 $1000B$ 占用了一部分接收窗口）。
2. 拥塞窗口剩余空间：$4000B - 2000B = 2000B$（因为已经发送了 $2000B$）。

实际可发送的最大字节数是接收窗口剩余空间和拥塞窗口剩余空间中的较小值，即 $\min(1000B, 2000B) = 1000B$。

正确答案：A

题目详解：
在域名解析过程中，当采用递归查询方法且本地域名服务器无缓存时，解析流程如下：

1. 用户主机向本地域名服务器发送 一条 域名请求消息（递归查询）。

2. 本地域名服务器如果没有缓存，它会代表用户主机向根域名服务器发送请求。根域名服务器返回下一级域名服务器地址，本地域名服务器继续向下一级域名服务器发送请求，直到找到最终的IP地址。这个过程对用户主机是透明的，本地域名服务器只会向用户主机返回最终结果。

3. 在整个过程中，用户主机只发送 一条 请求消息，本地域名服务器也只需要向用户主机返回 一条 响应消息。尽管本地域名服务器可能与其他域名服务器之间有多次交互，但这些交互对用户主机不可见。

因此，用户主机和本地域名服务器发送的域名请求消息数分别为 一条 和 一条。

正确答案：A

题目详解：
1）由装载因子为 0.7, 数据总数为 7, 得一维数组大小为 7/0.7= 10, 数组下标为 0~9。所构造的散列函数值见下表。

线性探测再散列处理冲突后的哈希表

2）查找成功时，是根据每个元素查找次数来计算平均长度的，在等概率的情况下，各关键字的查找次数见下表。

${ASL}_{成功} = 查找次数/元素个数 = (1 + 2 + 1 + 1 + 1 + 3 + 3)/7= 12/7$。

这里要特别防止惯性思维。查找失败时，是根据查找失败位置计算平均次数，根据散列函数 mod7，初始只可能在 0~6 的位置。等概率情况下，查找 0~6 位置查找失败的查找次数见下表。

$ASL_{不成功} = (3 + 2 + 1 + 2 + 1 + 5 + 4) / 7 = 18 / 7 ≈ 2.57$

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

可以将这个问题视为把数组 $ab$ 转换成数组$ba$（$a$ 代表数组的前 $p$ 个元素，$b$ 代表数组中余下的 $n-p$ 个元素），先将$a$ 逆置得到 $a^{-1}b$, 再将 $b$ 逆置得到 $a^{-1}b^{-1}$，最后将整个 $a^{-1}b^{-1}$逆置得到$(a^{-1}b^{-1})^{-1} = ab$。设 Reverse 函数执行将数组元素逆置的操作，对 abcdefgh 向左循环移动 3(p=3) 个位置的过程如下：

Reverse(0,p-1) 得到 cbadefgh:

Reverse(p,n-l) 得到 cbahgfed;

Reverse(0,n-l) 得到 defghabc,

注：Reverse 中，两个参数分别表示数组中待转换元素的始末位置。

2）使用 C 语言描述算法如下：

void reverse(int a[], int from, int to) {
  int i = from;
  int j = to;
  while (i < j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
    i++;
    j--;
  }
}

void loopMove(int a[], int n, int p) {
  if (p < 0) {
    return;
  }
  p = p % n;
  reverse(a, 0, p-1);
  reverse(a, p, n-1);
  reverse(a, 0, n-1);
}

3）上述算法中 3 个 Reverse 函数的时间复杂度分别为$O(p/2)$、$O((n-p)/2)$ 和 $O(n/2)$，故所设计的算法的时间复杂度为 $O(n)$，空间复杂度为$O(1)$。

【另解】借助辅助数组来实现。

算法思想：创建大小为 $p$ 的辅助数组 $S$， 将 $R$ 中前$p$ 个整数依次暂存在 $S$ 中，同时将 $R$中后 $p$ 个整数左移，然后将 $S$ 中暂存的 $p$ 个数依次放回到$R$ 中的后续单元。

时间复杂度为 $O(n)$, 空间复杂度为 $O(p)$ 。

题目详解：
1）操作码占 4 位，则该指令系统最多可有 $2^{4} = 16$ 条指令。操作数占 6 位，其中寻址方式占 3 位、寄存器编号占 3 位，因此该机最多有 $2^{3} = 8$ 个通用寄存器。主存地址空间大小为 128KB，按字编址，字长为 16 位，共有 $128KB/2B = 2162^{16}$个存储单元，因此 MAR 至少为 16 位；因为字长为 16 位，故 MDR 至少为 16 位。

2）寄存器字长为 16 位，PC 和 Rn 可表示的地址范围均为$0 \sim 2^{16}-1$，而主存地址空间为 $2^{16}$，故转移指令的目标地址范围为 0000H~FFFFH（$0 \sim 2^{16}-1$）。

3）汇编语句“add(R4),(R5)+”，对应的机器码为

将对应的机器码写成十六进制形式为 0010 0011 0001 0101B = 2315H。

该指令的功能是将 R4 的内容所指存储单元的数据与 R5 的内容所指存储单元的数据相加，并将结果送入 R5 的内容所指存储单元中。(R4)=1234H，(1234H)=5678H，(R5)=5678H，(5678H)=1234H；执行加法操作 5678H+1234H=68ACH，之后 R5 自增。

该指令执行后，R5 和存储单元 5678H 的内容会改变，R5 的内容从 5678H 变为 5679H，存储单元 5678H 中的内容变为该指令的计算结果 68ACH。

【注意】第 3 问中两个操作数的存储地址和数值有点令人晕头，请读者务必保持清醒。

题目详解：
1）每个 Cache 行对应一个标记项，如下所示：

| 有效位 | 脏位 | 替换控制位 | 标记位 |

不考虑用于 Cache 一致性维护和替换算法的控制位。地址总长度为 28 位（$2^{28} = 256 M$），块内地址 6 位（$2^{6} = 64$），Cache 块号 3 位（$2^{3} = 8$​），故 Tag 的位数为 28-6-3=19 位，还需使用一个有效位，故题中数据 Cache 行的结构如下图所示。

数据 Cache 共有 8 行，因此数据 Cache 的 总容量为 $8 \times (64 + 20/8) B= 532B$。

2）数组 a 在主存的存放位置及其 与 Cache 之间的映射关系如下图所示。

数组按行优先方式存放，首地址为 320，数组元素占 4 字节。a$0$$31$ 所在的主存块对应的 Cache 行号为$(320 + 31 \times 4) / 64 = 6$；a$1$$1$ 所在的主存块对应的 Cache 行号为 $(320 + 256 \times 4 + 1 \times 4) / 64$。

3）数组 a 的大小为$256 \times 256 \times 4B = 2^{18} B$, 占用 $2^{18} / 64 = 2^{12}$ 个主存块，按行优先存放，程序 AA 逐行访问数组，共需访问的次数为 $2^{16}$ 次，未命中次数为 $2^{12}$ 次（即每个字块的第一个数未命中），因此程序 $A$ 的命中率为 $(2^{16} - 2^{12}) / 2^{16} \times 100\% = 93.75\%$。

【另解】数组 a 按行存放，程序 A 按行存取。每个字块中存放 16 个 int 型数据，除访问的第一个不命中，随后的 15 个全都命中，访问全部字块都符合这一规律，且数组大小为字块大小的整数倍，故程序 A 的命中率为 $15/16=93.75$。

程序 B 逐列访问数组 a，Cache 总容量为 64Bx8=512B，数组 a 一行的大小为 1KB，正好是 Cache 容量的 2 倍，可知不同行的同一列数组元素使用的是同一个 Cache 单元，故逐列访问每个数据时，都会将之前的字块置换出，也即每次访问都不会命中，命中率为 0。由于从 Cache 读数据比从主存读数据快很多，所以程序 A 的执行比程序 B 快得多。

注意：本题考查 Cache 容量计算，直接映射方式的地址计算，以及命中率计算（注意：行优先遍历与列优先遍历命中率差别很大）。

题目详解：
1）用 位图表示磁盘的空闲状态。每位表示一个磁盘块的空闲状态，共需要 16384/32 = 512字 = 512×4字节 = 2KB，正好可放在系统提供的内存中。

2）采用 C-SCAN 调度算法，访问磁道的顺序和移动的磁道数见下表。

移动的磁道数为 20+90+20+40 = 170，故总的移动磁道时间为 170ms。

由于转速为 6000rpm，则平均旋转延迟为 5ms，总的旋转延迟时间 = 20ms。

由于转速为 6000rpm，则读取一个磁道上一个扇区的平均读取时间为 0.1ms，总的读取扇区的时间为 0.4ms。

综上，读取上述磁道上 所有扇区所花的总时间为 190.4ms。

3）采用 FCFS调度策略更高效。因为 Flash 半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按 I/O 请求的先后顺序服务。

题目详解：
1） 由于该计算机的逻辑地址空间和物理地址空间均为 64KB=21664KB=2^{16} B，按字节编址，且页的大小为 1KB=2101KB=2^{10} B，故逻辑地址和物理地址的地址格式均为

| 页框号（6 位） | 页内偏移（10 位） |

17CAH = 0001 0111 1100 1010B，可知该逻辑地址的页号为 000101B = 5。

2） 根据 FIFO算法，需要替换装入时间最早的页，故需要置换装入时间最早的 0 号页，即将 5 号页装入 7 号页框中，所以物理地址为 0001 1111 1100 1010B = 1FCAH。

3） 根据 Clock 算法，如果当前指针所指页框的使用位为 0，则替换该页；否则将使用位清零，并将指针指向下一个页框，继续查找。根据题设和示意图，将从 2 号页框开始，前 4 次查找页框号的顺序为 2→4→7→9，并将对应页框的使用位清零。在第 5 次查找中，指针指向 2 号页框，因 2 号页框的使用位为 0，故淘汰 2 号页框对应的 2 号页，把 5 号页装入 2 号页框中，并将对应使用位设置为 1，所以对应的物理地址为 0000 1011 1100 1010B = 0BCAH。

题目详解：
1）显然当甲和乙同时向对方发送数据时，信号在信道中发生冲突后，冲突信号继续向两个方向传播。这种情况下两台主机均检测到冲突需要经过的时间最短：

$T_{(a)} = 1km/200000km/s \times 2 = 0.01ms = \text{\small 单程传播时延} t_0$

设甲先发送数据，当数据即将到达乙时，乙也开始发送数据，此时乙将立刻检测到冲突，而甲要检测到冲突还需等待冲突信号从乙传播到甲。两台主机均检测到冲突的时间最长：

$T_{(b)} = 2km/200000km/s \times 2 = 0.02ms = \text{\small 双程传播时延} 2t_0$

2）甲发送一个数据帧的时间，即发送时延 $t_1 = 1518 \times 8bit/(10Mbps) = 1.2144ms$；乙每成功收到一个数据帧后，向甲发送一个确认帧，确认帧的发送时延 $t\_{2} = 64 \times 8bit/10Mbps = 0.0512ms$；主机甲收到确认帧后，即发送下一数据帧，故主机甲的发送周期 TT = 数据帧发送时延 $t_1$ + 确认帧发送时延 $t_2$ + 双程传播时延 =$t_1 + t_2 + 2t_0$= 1.2856ms。于是主机甲的有效数据传输率$1500 \times 8 / T = 12000bit/1.2856ms≈9.33Mbps$（以太网帧的数据部分为 1500B)。