2013年408真题

题目详解：
要合并两个长度分别为 $m$ 和 $n$ 的升序链表为一个长度为 $m + n$ 的降序链表，最坏情况下的时间复杂度取决于如何遍历和比较两个链表的节点。

1. 合并过程分析：

   • 每次从两个链表的头部选择较大的节点，将其插入到新链表的头部，形成降序链表。
   • 最坏情况下，需要比较所有 $m + n$ 个节点，但每次比较只需 $O(1)$ 时间。
   • 关键在于如何高效找到每次要插入的节点。如果使用双指针法，每次移动一个链表的指针，最多需要遍历 $m + n$ 次。

2. 时间复杂度推导：

   • 双指针法的最坏情况是两个链表交替比较，最多需要 $m + n$ 次操作。
   • 因此，时间复杂度为 $O(m + n)$。
   • 由于 $O(m + n)$ 等价于 $O(\max(m, n))$（因为 $\max(m, n)$ 主导了增长趋势），所以最坏情况下的时间复杂度为 $O(\max(m, n))$。

3. 选项分析：

   • A. $O(n)$：忽略了 $m$ 的影响。
   • B. $O(mn)$：远高于实际复杂度。
   • C. $O(\min(m, n))$：低估了复杂度。
   • D. $O(\max(m, n))$：正确反映了最坏情况下的时间复杂度。

正确答案：D

题目详解：
本题考察 入栈出栈序列。显然，33 之后的 4,5,⋯ ,n4,5,\cdots,n 都是 p3p_3 可取的数（一直进栈直到该数入栈后马上出栈）。接下来分析 1 和 2：p1p_1 只能是 33 之前入栈的数（可能是 1 或 2），当 p1=1p_1 = 1 时，p3p_3 可取 22；当 p1=2p_1 = 2 时，p3p_3 可取 11，故 p3p_3 可能取除 33 之外的所有数，个数为 n−1n-1。

正确答案是 $\boxed{C}$ 。

题目详解：
首先，我们需要构建一个平衡二叉树（AVL树），并计算每个分支结点的平衡因子。平衡因子定义为左子树的高度减去右子树的高度。平衡因子为 $0$ 表示该结点的左右子树高度相等。

关键字依次插入 $1, 2, 3, 4, 5, 6, 7$ 到初始为空的平衡二叉树中：

1. 插入 $1$：树为 $1$，平衡因子为 $0$（叶子结点不计为分支结点）。
2. 插入 $2$：树为 $1 \rightarrow 2$，$1$ 的平衡因子为 $-1$。
3. 插入 $3$：发生右右不平衡，单旋转调整后树为 $2$ 为根，$1$ 和 $3$ 为左右孩子。$2$ 的平衡因子为 $0$。
4. 插入 $4$：树为 $2 \rightarrow 1, 3 \rightarrow 4$，$3$ 的平衡因子为 $-1$，$2$ 的平衡因子为 $-1$。
5. 插入 $5$：发生右右不平衡，单旋转调整后树为 $2 \rightarrow 1, 4 \rightarrow 3, 5$。$4$ 的平衡因子为 $0$，$2$ 的平衡因子为 $-1$。
6. 插入 $6$：发生右右不平衡，单旋转调整后树为 $4$ 为根，$2$ 和 $5$ 为左右孩子，$2 \rightarrow 1, 3$，$5 \rightarrow 6$。$4$ 的平衡因子为 $0$，$2$ 的平衡因子为 $0$，$5$ 的平衡因子为 $-1$。
7. 插入 $7$：发生右右不平衡，单旋转调整后树为 $4$ 为根，$2$ 和 $6$ 为左右孩子，$2 \rightarrow 1, 3$，$6 \rightarrow 5, 7$。$4$ 的平衡因子为 $0$，$2$ 的平衡因子为 $0$，$6$ 的平衡因子为 $0$。

最终平衡二叉树的结构如下：

4
/ \
 2 6
/ \ / \
 1 3 5 7

分支结点为 $2, 4, 6$，它们的平衡因子均为 $0$。因此，平衡因子为 $0$ 的分支结点个数是 $3$。

正确答案：D

题目详解：
要计算三叉树 $T$ 的最小带权外部路径长度，可以使用类似哈夫曼编码的贪心算法。对于 $k$-叉树，每次选择 $k$ 个最小的权值合并，直到只剩一个节点。具体步骤如下：

1. 给定的叶结点权值为 $2, 3, 4, 5, 6, 7$。

2. 因为是三叉树（$k = 3$），每次合并 $3$ 个最小的权值。如果节点数不足 $3$ 的倍数，可以添加虚拟节点（权值为 $0$），但这里可以通过调整合并策略来处理。

3. 第一次合并：选择最小的 $3$ 个权值 $2, 3, 4$，合并为一个新节点，其权值为 $2 + 3 + 4 = 9$。新的权值列表为 $5, 6, 7, 9$。

4. 第二次合并：选择最小的 $3$ 个权值 $5, 6, 7$，合并为一个新节点，其权值为 $5 + 6 + 7 = 18$。新的权值列表为 $9, 18$。

5. 此时只剩 $2$ 个节点，不足 $3$ 个，直接合并 $9$ 和 $18$，得到根节点，其权值为 $9 + 18 = 27$。

6. 计算带权路径长度：每个叶结点的贡献为其权值乘以其到根的路径长度（边数）。具体计算如下：

   • $2, 3, 4$ 的路径长度为 $2$（经过两次合并），贡献为 $(2 + 3 + 4) \times 2 = 18$。
   • $5, 6, 7$ 的路径长度为 $1$（经过一次合并），贡献为 $(5 + 6 + 7) \times 1 = 18$。
   • 总带权路径长度为 $18 + 18 = 46$。

因此，最小带权外部路径长度为 $46$。

正确答案：B

题目详解：
在后序线索二叉树中，结点的右线索通常指向其后序后继结点。题目中给定 $X$ 是叶结点，且 $X$ 存在左兄弟结点 $Y$。我们需要分析 $X$ 的后序后继是什么。

后序遍历的顺序是：左子树 → 右子树 → 根结点。由于 $X$ 是叶结点，它的后序后继是其父结点。具体分析如下：

1. 若 $X$ 是其父结点的右孩子，则 $X$ 的后序后继是其父结点。
2. 若 $X$ 是其父结点的左孩子，且其父结点没有右孩子，则 $X$ 的后序后继仍然是其父结点。
3. 若 $X$ 是其父结点的左孩子，且其父结点有右孩子，则 $X$ 的后序后继是以其父结点的右孩子为根的子树的最左下结点。但题目中 $X$ 是叶结点，且存在左兄弟 $Y$，说明 $X$ 是其父结点的右孩子（因为 $Y$ 是左兄弟），因此 $X$ 的后序后继是其父结点。

综上所述，$X$ 的右线索指向的是 $X$ 的父结点。

正确答案：A

题目详解：
在二叉排序树（BST）中，删除和插入结点的操作会影响树的结构。我们需要分析不同情况下 $T1$ 和 $T3$ 的关系：

1. 若 $v$ 是 $T1$ 的叶结点：

   • 删除 $v$ 时，直接移除该结点，不会影响其他结点的结构，因此 $T2$ 是 $T1$ 去掉 $v$ 后的树。
   • 将 $v$ 重新插入 $T2$ 时，由于 $v$ 是叶结点，其插入路径与删除前完全相同，因此 $T3$ 的结构与 $T1$ 完全一致。
   • 结论：$T1$ 与 $T3$ 相同，即 II 正确，I 错误。

2. 若 $v$ 不是 $T1$ 的叶结点：

   • 删除 $v$ 时，需要找到其前驱或后继结点替代 $v$ 的位置，这会导致树的结构发生变化，因此 $T2$ 与 $T1$ 不同。
   • 将 $v$ 重新插入 $T2$ 时，由于 $v$ 不是叶结点，其插入路径可能与删除前不同，因此 $T3$ 的结构与 $T1$ 不同。
   • 结论：$T1$ 与 $T3$ 不同，即 III 正确，IV 错误（因为 $T1$ 与 $T2$ 不同）。

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

正确答案：C

题目详解：
邻接矩阵A 为非对称矩阵，说明图是有向图，度为入度加出度之和。各顶点的度是矩阵中此结点对应的行（对应出度）和列（对应入度）的非零元素之和。

正确答案：C

题目详解：
此题为送分题。只要掌握DFS和BFS的遍历过程，便能轻易解决。逐个代入，手工模拟，选项 D 是深度优先遍历，而不是广度优先遍历。

正确答案：D

题目详解：
找出 AOE 网的全部关键路径为 (b,d,c,g)、(b,d,e,h) 和 (b,f,h)。根据定义，只有关键路径上的活动时间同时减少时，才能缩短工期，即正确选项中的两条路径必须涵盖在所有关键路径之中。利用关键路径算法可求出图中的关键路径共有三条：(b,d,cg)、(b,d,e,h) 和 (b,f,h)。由此可知，选项 A 和 B 中并不能包含 (b,f,h) 这条路径，选项 C 中，并不能包含 (b,d,c,g) 和 (b,d,e,h) 这两条路径，只有 C 包含了所有的关键路径，因此只有加快 f 和 d 的进度才能缩短工期。

正确答案：C

题目详解：
一棵 $m$ 阶B树的最小关键字数量可以通过以下规则计算：

1. 根结点至少包含 $1$ 个关键字。
2. 非根结点至少包含 $\lceil \frac{m}{2} \rceil - 1$ 个关键字。

对于高度为 $2$ 的 $5$ 阶B树：

• 根结点至少有 $1$ 个关键字。
• 根结点的每个子结点（第二层结点）至少包含 $\lceil \frac{5}{2} \rceil - 1 = 2$ 个关键字。
• 因为 $5$ 阶B树每个结点最多有 $5$ 个子结点，所以根结点可以有 $2$ 到 $5$ 个子结点。为了达到最小关键字数量，根结点取 $2$ 个子结点。

因此，最小关键字数量为：

$$1 \text{（根结点）} + 2 \times 2 \text{（两个子结点）} = 5$$

正确答案：A

题目详解：
基数排序的第 2 趟分配收集是针对关键字的十位数进行操作。首先，我们需要将关键字序列补齐为三位数： $110, 119, 007, 911, 114, 120, 122$。

第 1 趟分配收集（按个位数排序）后的序列为：
$110, 120, 911, 122, 114, 007, 119$

第 2 趟分配收集（按十位数排序）的步骤如下：

1. 分配：

   • 十位数为 $0$ 的关键字： $007$
   • 十位数为 $1$ 的关键字： $110, 911, 114, 119$
   • 十位数为 $2$ 的关键字： $120, 122$

2. 收集：
   将分配后的桶按顺序合并，得到第 2 趟收集后的序列：
   $007, 110, 911, 114, 119, 120, 122$

因此，第 2 趟分配收集后的关键字序列为 $007, 110, 911, 114, 119, 120, 122$，对应选项 C。

正确答案：C

题目详解：
首先，我们需要计算该计算机的平均CPI（每条指令的平均时钟周期数）。平均CPI可以通过各类指令的CPI与其所占比例的加权平均来计算：

$\text{平均CPI} = \sum (\text{CPI}_i \times \text{比例}_i)$

根据题目给出的数据：

$\text{平均CPI} = (2 \times 0.5) + (3 \times 0.2) + (4 \times 0.1) + (5 \times 0.2)$

计算各项：

$= (1) + (0.6) + (0.4) + (1)$

$= 3$

接下来，计算MIPS（每秒百万条指令数）。MIPS的计算公式为：

$\text{MIPS} = \frac{\text{主频（Hz）}}{\text{平均CPI} \times 10^6}$

题目中主频为 1.2GHz，即 $1.2 \times 10^9$ Hz。代入公式：

$\text{MIPS} = \frac{1.2 \times 10^9}{3 \times 10^6}$

$= \frac{1.2 \times 10^3}{3}$

$= 0.4 \times 10^3$

$= 400$

因此，该机的MIPS数是 400。

正确答案：C

题目详解：
IEEE754 单精度浮点数格式由 $32$ 位组成，分为三个部分：

1. 符号位 $S$（1位）：最高位，表示正负。
2. 阶码 $E$（8位）：接下来的8位，表示指数部分，采用移码表示（偏移量为 $127$）。
3. 尾数 $M$（23位）：剩下的23位，表示小数部分，隐含最高位为1。

给定的十六进制数为 $C6400000H$，转换为二进制为：
$1100 \ 0110 \ 0100 \ 0000 \ 0000 \ 0000 \ 0000 \ 0000$

分解各部分：

1. 符号位 $S = 1$，表示负数（但题目问的是绝对值，暂不考虑符号）。
2. 阶码 $E = 10001100$（二进制），转换为十进制为 $140$。
   • 实际指数 $e = E - 127 = 140 - 127 = 13$。
3. 尾数 $M = 100 \ 0000 \ 0000 \ 0000 \ 0000 \ 0000$（二进制），隐含最高位为1，因此实际尾数为 $1.100 \ 0000 \ 0000 \ 0000 \ 0000 \ 0000$（二进制）。

计算数值：
$(-1)^S \times 1.M \times 2^e = 1.1 \times 2^{13}$（二进制）。
$1.1$（二进制）等于 $1.5$（十进制），因此数值为 $1.5 \times 2^{13}$。

正确答案：A

题目详解：
x*2，将 x 算术左移一位为 1 1101000；y/2，将 y 算术右移一位为 1 1011000, 均无溢出或丢失精度。补码相加为 1 1101000 + 1 1011000 = 1 1000000, 亦无溢出。

正确答案：A

题目详解：
海明码是一种用于检错和纠错的编码方法。为了能够检测和纠正 1 位错误，校验位的数量 $k$ 必须满足海明不等式：

$2^k \geq m + k + 1$

其中：

• $m$ 是数据位的长度，本题中 $m = 8$。
• $k$ 是校验位的最小数量。

将 $m = 8$ 代入不等式：

$2^k \geq 8 + k + 1$

即：

$2^k \geq k + 9$

我们需要找到最小的 $k$ 满足上述不等式。

尝试 $k = 3$：
$2^3 = 8$
$8 \geq 3 + 9$ → $8 \geq 12$ 不成立。

尝试 $k = 4$：
$2^4 = 16$
$16 \geq 4 + 9$ → $16 \geq 13$ 成立。

因此，最小的校验位数量 $k$ 是 4。

正确答案：C

题目详解：
按字节编址，页面大小为 4KB，页内地址共 12 位。地址空间大小为 4GB，虚拟地址共 32 位，前 20 位为页号。虚拟地址为 03FF F180H，故页号为 03 FFFH，页内地址为 180H。查找页标记 03FFFH 所对应的页表项，页框号为 0153H，页框号与页内地址拼接即为物理地址 0153180H。

正确答案：A

题目详解：
在变址寻址方式下，有效地址（EA）的计算公式为：

$EA = (R) + D$

其中：

• $(R)$ 表示变址寄存器 $R$ 中的内容；
• $D$ 表示指令中给出的形式地址。

根据题目给出的数据：

• 变址寄存器 $R$ 的内容为 $1000H$；
• 形式地址 $D$ 为 $2000H$。

因此，有效地址 $EA$ 的计算如下：

$EA = (R) + D = 1000H + 2000H = 3000H$

接下来，根据有效地址 $3000H$ 访问内存，地址 $3000H$ 中的内容为 $4000H$，这就是变址寻址方式下访问到的操作数。

正确答案：D

题目详解：
首先，我们需要明确几个关键参数和概念：

1. CPU主频： $1.03 \text{GHz}$，即 $1.03 \times 10^9 \text{Hz}$，表示每秒钟有 $1.03 \times 10^9$ 个时钟周期。

2. 流水线级数：4 级流水线，每个流水段需要 1 个时钟周期。

3. 指令数量：100 条指令。

4. 流水线执行时间：在没有流水线阻塞的情况下，流水线的执行时间可以通过以下公式计算：
   $\text{总时间} = (\text{流水线级数} + \text{指令数量} - 1) \times \text{时钟周期}$
   其中，时钟周期 $T = \frac{1}{\text{主频}} = \frac{1}{1.03 \times 10^9} \text{秒}$。

   代入数值：
   $\text{总时间} = (4 + 100 - 1) \times \frac{1}{1.03 \times 10^9} = 103 \times \frac{1}{1.03 \times 10^9} = \frac{103}{1.03 \times 10^9} = \frac{100}{10^9} = 10^{-7} \text{秒}$

5. 吞吐率：吞吐率是指单位时间内执行的指令数量，计算公式为：
   $\text{吞吐率} = \frac{\text{指令数量}}{\text{总时间}} = \frac{100}{10^{-7}} = 100 \times 10^7 = 1.0 \times 10^9 \text{条指令/秒}$

因此，流水线的吞吐率为 $1.0 \times 10^9$ 条指令/秒。

正确答案：C

题目详解：
设备和设备控制器（I/O 接口）之间互连的接口标准需要满足通用性和广泛兼容性的特点。题目中的选项分析如下：

• A. PCI：PCI（Peripheral Component Interconnect）是一种用于连接主板和外部设备的总线标准，主要用于扩展卡（如显卡、网卡等），但它不是专门用于设备和设备控制器之间的接口标准。

• B. USB：USB（Universal Serial Bus）是一种通用串行总线标准，广泛用于设备和设备控制器（如键盘、鼠标、打印机等外设与计算机的连接），具有即插即用、热插拔等特点，是典型的设备和设备控制器之间的接口标准。

• C. AGP：AGP（Accelerated Graphics Port）是一种专门为显卡设计的接口标准，用于连接显卡和主板，不适用于通用设备和设备控制器的连接。

• D. PCI-Express：PCI-Express（PCIe）是一种高速串行计算机扩展总线标准，主要用于高性能设备（如显卡、固态硬盘等），但它也不是专门用于设备和设备控制器之间的接口标准。

因此，最符合题目描述的选项是 USB，它是设备和设备控制器之间互连的通用接口标准。

正确答案：B

题目详解：
RAID（Redundant Array of Independent Disks）通过多种技术提高数据可靠性和性能。题目中的选项分析如下：

1. 磁盘镜像（I）：通过将数据完全复制到多个磁盘上实现冗余。如果一块磁盘损坏，可以从镜像磁盘恢复数据，显著提高可靠性。

2. 条带化（II）：将数据分割成块并分散存储在多个磁盘上，主要目的是提高性能（如读写速度），但本身不提供冗余或可靠性保障。

3. 奇偶校验（III）：通过计算数据的奇偶校验信息并存储到专用磁盘或分散存储，可以在磁盘故障时恢复数据，从而提高可靠性。

4. 增加Cache 机制（IV）：主要用于提升读写性能，例如通过缓存频繁访问的数据减少磁盘I/O，但对数据可靠性无直接影响。

综上，**磁盘镜像（I）和奇偶校验（III）**是直接提高RAID可靠性的措施，而条带化（II）和Cache机制（IV）与可靠性无关。因此正确答案为 B. 仅I、III。

正确答案：B

题目详解：
计算读取一个 4KB 扇区的平均时间需要综合考虑以下几个部分：

1. 平均寻道时间（$T_{seek}$）：题目中给出为 $6ms$。

2. 平均旋转延迟（$T_{rotation}$）：磁盘转速为 $10000rpm$，即每分钟 10000 转。旋转延迟是磁盘旋转半圈所需的时间：
   $T_{rotation} = \frac{1}{2} \times \left( \frac{60 \times 1000}{10000} \right) ms = 3ms$

3. 传输时间（$T_{transfer}$）：磁盘传输速率为 $20MB/s$，读取 $4KB$ 数据所需时间为：
   $T_{transfer} = \frac{4KB}{20MB/s} = \frac{4 \times 1024}{20 \times 1024 \times 1024} s \approx 0.000195s = 0.2ms$

4. 控制器延迟（$T_{controller}$）：题目中给出为 $0.2ms$。

将以上各部分时间相加，得到总平均时间：
$T_{total} = T_{seek} + T_{rotation} + T_{transfer} + T_{controller} = 6ms + 3ms + 0.2ms + 0.2ms = 9.4ms$

因此，正确答案是 B。

题目详解：
中断I/O 方式和DMA 方式是两种不同的I/O 数据传输方式，它们的比较如下：

A. 中断I/O 方式通过中断请求CPU 的处理时间，由CPU 负责数据传输；而DMA 方式通过请求总线使用权，由DMA 控制器直接管理数据传输，无需CPU 介入。因此，该选项描述正确。

B. 中断响应通常发生在当前指令执行完成后，CPU 才会处理中断请求；而DMA 响应需要等待当前总线事务（如内存读写）完成，才能获得总线控制权。因此，该选项描述正确。

C. 中断I/O 方式的数据传输由CPU 执行中断服务程序（软件）完成；而DMA 方式的数据传输由DMA 控制器（硬件）直接管理。因此，该选项描述正确。

D. 中断I/O 方式可以适用于所有外部设备，但DMA 方式并不仅限于快速外部设备。DMA 的优势在于减少CPU 开销，适用于需要高速或大批量数据传输的设备，但也可以用于其他设备。因此，该选项描述错误。

正确答案：D

题目详解：
此文件所在目录下可能还存在其他文件，因此删除文件时不能（也不需要）删除文件所在的目录，而与此文件关联的目录项和文件控制块需要随着文件一同删除，同时释放文件关联的内存缓冲区。

正确答案：A

题目详解：
为了支持CD-ROM中视频文件的快速随机播放，文件数据块的组织方式需要满足以下关键要求：

1. 快速定位：随机访问时需要能够快速定位到任意数据块的位置。
2. 最小化寻道时间：CD-ROM的读取头移动（寻道时间）是性能瓶颈，因此需要尽量减少寻道操作。

连续结构（A选项）的特点是将文件数据块顺序存储在连续的物理块中。这种方式的优势在于：

• 可以通过起始地址 $L$ 和块大小 $S$ 直接计算出任意数据块的物理位置，公式为：$L + n \times S$，其中 $n$ 是块编号。
• 无需额外的寻道操作，读取头可以连续读取数据，非常适合顺序访问和随机访问。

链式结构（B选项）通过指针链接数据块，随机访问时需要从头遍历链表，效率低下。直接索引结构（C选项）和多级索引结构（D选项）虽然支持随机访问，但需要多次查找索引表或间接块，增加了额外的I/O开销，不适合CD-ROM的物理特性。

因此，连续结构是最佳选择，能够最大化CD-ROM的播放性能。

正确答案：A

题目详解：
在磁盘I/O 请求的处理流程中，各模块的功能分工如下：

1. 用户程序：负责发起I/O 请求，但不涉及底层磁盘物理位置的计算。
2. 系统调用处理程序：负责将用户程序的请求转换为内核可识别的形式，并传递给下层模块。
3. 设备驱动程序：是核心模块，负责将逻辑请求转换为物理操作。具体包括：
   • 计算数据所在磁盘的物理位置，即 $柱面号$ (Cylinder)、$磁头号$ (Head) 和 $扇区号$ (Sector)。
   • 向磁盘控制器发送具体指令。
4. 中断处理程序：负责在I/O 操作完成后通知CPU，处理中断信号。

因此，计算磁盘物理位置（$C$、$H$、$S$）的任务是由 设备驱动程序 完成的。

正确答案：C

题目详解：
在文件系统中，单个文件的最大长度主要取决于以下因素：

1. 文件块大小 ($\text{Block Size}$)：文件被分割成固定大小的块，块大小直接影响文件能寻址的最大空间。例如，若块大小为 $4 \text{KB}$，则更大的块可以支持更大的文件。

2. 地址项的个数：索引结点中直接地址项和间接地址项的数量决定了文件能引用的块数。直接地址项直接指向数据块，而间接地址项通过多级索引指向数据块。例如，若有 $10$ 个直接地址项和 $1$ 个一级间接地址项，则文件能引用的总块数为 $10 + \frac{\text{Block Size}}{\text{Address Size}}$。

3. 间接地址索引的级数：多级索引（如一级、二级、三级间接地址）可以显著增加文件的最大长度。例如，二级间接地址可以寻址 $\left( \frac{\text{Block Size}}{\text{Address Size}} \right)^2$ 个块。

4. 索引结点的总数：这是文件系统中所有文件的索引结点数量，与单个文件的长度无关，因为它只限制文件系统中文件的总数，而不影响单个文件的大小。

因此，与单个文件长度无关的因素是索引结点的总数。

正确答案：A

题目详解：
在单缓冲中，数据块 1 从外设到用户工作区的总时间为 105，在这段时间中，数据块 2 没有进行操作。在数据块 1 进行分析处理 时，数据块 2 从外设到用户工作区的总时间为 105，这段时间是并行的。再加上处理数据块 2 的时间 90，总时间为 300。

正确答案：C

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

1. 异常/中断：当 CPU 执行指令时发生异常（如除以零），会触发中断机制，切换到内核态处理异常。例如：

   • 整数除以零（I）会导致算术异常，属于上述情况。

2. 系统调用（III）：用户程序主动通过 $\text{int 0x80}$ 或 $\text{syscall}$ 等指令发起系统调用，陷入内核态执行特权操作。

3. 外部中断：如硬件中断，但与本题无关。

对于选项：

• $\text{sin()}$ 函数调用（II）是普通的数学库函数，在用户态即可完成，无需切换内核态。

因此，仅 I（异常）和 III（系统调用）会导致态切换。

正确答案：B

题目详解：
计算机开机后，操作系统的加载过程如下：

1. 开机时，BIOS（Basic Input/Output System）存储在 $ROM$ 中，首先被执行。BIOS 进行硬件自检（POST）和初始化。

2. BIOS 根据启动顺序（如硬盘、U盘等）找到引导设备，并加载引导扇区（Boot Sector）中的引导程序（如 $MBR$ 或 $GPT$）。

3. 引导程序进一步加载操作系统的核心部分（如内核文件）。此时，操作系统的代码和数据会被加载到 $RAM$（随机存取存储器）中。

4. 操作系统被加载到 $RAM$ 后，CPU 开始执行 $RAM$ 中的指令，完成操作系统的启动过程。

$RAM$ 是易失性存储器，读写速度快，适合作为操作系统和应用程序运行时的临时存储介质。而 $BIOS$、$ROM$ 和 $EPROM$ 是非易失性存储器，通常用于存储固件或引导程序，而不是操作系统的运行环境。

正确答案：D

题目详解：
当用户进程访问内存时产生缺页，操作系统会执行以下可能操作：

1. 置换页（II）：如果物理内存已满，操作系统需要通过页面置换算法（如 $LRU$ 、 $FIFO$ 等）选择一个页面换出到磁盘，为新的页面腾出空间。

2. 分配内存（III）：操作系统需要为缺页的进程分配一个空闲的物理页框，并将所需的页面从磁盘加载到该页框中。

选项 $I$ （处理越界错）与缺页无关，越界错误通常是由于访问了进程地址空间之外的非法内存地址，而缺页是由于访问的页面不在物理内存中。因此，$I$ 不是缺页处理的操作。

综上所述，正确的操作是 $II$ 和 $III$ ，对应选项 $B$ 。

正确答案：B

题目详解：
为了合理地设置进程优先级，应该将进程的 CPU 时间和 I/0 时间做综合考虑，对千 CPU 占用时间较少而 I/O 占用时间较多的进程，优先调度能让 I/O 更早地得到使用，提高了系统的资源利用率，显然应该具有更高的优先级。

正确答案：B

题目详解：
银行家算法是一种用于避免死锁的资源分配算法，其核心思想是通过动态检查资源分配状态来确保系统始终处于安全状态。下面逐一分析各选项：

A. 银行家算法可以预防死锁
错误。银行家算法属于 死锁避免（Avoidance） 算法，而非 死锁预防（Prevention） 算法。预防死锁是通过破坏死锁的四个必要条件之一实现的，而银行家算法是通过动态检查避免系统进入不安全状态。

B. 当系统处于安全状态时，系统中一定无死锁进程
正确。安全状态的定义是存在一个安全序列，使得所有进程都能顺利完成。如果系统处于安全状态，则说明资源分配合理，不会发生死锁。

C. 当系统处于不安全状态时，系统中一定会出现死锁进程
错误。不安全状态只是 可能 导致死锁，而非必然。系统可能通过后续的资源释放或进程终止重新回到安全状态。

D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件
错误。银行家算法并未破坏任何死锁必要条件，而是通过 避免循环等待 来防止死锁。

正确答案：B

题目详解：
在OSI参考模型中，应用层是第7层，其相邻层是第6层表示层。题目问的是由应用层的相邻层（即表示层）实现的功能。我们需要分析各选项的功能归属：

A. 对话管理 - 这是会话层（第5层）的功能，不属于应用层的相邻层。

B. 数据格式转换 - 这是表示层（第6层）的核心功能，包括数据编码、加密、压缩等。表示层是应用层的直接相邻下层，因此这是正确答案。

C. 路由选择 - 这是网络层（第3层）的功能，与应用层相隔较远。

D. 可靠数据传输 - 这是传输层（第4层）的功能，不是应用层的直接相邻层。

表示层的主要职责是处理数据的 $表示形式$ ，包括 $数据格式转换$ 、 $加密/解密$ 和 $数据压缩$ 等，确保应用层数据能被正确解释。

正确答案：B

题目详解：
需要了解传输介质的命名规则：10BaseT 即 10Mbps 的以太网，采用曼彻斯特编码，将一个码元分成两个相等的间隔，前一个间隔为低电平后一个间隔为高电平表示码元 1；码元 0 正好相反，也可以采用相反的规定。故对应比特串可以是 0011 0110 或 1100 1001。

正确答案：A

题目详解：
首先，我们需要计算报文交换和分组交换的总传输时间。

1. 报文交换：

   • 在报文交换中，整个报文作为一个整体传输。
   • 报文大小：$8 \text{Mb} = 8 \times 10^6 \text{ bits}$。
   • 数据传输速率：$10 \text{Mbps} = 10 \times 10^6 \text{ bits/s}$。
   • 传输时间计算公式：$\text{传输时间} = \frac{\text{报文大小}}{\text{数据传输速率}}$。
   • 主机甲到路由器的传输时间：$\frac{8 \times 10^6}{10 \times 10^6} = 0.8 \text{s} = 800 \text{ms}$。
   • 路由器到主机乙的传输时间同样为 $800 \text{ms}$。
   • 总时间：$800 \text{ms} + 800 \text{ms} = 1600 \text{ms}$。

2. 分组交换：

   • 分组大小：$10 \text{kb} = 10 \times 10^3 \text{ bits}$。
   • 报文总大小：$8 \times 10^6 \text{ bits}$。
   • 分组数量：$\frac{8 \times 10^6}{10 \times 10^3} = 800 \text{ 个分组}$。
   • 每个分组的传输时间：$\frac{10 \times 10^3}{10 \times 10^6} = 1 \text{ms}$。
   • 在分组交换中，第一个分组经过路由器后，第二个分组开始传输，因此总时间为：
     • 第一个分组从主机甲到主机乙的时间：$1 \text{ms} \times 2 = 2 \text{ms}$。
     • 其余 $799$ 个分组从主机甲到路由器的传输时间：$799 \times 1 \text{ms} = 799 \text{ms}$。
   • 总时间：$2 \text{ms} + 799 \text{ms} = 801 \text{ms}$。

综上所述，报文交换的总时间为 $1600 \text{ms}$，分组交换的总时间为 $801 \text{ms}$。

正确答案：D

题目详解：
介质访问控制（MAC）方法用于管理多个设备共享同一通信介质的访问权限。以下是选项中各方法的分析：

1. CDMA（码分多址）：通过为每个用户分配独特的编码序列来区分信号，所有用户同时使用同一频段，但不会发生冲突。冲突的可能性为 $0$。

2. CSMA（载波侦听多路访问）：设备在发送数据前先侦听信道是否空闲。如果多个设备同时检测到空闲并发送数据，则会发生冲突。冲突的概率为 $P_{collision} > 0$。

3. TDMA（时分多址）：将时间划分为固定时隙，每个用户在特定时隙内独占信道，因此不会发生冲突。冲突的可能性为 $0$。

4. FDMA（频分多址）：将频带划分为多个子频带，每个用户独占一个子频带，因此不会发生冲突。冲突的可能性为 $0$。

综上，只有 CSMA 可能发生冲突。

正确答案：B

题目详解：
HDLC（高级数据链路控制）协议使用比特填充法来实现透明传输，避免数据部分出现与帧标志相同的比特模式。HDLC的帧标志为 $01111110$，因此在数据部分遇到连续五个 $1$ 后会自动插入一个 $0$，以防止与帧标志混淆。

原始数据为 $01111100 \ 01111110$，需要对其进行比特填充：

1. 第一个字节 $01111100$：

   • 检查连续的 $1$ 的个数，没有达到五个 $1$，因此无需填充，保持不变。
   • 结果为 $01111100$。

2. 第二个字节 $01111110$：

   • 从高位开始检查，遇到连续五个 $1$（即 $11111$）后，需要插入一个 $0$。
   • 原始比特串为 $01111110$，在五个 $1$ 后插入 $0$，变为 $011111010$。
   • 但实际填充时，只填充到连续五个 $1$ 后的位置，因此填充后的结果为 $01111101 \ 0$（因为最后一个 $1$ 不属于连续五个 $1$ 的部分）。

3. 组合填充后的结果：

   • 第一个字节保持不变：$01111100$。
   • 第二个字节填充后为 $00111110 \ 10$（填充后拆分）。
   • 因此完整的组帧后比特串为 $01111100 \ 00111110 \ 10$。

正确答案是选项 A $01111100 \ 00111110 \ 10$。

正确答案：A

题目详解：
在直通交换（cut-through switching）方式下，交换机只需要检测到帧的目的地址（6字节）就可以开始转发，而不需要等待整个帧接收完毕。因此，转发延迟主要由读取目的地址所需的时间决定。

计算步骤如下：

1. 目的地址长度为 $6$ 字节，即 $48$ 比特。
2. 链路速率为 $100 \text{Mbps}$，即每秒传输 $100 \times 10^6$ 比特。
3. 传输 $48$ 比特所需的时间为：
   $\text{延迟} = \frac{48 \text{比特}}{100 \times 10^6 \text{比特/秒}} = 0.48 \times 10^{-6} \text{秒} = 0.48 \mu \text{s}$

因此，引入的转发延迟至少是 $0.48 \mu \text{s}$。

正确答案：B

题目详解：
在TCP连接中，序号（Sequence Number）和确认序号（Acknowledgment Number）用于确保数据的可靠传输。根据题目描述：

1. 主机乙发送给主机甲的TCP段信息如下：

   • 序号（Sequence Number）为 $1913$，表示该段的第一个字节的编号是 $1913$。
   • 确认序号（Acknowledgment Number）为 $2046$，表示主机乙期望下次收到主机甲发送的数据的第一个字节的编号是 $2046$。
   • 有效载荷为 $100$ 字节，因此该段的数据字节编号范围为 $1913$ 到 $2012$（即 $1913 + 100 - 1 = 2012$）。

2. 主机甲在收到该段后，需要立即回复一个TCP段，其信息如下：

   • 序号（Sequence Number）应为 $2046$，因为这是主机乙期望的下一个字节编号。
   • 确认序号（Acknowledgment Number）应为 $2013$，表示主机甲期望下次收到主机乙发送的数据的第一个字节的编号是 $2013$（即 $2012 + 1$）。

因此，主机甲发送的TCP段的序号和确认序号分别是 $2046$ 和 $2013$。

正确答案：B

题目详解：
SMTP（Simple Mail Transfer Protocol）是用于电子邮件传输的协议，其特点和工作方式如下：

1. I. 只支持传输 7 比特ASCII 码内容
   SMTP 最初设计时仅支持传输 $7$ 比特的 ASCII 码内容。对于非 ASCII 内容（如二进制文件或非英文字符），需要通过编码（如 Base64）转换为 ASCII 格式后再传输。因此，这一叙述是正确的。

2. II. 支持在邮件服务器之间发送邮件
   SMTP 的主要用途之一是在邮件服务器之间传递邮件。例如，当邮件从发送方的邮件服务器（如 $example.com$）传递到接收方的邮件服务器（如 $recipient.net$）时，使用的是 SMTP 协议。因此，这一叙述是正确的。

3. III. 支持从用户代理向邮件服务器发送邮件
   用户代理（如 Outlook、Thunderbird 等邮件客户端）使用 SMTP 协议将邮件发送到发件人的邮件服务器。因此，这一叙述是正确的。

4. IV. 支持从邮件服务器向用户代理发送邮件
   从邮件服务器向用户代理（客户端）传递邮件通常使用 POP3 或 IMAP 协议，而不是 SMTP。因此，这一叙述是错误的。

综上所述，正确的叙述是 I、II 和 III，因此正确答案是 A。

正确答案：A

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

算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素 Num。然后重新计数，确认 Num 是否为主元素。

算法可分为以下两步：

① 选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数 Num 保存到 c 中，记录 Num 的出现次数为 1；若遇到的下一个整数仍等于 Num，则计数加 1，否则计数减 1；当计数减到 0 时，将遇到的下一个整数保存到 c 中，计数重新记为 1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。

② 判断 c 中元素是否是真正的主元素：再次扫描该数组，统计 c 中元素出现的次数，若大于 2，则为主元素；否则，序列中不存在主元素。

2）算法实现

int majority(int a[], int n) {
  if (n == 0) {
    return -1;
  }
  // 选取候选元素
  int num = a[0];
  int cnt = 1;

  // 如果主元素存在，会被以下过程筛选出来
  // 但是筛选出来的不一定是主元素
  for (int i = 1; i < n; i++) {
    if (a[i] == num) {
      // 候选元素个数 +1
      cnt++;
    } else {
      // 重新设置候选元素
      cnt--;
      if (cnt == 0) {
        num = a[i];
        cnt = 1;
      }
    }
  }

  // 再判断候选元素是不是主元素
  int m = 0;
  for (int i = 0; i < n; i++) {
    // 统计候选元素出现的次数
    if (a[i] == num) {
      m++;
    }
  }
  if (m > n / 2) {
    return num;
  }
  return -1;
}

【评分说明】

① 若考生设计的算法满足题目的功能要求且正确，则 (1)、(2) 根据所实现算法的效率给分，细则见下表：

② 若在算法的基本设计思想描述中因文字表达没有非常清晰反映出算法思路，但在算法实现中能够清晰看出算法思想且正确的，可参照①的标准给分。

③ 若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。

(3) 说明算法复杂性：

参考答案中实现的程序的时间复杂度为 $O(m)$，空间复杂度为 $O(1)$。

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

【说明】本题如果采用先排好序再统计的方法，只要解答正确，最高可拿 9 分，因此对于统考算法题，去花费大量时间去思考最优解法是得不偿失的。

题目详解：
1）折半查找要求元素有序顺序存储，若各个元素的查找概率不同，则折半查找的性能不一定优于顺序查找。采用顺序查找时，元素按其查找概率的降序排列时查找长度最小。

采用顺序存储结构，数据元素按其查找概率降序排列。采用顺序查找方法。

查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。

此时，显然查找长度比折半查找的更短。

2）答案一：采用链式存储结构时，只能采用顺序查找，其性能和顺序表一样，类似于上题。数据元素按其查找概率降序排列，构成单链表。采用顺序查找方法。

查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。

答案二：还可以构造成二叉排序树的形式。采用二叉链表的存储结构，构造二叉排序树，元素的存储方式见下图。采用二叉排序树的查找方法。

查找成功时的平均查找长度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。

【评分说明】

①若考生以实际元素表示“降序排列”，同样给分。

②若考生正确求出与其查找方法对应的查找成功时的平均查找长度，给 2 分；若计算过 程正确，但结果错误，给 1 分。

③考生给出其他更高效的查找方法且正确，可参照评分标准给分。

题目详解：
1）CPU 的时钟周期是主频的倒数，即 1/800MHz=1.25ns。

总线的时钟周期是总线频率的倒数，即 1/200MHz=5ns。

总线宽度为 32 位，故总线带宽为 4B×200MHz=800MB/s 或 4B/5ns=800MB/s。

2）Cache 块大小是 32B，因此 Cache 缺失时需要一个读突发传送总线事务读取一个主存块。

3）一次读突发总线传输事务包括一次地址传送和 32B 数据传送：用 1 个总线时钟周期传输地址；每隔 40ns/8=5ns 启动一个体工作（各进行 1 次存取），第一个体读数据花费 40ns，之后数据存取与数据传输重叠；用 8 个总线时钟周期传输数据。读突发传送总线事务时间：5ns+40s+8×5ns=85ns

4）BP 的 CPU 执行时间包括 Cache 命中时的指令执行时间和 Cache 缺失时带来的额外开销。命中时的指令执行时间：100×4×1.25ns=500ns。 指令执行过程中 Cache 缺失时的额外开销：1.2×100×5%×85ns=510ns。BP 的 CPU 执行时间：500ns+510ns=1010ns。

【评分说明】

① 执行时间采用如下公式计算时，可酌情给分。

执行时间=指令条数×CPI×时钟周期×命中率 + 访存次数×缺失率×缺失损失

② 计算公式正确但运算结果不正确时，可酌情给分。

题目详解：
1）因为指令长度为 16 位，且下条指令地址为 (PC)+2，故编址单位是字节。

偏移量 OFFSET 为 8 位补码，范围为 -128~127，故相对于当前条件转移指令，向后最多可跳转 127 条指令。

【评分说明】若正确给出 OFFSET 的取值范围，则酌情给分。

2）指令中 C=0，Z=1，N=1，故应根据 ZF 和 NT 的值来判断是否转移。当 CF=0，ZF=0，NF=1 时，需转移。己知指令中偏移量为 11100011B=E3H，符号扩展后为 FFE3H，左移一位（乘 2）后为 FFC6H，故 PC 的值（即转移目标地址）为 200CH+2+FFC6H=1FD4H。当 CF=1，ZF=0，NF=0 时不转移。PC 的值为 200CH+2=200EH。

3）指令中的 C、Z 和 N 应分别设置为 C=Z=1，N=0，进行数之间的大小比较通常是对两个数进行减法，而因为是无符号数比较小于等于时转移，即两个数相减结果为 0 或者负数都应该转移，若是 0，则 ZF 标志应当为 1，所以是负数，则借位标志应该为 1，而无符号数并不涉及符号标志 NF。

4）部件①用于存放当前指令，不难得出为指令寄存器；多路选择器根据符号标志 C/Z/N 来决定下一条指令的地址是 PC+2 还是 PC+2+2×OFFSET，故多路选择器左边线上的结果应该是 PC+2+2×OFFSET。根据运算的先后顺序以及与 PC+2 的连接，部件②用于左移一位实现乘 2，为移位寄存器。部件③用于 PC+2 和 2×OFFSET 相加，为加法器。

部件②：移位寄存器（用于左移一位）；部件③：加法器（地址相加）。

【评分说明】合理给出部件名称或功能说明均给分。

题目详解：
出入口一次仅允许一个人通过，设置互斥信号量 mutex, 初值为 1。博物馆最多可同时容 纳 500 人，故设置信号量 empty, 初值为 500。

semaphore empty = 500;
semaphore mutex = 1;

visitor() {
    P(empty);
    P(mutex);
    进门;
    V(mutex);
    参观;
    P(mutex);
    出门;
    V(mutex);
    V(empty);
}

【评分说明】

①信号量初值给 1 分，说明含义给 1 分，两个信号量的初值和含义共 4 分。

②对 mutex 的 P、V 操作正确给 2 分。

③对 empty 的 P、V 操作正确给 1 分。

④其他答案，参照①~③的标准给分。

题目详解：
1）因为主存按字节编址，页内偏移量是 12 位，所以页大小为 $2^{12}B=44KB$。（1 分）

页表项数为 $2^{20}$，故该一级页表最大为 $2^{20}×4B = 44 MB$。（2 分）

2）页目录号可表示为：(((unsigned int)(LA)) >> 22) & 0x3FF。（1 分）

页表索引可表示为：(((unsigned int)(LA)) >> 12) & 0x3FF。（1 分）

【评分说明】

①页目录号也可以写成 (unsigned int)(LA) > 22；如果两个表达式没有对 LA 进行类型转换，同样给分。

②如果用除法和其他开销很大的运算方法，但对基本原理是理解的，同样给分。

③参考答案给出的是 C 语言的描述，用其他语言（包括自然语言）正确地表述了，同样给分。

3）代码页面 1 的逻辑地址为 00008000H，表明其位于第 8 个页的位置，对应页表中的第 8 个页表项，所以第 8 个页表项的物理地址 = 页表起始地址 + 8×页表项的字节数 = 00200000H + 8×4 = 00200020H。由此可得如下图所示的答案。（3 分）

【评分说明】共 5 个答数。物理地址 1 和物理地址 2 共 1 分；页框号 1 和页框号 2 共 1 分；物理地址 3 给 1 分。

题目详解：
1）要求 R2 的路由表能到达图中所有的子网，且路由项尽可能的少，则应对每个路由接口的子网进行聚合。在 AS1 中，子网 153.14.5.0/25 和子网 153.14.5.128/25 可以聚合为子网 153.14.5.0/24；在 AS2 中，子网 194.17.20.0/25 和子网 194.17.21.0/24 可以聚合为子网 194.17.20.0/23；子网 194.17.20.128/25 单独连接到 R2 的接口 E0。（6 分）

于是可以得到 R2 的路由表如下：

【评分说明】①每正确解答 1 个路由项，给 2 分，共 6 分。每条路由项正确解答目的网络 IP 地址但无前缀长度，给 0.5 分，正确解答前缀长度给 0.5 分，正确解答下一跳 IP 地址给 0.5 分，正确解答接口给 0.5 分。

②路由项解答部分正确或路由项多于 3 条，可酌情给分。

2）该 IP 分组的目的 P 地址 194.17.20.200 与路由表中 194.17.20.0/23 和 194.17.20.128/25 两个路由表项均匹配，根据最长匹配原则，R2 将通过 E0 接口转发该 P 分组。（1 分）

3）R1 和 R2 属于不同的自治系统，故应使用边界网关协议 BGP（或 BGP4）交换路由信息；（1 分）BGP 是应用层协议，它的报文被封装到 TCP 协议段中进行传输。（1 分）

【评分说明】若考生解答为 EGP 协议，且正确解答 EGP 采用 IP 协议进行通信，亦给分。