2019年408真题

题目详解：
程序段的时间复杂度取决于循环的执行次数。我们需要分析循环的终止条件以及变量 $x$ 的增长方式。

1. 循环终止条件：循环在 $n \geq (x+1)^2$ 时继续执行，当 $n < (x+1)^2$ 时终止。因此，循环执行的次数 $k$ 满足 $(k+1)^2 > n$。

2. 解不等式：为了找到 $k$ 的上界，我们可以解不等式 $(k+1)^2 > n$：
   $k+1 > \sqrt{n}$
   $k > \sqrt{n} - 1$
   因此，$k$ 的数量级为 $O(\sqrt{n})$。

3. 时间复杂度：每次循环的操作是常数时间 $O(1)$，因此整个程序段的时间复杂度为 $O(\sqrt{n})$，即 $O(n^{1/2})$。

正确答案：B

题目详解：
将一棵树 $T$ 转化为对应的二叉树 $BT$ 时，转换规则如下：

1. 树 $T$ 中的每个结点的第一个子结点作为 $BT$ 中该结点的左子结点。
2. 树 $T$ 中的同一层级的兄弟结点作为 $BT$ 中对应结点的右子结点。

树 $T$ 的后根遍历顺序是：先依次遍历每棵子树，最后访问根结点。这种遍历方式对应于二叉树 $BT$ 的中序遍历，因为：

• 在 $BT$ 中，左子树代表树 $T$ 的子结点，右子树代表树 $T$ 的兄弟结点。
• 中序遍历的顺序是：左子树 → 根结点 → 右子树，这与树 $T$ 的后根遍历（子结点 → 根结点 → 兄弟结点）完全一致。

因此，二叉树 $BT$ 的中序遍历序列与树 $T$ 的后根遍历序列相同。

正确答案：B

题目详解：
哈夫曼树是一种带权路径长度最短的二叉树，用于哈夫曼编码。对于 $n$ 个互不相同的符号进行哈夫曼编码，生成的哈夫曼树具有以下性质：

1. 哈夫曼树是一棵严格的二叉树，即每个非叶子结点都有恰好两个子结点。
2. 对于 $n$ 个叶子结点（即符号），哈夫曼树的总结点数为 $2n - 1$ 。

题目中给出哈夫曼树共有 $115$ 个结点，因此可以列出方程：
$2n - 1 = 115$

解这个方程：
$2n = 115 + 1$
$2n = 116$
$n = \frac{116}{2}$
$n = 58$

因此，$n$ 的值是 $58$ 。

正确答案：C

题目详解：
在平衡二叉树（AVL 树）中，删除和插入操作可能会触发旋转操作以保持树的平衡性。我们需要分析题目中三种叙述的正确性：

1. 叙述 I：若 $v$ 是 $T1$ 的叶结点，删除 $v$ 后形成 $T2$，再将 $v$ 插入 $T2$ 形成 $T3$。由于 $v$ 是叶结点，删除 $v$ 不会导致 $T2$ 的结构发生变化（不需要旋转），重新插入 $v$ 后 $T3$ 的结构可能与 $T1$ 相同，也可能不同（例如插入时触发旋转）。因此叙述 I 是正确的。

2. 叙述 II：若 $v$ 不是 $T1$ 的叶结点，删除 $v$ 后可能会引起旋转操作，导致 $T2$ 的结构与 $T1$ 不同。重新插入 $v$ 后，$T3$ 的结构可能与 $T1$ 相同，也可能不同（取决于具体的旋转情况）。因此叙述 II 中“一定不相同”的说法是错误的。

3. 叙述 III：与叙述 II 类似，$v$ 不是叶结点时，$T3$ 的结构可能与 $T1$ 相同，也可能不同，因此叙述 III 中“一定相同”的说法也是错误的。

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

正确答案：A

题目详解：
AOE 网]是以边表示活动的有向无环网。活动 d 开始必须满足活动 a 和活动 b 结束，所以最早开始时间是 12。最晚开始时间是指不会延长整个网的结束时间的前提下，d 的开始时间。结点 1 到结点 6 的最长路径（关键路径）是 27，结点 4 的最晚开始时间是 27-6=21，结点 d 的最晚开始时间是 21-7=14。答案选 C。

正确答案：C

题目详解：
为了用有向无环图（DAG）描述表达式 $(x + y)((x + y) / x)$，我们需要分析表达式的结构并尽可能共享相同的子表达式以减少顶点个数。以下是步骤分解：

1. 子表达式 $(x + y)$：这个子表达式在原始表达式中出现了两次，但在DAG中可以只用一个顶点表示，共享使用。

   • 顶点 $v_1$ 表示 $x$。
   • 顶点 $v_2$ 表示 $y$。
   • 顶点 $v_3$ 表示 $v_1 + v_2$（即 $x + y$）。

2. 子表达式 $(x + y) / x$：

   • 顶点 $v_4$ 表示 $v_3 / v_1$（即 $(x + y) / x$）。

3. 最终表达式 $(x + y)((x + y) / x)$：

   • 顶点 $v_5$ 表示 $v_3 \times v_4$（即 $(x + y) \times ((x + y) / x)$）。

通过共享子表达式 $(x + y)$，整个DAG只需要 $5$ 个顶点即可表示原始表达式。因此，最少的顶点个数是 $5$。

正确答案：A

题目详解：
在选择排序算法时，除了时间复杂度和空间复杂度（时空效率）外，还需要综合考虑以下因素：

1. 数据的规模（I）：不同算法在不同数据规模下的表现可能差异很大。例如，对于小规模数据，插入排序可能比快速排序更高效。

2. 数据的存储方式（II）：数据是存储在内存中还是外部存储（如磁盘），以及数据的结构（如数组、链表）会影响算法的选择。例如，链表适合归并排序，而数组适合快速排序。

3. 算法的稳定性（III）：稳定性指相等元素的相对顺序在排序后是否保持不变。例如，冒泡排序是稳定的，而快速排序是不稳定的。在需要保持相对顺序的场景（如多关键字排序）中，稳定性很重要。

4. 数据的初始状态（IV）：某些算法对初始状态敏感。例如，插入排序在数据接近有序时性能接近 $O(n)$，而快速排序在数据已有序时性能可能退化到 $O(n^2)$。

因此，所有选项 I、II、III、IV 都需要考虑。

正确答案：D

题目详解：
散列表长度为 11，散列函数为 $H(key) = key \% 7$。关键字序列为 87, 40, 30, 6, 11, 22, 98, 20。以下是插入过程：

1. 计算每个关键字的散列值：
   • $H(87) = 87 \% 7 = 3$
   • $H(40) = 40 \% 7 = 5$
   • $H(30) = 30 \% 7 = 2$
   • $H(6) = 6 \% 7 = 6$
   • $H(11) = 11 \% 7 = 4$
   • $H(22) = 22 \% 7 = 1$
   • $H(98) = 98 \% 7 = 0$
   • $H(20) = 20 \% 7 = 6$（冲突，线性探查到位置 7）

插入后的散列表 HT 如下：

查找失败的平均查找长度（ASL）计算方法是：对于散列函数 $H(key) = key \% 7$，可能的余数为 0 到 6。对于每个余数 $i$，从 $HT[i]$ 开始顺序查找，直到遇到空位置为止，记录查找长度。

计算各余数的查找失败长度：

• $i = 0$：查找 0, 1, 2, 3, 4, 5, 6, 7, 8（找到空位置 8），长度为 9
• $i = 1$：查找 1, 2, 3, 4, 5, 6, 7, 8（找到空位置 8），长度为 8
• $i = 2$：查找 2, 3, 4, 5, 6, 7, 8（找到空位置 8），长度为 7
• $i = 3$：查找 3, 4, 5, 6, 7, 8（找到空位置 8），长度为 6
• $i = 4$：查找 4, 5, 6, 7, 8（找到空位置 8），长度为 5
• $i = 5$：查找 5, 6, 7, 8（找到空位置 8），长度为 4
• $i = 6$：查找 6, 7, 8（找到空位置 8），长度为 3

平均查找长度 $ASL = \frac{9 + 8 + 7 + 6 + 5 + 4 + 3}{7} = \frac{42}{7} = 6$。

正确答案：C

题目详解：
首先，我们需要为模式串 $S = "abaabc"$ 构建部分匹配表（也称为 next 数组）。部分匹配表的构建规则是：对于模式串的每个位置 $i$，找到最长的前缀和后缀相等的长度（不包括整个字符串本身）。

模式串 $S$ 的索引和字符如下：

$0: a$
$1: b$
$2: a$
$3: a$
$4: b$
$5: c$

构建部分匹配表的过程如下：

1. $i = 0$：没有前缀和后缀，$next[0] = -1$。
2. $i = 1$：前缀和后缀不匹配，$next[1] = 0$。
3. $i = 2$：比较 $S[0]$ 和 $S[1]$（$a$ 和 $b$），不匹配，$next[2] = 0$。
4. $i = 3$：比较 $S[0]$ 和 $S[2]$（$a$ 和 $a$），匹配，$next[3] = 1$。
5. $i = 4$：比较 $S[1]$ 和 $S[3]$（$b$ 和 $a$），不匹配，回退到 $next[1] = 0$，比较 $S[0]$ 和 $S[3]$（$a$ 和 $a$），匹配，$next[4] = 1$。
6. $i = 5$：比较 $S[1]$ 和 $S[4]$（$b$ 和 $b$），匹配，$next[5] = 2$。

最终的部分匹配表为：$next = [-1, 0, 0, 1, 1, 2]$。

接下来，使用 KMP 算法在主串 $T = "abaabaabcabaabc"$ 中匹配模式串 $S$。匹配过程如下：

1. 初始时，$i = 0$（主串指针），$j = 0$（模式串指针）。
2. 比较 $T[0]$ 和 $S[0]$（$a$ 和 $a$），匹配，$i = 1$，$j = 1$，比较次数 $+1$。
3. 比较 $T[1]$ 和 $S[1]$（$b$ 和 $b$），匹配，$i = 2$，$j = 2$，比较次数 $+1$。
4. 比较 $T[2]$ 和 $S[2]$（$a$ 和 $a$），匹配，$i = 3$，$j = 3$，比较次数 $+1$。
5. 比较 $T[3]$ 和 $S[3]$（$a$ 和 $a$），匹配，$i = 4$，$j = 4$，比较次数 $+1$。
6. 比较 $T[4]$ 和 $S[4]$（$b$ 和 $b$），匹配，$i = 5$，$j = 5$，比较次数 $+1$。
7. 比较 $T[5]$ 和 $S[5]$（$a$ 和 $c$），不匹配，根据 $next[5] = 2$，回退 $j = 2$，比较次数 $+1$。
8. 比较 $T[5]$ 和 $S[2]$（$a$ 和 $a$），匹配，$i = 6$，$j = 3$，比较次数 $+1$。
9. 比较 $T[6]$ 和 $S[3]$（$a$ 和 $a$），匹配，$i = 7$，$j = 4$，比较次数 $+1$。
10. 比较 $T[7]$ 和 $S[4]$（$b$ 和 $b$），匹配，$i = 8$，$j = 5$，比较次数 $+1$。
11. 比较 $T[8]$ 和 $S[5]$（$c$ 和 $c$），匹配，匹配成功，比较次数 $+1$。

总比较次数为 $10$ 次。

正确答案：B

题目详解：
快速排序每一趟会确定一个基准元素的最终位置，并将序列分为两个子序列（左子序列元素均小于基准，右子序列元素均大于基准）。我们需要分析每个选项是否符合快速排序第二趟的特征。

1. 选项A：$5, 2, 16, 12, 28, 60, 32, 72$

   • 第一趟可能以 $28$ 为基准，将序列分为 $[5, 2, 16, 12]$ 和 $[60, 32, 72]$。
   • 第二趟对左子序列以 $12$ 为基准，得到 $[5, 2]$ 和 $[16]$；对右子序列以 $60$ 为基准，得到 $[32]$ 和 $[72]$。
   • 最终序列可能是 $5, 2, 16, 12, 28, 60, 32, 72$，符合快速排序第二趟结果。

2. 选项B：$2, 16, 5, 28, 12, 60, 32, 72$

   • 第一趟可能以 $12$ 为基准，将序列分为 $[2, 5]$ 和 $[16, 28, 60, 32, 72]$。
   • 第二趟对左子序列以 $5$ 为基准，得到 $[2]$ 和 $[]$；对右子序列以 $28$ 为基准，得到 $[16]$ 和 $[60, 32, 72]$。
   • 最终序列可能是 $2, 16, 5, 28, 12, 60, 32, 72$，符合快速排序第二趟结果。

3. 选项C：$2, 12, 16, 5, 28, 32, 72, 60$

   • 第一趟可能以 $28$ 为基准，将序列分为 $[2, 12, 16, 5]$ 和 $[32, 72, 60]$。
   • 第二趟对左子序列以 $12$ 为基准，得到 $[2, 5]$ 和 $[16]$；对右子序列以 $60$ 为基准，得到 $[32]$ 和 $[72]$。
   • 最终序列可能是 $2, 12, 16, 5, 28, 32, 72, 60$，符合快速排序第二趟结果。

4. 选项D：$5, 2, 12, 28, 16, 32, 72, 60$

   • 第一趟可能以 $16$ 为基准，将序列分为 $[5, 2, 12]$ 和 $[28, 32, 72, 60]$。
   • 第二趟对左子序列以 $5$ 为基准，得到 $[2]$ 和 $[12]$；对右子序列以 $32$ 为基准，得到 $[28]$ 和 $[72, 60]$。
   • 最终序列应为 $2, 5, 12, 16, 28, 32, 60, 72$，与选项D不符。因此，选项D不可能是快速排序第二趟的结果。

正确答案：D

题目详解：
在外部排序的多路归并中，为了构造一个严格的 $k$ 路归并树（即每个内部节点都有恰好 $k$ 个子节点），初始归并段的数量 $n$ 必须满足 $n \equiv 1 \mod (k-1)$ 。如果 $n$ 不满足这一条件，则需要补充 $d$ 个虚段（dummy runs），使得 $(n + d) \equiv 1 \mod (k-1)$ 。

给定：

• 初始归并段数 $n = 120$
• 归并路数 $k = 12$

计算步骤如下：

1. 检查 $n \mod (k-1)$ ：
   $120 \mod (12 - 1) = 120 \mod 11 = 10$
2. 需要满足 $(120 + d) \mod 11 = 1$ ，即：
   $(10 + d) \mod 11 = 1$
3. 解得 $d = 2$ （因为 $10 + 2 = 12$ ，而 $12 \mod 11 = 1$ ）。

因此，需要补充 $2$ 个虚段。

正确答案：B

题目详解：
冯·诺依曼结构计算机的基本思想包括以下核心要点：

1. 程序存储和程序控制：程序执行前，指令和数据需预先存放在存储器中（对应选项 D）。这是冯·诺依曼结构的基本原则之一。

2. 二进制表示：指令和数据都用二进制数表示，形式上无差别（对应选项 B）。这也是冯·诺依曼结构的重要特征。

3. 中央处理器执行指令：程序的功能都通过中央处理器（CPU）执行指令实现（对应选项 A）。CPU 是冯·诺依曼结构的核心部件。

4. 指令和数据的访问方式：

   • 指令按地址访问（即通过程序计数器 PC 指向的地址获取指令）。
   • 数据通常通过指令中的地址字段间接访问，而非直接在指令中给出（即选项 C 中“数据都在指令中直接给出”是错误的）。数据通常存储在存储器中，指令通过地址访问数据。

选项 C 的错误在于，数据通常不直接在指令中给出，而是通过指令中的地址字段访问存储器中的数据。只有少数特殊指令（如立即数指令）可能直接包含数据，但这不是普遍情况。

正确答案：C

题目详解：
在C语言中，unsigned short 和 short 都是16位整数类型，但它们的表示范围不同：

• unsigned short 的范围是 $0$ 到 $65535$（即 $2^{16} - 1$）。
• short 的范围是 $-32768$ 到 $32767$（使用补码表示）。

代码的执行过程如下：

1. unsigned short usi = 65535; 将 usi 初始化为 $65535$，这是 unsigned short 的最大值，其二进制表示为 1111111111111111（16个1）。
2. short si = usi; 将 usi 的值赋给 short 类型的 si。由于 short 是有符号类型，最高位是符号位。1111111111111111 在补码表示中对应的是 $-1$（因为补码的 $-1$ 是全1的二进制表示）。

因此，si 的值是 $-1$。

正确答案：A

题目详解：
缺页处理是操作系统中内存管理的重要机制，涉及以下关键点：

1. 缺页触发条件：当CPU在地址转换过程中发现虚拟地址对应的页表项有效位为 $0$ 时，会触发缺页异常（Page Fault），属于CPU检测到的异常。因此选项A正确。

2. 缺页处理程序：缺页异常由操作系统的缺页处理程序（Page Fault Handler）接管，负责处理缺失页的加载。因此选项B正确。

3. 处理过程：缺页处理程序通过页故障地址（Cr2寄存器保存）定位缺失的页，并从外存（如磁盘）调入物理内存。因此选项C正确。

4. 返回执行点：缺页处理完成后，CPU会重新执行发生缺页的指令（而非下一条指令），因为原指令可能因缺页未完成操作。因此选项D错误。

正确答案：D

题目详解：
首先，我们需要理解几个关键概念和步骤：

1. 大端方式：在大端模式下，数据的高字节存储在低地址，低字节存储在高地址。例如，机器数 $1234FF00H$ 在内存中的存储方式为：

   • 地址 $A$：$12H$
   • 地址 $A+1$：$34H$
   • 地址 $A+2$：$FFH$
   • 地址 $A+3$：$00H$

2. 基址寻址方式：操作数的有效地址 $EA$ 由基址寄存器的内容加上形式地址（偏移量）得到。公式为：

   $$EA = \text{基址寄存器内容} + \text{形式地址}$$

3. 形式地址：题目中给出的形式地址是 $FF12H$，用补码表示。由于 $FF12H$ 的最高位为 $1$，它是一个负数。我们需要将其转换为真实的偏移量：

   • 补码 $FF12H$ 对应的原码为 $-0EEH$（即 $-238$ 的补码表示）。
   • 因此，形式地址的实际值是 $-0EEH$。

4. 计算有效地址：

   • 基址寄存器内容为 $F0000000H$。
   • 形式地址为 $-0EEH$。
   • 有效地址 $EA$ 计算如下：

     $$EA = F0000000H + (-0EEH) = F0000000H - 0EEH = EFFFFF12H$$

5. 操作数的 LSB（最低有效字节）：

   • 操作数的机器数为 $1234FF00H$，其最低有效字节是 $00H$。
   • 在大端模式下，$00H$ 存储在最高地址，即 $EA + 3$。
   • 因此，LSB 的地址为：

     $$EFFFFF12H + 3 = EFFFFF15H$$

综上所述，操作数的 LSB 所在的地址是 $EFFFFF15H$。

正确答案：D

题目详解：
A. 时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成

• 这是正确的。时钟信号通常由一个高频率的振荡器（脉冲源）产生，然后经过整形（如施密特触发器）和分频电路处理，以生成适合处理器使用的时钟信号。

B. 时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频

• 这是正确的。时钟周期（$T$）是指一个时钟脉冲的持续时间，而主频（$f$）是时钟周期的倒数，即 $f = \frac{1}{T}$。

C. 时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定

• 这是正确的。时钟周期的设计必须满足最坏情况下的时序要求，即确保信号能够在一个时钟周期内通过最长的组合逻辑路径（最大延迟）。

D. 处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令

• 这是错误的。处理器并非每个时钟周期都开始执行一条新指令。现代处理器采用流水线技术，指令的执行是重叠的，每条指令可能需要多个时钟周期才能完成。此外，还存在多周期指令、分支延迟等情况。

正确答案：D

题目详解：
该指令的功能为 $R[r2] \leftarrow R[r1] + M[R[r0]]$，即从寄存器 $r1$ 中读取数据，从寄存器 $r0$ 中读取地址，再根据该地址从存储器中读取数据，最后将两者相加并存入寄存器 $r2$。分析各部件的作用如下：

1. 通用寄存器组（GPRs）：需要用到 $r0$、$r1$ 和 $r2$。$r0$ 提供存储器地址，$r1$ 提供加数，$r2$ 存储结果。因此 I 是必需的。

2. 算术逻辑单元（ALU）：需要执行加法操作 $R[r1] + M[R[r0]]$，因此 II 是必需的。

3. 存储器（Memory）：需要通过 $R[r0]$ 间接寻址读取数据 $M[R[r0]]$，因此 III 是必需的。

4. 指令译码器（ID）：在取数及执行过程中，指令译码器的作用是解析指令，但题目问的是“取数及执行过程”中实际用到的部件，ID 不直接参与数据的读取或运算，因此 IV 不需要。

综上所述，必需的部件是 I、II、III。

正确答案：B

题目详解：
这四条指令在流水线中执行的过程如下图所示：

数据冒险指在程序中存在必须等前条指令执行完才能执行后一条指令的情况，此时这两条指令即为数据相关。其中 $I1$ 和 $I3$、$I2$ 和 $I3$、$I3$ 和 $I4$ 均发生了写后读相关，因此必须等相关的前条指令执行完才能执行后一条指令。只有 $I2$ 和 $I4$ 不存在数据冒险。所以答案选 C。

正确答案：C

题目详解：
由题目可知，计算机采用 3 通道存储器总线，存储器总线的工作频率为 1333MHz，即 1 秒内传送 1333M 次数据，总线宽度为 64 位即单条总线工作一次可传输 8 字节（Byte），因此存储器总线的总带宽 3×8×1333MB/s，约为 32GB/s，故答案选 B。

正确答案：B

题目详解：
磁盘存储器的相关知识如下：

1. 格式化容量与非格式化容量：

   • 非格式化容量是指磁盘理论上可以存储的最大数据量，计算公式为：
     $非格式化容量 = 磁道数 \times 每磁道位数$
   • 格式化容量是实际可用的存储容量，由于需要保留部分空间用于扇区划分、校验等信息，因此格式化容量比非格式化容量小。所以选项 A 是正确的。

2. 扇区的组成：

   • 每个扇区通常包含以下几个部分：
     • 数据字段（存储实际数据）
     • 地址字段（标识扇区位置）
     • 校验字段（如CRC，用于错误检测）
       因此，选项 B 是正确的。

3. 最小读写单位：

   • 磁盘存储器的最小读写单位是一个扇区（通常为512字节或4KB），而不是一字节。操作系统和磁盘控制器以扇区为单位进行数据读写。因此，选项 C 是错误的。

4. 磁盘存储器的组成：

   • 磁盘存储器主要由三部分组成：
     • 磁盘控制器（控制磁盘操作）
     • 磁盘驱动器（驱动盘片旋转和磁头移动）
     • 盘片（存储数据的物理介质）
       因此，选项 D 是正确的。

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

正确答案：C

题目详解：
设备接口中的数据缓冲寄存器为 32 位，即一次 中断可以传输 4B 数据，设备数据传输率为 50kB/s，共需要 12.5k 次中断，每次中断开销为 1000 个时钟周期，CPU 频为 1GHz，则 CPU 用于该设备输入/输出的时间占整个 CPU 时间的百分比最多是 (12.5k×1000)/1G=1.25%。

正确答案：A

题目详解：
DMA（Direct Memory Access，直接存储器访问）是一种数据传输方式，允许外设直接与内存进行数据交换而不需要 CPU 的全程干预。以下是关于 DMA 方式的详细分析：

1. I. DMA 传送前由设备驱动程序设置传送参数

   • 在 DMA 传输开始前，设备驱动程序需要初始化 DMA 控制器，设置传输参数，包括源地址、目标地址、传输数据长度等。因此，该叙述是正确的。

2. II. 数据传送前由 DMA 控制器请求总线使用权

   • DMA 控制器在数据传输前需要向总线仲裁器请求总线使用权，获得批准后才能控制总线进行数据传输。因此，该叙述是正确的。

3. III. 数据传送由 DMA 控制器直接控制总线完成

   • DMA 控制器在获得总线使用权后，直接控制总线完成数据传输，无需 CPU 干预。因此，该叙述是正确的。

4. IV. DMA 传送结束后的处理由中断服务程序完成

   • DMA 传输完成后，DMA 控制器会向 CPU 发出中断信号，由中断服务程序进行后续处理（如释放资源、通知驱动程序等）。因此，该叙述是正确的。

综上所述，所有叙述 I、II、III、IV 都是正确的。

正确答案：D

题目详解：
线程是程序执行流的最小单元，可以分为用户级线程（User-Level Threads, ULT）和内核级线程（Kernel-Level Threads, KLT）。以下是各选项的详细分析：

• 选项A：内核级线程的调度由操作系统完成。这是正确的，因为内核级线程由操作系统内核直接管理，线程的创建、调度和同步等操作都需要内核介入。

• 选项B：操作系统为每个用户级线程建立一个线程控制块。这是错误的，因为用户级线程是由用户空间的线程库（如POSIX的pthread库）管理的，线程控制块（Thread Control Block, TCB）也由线程库维护，而不是由操作系统内核直接管理。操作系统通常感知不到用户级线程的存在。

• 选项C：用户级线程间的切换比内核级线程间的切换效率高。这是正确的，因为用户级线程的切换不需要陷入内核态，避免了上下文切换的开销，切换过程完全在用户空间完成。

• 选项D：用户级线程可以在不支持内核级线程的操作系统上实现。这是正确的，因为用户级线程完全由用户空间的线程库实现，不依赖于操作系统内核的支持。

综上所述，错误的描述是选项B。

正确答案：B

题目详解：
进程唤醒通常发生在以下情况：

1. I/O 结束（I）：当一个进程因为等待 I/O 操作而进入阻塞状态时，I/O 操作完成后，操作系统会将该进程唤醒，使其从阻塞状态转为就绪状态。

2. 某进程退出临界区（II）：当某个进程退出临界区时，可能会释放某些资源或信号量，从而唤醒其他正在等待这些资源或信号量的进程。

3. 当前进程的时间片用完（III）：当前进程的时间片用完并不会直接唤醒其他进程，而是触发进程调度，将 CPU 分配给其他就绪状态的进程。因此，这种情况不会直接导致进程唤醒。

综上所述，可能将进程唤醒的事件是 I 和 II，而 III 不会直接唤醒进程。

正确答案：C

题目详解：
关于系统调用的叙述，我们逐一分析各选项：

I. 正确。在执行系统调用服务程序的过程中，CPU 需要从用户态切换到内核态，此时 CPU 处于内核态，以执行特权指令和访问受保护的内核资源。

II. 正确。操作系统通过系统调用封装底层硬件操作，避免用户程序直接访问外设，从而保证系统的安全性和稳定性。用户程序必须通过系统调用来请求内核代为完成外设操作。

III. 错误。不同的操作系统提供的系统调用接口通常是不相同的，没有统一的接口标准。例如 Linux 和 Windows 的系统调用编号和实现方式就有很大差异。

IV. 正确。系统调用是操作系统内核为应用程序提供服务的接口，应用程序通过系统调用可以请求内核完成文件操作、进程管理等服务。

综上所述，正确的叙述是 I、II、IV。

正确答案：C

题目详解：
文件系统管理空闲磁盘块时，常用的数据结构包括以下几种：

1. 位图（I）：位图（Bitmap）是一种简单高效的数据结构，用二进制位（ $0$ 和 $1$ ）表示磁盘块的空闲或占用状态。 $0$ 表示空闲， $1$ 表示占用。位图占用空间小，适合快速查找空闲块。

2. 索引结点（II）：索引结点（inode）是用于描述文件元数据的数据结构，主要记录文件的属性、权限、大小以及数据块的位置等信息，不直接用于管理空闲磁盘块，因此不符合题意。

3. 空闲磁盘块链（III）：空闲磁盘块链通过链表的方式将空闲磁盘块链接起来，每个空闲块存储下一个空闲块的地址。这种方式实现简单，但遍历效率较低。

4. 文件分配表（FAT）（IV）：文件分配表（File Allocation Table）是一种表格结构，用于记录磁盘块的分配状态。FAT 表项可以标记空闲块，因此也可用于空闲磁盘块的管理。

综上，可用于文件系统管理空闲磁盘块的数据结构是 位图（I）、空闲磁盘块链（III） 和 文件分配表（FAT）（IV）。

正确答案：B

题目详解：
进程 P1、P2 依次创建后进入队列 Q1，根据时间片调度算法的规则，进程 P1、P2 将依次被分配 10ms 的 CPU 时间，两个进程分别执行完一个时间片后都会被转入队列 Q2，就绪队列 Q2 采用短进程优先调度算法，此时 P1 还需要 20ms 的 CPU 时间，P2 还需要 10ms 的 CPU 时间，所以 P2 会被优先调度执行，10ms 后进程 P2 执行完成，之后 P1 再调度执行，再过 20ms 后 P1 也执行完成。平均等待时间 = (P1 等待时间 + P2 等待时间) / 2 = (20 + 10) / 2 = 15。

正确答案：C

题目详解：
在分段存储管理系统中，共享段表用于管理被多个进程共享的段。对于进程 $P_1$ 和 $P_2$ 共享段 $S$ 的情况：

• 选项A：正确。共享段的核心思想是在物理内存中只保留一份 $S$ 的内容，多个进程通过映射共享同一份物理副本，节省内存空间。

• 选项B：错误。共享段 $S$ 在 $P_1$ 和 $P_2$ 中的段号可以不同，因为段号是进程逻辑地址空间内的局部标识，不同进程的段号是独立的。共享是通过共享段表的全局管理实现的，不需要段号一致。

• 选项C：正确。$P_1$ 和 $P_2$ 共享段 $S$ 时，共享段表中只有一个对应的段表项，记录 $S$ 的物理地址、长度等信息，供两个进程共同引用。

• 选项D：正确。共享段的回收采用引用计数机制，只有当所有共享该段的进程（如 $P_1$ 和 $P_2$ ）都不再使用时，才会释放 $S$ 所占的内存空间。

正确答案：B

题目详解：
首先，我们需要理解 LRU（Least Recently Used）页置换算法的原理。LRU 算法会淘汰最近最少使用的页面。系统为进程 P 预分配了 $4$ 个页框，初始时页框为空。我们逐步分析页访问序列 $0, 1, 2, 7, 0, 5, 3, 5, 0, 2, 7, 6$ 的过程：

1. 访问 $0$：页框为空，加载 $0$，页框状态为 $[0]$，缺页。
2. 访问 $1$：加载 $1$，页框状态为 $[0, 1]$，缺页。
3. 访问 $2$：加载 $2$，页框状态为 $[0, 1, 2]$，缺页。
4. 访问 $7$：加载 $7$，页框状态为 $[0, 1, 2, 7]$，缺页。
5. 访问 $0$：$0$ 已在页框中，页框状态不变 $[0, 1, 2, 7]$，命中。
6. 访问 $5$：页框已满，淘汰最近最少使用的 $1$，加载 $5$，页框状态为 $[0, 2, 7, 5]$，缺页（置换 1 次）。
7. 访问 $3$：页框已满，淘汰最近最少使用的 $2$，加载 $3$，页框状态为 $[0, 7, 5, 3]$，缺页（置换 2 次）。
8. 访问 $5$：$5$ 已在页框中，页框状态不变 $[0, 7, 5, 3]$，命中。
9. 访问 $0$：$0$ 已在页框中，页框状态不变 $[0, 7, 5, 3]$，命中。
10. 访问 $2$：页框已满，淘汰最近最少使用的 $7$，加载 $2$，页框状态为 $[0, 5, 3, 2]$，缺页（置换 3 次）。
11. 访问 $7$：页框已满，淘汰最近最少使用的 $5$，加载 $7$，页框状态为 $[0, 3, 2, 7]$，缺页（置换 4 次）。
12. 访问 $6$：页框已满，淘汰最近最少使用的 $0$，加载 $6$，页框状态为 $[3, 2, 7, 6]$，缺页（置换 5 次）。

综上，总共发生了 $5$ 次页置换。

正确答案：C

题目详解：
死锁是指多个进程在执行过程中因争夺资源而造成的一种互相等待的现象，导致这些进程都无法继续执行下去。下面逐一分析各个叙述的正确性：

I. 可以通过剥夺进程资源解除死锁
正确。死锁解除的方法之一是通过资源剥夺，即从某些进程中强行剥夺资源，分配给其他进程，以打破死锁状态。

II. 死锁的预防方法能确保系统不发生死锁
正确。死锁预防是通过破坏死锁的四个必要条件（互斥、占有并等待、非抢占、循环等待）中的一个或多个，从而确保系统不会进入死锁状态。

III. 银行家算法可以判断系统是否处于死锁状态
错误。银行家算法是一种死锁避免算法，用于判断系统是否处于安全状态，从而决定是否分配资源，但它不能直接判断系统是否已经处于死锁状态。

IV. 当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态
正确。死锁发生时，至少有两个或两个以上的进程因互相等待资源而被阻塞，无法继续执行。

综上所述，叙述 I、II、IV 是正确的，III 是错误的。因此，正确答案是 B。

正确答案：B

题目详解：
题中给出的是十六进制地址，首先将它转化为二进制地址，然后用二进制地址去匹配题中对应的地址结构。转换为进制地址和地址结构的对应关系如下所示。

2050 1225H = 0010 0000 01010000 00010010 00100101

前 10 位、11~20 位、21~32 位分别对应页目录号、页号和页内偏移。把页目录号、页号单独拿出，转换为十六进制时缺少的位数在高位补零，0000 1000 0001、0001 0000 0001 分别对应 081H、101H，选项 A 正确。

题目详解：
在动态分区分配算法中，内存碎片的产生与算法的分配策略密切相关。题目中给出的四种算法特点如下：

1. 首次适应算法（A）：从内存起始地址开始查找，选择第一个足够大的空闲分区。这种算法倾向于利用低地址部分的内存，可能导致高地址部分留下较大的空闲块，但碎片化程度相对较低。

2. 最坏适应算法（B）：总是选择最大的空闲分区进行分配。这种算法试图减少外部碎片，但可能导致较大的空闲块被分割，后期难以满足大进程的需求。

3. 最佳适应算法（C）：选择最小的足够大的空闲分区进行分配。这种算法容易将空闲分区切割成许多小块，导致大量无法利用的小碎片（外部碎片），因此最容易产生内存碎片。

4. 循环首次适应算法（D）：类似于首次适应算法，但从上次分配的位置开始查找。碎片化程度与首次适应算法相近。

综上，最佳适应算法由于总是寻找最小的合适分区，会留下大量难以利用的小空闲块，因此最容易产生内存碎片。

正确答案：C

题目详解：
OSI（Open Systems Interconnection）参考模型是一个七层网络架构模型，自下而上依次为：

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

题目问的是第 5 层（自下而上）的功能，即会话层（Session Layer）的主要功能。会话层的主要职责是建立、管理和终止应用程序之间的会话（Session），包括会话同步和会话控制等功能。具体来说：

• 选项 A（差错控制）主要由数据链路层和传输层负责。
• 选项 B（路由选择）是网络层的功能。
• 选项 C（会话管理）是会话层的核心功能。
• 选项 D（数据表示转换）是表示层的功能。

因此，正确答案是 C（会话管理）。

正确答案：C

题目详解：
100BaseT 快速以太网是一种常见的以太网标准，其名称中的各部分含义如下：

• $100$ 表示传输速率为 $100$ Mbps。
• $Base$ 表示采用基带传输方式。
• $T$ 表示使用的传输介质是双绞线（Twisted Pair）。

100BaseT 快速以太网通常使用 $2$ 对 $5$ 类（或更高）非屏蔽双绞线（UTP）或屏蔽双绞线（STP）作为导向传输介质。双绞线通过将两根绝缘铜导线相互缠绕，可以减少电磁干扰（EMI）和串扰，从而支持高速数据传输。

其他选项的传输介质：

• 单模光纤（B 选项）通常用于长距离、高带宽的应用，如 $1000BaseLX$ 千兆以太网。
• 多模光纤（C 选项）通常用于中等距离的应用，如 $1000BaseSX$ 千兆以太网。
• 同轴电缆（D 选项）主要用于早期的以太网标准，如 $10Base5$ 和 $10Base2$，现已较少使用。

正确答案：A

题目详解：
在滑动窗口协议中，为了保证协议的正确性，发送窗口大小 $W_s$ 和接收窗口大小 $W_r$ 必须满足以下条件：
$W_s + W_r \leq 2^n$
其中 $n$ 是分组序号的比特数。题目中给出分组序号采用 3 比特编号，因此 $n = 3$，所以：
$W_s + W_r \leq 8$
题目中发送窗口大小 $W_s = 5$，代入上式：
$5 + W_r \leq 8$
解得：
$W_r \leq 3$
因此，接收窗口的最大值是 3。

正确答案：B

题目详解：
本题考察 CSMA/CD 协议中的 限制条件：每次发送一个数据帧，最少需要 2τ时间才能收到其回复。因此发送一个最小数据帧的时间必须大于 2τ，再本题中 128×8/100M>=2τ，所以 τ 最大为 5.12us，答案为 B。

正确答案：B

题目详解：
要将网络 $101.200.16.0/20$ 划分为 5 个子网，首先需要确定每个子网所需的地址数。

1. 计算原始网络的地址空间：

   • 原始网络前缀为 $/20$，因此主机位有 $32 - 20 = 12$ 位。
   • 可分配的地址数为 $2^{12} - 2 = 4094$（减去网络地址和广播地址）。

2. 划分子网：

   • 需要划分为 5 个子网，因此需要至少 $\lceil \log_2 5 \rceil = 3$ 个额外的子网位。
   • 新的子网前缀为 $/23$（$20 + 3 = 23$）。
   • 每个子网的主机位为 $32 - 23 = 9$ 位。
   • 每个子网的可分配 IP 地址数为 $2^{9} - 2 = 510$。

3. 验证最小子网的可分配地址数：

   • 题目问的是“可能的最小子网的可分配 IP 地址数”，即需要确保所有子网都能满足最小的地址需求。
   • 如果进一步划分子网，例如使用 $/24$ 前缀，每个子网的可分配地址数为 $2^{8} - 2 = 254$。
   • 由于 $254 \times 5 = 1270 \leq 4094$，因此最小的子网可分配地址数为 $254$。

正确答案：B

题目详解：
TCP 规定当发送方收到对同一个报文段的 3 个重复的确认时，就可以认为跟在这个被确认报文段之后的报文已经丢失，立即执行快速重传算法。t3 时刻连续收到了来自服务器的三个确认序列号 ack_seq = 100 的段。发送方认为 seq = 100 的段已经丢失，执行快速重传算法，重新发送 seq = 100 段。

题目详解：
在TCP三次握手过程中，序列号和确认序列号的变化如下：

1. 第一次握手：主机甲向主机乙发送SYN报文，序列号（seq）为 $2018$，确认序列号（ack）为空。
2. 第二次握手：主机乙向主机甲发送SYN+ACK报文，序列号（seq）为 $2046$，确认序列号（ack）为 $2018 + 1 = 2019$，表示期望收到主机甲的下一个序列号。
3. 第三次握手：主机甲向主机乙发送ACK报文，序列号（seq）为 $2019$，确认序列号（ack）为 $2046 + 1 = 2047$，表示期望收到主机乙的下一个序列号。

因此，第三次握手TCP段的确认序列号是 $2047$。

正确答案：D

题目详解：
在计算机网络中，常见的网络应用模型包括客户/服务器（C/S）模型和对等网络（P2P）模型。下面对各选项进行分析：

A. 在 P2P 模型中，结点之间具有对等关系。这是正确的，因为 P2P 模型中的每个结点（peer）既是客户端又是服务器，彼此之间是对等的关系。

B. 在客户/服务器（C/S）模型中，客户与客户之间可以直接通信。这是错误的，因为在 C/S 模型中，客户之间不能直接通信，必须通过服务器进行中转。通信是客户与服务器之间的交互。

C. 在 C/S 模型中，主动发起通信的是客户，被动通信的是服务器。这是正确的，C/S 模型的基本特点是客户主动发起请求，服务器被动响应请求。

D. 在向多用户分发一个文件时，P2P 模型通常比 C/S 模型所需的时间短。这是正确的，因为 P2P 模型可以利用多个结点的带宽并行传输，而 C/S 模型依赖单一服务器，容易成为瓶颈。

因此，错误的叙述是选项 B。

正确答案：B

题目详解：
1）算法的基本设计思想：先观察 $L(a_1, a_2, a_3, \cdots, a_{n-2}, a_{n-1}, a_n)$ 和 $L'(a_1, a_{n}, a_{2}, a_{n-1}, a_{3}, a_{n-2}, \cdots)$，发现 $L'$ 是由 $L$ 摘取第一个元素，再摘取倒数第一个元素 $\cdots$ 依次合并而成的。为了方便链表后半段取元素，需要先将 $L$ 后半段原地逆置［题目要求空间复杂度为 $O(1)$，不需要辅助栈］，否则每取最后一个结点都需要遍历一次链表。

①先找出链表 $L$ 的中间结点，为此设置两个指针 $p$ 和 $q$，指针 $p$ 每次走一步，指针 $q$ 每次走两步，当指针 $q$ 到达链尾时，指针 $p$ 正好在链表的中间结点；

②然后将 $L$ 的后半段结点原地逆置。

③从单链表前后两段中依次各取一个结点，按要求重排。

2）算法实现如下：

// 找到链表的中间结点
NODE *findMiddleNode(NODE *head) {
  NODE *slow = head;
  NODE *fast = head;
  while (fast != NULL) {
    fast = fast->next;
    if (fast != NULL) {
      fast = fast->next;
    }
    slow = slow->next;
  }
  return slow;
}

// 反转链表
NODE *reverse(NODE *start) {
  NODE *p = start;
  NODE *q = start->next;
  while (q != NULL) {
    NODE *tmp = q->next;
    q->next = p;
    p = q;
    q = tmp;
  }
  return p;
}

// 1. 找到中位结点
// 2. 翻转后一半链表
// 3. 遍历两个链表，依次穿插所有结点
void solve(HEAD *head) {
  if (head->next == NULL) {
    return;
  }
  NODE *middle = findMiddleNode(head);
  NODE *list2 = reverse(middle);
  NODE *list1 = head->next;
  // 穿插操作
  NODE *p = list1;
  NODE *q = list2;
  // 退出循环的条件
  // 链表长度为奇数：p == q
  // 链表长度为偶数：p->next == q
  // while (!(p == q || p->next == q))
  while (p != q && p->next != q) {
    NODE *tmp1 = p->next;
    NODE *tmp2 = q->next;
    p->next = q;
    q->next = tmp1;
    p = tmp1;
    q = tmp2;
  }
}

3）第 1 步找中间结点的时间复杂度为 $O(n)$，第 2 步逆置的时间复杂度为 $O(n)$，第 3 步合并链表的时间复杂度为 $O(n)$，所以该算法的时间复杂度为 $O(n)$。

题目详解：
1）顺序存储无法满足要求②的队列占用空间随着入队操作而增加。根据要求来分析：要求①容易满足；链式存储方便开辟新空间，要求②容易满足；对于要求③，出队后的结点并不真正释放，用队头指针指向新的队头结点，新元素入队时，有空余结点则无须开辟新空间，赋值到队尾后的第一个空结点即可，然后用队尾指针指向新的队尾结点，这就需要设计成一个首尾相接的循环单链表，类似于循环队列的思想。设置队头、队尾指针后，链式队列的入队操作和出队操作的时间复杂度均为 $O(1)$，要求④可以满足。因此，采用链式存储结构（两段式单向循环链表），队头指针为 $front$，队尾指针为 $rear$。

2）该循环链式队列的实现，可以参考循环队列，不同之处在于循环链式队列可以方便增加空间，出队的结点可以循环利用，入队时空间不够也可以动态增加。同样，循环链式队列也要区分队满和队空的情况，这里参考循环队列牺牲一个单元来判断。初始时，创建只有一个空闲结点的循环单链表，头指针 $front$ 和尾指针 $rear$ 均指向空闲结点，如下图所示。

队空的判定条件：$front == rear$。

队满的判定条件：$front == rear\rightarrow next$。

3）插入第一个元素后的状态如下图所示。

4）操作的基本过程：

入队操作

if (front == rear->next)
    则在 rear 后面插入一个新的空闲结点；
入队元素保存到 rear 所指结点中；rear=rear->next；返回。

出队操作

if（front==rear） // 队空
    则出队失败，返回；
取 front 所指结点中的元素 e；front=front->next；返回 e。

题目详解：
回顾传统的哲学家就餐问题，假设餐桌上有 n 个哲学家、n 根筷子，那么可以用这种方法避免死锁：限制至多允许 n-1 个哲学家同时“抢”筷子，那么至少会有 1 个哲学家可以获得两根筷子并顺利进餐，于是不可能发生死锁的情况。

本题可以用碗这个限制资源来避免死锁：当碗的数量 m 小于哲学家的数量 n 时，可以直接让碗的资源量等于 m，确保不会出现所有哲学家都拿一侧筷子而无限等待另一侧筷子进而造成死锁的情况；当碗的数量大于等于哲学家的数量时，为了让碗起到同样的限制效果，我们让碗的资源量等于 n-1，这样就能保证最多只有 n-1 个哲学家同时进餐，所以得到碗的资源量为 $min(n-1, m)$。在 PV 操作时，碗的资源量起限制哲学家取筷子的作用，所以需要先对碗的资源量进行 P 操作。具体过程如下：

// 限制哲学家能同时拿到盘子的数量
semaphore fork[n] = {1};
// 并发盘子数量 < n
semaphore plate = min(m, n-1);
philosopher(int i) {
  while (1) {
    think();
    P(plate);
    P(fork[i]);
    P(fork[(i + 1) % n]);
    eat();
    V(fork[i]);
    V(fork[(i + 1) % n]);
    V(plate);
  }
}

题目详解：
1）磁盘容量 = 磁盘的柱面数 $\times$ 每个柱面的磁道数 $\times$ 每个磁道的扇区数 $\times$ 每个扇区的大小 = $(300 \times 10 \times 200 \times 512 / 1024) \text{KB} = 3 \times 10^5 \text{KB}$。

2）磁头在 85 号柱面上，对 SSTF算法而言，总是访问当前柱面距离最近的地址。注意每个簇包含 2 个扇区，通过计算得到，85 号柱面对应的簇号为 85000～85999。通过比较得出，系统最先访问离 85000～85999 最近的 100260，随后访问离 100260 最近的 101660，然后访问 110560，最后访问 60005。顺序为 100260、101660、110560、60005。

3）第 100530 簇在磁盘上的物理地址由其所在的柱面号、磁道号、扇区号构成。

• 柱面号 = $\lfloor \text{簇号} / \text{每个柱面的簇数} \rfloor = \lfloor 100530 / (10 \times 200 / 2) \rfloor = 100$。
• 磁道号 = $\lfloor (\text{簇号} \% \text{每个柱面的簇数}) / \text{每个磁道的簇数} \rfloor = \lfloor 530 / (200 / 2) \rfloor = 5$。
• 扇区号 = $\text{扇区地址} \% \text{每个磁道的扇区数} = (530 \times 2) \% 200 = 60$。

将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。

题目详解：
1）计算 $f(10)$ 需要调用函数 $f1$ 共 10 次，执行第 16 行的 call 指令会递归调用 $f1$。