2015年408真题

题目详解：
程序执行时，函数调用栈的顺序遵循“后进先出”原则。以下是详细分析：

1. 程序从 $main()$ 函数开始执行，首先将 $main()$ 的上下文压入栈底。
2. 在 $main()$ 中调用 $S(1)$，此时 $S(1)$ 的上下文被压入栈，位于 $main()$ 之上。
3. 在 $S(1)$ 中，由于 $n=1$ 不满足 $n<=0$ 的条件，会继续递归调用 $S(n-1)$ 即 $S(0)$，因此 $S(0)$ 的上下文被压入栈顶。
4. 当 $S(0)$ 执行时，满足 $n<=0$，返回 $0$ 并出栈，接着 $S(1)$ 计算 $S(0)+1$ 并出栈，最后 $main()$ 输出结果后出栈。

因此，栈中信息自栈底到栈顶的顺序为：$main() \rightarrow S(1) \rightarrow S(0)$。

正确答案：A

题目详解：
先序序列为 $a, b, c, d$ 的不同二叉树个数可以通过 卡塔兰数（Catalan Number） 计算。卡塔兰数的公式为：

$C_n = \frac{1}{n+1} \dbinom{2n}{n} = \frac{(2n)!}{(n+1)! \, n!}$

其中，$n$ 表示二叉树的节点数。本题中节点数为 4，因此计算 $C_4$：

$C_4 = \frac{1}{5} \binom{8}{4} = \frac{1}{5} \times 70 = 14$

因此，先序序列为 $a, b, c, d$ 的不同二叉树共有 14 种。

正确答案：B

题目详解：
哈夫曼树是一种带权路径长度最短的二叉树，构建过程中每次选择两个权值最小的节点合并。要判断两个路径是否属于同一棵哈夫曼树，需要满足以下条件：

1. 路径的根节点必须相同：所有路径必须以相同的根节点（这里是 $24$）开始。
2. 路径的中间节点必须一致或可合并：路径中的非叶节点必须是其子节点权值之和。
3. 路径的合法性：路径中的权值序列必须符合哈夫曼树的构建规则，即每次合并的两个节点是当前最小的。

我们逐一分析选项：

• 选项A：路径 $24, 10, 5$ 和 $24, 10, 7$。

  • 两条路径的第二层都是 $10$，但 $10$ 不能同时是 $5$ 和 $7$ 的父节点，因为 $5 + 7 = 12 \neq 10$。不合法。

• 选项B：路径 $24, 10, 5$ 和 $24, 12, 7$。

  • 两条路径的第二层分别是 $10$ 和 $12$，但 $24$ 的子节点必须满足 $10 + 12 = 22 \neq 24$。不合法。

• 选项C：路径 $24, 10, 10$ 和 $24, 14, 11$。

  • 路径 $24, 10, 10$ 中 $10$ 不能是 $10$ 的父节点，因为 $10$ 不能由两个相同的数合并而来（除非是叶子节点，但这里重复了）。不合法。

• 选项D：路径 $24, 10, 5$ 和 $24, 14, 6$。

  • 检查路径合法性：
    • 第一条路径：$24$ 的子节点可以是 $10$ 和 $14$（因为 $10 + 14 = 24$），$10$ 的子节点是 $5$ 和 $5$（$5 + 5 = 10$），$14$ 的子节点是 $6$ 和 $8$（$6 + 8 = 14$）。
    • 第二条路径：$24, 14, 6$ 是合法的，因为 $6$ 是 $14$ 的子节点之一。
  • 两条路径可以属于同一棵哈夫曼树。

正确答案：D

题目详解：
题目描述了一棵无重复关键字的平衡二叉树（AVL 树），其中序遍历得到一个降序序列。这意味着这棵 AVL 树的中序遍历顺序是从大到小排列的，因此可以推断出这棵树的构造是每个结点的左子树的所有关键字都大于当前结点，右子树的所有关键字都小于当前结点（即与常规的二叉搜索树左右子树的定义相反）。

接下来逐一分析选项：

A. 根结点的度一定为 2

• 根结点的度不一定为 2。例如，当 AVL 树只有一个结点时，根结点的度为 0；当 AVL 树有两个结点时，根结点的度为 1。因此，选项 A 错误。

B. 树中最小元素一定是叶结点

• 树中最小元素是通过不断遍历右子树（因为右子树的关键字更小）直到无法继续为止的结点。这个结点可能没有右子树，但它可能有左子树（左子树的关键字更大），因此不一定是叶结点。例如，如果最小元素的左子树存在，它就不是叶结点。因此，选项 B 错误。

C. 最后插入的元素一定是叶结点

• 在 AVL 树中，新插入的元素最初是作为叶结点插入的，但随后可能会因为平衡调整（旋转操作）而变为非叶结点。因此，最后插入的元素不一定是叶结点。选项 C 错误。

D. 树中最大元素一定是无左子树

• 树中最大元素是通过不断遍历左子树（因为左子树的关键字更大）直到无法继续为止的结点。这个结点一定没有左子树（否则可以继续向左遍历找到更大的元素），但它可能有右子树。因此，树中最大元素一定是无左子树的结点。选项 D 正确。

正确答案：D

题目详解：
画出该有向图图形如下：

采用图的深度优先遍历，共 5 种可能： $<v_0, v_1, v_3, v_2>, <v_0, v_2, v_3, v_1>, <v_0, v_2, vi, v_3>, <v_0, v_3,v_2, v_1>, <v_0, v_3, v_1, v_2>$, 选 D。

正确答案：D

题目详解：
V4 开始， kruskal 算法选中的第一条边一定是权值最小的 (V1V1, V4V4), B 错误。由于 V1V1 和 V4V4 已经可达，第二条边含有 V1V1 和 V4V4 的权值为 8 的一定符合prim 算法，排除 A、D。

正确答案：C

题目详解：
折半查找（二分查找）的关键字比较序列必须满足每次比较后搜索范围按规则缩小，即每次比较的关键字必须是当前搜索区间的中间元素。我们需要验证每个选项是否符合这一规则。

1. 选项A：500, 200, 450, 180

   • 初始搜索区间为整个序列，假设序列有序且包含这些关键字。第一次比较 $500$ ，如果目标小于 $500$ ，则搜索区间应为 $[-\infty, 500)$ 。
   • 下一次比较 $200$ ，但 $200$ 不是 $[-\infty, 500)$ 的中间元素，因为 $200$ 小于 $500$ 但无法保证是中间值。进一步比较 $450$ 和 $180$ 也不符合折半查找的规则。因此，选项A不能构成合法的比较序列。

2. 选项B：500, 450, 200, 180

   • 第一次比较 $500$ ，如果目标小于 $500$ ，搜索区间为 $[-\infty, 500)$ 。
   • 下一次比较 $450$ ，可能是 $[-\infty, 500)$ 的中间元素。
   • 接着比较 $200$ 和 $180$ ，也可能是合理的中间元素。因此，选项B可能构成合法的比较序列。

3. 选项C：180, 500, 200, 450

   • 第一次比较 $180$ ，如果目标大于 $180$ ，搜索区间为 $(180, +\infty)$ 。
   • 下一次比较 $500$ ，可能是 $(180, +\infty)$ 的中间元素。
   • 接着比较 $200$ 和 $450$ ，也可能是合理的中间元素。因此，选项C可能构成合法的比较序列。

4. 选项D：180, 200, 500, 450

   • 第一次比较 $180$ ，如果目标大于 $180$ ，搜索区间为 $(180, +\infty)$ 。
   • 下一次比较 $200$ ，可能是 $(180, +\infty)$ 的中间元素。
   • 接着比较 $500$ 和 $450$ ，也可能是合理的中间元素。因此，选项D可能构成合法的比较序列。

综上所述，选项A不符合折半查找的规则。

正确答案：A

题目详解：
由题中失配 s[i] ≠ s[j] 时，i = j = 5, 可知题中的主串和模式串 的位序都是从 0 开始的（要注意灵活应变）。按照 next 数组生成算法，对于 t 有：

依据KMP 算法 ，当失配时，i 不变，j 回退到 next[j] 的位置并重新比较，当失配 s[i] ≠ s[j]时，i=j=5, 由上表不难得出 next[j]=next[5]=2（位序从 0 开始）。从而最后结果应为 i=5（i 保持不变），j=2 。

正确答案：C

题目详解：
在分析排序算法的元素移动次数与关键字初始排列次序的关系时，我们需要关注算法的工作原理：

1. 直接插入排序 (A)：每次将待排序元素插入到已排序序列的适当位置。移动次数取决于初始序列的有序程度，最坏情况下为 $O(n^2)$，与初始次序相关。

2. 起泡排序 (B)：通过相邻元素的比较和交换来排序。移动次数取决于初始序列的逆序对数，最坏情况下为 $O(n^2)$，与初始次序相关。

3. 基数排序 (C)：按照关键字的每一位（如个位、十位等）进行分配和收集。移动次数仅与数据的位数和基数有关，与初始排列次序无关，时间复杂度为 $O(d \cdot n)$（$d$ 为位数）。

4. 快速排序 (D)：通过划分操作将序列分为两部分。移动次数取决于划分的平衡性，最坏情况下为 $O(n^2)$，与初始次序相关。

因此，基数排序是唯一一个元素移动次数与关键字初始排列次序无关的算法。

正确答案：C

题目详解：
小根堆初始状态为：$8, 15, 10, 21, 34, 16, 12$，用数组表示为 $[8, 15, 10, 21, 34, 16, 12]$。

删除堆顶元素 $8$ 后，将最后一个元素 $12$ 移到堆顶，堆变为 $[12, 15, 10, 21, 34, 16]$。接下来需要调整堆以满足小根堆的性质：

1. 比较 $12$ 和其左右子节点 $15$ 和 $10$，选择较小的子节点 $10$ 进行交换。交换后堆为 $[10, 15, 12, 21, 34, 16]$。比较次数：1（$15$ 和 $10$ 比较）。
2. 现在 $12$ 的新位置需要继续调整，比较 $12$ 和其左右子节点 $21$ 和 $16$，选择较小的子节点 $16$ 进行交换。交换后堆为 $[10, 15, 16, 21, 34, 12]$。比较次数：2（$21$ 和 $16$ 比较）。
3. 最后 $12$ 的新位置没有子节点，调整结束。总比较次数为 3（步骤 1 和步骤 2 各 1 次，加上 $12$ 和 $16$ 的比较）。

因此，关键字之间的比较次数是 $3$。

正确答案：C

题目详解：
希尔排序（Shell Sort）是一种改进的插入排序算法，其核心思想是将原始数组分成若干个子序列，对每个子序列进行插入排序。随着排序的进行，子序列的长度逐渐增大，最终整个数组变成一个序列，此时再进行一次直接插入排序即可完成排序。

希尔排序的组内排序采用的是 直接插入排序 ，因为直接插入排序在部分有序的数组中效率较高，适合用于希尔排序的子序列排序过程。其他选项如 折半插入排序 、 快速排序 和 归并排序 虽然也是排序算法，但它们并不适合作为希尔排序的组内排序方法。

正确答案：A

题目详解：
计算机硬件能够直接执行的只有机器语言程序，即选项 I。机器语言是由二进制代码组成的，计算机的中央处理器（CPU）可以直接识别和执行这些二进制指令。机器语言是计算机硬件能够理解和执行的唯一语言。

汇编语言程序（选项 II）和硬件描述语言程序（选项 III）都需要经过翻译或编译过程才能被计算机硬件执行。汇编语言需要通过汇编器转换为机器语言，而硬件描述语言需要通过综合工具转换为硬件电路设计。因此，计算机硬件不能直接执行汇编语言程序和硬件描述语言程序。

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

正确答案：A

题目详解：
补码整数表示时，负数的符号位为 1, 数值位按位取反，末位加 1, 因此剩下的 2 个 1 在最低位时，表示的是最小整数，为 10000011, 转换成真值为 -125。

正确答案：B

题目详解：
浮点数加减运算的步骤如下：

1. 对阶操作：将两个浮点数的阶码对齐，小阶向大阶看齐。对阶过程中，阶码不会增大或减小，因此不会引起阶码上溢或下溢。故叙述 I 正确。

2. 尾数加减：对阶后，尾数直接相加或相减。尾数加减可能导致尾数溢出（即尾数的绝对值大于等于 $2$ ），此时需要通过右规操作调整。

3. 右规操作：尾数右移一位，阶码加 $1$ 。如果阶码已经达到最大值，右规会导致阶码上溢。此外，尾数舍入时可能需要进一步右规，同样可能引起阶码上溢。故叙述 II 正确。

4. 左规操作：如果尾数结果的最高位不是 $1$ ，则需要左规，尾数左移一位，阶码减 $1$ 。如果阶码已经是最小值，左规会导致阶码下溢。故叙述 III 正确。

5. 尾数溢出与结果溢出：尾数溢出可以通过右规调整，不一定导致最终结果的溢出。最终溢出与否取决于阶码是否超出表示范围。故叙述 IV 正确。

综上所述，叙述 I、II、III、IV 均正确。

正确答案：D

题目详解：
主存地址为 32 位，按字节编址，主存块大小为 4 个字，每字 32 位（即 4 字节），因此主存块大小为 $4 \times 4 = 16$ 字节。块内地址需要 $\log_2{16} = 4$ 位。

Cache 能存放 4K 字数据，每字 32 位（即 4 字节），因此 Cache 的数据容量为 $4K \times 4 = 16K$ 字节。每个主存块大小为 16 字节，所以 Cache 中有 $\frac{16K}{16} = 1K$ 个块。因此，块索引需要 $\log_2{1K} = 10$ 位。

直接映射方式下，主存地址分为三部分：标记（Tag）、块索引（Index）和块内地址（Offset）。标记位数为 $32 - 10 - 4 = 18$ 位。

Cache 的总容量包括数据容量和标记容量。数据容量为 $16K \times 8 = 128K$ 位（因为 1 字节 = 8 位）。标记容量为每个块有一个标记，标记位数为 18 位，因此标记总容量为 $1K \times 18 = 18K$ 位。

此外，采用回写方式，每个块需要一个修改位（Dirty Bit），因此需要额外的 $1K \times 1 = 1K$ 位。同时，每个块还需要一个有效位（Valid Bit），因此还需要额外的 $1K \times 1 = 1K$ 位。

因此，Cache 的总容量至少为：
$128K$（数据） $+$ $18K$（标记） $+$ $1K$（修改位） $+$ $1K$（有效位） $=$ $148K$ 位。

正确答案：C

题目详解：
在执行指令 $add \ xaddr, \ 3$ 时，需要访问 $xaddr$ 对应的存储单元。以下是访问主存的过程分析：

1. TLB 查找：首先通过 TLB（快表）查找 $xaddr$ 对应的物理地址。若 TLB 命中，则无需访问主存中的页表；若未命中，则需访问主存中的页表获取物理地址（此时需要 1 次主存访问）。

2. Cache 查找：获取物理地址后，检查 Cache 中是否存在 $xaddr$ 对应的数据。若 Cache 命中，则直接从 Cache 读取数据；若未命中，则需访问主存加载数据到 Cache（此时需要 1 次主存访问）。

3. 直写（Write Through）方式：在 Cache 使用直写方式时，修改 Cache 中的数据会同步写回主存。因此，执行 $add \ xaddr, \ 3$ 后，数据更新会直接写入主存（此时需要 1 次主存访问）。

最优情况：TLB 和 Cache 均命中，此时只需在直写方式下将更新后的数据写回主存 1 次。因此，访问主存的最少次数为 $1$。

正确答案：B

题目详解：
在计算机存储器中，不同类型的存储器具有不同的特性和工作方式。题目问的是哪种存储器在工作期间需要周期性刷新，这主要与存储器的存储原理有关。

1. SRAM（Static RAM，静态随机存储器）：
   使用触发器（Flip-Flop）作为存储单元，只要保持通电，数据就会一直保持，不需要周期性刷新。因此选项 A 不正确。

2. SDRAM（Synchronous Dynamic RAM，同步动态随机存储器）：
   使用电容作为存储单元，由于电容会漏电，数据会逐渐丢失，因此需要周期性刷新（通常每 $64ms$ 刷新一次）以保持数据。因此选项 B 是正确的。

3. ROM（Read-Only Memory，只读存储器）：
   是一种非易失性存储器，数据写入后不可更改，也不需要刷新。因此选项 C 不正确。

4. FLASH（闪存）：
   也是一种非易失性存储器，数据可以多次擦写，但不需要刷新。因此选项 D 不正确。

综上所述，只有 SDRAM 需要周期性刷新。

正确答案：B

题目详解：
在 4 体交叉编址存储器中，存储体编号由主存地址的低 $\log_2 4 = 2$ 位决定。具体计算方式为：存储体编号 $= \text{地址} \mod 4$。

我们首先计算每个地址对应的存储体编号：

• 8005：$8005 \mod 4 = 1$
• 8006：$8006 \mod 4 = 2$
• 8007：$8007 \mod 4 = 3$
• 8008：$8008 \mod 4 = 0$
• 8001：$8001 \mod 4 = 1$
• 8002：$8002 \mod 4 = 2$
• 8003：$8003 \mod 4 = 3$
• 8004：$8004 \mod 4 = 0$
• 8000：$8000 \mod 4 = 0$

访存冲突发生在两个地址访问同一个存储体且连续出现的情况下。我们检查每个选项：

A. 8004 和 8008：存储体编号分别为 $0$ 和 $0$，但它们在序列中不连续（中间有 8001, 8002, 8003, 8004），因此不会冲突。

B. 8002 和 8007：存储体编号分别为 $2$ 和 $3$，不同存储体，不会冲突。

C. 8001 和 8008：存储体编号分别为 $1$ 和 $0$，不同存储体，不会冲突。

D. 8000 和 8004：存储体编号均为 $0$，且它们在序列中是连续的（8004 之后是 8000），因此会发生访存冲突。

正确答案：D

题目详解：
在总线定时中，通信方式主要分为同步通信、异步通信和半同步通信三种类型：

1. 异步通信方式：

   • 全互锁协议（A选项）：需要等待对方的应答信号才能进行下一步操作，因此通信速度最慢，但可靠性最高。该叙述正确。
   • 非互锁协议（B选项）：不依赖应答信号，发送方发出信号后不等待确认，因此可靠性最差。该叙述正确。

2. 同步通信方式（C选项）：

   • 同步通信依赖于统一的同步时钟信号，该时钟信号通常由总线控制器或主设备提供，而不是由各设备分别提供。因此，叙述“同步时钟信号可由各设备提供”是错误的。

3. 半同步通信方式（D选项）：

   • 半同步通信结合了同步和异步的特点，握手信号（如就绪和应答）的采样由同步时钟控制，但允许插入等待周期。该叙述正确。

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

正确答案：C

题目详解：
访问一个扇区的平均存取时间 $T$ 由三部分组成：平均寻道时间 $T_{\text{seek}}$ 、平均旋转延迟 $T_{\text{rotation}}$ 和传输时间 $T_{\text{transfer}}$ 。即：

$T = T_{\text{seek}} + T_{\text{rotation}} + T_{\text{transfer}}$

1. 平均寻道时间 $T_{\text{seek}}$ 已经给出为 $8ms$ 。

2. 平均旋转延迟 $T_{\text{rotation}}$ 是磁盘旋转半圈的时间。磁盘转速为 $7200rpm$ ，即每分钟转 $7200$ 圈，因此每转一圈的时间为：$\frac{60 \text{秒}}{7200} = \frac{1}{120} \text{秒} = 8.33ms$平均旋转延迟为半圈时间：$T_{\text{rotation}} = \frac{8.33ms}{2} = 4.17ms$

3. 传输时间 $T_{\text{transfer}}$ 是从磁头定位到扇区后读取数据的时间。每个磁道有 $1000$ 个扇区，因此读取一个扇区的时间为旋转一圈时间的 $\frac{1}{1000}$ ：$T_{\text{transfer}} = \frac{8.33ms}{1000} = 0.00833ms \approx 0.008ms$将三部分相加得到平均存取时间：$T = 8ms + 4.17ms + 0.008ms \approx 12.18ms$四舍五入后约为 $12.2ms$ 。

正确答案：B

题目详解：
在中断I/O 方式下，CPU 和打印控制接口之间的信息交换主要包括以下几种类型：

1. 打印字符（选项A）：这是需要传输的实际数据，CPU 会将待打印的字符发送到打印控制接口的 $data\ register$ 中，因此这是可能交换的信息。

2. 设备状态（选项C）：打印控制接口会通过 $status\ register$ 向CPU 反馈设备的当前状态（如忙/闲、错误等），因此这也是可能交换的信息。

3. 控制命令（选项D）：CPU 会通过 $control\ register$ 向打印控制接口发送命令（如启动打印、停止打印等），因此这也是可能交换的信息。

4. 主存地址（选项B）：在中断I/O 方式中，数据传输是直接由CPU 控制的，不需要打印控制接口知道或处理主存地址。主存地址通常是在DMA（直接内存访问）方式中使用的，而非中断I/O 方式。因此，主存地址不可能是CPU 和打印控制接口之间交换的信息。

正确答案：B

题目详解：
内部异常（内中断）是CPU在执行指令过程中检测到的异常事件，主要分为以下三类：

1. 故障（fault）：在指令执行前或执行中检测到异常，异常处理后返回到发生异常的指令重新执行。例如缺页异常。

2. 陷阱（trap）：在指令执行后检测到异常，异常处理后返回到下一条指令继续执行。例如系统调用。

3. 终止（abort）：无法确定导致异常的指令位置，通常无法恢复执行，直接终止程序。例如硬件错误。

选项分析：

• A：正确。内部异常是由当前执行的指令直接或间接引发的。
• B：正确。内部异常由CPU内部的异常检测逻辑实时检测。
• C：正确。内部异常的响应是同步的，即在指令执行过程中检测并响应。
• D：错误。只有**故障（fault）**会返回到发生异常的指令继续执行，而陷阱（trap）和终止（abort）不会。

正确答案：D

题目详解：
在处理外部中断时，操作系统需要保存当前进程的执行现场，以便在中断处理完成后能够恢复进程的执行。执行现场主要包括以下内容：

1. 程序计数器（PC）：由硬件自动保存，因为中断发生时硬件需要知道返回地址，所以PC的内容通常由硬件保存到特定的寄存器或栈中，而不是由操作系统负责。

2. 通用寄存器的内容：这些寄存器保存了进程运行时的中间数据，操作系统需要手动保存这些内容，因为硬件不会自动处理通用寄存器的保存和恢复。

3. 块表（TLB）中的内容和 Cache 中的内容：这些是由硬件管理的缓存机制，操作系统通常不会直接干预其内容的保存。

因此，在处理外部中断时，通用寄存器的内容 是由操作系统负责保存的。

正确答案：B

题目详解：
CPU从用户态切换到内核态通常发生在以下情况：

1. 执行特权指令（如中断指令、I/O操作等）
2. 发生异常或中断（如除零错误、缺页异常等）

选项分析：

A. DIV R0, R1
该指令执行除法运算，若 $R1$ 的值为 $0$，会触发除零异常，导致CPU切换到内核态处理异常。因此可能引发态切换。

B. INT n
这是软中断指令，直接触发中断处理流程，强制CPU进入内核态。因此必然引发态切换。

C. NOT R0
该指令仅对寄存器 $R0$ 的内容进行按位取非操作，不涉及特权指令或异常，因此不会导致态切换。

D. MOV R0, addr
若 $addr$ 指向的地址未映射到物理内存（如缺页），会触发缺页异常；或者 $addr$ 属于内核空间时，用户态无权限访问，会触发保护异常。这两种情况均会导致态切换。

综上，只有 NOT R0 是纯逻辑运算，不会触发任何异常或特权操作。

正确答案：C

题目详解：
进程状态转换是操作系统中进程调度的重要概念。进程从执行态变为就绪态通常发生在以下情况：

1. 时间片用完：分时系统中，进程的时间片用完，会被迫让出CPU。
2. 被高优先级进程抢占：当有更高优先级的进程就绪时，当前执行进程会被抢占。

选项分析：

• A. 执行P(wait)操作：$P(wait)$ 操作是信号量的等待操作，会导致进程从执行态变为阻塞态，而非就绪态。
• B. 申请内存失败：申请内存失败会导致进程阻塞，等待内存资源，进入阻塞态。
• C. 启动I/O 设备：启动I/O设备后，进程需要等待I/O完成，进入阻塞态。
• D. 被高优先级进程抢占：这是导致进程从执行态变为就绪态的典型事件，符合题目要求。

因此，正确答案是 $D$。

题目详解：
死锁避免（Deadlock Avoidance）和死锁检测（Deadlock Detection）是两种不同的死锁处理策略，它们的实现方式和特点如下：

1. 死锁避免（S1）：

   • 死锁避免通过动态检查资源分配状态，确保系统始终处于安全状态，从而避免死锁的发生。
   • I 错误：死锁避免并不限制用户申请资源的顺序，而是通过算法（如银行家算法）判断分配资源后系统是否仍处于安全状态。
   • II 正确：死锁避免需要预先知道进程运行所需的资源总量信息，例如银行家算法需要 $\text{Max}$ 、 $\text{Allocation}$ 和 $\text{Need}$ 矩阵。
   • III 正确：死锁避免会拒绝可能导致死锁的资源分配请求，因此不会给可能导致死锁的进程分配资源。

2. 死锁检测（S2）：

   • 死锁检测允许系统进入死锁状态，但会定期检测死锁并采取措施恢复。
   • I 错误：死锁检测不会限制用户申请资源的顺序，因为它允许系统进入死锁状态。
   • II 错误：死锁检测通常也需要资源分配信息（如资源分配图和等待图）来判断是否存在死锁，但不需要预先知道进程的资源总量。
   • III 正确：死锁检测会允许可能导致死锁的资源分配，因为它只在死锁发生后进行检测和恢复。

综上所述：

• I 是错误的，因为S1不限制申请顺序。
• II 是正确的，因为S1需要资源总量信息，而S2不需要。
• III 是正确的，因为S1会拒绝可能导致死锁的分配，而S2会允许。

正确答案：B

题目详解：
根据题目描述，系统为某进程分配了 4 个页框，页框初始为空。进程访问的页号序列为 $2, 0, 2, 9, 3, 4, 2, 8, 2, 4, 8, 4, 5$。接下来要访问的页号为 $7$，使用 LRU（最近最少使用）算法淘汰页面的过程如下：

1. 初始化页框为空：$\text{页框} = []$。
2. 访问页号 $2$：页框未满，直接加入。$\text{页框} = [2]$。
3. 访问页号 $0$：页框未满，直接加入。$\text{页框} = [2, 0]$。
4. 访问页号 $2$：$2$ 已在页框中，更新其访问时间。$\text{页框} = [0, 2]$。
5. 访问页号 $9$：页框未满，直接加入。$\text{页框} = [0, 2, 9]$。
6. 访问页号 $3$：页框未满，直接加入。$\text{页框} = [0, 2, 9, 3]$。
7. 访问页号 $4$：页框已满，淘汰最近最少使用的 $0$，加入 $4$。$\text{页框} = [2, 9, 3, 4]$。
8. 访问页号 $2$：$2$ 已在页框中，更新其访问时间。$\text{页框} = [9, 3, 4, 2]$。
9. 访问页号 $8$：页框已满，淘汰最近最少使用的 $9$，加入 $8$。$\text{页框} = [3, 4, 2, 8]$。
10. 访问页号 $2$：$2$ 已在页框中，更新其访问时间。$\text{页框} = [3, 4, 8, 2]$。
11. 访问页号 $4$：$4$ 已在页框中，更新其访问时间。$\text{页框} = [3, 8, 2, 4]$。
12. 访问页号 $8$：$8$ 已在页框中，更新其访问时间。$\text{页框} = [3, 2, 4, 8]$。
13. 访问页号 $4$：$4$ 已在页框中，更新其访问时间。$\text{页框} = [3, 2, 8, 4]$。
14. 访问页号 $5$：页框已满，淘汰最近最少使用的 $3$，加入 $5$。$\text{页框} = [2, 8, 4, 5]$。
15. 接下来要访问页号 $7$：页框已满，需要淘汰最近最少使用的页面。当前页框为 $[2, 8, 4, 5]$，最近最少使用的页面是 $2$（因为 $2$ 的最近访问时间最早）。

因此，应淘汰页的页号是 $2$。

正确答案：A

题目详解：
在系统内存中设置磁盘缓冲区的主要目的是通过缓存磁盘数据来 $\text{减少磁盘I/O 次数}$。其工作原理如下：

1. 当应用程序请求读取磁盘数据时，系统首先检查缓冲区中是否已存在该数据。若存在（即 $\text{命中}$），则直接从内存返回数据，避免实际磁盘访问。

2. 写入操作时，数据先暂存到缓冲区，后续通过 $\text{延迟写入}$ 或 $\text{批量合并}$ 的方式减少实际磁盘写入次数。

3. 缓冲区通过 $\text{局部性原理}$（时间局部性和空间局部性）优化性能，但不会直接影响：

   • 磁盘机械寻道时间（选项B）
   • 数据可靠性（选项C，需依赖冗余/校验机制）
   • 设备抽象层功能（选项D）

因此，核心目的是降低对慢速磁盘的访问频率。统计上，缓冲区命中率 $H$ 与I/O次数关系为：
$\text{实际I/O次数} = \text{请求次数} \times (1 - H)$

正确答案：A

题目详解：
首先，我们需要计算每个索引块可以存放多少个索引指针。磁盘块大小为 $1KB = 1024$ 字节，每个索引指针占 $4$ 字节，因此每个索引块可以存放的索引指针数量为：$\frac{1024}{4} = 256 \text{ 个}$

接下来，分析文件偏移量对应的磁盘块访问过程：

1. 直接索引：索引结点中有 $10$ 个直接索引指针，每个直接索引指向一个磁盘块。因此，直接索引可以寻址的文件大小为：$10 \times 1KB = 10KB$文件偏移量 $1234$ 字节位于 $10KB$ 范围内，因此可以直接通过直接索引访问对应的磁盘块，无需额外访问其他索引块，仅需访问 $1$ 次磁盘块。

2. 一级索引：一级索引指针指向一个索引块，该索引块可以存放 $256$ 个指针，因此一级索引可以寻址的文件大小为：$256 \times 1KB = 256KB$加上直接索引的 $10KB$，一级索引可以覆盖的文件范围为 $10KB + 256KB = 266KB$。

3. 二级索引：二级索引指针指向一个一级索引块，该一级索引块再指向 $256$ 个二级索引块，每个二级索引块又可以指向 $256$ 个数据块。因此，二级索引可以寻址的文件大小为：$256 \times 256 \times 1KB = 65536KB$加上直接索引和一级索引的范围，总覆盖范围为 $10KB + 256KB + 65536KB = 65802KB$。

文件偏移量 $307400$ 字节转换为 $KB$：$\frac{307400}{1024} \approx 300.2KB$由于 $300.2KB > 266KB$，因此需要通过二级索引访问。

具体过程如下：

• 首先访问二级索引块（第一次磁盘访问）。
• 然后通过二级索引块找到对应的一级索引块（第二次磁盘访问）。
• 最后通过一级索引块找到数据块（第三次磁盘访问）。
  因此，总共需要访问 $3$ 次磁盘块。

综上所述，文件偏移量 $1234$ 和 $307400$ 处所在的磁盘块读入内存，分别需要访问 $1$ 次和 $3$ 次磁盘块。

正确答案：B

题目详解：
在请求分页系统中，页面分配策略和页面置换策略的组合需要满足一定的逻辑关系。具体分析如下：

1. 固定分配（Fixed Allocation）：
   固定分配是指进程的物理页面数量在运行期间是固定的，不会动态调整。因此，它只能使用 局部置换（Local Replacement），即进程只能从自己的物理页面中选择置换的页面。如果固定分配尝试使用 全局置换（Global Replacement），会导致进程的物理页面数量被其他进程抢占，这与“固定分配”的定义矛盾。因此，固定分配不能与全局置换组合使用。

2. 可变分配（Variable Allocation）：
   可变分配允许进程的物理页面数量动态调整，因此它可以与 全局置换（Global Replacement） 或 局部置换（Local Replacement） 组合使用：

   • 可变分配 + 全局置换：全局置换可以从所有进程的物理页面中选择置换的页面，但可能导致某些进程的页面被过度置换，因此通常需要结合页面分配策略的动态调整。
   • 可变分配 + 局部置换：局部置换仅从当前进程的物理页面中选择置换的页面，同时系统可以根据进程的缺页率动态调整其物理页面数量。

综上所述，固定分配与全局置换的组合是不合理的，因为固定分配要求进程的物理页面数量固定，而全局置换会破坏这一约束。因此，选项 C（固定分配，全局置换） 是不能组合使用的策略。

正确答案：C

题目详解：
要计算盘块号为 $409612$ 在位图中的位置，步骤如下：

1. 确定位图的总位数：
   每个盘块占 $1024$ 字节，每字节有 $8$ 位，因此每个盘块可以表示的位数是：$1024 \times 8 = 8192 \text{ 位}$

2. 计算盘块号在位图中的相对位置：
   位图存储在 $32$ 和 $127$ 号块中，因此位图可以管理的盘块号范围是：$8192 \times 2 = 16384 \text{ 个盘块}$
   但题目中的盘块号 $409612$ 远大于 $16384$，说明位图管理的盘块号是从 $0$ 开始的全局盘块号。因此，我们需要计算 $409612$ 在位图中的相对位置：$\text{相对盘块号} = 409612$

3. 计算位图中的盘块号和块内字节序号：

   • 盘块号：
     由于每个盘块可以表示 $8192$ 个盘块，因此盘块号在位图中的盘块偏移为：$\text{盘块偏移} = \left\lfloor \frac{409612}{8192} \right\rfloor = 50$
     位图存储在 $32$ 和 $127$ 号块中，因此实际的盘块号为：$32 + 50 = 82$
   • 块内字节序号：
     计算块内的位偏移：$\text{位偏移} = 409612 \mod 8192 = 12$
     字节序号为：$\left\lfloor \frac{12}{8} \right\rfloor = 1$
     因此，块内字节序号是 $1$。

综上所述，位图中要修改的位所在的盘块号是 $82$，块内字节序号是 $1$。

正确答案：C

题目详解：
SCAN 调度算法（电梯算法）中，磁头按固定方向移动，依次处理经过的磁道请求，到达最内或最外侧后再反向移动。根据题目描述：

1. 初始状态：

   • 磁头位于 $58$ 号磁道，方向为从外侧（$0$）向内侧（$199$）移动。
   • 请求序列：$130, 42, 180, 15, 199$。

2. 移动过程：

   • 从 $58$ 向内侧移动，依次访问大于等于 $58$ 的请求：$130 \rightarrow 180 \rightarrow 199$。
   • 到达最内侧 $199$ 后反向移动，依次访问小于 $199$ 的请求：$180$（已访问）$\rightarrow 130$（已访问）$\rightarrow 42 \rightarrow 15$。
   • 到达最外侧 $0$ 后停止（题目未要求继续移动）。

3. 磁头移动路径：

   • $58 \rightarrow 130$：移动 $|130 - 58| = 72$ 磁道。
   • $130 \rightarrow 180$：移动 $|180 - 130| = 50$ 磁道。
   • $180 \rightarrow 199$：移动 $|199 - 180| = 19$ 磁道。
   • $199 \rightarrow 42$：移动 $|199 - 42| = 157$ 磁道。
   • $42 \rightarrow 15$：移动 $|42 - 15| = 27$ 磁道。

4. 总移动磁道数：

   • $72 + 50 + 19 + 157 + 27 = 325$。

正确答案：C

题目详解：
POP3（Post Office Protocol version 3）是一种用于接收电子邮件的应用层协议。在分析其传输层服务类型时，需要注意以下几点：

1. POP3 依赖于 TCP（Transmission Control Protocol）作为其传输层协议。TCP 是一种 $有连接$ 的协议，即在数据传输前需要建立连接（三次握手），传输结束后需要释放连接（四次挥手）。

2. TCP 提供 $可靠$ 的数据传输服务，通过确认机制、重传机制、流量控制和拥塞控制等确保数据正确、有序地传输。

3. 题目中其他选项的分析：

   • 选项 A 的 $无连接不可靠$ 是 UDP 的特点；
   • 选项 B 的 $无连接可靠$ 在标准传输层协议中不存在；
   • 选项 C 的 $有连接不可靠$ 是矛盾描述，有连接协议通常保证可靠性。

因此，POP3 使用的传输层服务类型是 $有连接可靠的数据传输服务$。

正确答案：D

题目详解：
NRZ是最简单的串行编码技术，用两个电压来代表两个二进制数，如高电平表示 1，低电平表示 0，题中编码 1 符合。NRZI 则是用电平的一次翻转来表示 1，与前一个 NRZI 电平相同的电平表示 0。曼彻斯特编码将一个码元分成两个相等的间隔，前一个间隔为低电平后一个间隔为高电平表示 1；0 的表示正好相反，题中编码 2 符合。

正确答案：A

题目详解：
首先，我们需要计算链路的利用率。链路的利用率 $U$ 可以表示为：$U = \frac{T_{\text{发送}}}{T_{\text{发送}} + T_{\text{传播}}} \times \text{窗口大小}$

其中：

• $T_{\text{发送}}$ 是发送一帧的时间。
• $T_{\text{传播}}$ 是单向传播延迟。
• 窗口大小 $W$ 是滑动窗口协议中允许连续发送的帧数。

1. 计算发送一帧的时间 $T_{\text{发送}}$：
   帧长为 $1000$ 字节，即 $8000$ 比特。链路速率为 $128 \text{kbps} = 128000 \text{bps}$。
   $T_{\text{发送}} = \frac{8000}{128000} = 0.0625 \text{s} = 62.5 \text{ms}$

2. 已知单向传播延迟 $T_{\text{传播}} = 250 \text{ms}$。

3. 为了使链路利用率不小于 $80\%$，即 $U \geq 0.8$，代入公式：
   $0.8 \leq \frac{62.5}{62.5 + 250} \times W$
   $0.8 \leq \frac{62.5}{312.5} \times W$
   $0.8 \leq 0.2 \times W$
   $W \geq \frac{0.8}{0.2} = 4$

4. 滑动窗口协议中，窗口大小 $W$ 和帧序号比特数 $n$ 的关系为 $W \leq 2^n - 1$。为了满足 $W \geq 4$，我们需要：
   $2^n - 1 \geq 4$
   $2^n \geq 5$
   最小的 $n$ 满足 $n \geq \log_2{5} \approx 2.32$，因此 $n \geq 3$。但考虑到帧序号从 $0$ 开始，实际需要 $n = 4$ 才能满足 $W \geq 4$。

因此，帧序号的比特数至少是 $4$。

正确答案：B

题目详解：
CSMA/CD（Carrier Sense Multiple Access with Collision Detection）是一种用于有线以太网的介质访问控制协议，其工作原理和特性如下：

1. 边发送边检测（A选项）：CSMA/CD 要求节点在发送数据帧的同时持续检测信道是否发生冲突。如果检测到冲突，立即停止发送并执行退避算法。这是 CSMA/CD 的核心机制，因此 A 选项描述正确。

2. 不适用于无线网络（B选项）：CSMA/CD 依赖有线信道的冲突检测（如电压变化），而无线网络中冲突检测难以实现（隐藏终端问题等）。无线网络通常采用 CSMA/CA（冲突避免），因此 B 选项错误，是本题答案。

3. 最小帧长限制（C选项）：为确保发送方在帧传输完毕前能检测到冲突，最小帧长 $L_{\text{min}}$ 需满足：
   $L_{\text{min}} = \text{数据传输速率} \times \text{往返传播延迟}$
   网络跨距（传播延迟）和数据速率越大，最小帧长要求越长。因此 C 选项正确。

4. 信道利用率（D选项）：当信号传播延迟趋近 0 时，冲突概率降低，信道利用率 $U$ 趋近 100%。公式为：$U \approx \frac{1}{1 + 2a} \quad (a = \frac{\text{传播延迟}}{\text{帧发送时间}})$
   当 $a \to 0$ 时，$U \to 1$。因此 D 选项正确。

正确答案：B

题目详解：
以太网交换机是一种网络设备，其核心功能是在数据链路层（OSI模型的第2层）转发帧。以下是对各选项的详细分析：

A. 以太网交换机本质上是一种多端口网桥：

• 交换机与网桥的核心功能相同，都是基于MAC地址进行帧的转发。交换机可以视为拥有多个端口的网桥，因此该选项正确。

B. 通过交换机互连的一组工作站构成一个冲突域：

• 交换机的每个端口是一个独立的冲突域（collision domain），因此互连的工作站不共享同一个冲突域，该选项错误。

C. 交换机每个端口所连网络构成一个独立的广播域：

• 广播域（broadcast domain）是由路由器或三层设备划分的，交换机的所有端口默认属于同一个广播域，除非使用VLAN技术。因此该选项错误。

D. 以太网交换机可实现采用不同网络层协议的网络互联：

• 交换机工作在数据链路层，无法处理网络层（第3层）协议，因此该选项错误。

正确答案：A

题目详解：
在路由器的路由表中，当匹配目的IP地址时，会遵循最长前缀匹配原则（Longest Prefix Match），即选择子网掩码最长的路由条目进行转发。

给定的目的IP地址是 $169.96.40.5$ ，我们需要将其与路由表中的条目逐一匹配：

1. 第一条目的网络是 $169.96.40.0/23$ ，子网掩码为 $23$ 位，网络地址范围是 $169.96.40.0$ 到 $169.96.41.255$ 。$169.96.40.5$ 落在该范围内。

2. 第二条目的网络是 $169.96.40.0/25$ ，子网掩码为 $25$ 位，网络地址范围是 $169.96.40.0$ 到 $169.96.40.127$ 。$169.96.40.5$ 也落在该范围内。

3. 第三条目的网络是 $169.96.40.0/27$ ，子网掩码为 $27$ 位，网络地址范围是 $169.96.40.0$ 到 $169.96.40.31$ 。$169.96.40.5$ 仍然落在该范围内。

4. 第四条是默认路由 $0.0.0.0/0$ ，只有在其他条目都不匹配时才会使用。

根据最长前缀匹配原则，$/27$ 的子网掩码最长（$27 > 25 > 23$），因此选择第三条路由条目，对应的接口是 $S3$ 。

正确答案：C

题目详解：
TCP 拥塞控制过程如下：

1. 慢启动阶段：

   • 初始拥塞窗口（cwnd）为 1 MSS（即 1KB）。
   • 初始阈值（ssthresh）为 32KB。
   • 每经过 1 个 RTT，cwnd 翻倍。

2. 拥塞避免阶段：

   • 当 cwnd 达到 ssthresh 时，进入拥塞避免阶段。
   • 每经过 1 个 RTT，cwnd 增加 1 MSS。

3. 接收窗口（rwnd）限制：

   • 乙的接收缓存为 16KB，因此 rwnd 最大为 16KB。
   • 由于乙的缓存未被取走，rwnd 会逐渐减小。

具体过程分析：

• 第 1 个 RTT：

  • cwnd = 1 KB（发送 1 个段）。
  • 乙接收 1 KB，缓存剩余 15 KB，rwnd = 15 KB。
  • 甲的发送窗口取 min(cwnd, rwnd) = min(1 KB, 15 KB) = 1 KB。

• 第 2 个 RTT：

  • cwnd = 2 KB（慢启动阶段，翻倍）。
  • 乙接收 2 KB，缓存剩余 13 KB，rwnd = 13 KB。
  • 甲的发送窗口取 min(2 KB, 13 KB) = 2 KB。

• 第 3 个 RTT：

  • cwnd = 4 KB（慢启动阶段，翻倍）。
  • 乙接收 4 KB，缓存剩余 9 KB，rwnd = 9 KB。
  • 甲的发送窗口取 min(4 KB, 9 KB) = 4 KB。

• 第 4 个 RTT：

  • cwnd = 8 KB（慢启动阶段，翻倍）。
  • 乙接收 8 KB，缓存剩余 1 KB，rwnd = 1 KB。
  • 甲的发送窗口取 min(8 KB, 1 KB) = 1 KB。

因此，经过 4 个 RTT 后，甲的发送窗口为 1 KB。

正确答案：A

题目详解：
根据题目给出的请求报文，我们逐项分析：

1. 请求行 GET/index.html HTTP/1.1 表明浏览器请求浏览 index.html 文件，因此选项 A 正确。

2. 首部行 Host: www.test.edu.cn 表明请求的主机是 www.test.edu.cn，因此 index.html 存放在该主机上，选项 B 正确。

3. 首部行 Connection: Close 表明浏览器要求服务器在发送完响应后就关闭连接，因此使用的是非持续连接，而不是持续连接，所以选项 C 错误。

4. 首部行 Cookie: 123456 表明浏览器曾经访问过 www.test.edu.cn，并且服务器给浏览器发送了 Cookie（值为 123456），因此选项 D 正确。

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

正确答案：C

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

算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。

因为$|data| \le n$，故辅助数组 $q$的大小为 $n+1$，各元素的初值均为 0。依次扫描链表中的各 结点，同时检查 $q[|data|]$ 的值，如果为 $0$，则保留该结点，并令 $q[data]=1$；否则，将该结点从 链表中删除。

2）使用 C 语言描述的单链表结点的数据结构定义：

3）算法实现

void RemoveElements(ListNode *head, int n) {
  // 数组充当哈希表
  int hash[n+1];
  for (int i = 0; i <= n; i++) {
    // 0 表示没有命中
    hash[i] = 0;
  }
  // 当遍历的结点
  ListNode *q = head->link;
  // 先前的结点
  ListNode *p = head;
  while (q != NULL) {
    // 绝对值已经出现过
    if (hash[abs(q->data)] == 1) {
      // 删除该节点
      p->next = q->next;
      q = p->next;
    } else {
      // 设置哈希表
      hash[abs(q->data)] = 1;
      q = q->next;
      p = p->next;
    }
  }
}

【评分说明】若考生设计的算法满足题目的功能要求且正确，则酌情给分。

4）参考答案所给算法的时间复杂度为 O(m)，空间复杂度为 O(n)。

【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致，可给分。

题目详解：

1. 图 $A$ 的邻接矩阵如下：

   $A = \begin{bmatrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \end{bmatrix}$

2. $A^2)$ 如下：

   $A^2 = \begin{bmatrix} 3 & 1 & 0 & 3 & 1 \\ 1 & 3 & 2 & 1 & 2 \\ 0 & 2 & 2 & 0 & 2 \\ 3 & 1 & 0 & 3 & 1 \\ 1 & 2 & 2 & 1 & 3 \end{bmatrix}$

   第 0 行第 3 列的元素值 3 表示：从顶点 0 到顶点 3 之间长度为 2 的路径共有 3 条。

3. $B^m$（$2 \le m \le n$）中位于第 $i$ 行第 $j$ 列（$0 \le i, j \le n-1$）的非零元素的含义是：图中从顶点 $i$ 到顶点 $j$ 长度为 $m$ 的路径条数。

题目详解：
1. 程序员可见寄存器及暂存器作用

• 可见寄存器：通用寄存器（R0~R3）和程序计数器（PC）。
• 暂存器 T 的必要性：
  在单总线结构中，若无暂存器 T，ALU 的 A、B 端口可能同时接收相同数据，导致数据通路冲突。暂存器 T 用于临时存储端口 A 的数据，确保正确操作。

评分说明：

• 答出 R0~R3 或 PC 即得分。
• 暂存器原因需明确“暂存端口 A 数据”，其他解释酌情给分。

ALU 与移位器的控制信号位数

• ALUop 位数：ALU 支持 7 种操作，至少需要 3 位（$\lceil \log_2 7 \rceil = 3$）。
• SRop 位数：移位器有 3 种操作，至少需要 2 位（$\lceil \log_2 3 \rceil = 2$）。

3. 信号 SRout 的作用

• 功能：控制三态门，管理移位器与总线之间的数据通路连接/断开。

评分说明：

• 回答“三态门”或“通断控制”即得分。

4. 需连接控制部件的端口

• 端口编号：①、②、③、⑤、⑧。

评分说明：

• 若包含④、⑥、⑦、⑨中任意一个则不得分；不全则酌情扣分。

5. 关键数据通路连线

• 连线 1：⑥ → ⑨
• 连线 2：⑦ → ④

评分说明：

• 其他连线回答酌情给分。

6. PC+2 操作的硬件支持

• 原因：
  指令长度为 16 位（2 字节），按字节编址时，顺序执行的下条指令地址为 $\text{PC} + 2$。MUX 输入端固定值 2 用于快速实现此操作。

题目详解：
1）指令操作码有 7 位，因此最多可定义 $2^{7}=128$ 条指令。

2）各条指令的机器代码分别如下：

①“incR1”的机器码为 0000001001000000，即 0240H。
②“shlR2,R1”的机器码为 0000010010001000，即 0488H。
③“subR3,(R1),R2”的机器码为 0000011011101010，即 06EAH。

3）各标号处的控制信号或控制信号取值如下：
①0；②mov；③mova；④left；⑤read；⑥sub；⑦mov；⑧Srout

【评分说明】答对两个给分。

4）指令 subR1,R3,(R2) 的执行阶段至少包含 4 个时钟周期；指令 incR1 的执行阶段至少包含 2 个时钟周期。

题目详解：

semaphore A_full = x;        // A 信箱中已有的邮件个数
semaphore A_empty = M - x;   // A 信箱还可以放多少个邮件
semaphore B_full = y;        // B 信箱中已有的邮件个数
semaphore B_empty = N - y;   // B 信箱中还能放多少个邮件
semaphore A_mutex = 1;       // 互斥访问 A 信箱
semaphore B_mutex = 1;       // 互斥访问 B 信箱

A() {
  while (1) {
    P(A_full);               // 检查A信箱是否有邮件可取
    P(A_mutex);              // 获取A信箱的互斥访问权
    从A信箱中取出一个邮件;
    V(A_mutex);              // 释放A信箱的互斥访问权
    V(A_empty);              // 增加A信箱的空闲容量
    回答问题并提出新问题;
    P(B_empty);              // 检查B信箱是否有空间可放
    P(B_mutex);              // 获取B信箱的互斥访问权
    将信件放入B邮箱;
    V(B_mutex);              // 释放B信箱的互斥访问权
    V(B_full);               // 增加B信箱的邮件计数
  }
}

B() {
  while (1) {
    P(B_full);               // 检查B信箱是否有邮件可取
    P(B_mutex);              // 获取B信箱的互斥访问权
    从B信箱中取出一个邮件;
    V(B_mutex);              // 释放B信箱的互斥访问权
    V(B_empty);              // 增加B信箱的空闲容量
    回答问题并提出新问题;
    P(A_empty);              // 检查A信箱是否有空间可放
    P(A_mutex);              // 获取A信箱的互斥访问权
    将信件放入A邮箱;
    V(A_mutex);              // 释放A信箱的互斥访问权
    V(A_full);               // 增加A信箱的邮件计数
  }
}

【评分说明】
1）每对信号量的定义及初值正确，给分。
2）每个互斥信号量的 P、V 操作使用正确，各给分。
3）每个同步信号量的 P、V 操作使用正确，各给分。
4）其他答案酌情给分。

题目详解：
1）在分页存储管理方式中，将用户程序的地址空间分为若干固定大小的区域，称为"页"或"页面"。相应地，将内存空间分为若干物理块或页框（frame），页和页框大小相同。因此，页和页框大小均为 $2^{12}$B = 4KB。进程的虚拟地址空间大小为 $2^{32}/2^{12}=2^{20}$ 页。

2）页目录所占页数为 $(2^{10} \times 4)/2^{12} = 1$ 页，页表所占页数为 $(2^{20} \times 4)/2^{12} = 1024$ 页，因此总共需要 $1 + 1024 = 1025$ 页。

3）需要访问一个二级页表。因为虚拟地址 01000000H 和 01112048H 的最高 10 位（页目录号）的值都是 4（01000000B 和 01112048B 的前10位均为 0000000100），所以访问的是同一个二级页表。

【评分说明】用其他方法计算，思路和结果正确同样给分。

题目详解：
1）DHCP 服务器可为主机2～主机N动态分配IP地址的最大范围是：111.123.15.5～111.123.15.254；主机2发送的封装DHCP Discover报文的IP分组的源IP地址和目的IP地址分别是0.0.0.0和255.255.255.255。

2）主机2发出的第一个以太网帧的目的MAC地址是ff-ff-ff-ff-ff-ff（广播地址），封装主机2发往Internet的IP分组的以太网帧的目的MAC地址是00-a1-a1-a1-a1-a1（默认网关的MAC地址）。

3）主机1能访问WWW服务器，但不能访问Internet。由于主机1的子网掩码配置正确而默认网关IP地址被错误地配置为111.123.15.2（正确IP地址应为111.123.15.1），因此主机1可以通过ARP解析同一子网内的WWW服务器的MAC地址并直接通信，但当访问Internet时，主机1会将数据包发送到错误的网关111.123.15.2，导致无法正确路由到外部网络。

【评分说明】

• 第1）小题：IP地址范围、DHCP Discover的源/目的IP地址正确各给分。
• 第2）小题：两个MAC地址回答正确各给分。
• 第3）小题：现象解释正确给分，指出子网掩码正确但默认网关错误是关键点。