2022年408真题

题目详解：
这段代码的时间复杂度分析如下：

1. 外层循环的变量 $i$ 从 $1$ 开始，每次乘以 $2$，直到 $i$ 不小于 $n$。因此，外层循环的迭代次数为 $\log_2 n$ 次。

2. 内层循环的变量 $j$ 从 $0$ 开始，每次递增 $1$，直到 $j$ 不小于 $i$。因此，内层循环的迭代次数与当前的 $i$ 值相同。

3. 总的时间复杂度可以表示为内层循环迭代次数的总和：
   $T(n) = 1 + 2 + 4 + \cdots + 2^{\log_2 n - 1}$
   这是一个等比数列，其和为：
   $T(n) = 2^{\log_2 n} - 1 = n - 1$
   因此，总的时间复杂度为 $O(n)$。

正确答案：B

题目详解：
栈（ST）是一种遵循后进先出（LIFO）原则的数据结构。给定入栈序列 $in$ 和出栈序列 $out$，我们需要分析选项的正确性。

1. 选项A：若 $in$ 是 ST 的入栈序列，可以通过模拟栈操作来判断 $out$ 是否为其可能的出栈序列。因此，选项A是错误的。

2. 选项B：若 $out$ 是 ST 的出栈序列，可以通过逆向操作推断可能的入栈序列 $in$。因此，选项B是错误的。

3. 选项C：若 $in$ 是 ST 的入栈序列，$out$ 是对应 $in$ 的出栈序列，$in$ 和 $out$ 可以相同（例如，所有元素依次入栈后立即出栈）。因此，选项C是错误的。

4. 选项D：若 $in$ 是 ST 的入栈序列，$out$ 是对应的出栈序列，则 $in$ 与 $out$ 可能互为倒序。例如，当所有元素依次入栈后，再依次出栈时，$out$ 就是 $in$ 的倒序。因此，选项D是正确的。

正确答案：D

题目详解：
在中序遍历（LNR）中，若 $p$ 和 $q$ 相邻且 $p$ 在 $q$ 之前，则 $p$ 和 $q$ 的关系可能有以下几种情况：

1. $q$ 是 $p$ 的右子树的最左结点：此时 $p$ 是 $q$ 的双亲或祖先，$q$ 是 $p$ 的右孩子（II 可能成立）。
2. $p$ 是 $q$ 的左子树的最右结点：此时 $q$ 是 $p$ 的双亲（I 可能成立）。
3. $q$ 是 $p$ 的双亲的双亲：此时 $p$ 是 $q$ 的左孩子的右子树的最左结点（IV 可能成立）。
4. $q$ 是 $p$ 的右兄弟：如果 $q$ 是 $p$ 的右兄弟，则在中序遍历中，$p$ 的子树会先被遍历，接着是 $p$ 的双亲，然后是 $q$，因此 $p$ 和 $q$ 不会相邻（III 不可能成立）。

综上，III 不可能成立，而 I、II、IV 可能成立。

正确答案：B

题目详解：
要确定三叉树 $T$ 的最小高度，我们需要考虑一个完全三叉树的结构。对于高度为 $h$ 的完全三叉树，其结点总数 $N$ 可以通过以下公式计算：

$N = 1 + 3 + 3^2 + \cdots + 3^{h-1} = \frac{3^h - 1}{2}$

我们需要找到最小的 $h$ 使得 $\frac{3^h - 1}{2} \geq 244$。解这个不等式：

$\frac{3^h - 1}{2} \geq 244 \\ 3^h - 1 \geq 488 \\ 3^h \geq 489$

接下来计算 $3^h$ 的值：

$3^5 = 243 \\ 3^6 = 729$

因为 $3^6 = 729 \geq 489$，所以最小的 $h$ 是 $6$。

因此，三叉树 $T$ 的高度至少是 $6$。

正确答案：C

题目详解：
哈夫曼编码和定长编码是两种不同的编码方式，它们的二叉树表示有以下特点：

1. 哈夫曼编码（T1）：

   • 哈夫曼编码是一种可变长编码，根据字符出现的频次构建最优二叉树。
   • 频次高的字符位于较浅的层（靠近根节点），频次低的字符位于较深的层。
   • 因此，不同频次的字符通常处于不同的层。
   • 哈夫曼树的结点数为 $2n - 1$（$n$ 是字符集大小），因为每次合并两个结点会新增一个内部结点，共需合并 $n - 1$ 次。

2. 定长编码（T2）：

   • 定长编码是一种固定长度的编码，每个字符的编码长度相同。
   • 所有字符都位于二叉树的同一层（即叶子节点在同一层）。
   • 定长编码的二叉树是一棵完全二叉树，结点数为 $2^{k} - 1$，其中 $k$ 是编码长度（$k \geq \lceil \log_2 n \rceil$）。

选项分析：

• A：错误。哈夫曼树的结点数为 $2n - 1$，而定长编码的结点数通常大于 $2n - 1$（除非 $n$ 是 2 的幂次）。
• B：错误。哈夫曼树的高度通常小于或等于定长编码树的高度，因为哈夫曼树会优先合并高频字符。
• C：错误。哈夫曼树中，频次不同的字符可能处于同一层（例如，两个频次不同的字符可能被合并到同一子树中）。
• D：正确。定长编码中，所有字符的编码长度相同，因此它们必须处于相同的层。

正确答案：D

题目详解：
对于无向图 $G = (V, E)$，我们需要分析每个选项的正确性：

• 选项A：当 $|V| > |E|$ 时，$G$ 一定是连通的。
  这是错误的。例如，一个图有 $3$ 个顶点和 $1$ 条边（即 $|V| = 3$，$|E| = 1$），此时 $|V| > |E|$，但图是不连通的。

• 选项B：当 $|V| < |E|$ 时，$G$ 一定是连通的。
  这也是错误的。例如，一个图有 $3$ 个顶点和 $3$ 条边（即 $|V| = 3$，$|E| = 3$），如果这 $3$ 条边形成一个三角形，则图是连通的；但如果 $3$ 条边中有两条边连接两个顶点，另一条边连接另外两个顶点（重叠边），则图可能不连通。

• 选项C：当 $|V| = |E| - 1$ 时，$G$ 一定是不连通的。
  这是错误的。例如，一个树结构满足 $|E| = |V| - 1$，此时 $|V| = |E| + 1$，与题目条件不符。反例不成立，但更直观的反例是：如果 $|V| = 2$，$|E| = 1$，此时 $|V| = |E| + 1$，图是连通的。

• 选项D：当 $|V| > |E| + 1$ 时，$G$ 一定是不连通的。
  这是正确的。对于一个无向图，如果它是连通的，则最少需要 $|V| - 1$ 条边（即树结构）。因此，如果 $|E| < |V| - 1$（即 $|V| > |E| + 1$），则图不可能连通。

正确答案：D

题目详解：
在 AOE 网中，活动的时间余量 = 结束顶点的最迟开始时间 - 开始顶点的最早开始时间 - 该活动的持续时间。根据关键路径算法得到下表：

c 的时间余量 = vl(3) - ve(2) - 1 = 5 - 2 - 1 = 2，g 的时间余量 = vl(6) - ve(3) - 1 = 12 - 5 - 1 = 6， h 的时间余量 = vl(5) - ve(4) - 1 = 11 - 8 - 1 = 2，j 的时间余量 = vl(6) - ve(5) - 1 = 12 - 9 - 1 = 2， 时间余量最大的活动是 g。

题目详解：
在 5 阶 B 树中，除根结点外的非叶子结点的关键字数 k 需要满足 2 ≤ k ≤ 4。当被删关键字 x 不在终端结点（最底层非叶子结点）时，可以用 x 的前驱（或后继) 关键字 y 来替代 x，然后在相应结点中删除 y。

情况①：删除 260，将其前驱 110 放入 260 处，删除 110 后的结点 不满足 5 阶 B 树定义，从左兄弟中借 85，将 85 放入根中，将根中的 90 移入结点 变为 <90, 100>。

情况②：删除 260，将其后继 280 放入 260 处，结点 不满足 5 阶 B 树定义且左右兄弟都不够借，结点 可以和左兄弟 <100, 110> 以及关键字 280 合并成一个新的结点 <100, 110, 280, 300>。

情况③：在情况②中，结点 也可以和右兄弟 <400, 500> 以及关键字 350 合并成一个新的结点 <300, 350, 400, 500>。综上，T1 根结点中的关键字序列可能是 <60, 85, 110, 350> 或 <60, 90, 350> 或 <60, 90, 280>，仅 D 不可能。

题目详解：
散列（哈希）方法的平均查找长度（ASL）受以下因素影响：

1. 装填因子（I）：装填因子 $\alpha$ 定义为哈希表中已存储的元素个数 $n$ 与哈希表大小 $m$ 的比值，即 $\alpha = \frac{n}{m}$。$\alpha$ 越大，哈希表越满，发生冲突的概率越高，从而增加平均查找长度。

2. 散列函数（II）：散列函数 $h(k)$ 的设计直接影响键值的分布均匀性。一个好的散列函数能够将键值均匀分布在哈希表中，减少冲突，从而降低平均查找长度。

3. 冲突解决策略（III）：常见的冲突解决策略包括链地址法和开放寻址法（如线性探测、二次探测等）。不同的策略在冲突发生时的处理方式不同，直接影响查找效率。例如，链地址法在冲突时使用链表存储相同哈希值的元素，而开放寻址法则会寻找下一个空闲位置。

综上所述，装填因子、散列函数和冲突解决策略均会影响散列方法的平均查找长度。

正确答案：D

题目详解：
二路归并排序是一种基于分治思想的排序算法。其核心操作是 二路归并，具体步骤如下：

1. 分解：将数组 M 递归地分成两个子数组，直到每个子数组只包含一个元素（此时自然有序）。
2. 合并：将两个 已经有序的子数组合并为一个新的有序数组。这是二路归并排序的关键步骤。

选项分析：

• A：正确描述了二路归并操作的功能，即将两个有序表合并为一个新的有序表。
• B：描述的是分解步骤，而非归并操作。
• C：描述的是分解的最底层情况，每个部分仅含一个元素，但这不是归并操作。
• D：描述的是快速排序的划分操作，与归并排序无关。

因此，正确答案是 A。

正确答案：A

题目详解：
直接插入排序和快速排序在不同场景下各有优劣，题目中列举的四种情况都是可能选择直接插入排序而不采用快速排序的原因：

1. 大部分元素已有序（I）：
   直接插入排序在近乎有序的数据上表现优异，时间复杂度接近 $O(n)$，而快速排序在这种情况下可能退化为 $O(n^2)$。

2. 待排序元素数量很少（II）：
   当数据量较小时，直接插入排序的常数因子较小，实际运行效率可能高于快速排序，尽管两者时间复杂度理论值分别为 $O(n^2)$ 和 $O(n \log n)$。

3. 要求空间复杂度为 $O(1)$（III）：
   直接插入排序是原地排序算法，空间复杂度为 $O(1)$；而快速排序虽然平均空间复杂度为 $O(\log n)$（递归栈开销），但在最坏情况下会退化为 $O(n)$。

4. 要求排序算法是稳定的（IV）：
   直接插入排序是稳定的排序算法，而快速排序是不稳定的（分区操作可能导致相同元素的相对位置改变）。

因此，四种情况均可能成为选择直接插入排序的理由。

正确答案：D

题目详解：
程序 P 的平均 CPI（Cycles Per Instruction）可以通过加权平均计算得到。具体步骤如下：

1. 计算不同指令的时钟周期贡献：

   • 80% 的指令贡献： $0.8 \times 1 = 0.8$ 个时钟周期
   • 20% 的指令贡献： $0.2 \times 10 = 2$ 个时钟周期

2. 平均 CPI 为两部分之和：
   $\text{CPI} = 0.8 + 2 = 2.8$

3. 计算 CPU 执行时间：

   • 总时钟周期数： $\text{CPI} \times \text{指令数} = 2.8 \times 10000 = 28000$ 个时钟周期
   • 主频为 1GHz，即时钟周期时间为 $\frac{1}{1 \times 10^9} = 1 \text{ns}$
   • CPU 执行时间： $28000 \times 1 \text{ns} = 28000 \text{ns} = 28 \mu \text{s}$

因此，程序 P 的平均 CPI 为 $2.8$，CPU 执行时间为 $28 \mu \text{s}$。

正确答案：A

题目详解：
在计算机中，$n$ 位补码表示的整数范围可以表示为：

$$-2^{n-1} \sim 2^{n-1} - 1$$

对于 $32$ 位补码，$n = 32$，因此其表示的范围为：

$$-2^{31} \sim 2^{31} - 1$$

具体来说：

• 最小值为 $-2^{31}$，因为最高位是符号位，表示负数，剩余的 $31$ 位用于表示数值部分。
• 最大值为 $2^{31} - 1$，因为最高位为 $0$ 表示正数，剩余的 $31$ 位全为 $1$ 时表示最大值。

因此，正确答案是 $-2^{31} \sim 2^{31} - 1$。

正确答案：B

题目详解：
首先将十进制数 -0.4375 转换为二进制表示：

1. 转换小数部分 0.4375：
   $0.4375 \times 2 = 0.875$ → 取整数部分 0
   $0.875 \times 2 = 1.75$ → 取整数部分 1
   $0.75 \times 2 = 1.5$ → 取整数部分 1
   $0.5 \times 2 = 1.0$ → 取整数部分 1
   因此，0.4375 的二进制表示为 $0.0111_2$。

2. 科学记数法表示：
   $-0.0111_2 = -1.11_2 \times 2^{-2}$。

3. IEEE 754 单精度浮点数格式（32位）：

   • 符号位（S）：1 位（1 表示负数）
   • 指数位（E）：8 位（实际指数 + 127）
   • 尾数位（M）：23 位（去掉隐含的1）

4. 计算各部分：

   • 符号位：$S = 1$（因为是负数）
   • 指数部分：实际指数为 -2，加上偏置 127，得到 $E = -2 + 127 = 125$。
     转换为二进制：$125_{10} = 01111101_2$。
   • 尾数部分：科学记数法中的尾数是 $1.11_2$，去掉隐含的1后是 $11000000000000000000000_2$（不足23位补0）。

5. 组合各部分：

   • 符号位：1
   • 指数位：01111101
   • 尾数位：11000000000000000000000
     组合起来：$1\ 01111101\ 11000000000000000000000_2$。

6. 转换为十六进制：
   将上述二进制每4位一组转换为十六进制：
   $1011 1110 1110 0000 0000 0000 0000 0000_2$ → $BEE0 0000H$。

正确答案：A

题目详解：
页大小为 4KB = 212212B，按字节编址，故页内地址为 12 位。虚拟地址空间大小为 4GB=23，故虚拟地址共 32 位，其中低 12 位为页内地址，高 20 位为虚页号。题中给出的 虚拟地址为 00082840H，虚页号为高 20 位即 00082H（页内地址为低 12 位即 840H），82H 对 应的十进制数为 130（注意题中页表的虚页号部分末尾未写 H，所以是十进制数，故查找时要 先将虚页号转换为十进制数），查页表命中，且存在位为 1，对应页框号为 018H。将查找到的 页框号 018H 和页内地址 840H 拼接，得到主存地址为 018840H。

题目详解：
首先，我们需要根据题目给出的信息逐步计算比较器的个数和位数。

1. 主存地址结构分析：

   • 主存地址为 $32$ 位，按字节编址。
   • 主存块大小为 $64B$，因此块内地址需要 $\log_2{64} = 6$ 位。

2. Cache 结构分析：

   • Cache 数据区容量为 $32KB$，主存块大小为 $64B$，因此 Cache 中可以存放的块数为：
     $\frac{32KB}{64B} = \frac{32768}{64} = 512 \text{ 块}$
   • 采用 $8$ 路组相联映射方式，因此 Cache 的组数为：
     $\frac{512}{8} = 64 \text{ 组}$
   • 组号需要 $\log_2{64} = 6$ 位。

3. Tag 位计算：

   • 主存地址的 $32$ 位可以划分为：$Tag$ 位 + 组号 $6$ 位 + 块内地址 $6$ 位。
   • 因此，$Tag$ 位数为：
     $32 - 6 - 6 = 20 \text{ 位}$

4. 比较器的个数和位数：

   • 在 $8$ 路组相联映射中，每一组有 $8$ 个块，因此需要 $8$ 个比较器同时比较 $Tag$ 位。
   • 每个比较器的位数为 $Tag$ 的位数，即 $20$ 位。

综上所述，比较器的个数为 $8$，位数为 $20$。

正确答案：A

题目详解：
首先，我们分析题目给出的信息：

1. DRAM芯片结构：每个DRAM芯片的存储结构为 $8192 \times 8192 \times 8$ 位，即每个芯片有 $8192$ 行和 $8192$ 列，每个存储单元存储 $8$ 位数据。

2. 内存条总容量：内存条包含 $8$ 个这样的DRAM芯片，因此总容量为：
   $8 \times 8192 \times 8192 \times 8 \text{ 位} = 8 \times 8192 \times 8192 \times 1 \text{ 字节} = 512 \text{ MB}$
   所以选项A是正确的。

3. 芯片地址引脚数量：每个DRAM芯片的存储单元数量为 $8192 \times 8192 = 2^{13} \times 2^{13} = 2^{26}$，因此需要 $26$ 位地址来寻址。但是，DRAM芯片通常采用行列地址复用的方式，实际地址引脚数为行地址和列地址的较大值。行地址和列地址均为 $13$ 位（因为 $8192 = 2^{13}$），因此地址引脚数为 $13$ 位，而不是 $26$ 位。所以选项C是错误的。

4. 多模块交叉编址：题目提到内存条支持突发传送方式，且总线宽度为 $64$ 位，而每个芯片的数据宽度为 $8$ 位，因此需要 $8$ 个芯片并行工作（$8 \times 8 = 64$ 位）。这种配置通常采用多模块交叉编址方式以提高带宽，所以选项B是正确的。

5. 行缓冲区大小：题目说明每个DRAM芯片有一个行缓冲区，其大小为 $8192 \times 8$ 位（即一行数据），所以选项D是正确的。

综上所述，不正确的叙述是选项C。

正确答案：C

题目详解：
指令集体系结构（ISA）是计算机体系结构中软件与硬件的接口规范，它定义了程序员可见的计算机状态、指令集及其操作语义。具体分析各选项：

1. I. 指令字格式和指令类型：这是 ISA 的核心内容，规定了指令的编码格式（如 $\text{opcode}$ 和 $\text{operand}$ 的布局）以及支持的指令类型（如算术、逻辑、控制等）。

2. II. CPU 的时钟周期：这是微架构（Microarchitecture）的实现细节，属于处理器设计的物理层面，不属于 ISA 的范畴。

3. IV. 加法器的进位方式：这是硬件实现的具体技术（如行波进位、超前进位），属于微架构或电路设计层面，与 ISA 无关。

4. III. 通用寄存器个数和位数：这是 ISA 定义的可见编程资源，程序员需要知道寄存器的数量（如 $\text{32}$ 个）和位宽（如 $\text{64-bit}$）。

综上，I 和 III 是 ISA 规定的内容，而 II 和 IV 不是。因此正确答案是 B。

正确答案：B

题目详解：
指令字长度为 16 位，地址码为 6 位。操作码采用扩展编码方式，支持零地址、一地址和二地址三种指令格式。

1. 二地址指令：

   • 地址码占用 $2 \times 6 = 12$ 位，剩余操作码位数为 $16 - 12 = 4$ 位。
   • 二地址指令有 12 条，因此需要 $\lceil \log_2{12} \rceil = 4$ 位操作码。
   • 二地址指令的操作码范围为 $0000$ 到 $1011$（共 12 条），剩余 $1100$ 到 $1111$ 用于扩展。

2. 一地址指令：

   • 地址码占用 6 位，剩余操作码位数为 $16 - 6 = 10$ 位。
   • 二地址指令扩展出的 4 位操作码 $1100$ 到 $1111$ 用于一地址指令的前缀。
   • 因此，一地址指令的操作码总长度为 $4 + 6 = 10$ 位（前缀 4 位 + 新操作码 6 位）。
   • 一地址指令有 254 条，需要 $\lceil \log_2{254} \rceil = 8$ 位操作码，但实际可用操作码位数为 6 位（前缀固定 4 位），因此最多支持 $2^6 = 64$ 条一地址指令。但题目给出 254 条，说明前缀 4 位 $1100$ 到 $1111$ 全部用于扩展，实际可用操作码为 $6$ 位，因此总数为 $4 \times 64 = 256$ 条，题目给出 254 条，剩余 $256 - 254 = 2$ 个编码未使用。

3. 零地址指令：

   • 无地址码，操作码占用全部 16 位。
   • 前缀为未使用的一地址指令编码（2 个），每个前缀可扩展 $2^{10} = 1024$ 条零地址指令（因为剩余 $16 - 6 = 10$ 位操作码）。
   • 但实际可用前缀为 2 个，因此最多支持 $2 \times 64 = 128$ 条零地址指令（因为一地址指令的扩展操作码为 6 位，$2^6 = 64$）。
   • 因此，零地址指令最多为 $2 \times 64 = 128$ 条。

正确答案：D

题目详解：
将高级语言源程序转换为可执行目标文件的主要过程分为以下四个步骤：

1. 预处理（Preprocessing）：
   预处理器处理源代码中的宏定义（如 $\#define$ ）、文件包含（如 $\#include$ ）和条件编译（如 $\#ifdef$ ）等指令，生成一个扩展的源代码文件（通常为 $.i$ 或 $.ii$ 文件）。

2. 编译（Compilation）：
   编译器将预处理后的代码翻译成汇编代码（Assembly Code），生成一个汇编语言文件（通常为 $.s$ 文件）。这一步会进行词法分析、语法分析、语义分析和代码优化。

3. 汇编（Assembly）：
   汇编器将汇编代码转换为机器指令，生成目标文件（通常为 $.o$ 或 $.obj$ 文件）。目标文件包含二进制代码，但尚未解决外部引用。

4. 链接（Linking）：
   链接器将一个或多个目标文件与库文件合并，解析外部引用，生成最终的可执行目标文件（如 $.exe$ 或 $.out$ 文件）。

因此，正确的顺序是：
$\text{预处理} \rightarrow \text{编译} \rightarrow \text{汇编} \rightarrow \text{链接}$

正确答案：A

题目详解：
中断 I/O 方式是一种常见的输入输出控制方式，其工作原理和特点如下：

1. 适用设备：中断 I/O 方式适用于键盘、针式打印机等字符型设备（选项 A 正确）。这些设备的数据传输是间歇性的，且每次传输的数据量较小。

2. 数据传输方式：在中断 I/O 方式中，外设和主机之间的数据传送是通过硬件中断机制触发的，但具体的数据传输是由软件（中断服务程序）完成的（选项 B 正确）。

3. 中断处理时间：为了使系统高效运行，外设准备数据的时间通常应大于中断处理时间。如果外设准备数据的时间小于中断处理时间，会导致频繁中断，降低 CPU 效率（选项 C 不正确）。

4. CPU 利用率：在中断 I/O 方式下，外设为某进程准备数据时，CPU 可以运行其他进程，从而提高 CPU 的利用率（选项 D 正确）。

综上所述，不正确的是选项 C。

正确答案：C

题目详解：
并行处理技术涉及多种架构和方法，以下是各选项的详细分析：

• 选项A：多核处理器（Multi-core Processor）通常属于 MIMD（Multiple Instruction Multiple Data）结构，因为每个核心可以独立执行不同的指令流和处理不同的数据。因此，该叙述是正确的。

• 选项B：向量处理器（Vector Processor）通过单条指令对多个数据执行相同操作，属于 SIMD（Single Instruction Multiple Data）结构。因此，该叙述是正确的。

• 选项C：硬件多线程技术（Hardware Multithreading）不仅可用于多核处理器，也可用于单核处理器。例如，超线程技术（Hyper-Threading）允许单个物理核心模拟多个逻辑核心。因此，该叙述是不正确的。

• 选项D：SMP（Symmetric Multiprocessing）系统中，所有处理器共享单一的物理地址空间，这是 SMP 的主要特征之一。因此，该叙述是正确的。

综上所述，不正确的是选项 C。

正确答案：C

题目详解：
在多道程序系统中，多个程序可以同时驻留在内存中，通过分时共享 CPU 资源。以下是对各选项的分析：

A. 支持进程的并发执行：多道程序系统通过进程调度实现多个进程的并发执行，这是其核心特性之一。因此该叙述正确。

B. 不必支持虚拟存储管理：多道程序系统可以在没有虚拟存储管理的情况下运行（例如早期的批处理系统），虚拟存储管理是后续技术的扩展。因此该叙述正确。

C. 需要实现对共享资源的管理：多道程序系统中，多个进程共享 CPU、内存、I/O 设备等资源，必须通过同步、互斥等机制管理共享资源。因此该叙述正确。

D. 进程数越多 CPU 利用率越高：虽然增加进程数可以提高 CPU 利用率，但当进程数超过一定限度时，系统开销（如进程切换、资源竞争）会显著增加，反而可能降低 CPU 利用率。因此该叙述不正确。

正确答案：D

题目详解：
在操作系统初始化过程中，需要创建的关键数据结构包括 $中断向量表$ 。中断向量表是操作系统用于管理硬件中断的核心数据结构，它存储了各种中断服务程序（ISR）的入口地址。当硬件触发中断时，CPU 会根据中断号从 $中断向量表$ 中查找对应的 ISR 并执行。

其他选项的解释如下：

• $B. 文件系统的根目录$ 和 $D. 文件系统的索引结点表$ 是文件系统初始化时创建的，属于文件系统管理的范畴，而非操作系统初始化的核心步骤。
• $C. 硬盘分区表$ 是由磁盘分区工具（如 fdisk）创建的，属于磁盘管理层面，不属于操作系统初始化过程。

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

正确答案：A

题目详解：
根据题目描述，系统采用基于优先权的抢占式进程调度算法，优先级值越小优先权越高。我们需要从 $0ms$ 时刻开始调度，直到所有进程运行结束，统计进程调度的总次数。以下是详细调度过程：

1. $0ms$ 时刻：就绪队列中只有 $P0$，开始执行 $P0$。

   • 调度次数：$1$ 次（$P0$ 开始执行）。

2. $10ms$ 时刻：$P1$ 和 $P2$ 进入就绪队列。此时队列中有 $P0$（优先级 $15$）、$P1$（优先级 $20$）、$P2$（优先级 $10$）。$P2$ 的优先级最高，抢占 $P0$ 的执行。

   • 调度次数：$2$ 次（$P2$ 抢占 $P0$）。

3. $15ms$ 时刻：$P3$ 进入就绪队列。此时队列中有 $P0$（优先级 $15$）、$P1$（优先级 $20$）、$P2$（优先级 $10$）、$P3$（优先级 $6$）。$P3$ 的优先级最高，抢占 $P2$ 的执行。

   • 调度次数：$3$ 次（$P3$ 抢占 $P2$）。

4. $25ms$ 时刻：$P3$ 执行完毕（执行时间 $10ms$）。此时队列中有 $P0$（优先级 $15$）、$P1$（优先级 $20$）、$P2$（剩余执行时间 $10ms$，优先级 $10$）。$P2$ 的优先级最高，继续执行。

   • 调度次数：$4$ 次（$P2$ 恢复执行）。

5. $35ms$ 时刻：$P2$ 执行完毕。此时队列中有 $P0$（优先级 $15$）、$P1$（优先级 $20$）。$P0$ 的优先级更高，恢复执行。

   • 调度次数：$5$ 次（$P0$ 恢复执行）。

6. $115ms$ 时刻：$P0$ 执行完毕（剩余执行时间 $100ms - 10ms - 10ms = 80ms$）。此时队列中只有 $P1$，开始执行 $P1$。

   • 调度次数：$6$ 次（$P1$ 开始执行）。

7. $175ms$ 时刻：$P1$ 执行完毕（执行时间 $60ms$），所有进程结束。

综上，进程调度的总次数为 $6$ 次。

正确答案：C

题目详解：
初始时系统中的可用资源数为 <1,3,2>，只能满足 P0 的需求 <0,2,1>，所以安全分配序列第一个只能是 P0， 将资源分配给 P0 后，P0 执行完释放所占资源，可用资源数变为 <1,3,2> + <2,0,1> = <3,3,3>， 此时可用资源数既能满足 P1，也能满足 P2，可以先分配给 P1，P1 执行完释放资源再分配给 P2， 也可以先分配给 P2，P2 执行完释放资源再分配给 P1。 所以安全序列可以是 ①P0、P1、P2 或 ②P0、P2、P1

题目详解：
CPU 的工作模式主要分为用户态（User Mode）和内核态（Kernel Mode），这两种模式的区别在于对系统资源的访问权限不同。

1. 用户态（User Mode）：

   • CPU 在用户态下运行时，只能执行非特权指令（Non-privileged Instructions）。
   • 非特权指令是指那些不会直接访问硬件资源或影响系统整体运行的指令，例如普通的算术运算、逻辑运算等。
   • 如果用户态程序尝试执行特权指令（Privileged Instructions），CPU 会触发异常或中断，交由操作系统处理。

2. 内核态（Kernel Mode）：

   • CPU 在内核态下运行时，可以执行特权指令和非特权指令。
   • 特权指令是指那些可以直接访问硬件资源或修改系统关键数据的指令，例如 I/O 操作、内存管理指令等。
   • 内核态通常用于运行操作系统的核心代码，具有更高的权限。

根据以上分析：

• 选项 A 错误，因为用户态不能执行特权指令。
• 选项 B 错误，因为内核态可以执行非特权指令。
• 选项 C 正确，用户态只能执行非特权指令。
• 选项 D 错误，因为内核态可以执行特权指令。

正确答案：C

题目详解：
进程的状态转换是操作系统中的重要概念。本题考察从执行态（Running）变为阻塞态（Blocked）的条件。阻塞态通常发生在进程需要等待某个事件或资源时。我们逐一分析每个选项：

I. 进程 P 读文件：读文件属于 I/O 操作，通常需要等待磁盘响应，因此会从 $\text{执行态}$ 进入 $\text{阻塞态}$。

II. 进程 P 的时间片用完：时间片用完会导致进程从 $\text{执行态}$ 进入 $\text{就绪态}$（Ready），而非阻塞态。

III. 进程 P 申请外设：申请外设（如打印机）属于 I/O 操作，需要等待资源，因此会进入 $\text{阻塞态}$。

IV. 进程 P 执行信号量的 wait() 操作：如果信号量 $S \leq 0$，wait() 操作会导致进程阻塞，进入 $\text{阻塞态}$。

综上，I、III、IV 会导致进程阻塞，而 II 不会。因此正确答案是 D。

正确答案：D

题目详解：
缺页异常处理过程通常包含以下步骤：

1. 操作系统需要 建立页号与页框号的对应关系（对应选项 B），即在页表中为页 $b$ 分配一个页框。

2. 将页 $b$ 从外存读入内存（对应选项 C），这是缺页异常处理的核心操作。

3. 修改页表中页 $b$ 对应的存在位（对应选项 D），将其标记为已加载到内存中。

然而，淘汰内存中的页（选项 A）并不一定总是发生。只有在内存中没有空闲页框时，才需要通过页面置换算法淘汰一个页面以腾出空间。如果内存中有空闲页框，则无需淘汰页面。因此，选项 A 是缺页异常处理过程中不一定包含的操作。

正确答案：A

题目详解：
缺页率（Page Fault Rate）是指进程在运行过程中访问的页面不在内存中而需要从外存调入的次数与总访问次数的比率。影响缺页率的因素主要包括以下几个方面：

1. 页置换算法（A选项）：不同的页置换算法（如FIFO、LRU、OPT等）会影响页面置换的效率，从而影响缺页率。例如，LRU算法通常比FIFO算法有更低的缺页率。

2. 工作集的大小（B选项）：工作集是指进程在某一时间段内频繁访问的页面集合。工作集越大，进程需要的页面越多，如果内存无法容纳所有工作集页面，缺页率会上升。

3. 进程的数量（C选项）：系统中运行的进程数量越多，每个进程分到的物理页面数可能越少，导致缺页率增加。

4. 页缓冲队列的长度（D选项）：页缓冲队列是操作系统用于管理已分配页面的数据结构，其长度主要影响页面调度的效率，但不会直接影响缺页率。缺页率更多取决于页面置换算法和内存分配策略，而不是缓冲队列的长度。

因此，页缓冲队列的长度不会直接影响系统的缺页率。

正确答案：D

题目详解：
在执行系统调用的过程中，操作系统的职责和用户程序的职责需要明确区分。具体分析如下：

1. 保存断点和程序状态字（I）：这是由硬件（如中断机制）自动完成的，不属于操作系统的职责。硬件会在中断发生时自动保存当前的程序计数器 $PC$ 和程序状态字 $PSW$。

2. 保存通用寄存器的内容（II）：这是由操作系统完成的。操作系统需要保存用户程序的上下文（包括通用寄存器），以便在系统调用结束后恢复用户程序的执行状态。

3. 执行系统调用服务例程（III）：这是操作系统的核心功能。操作系统根据系统调用号执行相应的服务例程，完成用户请求的功能。

4. 将 CPU 模式改为内核态（IV）：这是由硬件自动完成的。当触发系统调用或中断时，硬件会自动将 CPU 模式从用户态切换到内核态。

因此，由操作系统完成的操作是 II 和 III。

正确答案：B

题目详解：
驱动程序是操作系统与硬件设备之间的桥梁，负责管理和控制设备的操作。关于选项的具体分析如下：

• 选项A：驱动程序与 I/O 控制方式密切相关。不同的 I/O 控制方式（如程序控制 I/O、中断驱动 I/O、DMA 等）需要驱动程序进行相应的处理。因此，驱动程序的设计和实现会受到 I/O 控制方式的影响，该叙述不正确。

• 选项B：初始化设备通常由驱动程序控制完成。驱动程序在设备启动或系统初始化时，会配置设备的寄存器、分配资源等，确保设备处于就绪状态。该叙述正确。

• 选项C：进程在执行驱动程序时可能因等待 I/O 操作完成而进入阻塞态。例如，当设备繁忙或数据未就绪时，进程会被阻塞。该叙述正确。

• 选项D：读/写设备的操作由驱动程序控制完成。驱动程序负责将用户或内核的请求转换为设备能够理解的命令，并管理数据的传输。该叙述正确。

综上所述，不正确的是选项A。

正确答案：A

题目详解：
在 ISO/OSI 参考模型中，数据链路层（Data Link Layer）负责实现两个相邻结点间的流量控制功能。具体分析如下：

1. 物理层（Physical Layer）：主要负责比特流的传输，不涉及流量控制。

2. 数据链路层（Data Link Layer）：主要功能包括：

   • 帧的封装与解封装
   • 差错控制（如 CRC 校验）
   • 流量控制（通过滑动窗口协议等技术实现相邻结点间的数据传输速率匹配）
   • 介质访问控制（MAC）

3. 网络层（Network Layer）：主要负责路由选择和分组转发，实现的是端到端的通信，而非相邻结点间的流量控制。

4. 传输层（Transport Layer）：提供端到端的流量控制，但这是针对通信的两个主机之间，而非相邻结点。

因此，实现两个相邻结点间流量控制功能的是数据链路层。

正确答案：B

题目详解：
在无噪声信道中，最大数据传输速率可以通过奈奎斯特公式计算：

$C = 2B \log_2 V$

其中：

• $C$ 是最大数据传输速率（单位：bps）
• $B$ 是信道带宽（单位：Hz）
• $V$ 是调制电平数（即幅值的数量）

题目中给出的参数为：

• 带宽 $B = 200 \text{ kHz} = 200,000 \text{ Hz}$
• 幅值数量 $V = 4$（因为采用 4 个幅值的 ASK 调制）

将数值代入公式：
$C = 2 \times 200,000 \times \log_2 4$

计算 $\log_2 4$：
$\log_2 4 = 2$

因此：
$C = 2 \times 200,000 \times 2 = 800,000 \text{ bps} = 800 \text{ kbps}$

正确答案：C

题目详解：
要计算该主机所在网络的网络地址，需要将 IP 地址和子网掩码进行按位与运算。具体步骤如下：

1. 将 IP 地址 $183.80.72.48$ 和子网掩码 $255.255.192.0$ 转换为二进制形式：

   • IP 地址 $183.80.72.48$ 的二进制表示：

     • $183$ 的二进制：$10110111$
     • $80$ 的二进制：$01010000$
     • $72$ 的二进制：$01001000$
     • $48$ 的二进制：$00110000$
       完整二进制形式：$10110111.01010000.01001000.00110000$

   • 子网掩码 $255.255.192.0$ 的二进制表示：

     • $255$ 的二进制：$11111111$
     • $255$ 的二进制：$11111111$
     • $192$ 的二进制：$11000000$
     • $0$ 的二进制：$00000000$
       完整二进制形式：$11111111.11111111.11000000.00000000$

2. 对 IP 地址和子网掩码进行按位与运算：

   • 按位与运算规则：$1 \& 1 = 1$，其他情况为 $0$。
   • 运算结果：
     • 第一字节：$10110111 \& 11111111 = 10110111$（$183$）
     • 第二字节：$01010000 \& 11111111 = 01010000$（$80$）
     • 第三字节：$01001000 \& 11000000 = 01000000$（$64$）
     • 第四字节：$00110000 \& 00000000 = 00000000$（$0$）

3. 将运算结果转换为十进制形式：

   • 网络地址为：$183.80.64.0$。

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

正确答案：B

题目详解：
默认网关可以理解为离当前主机最近的路由器的端口地址，所以是 192.168.1.62， 而该主机的子网掩码和网关的子网掩码也相同，/27 即为 255.255.255.224。

题目详解：
在 SDN（软件定义网络）体系结构中，网络被分为三个主要平面：数据平面、控制平面和应用平面。各平面之间的通信通过特定接口实现：

1. 南向接口（Southbound Interface）：负责 SDN 控制器与数据平面设备（如 SDN 交换机）之间的通信。控制器通过南向接口向交换机下发流表（Flow Table），指导数据包的转发行为。常见的南向接口协议包括 OpenFlow、NETCONF 等。

2. 北向接口（Northbound Interface）：位于控制平面与应用平面之间，为上层应用程序提供编程接口，例如 RESTful API。

3. 东向接口（Eastbound Interface） 和 西向接口（Westbound Interface）：主要用于多个 SDN 控制器之间的协同通信，不属于题目描述的场景。

题目中明确提到“控制器向数据平面的交换机下发流表”，因此正确答案是 南向接口。

正确答案：B

题目详解：
当 TCP 连接发生超时，拥塞控制算法会采取以下步骤：

1. 首先，将慢启动阈值 $ssthresh$ 设置为当前拥塞窗口的一半，即 $ssthresh = \frac{16KB}{2} = 8KB$。
2. 然后将拥塞窗口 $cwnd$ 重置为 1 个 MSS（即 $1KB$），进入慢启动阶段。
3. 在慢启动阶段，每经过一个 $RTT$，$cwnd$ 会指数增长（乘以 2），直到 $cwnd$ 达到 $ssthresh$：
   • 第 1 个 $RTT$ 后：$cwnd = 2KB$
   • 第 2 个 $RTT$ 后：$cwnd = 4KB$
   • 第 3 个 $RTT$ 后：$cwnd = 8KB$（达到 $ssthresh$）
4. 之后进入拥塞避免阶段，每经过一个 $RTT$，$cwnd$ 线性增长 1 个 MSS（即 $1KB$），直到 $cwnd$ 增长到 $16KB$：
   • 第 4 个 $RTT$ 后：$cwnd = 9KB$
   • 第 5 个 $RTT$ 后：$cwnd = 10KB$
   • 第 6 个 $RTT$ 后：$cwnd = 11KB$
   • 第 7 个 $RTT$ 后：$cwnd = 12KB$
   • 第 8 个 $RTT$ 后：$cwnd = 13KB$
   • 第 9 个 $RTT$ 后：$cwnd = 14KB$
   • 第 10 个 $RTT$ 后：$cwnd = 15KB$
   • 第 11 个 $RTT$ 后：$cwnd = 16KB$

因此，从超时发生到 $cwnd$ 再次增长到 $16KB$，至少需要 $11RTT$。

正确答案：C

题目详解：
TCP 连接断开过程采用四次挥手，具体步骤如下：

1. 客户 C 发送 FIN 段给服务器 S，进入 FIN_WAIT_1 状态。
2. 服务器 S 收到 FIN 后，发送 ACK 段给 C，进入 CLOSE_WAIT 状态。C 收到 ACK 后进入 FIN_WAIT_2 状态。此过程耗时 $RTT = 50ms$。
3. 服务器 S 发送 FIN 段给 C，进入 LAST_ACK 状态。
4. 客户 C 收到 FIN 后，发送 ACK 段给 S，进入 TIME_WAIT 状态，并等待 $2 \times MSL = 2 \times 800ms = 1600ms$ 后进入 CLOSED 状态。S 收到 ACK 后立即进入 CLOSED 状态。

对于客户 C：

• 从发送 FIN 到收到 S 的 ACK 耗时 $RTT/2 = 25ms$。
• 从收到 S 的 FIN 到发送 ACK 耗时 $RTT/2 = 25ms$。
• TIME_WAIT 状态持续 $2 \times MSL = 1600ms$。
• 总时间至少为 $25ms + 25ms + 1600ms = 1650ms$。

对于服务器 S：

• 从收到 C 的 FIN 到发送 ACK 耗时 $RTT/2 = 25ms$。
• 从发送 FIN 到收到 C 的 ACK 耗时 $RTT/2 = 25ms$。
• 总时间至少为 $25ms + 25ms = 50ms$。

因此，C 和 S 进入 CLOSED 状态所需的时间至少分别是 $1650ms$ 和 $50ms$。但题目中 S 的选项为 $75ms$，可能是考虑了额外的处理延迟，因此最接近的选项是 D。

正确答案：D

题目详解：

1. 建立 TCP 连接：需要三次握手，耗时 $1.5 \times RTT = 15 \text{ms}$。

2. 请求 news408.html：

   • H 发送 HTTP 请求报文，耗时 $0.5 \times RTT = 5 \text{ms}$（单向传输时间）。
   • S 发送 news408.html 文件，文件大小为 $1 \text{MSS}$，耗时 $0.5 \times RTT = 5 \text{ms}$（单向传输时间）。
   • 总耗时 $1 \times RTT = 10 \text{ms}$。

3. 请求图像文件：

   • H 解析 news408.html 后，发现需要加载图像文件，发送 HTTP 请求报文，耗时 $0.5 \times RTT = 5 \text{ms}$。
   • S 发送图像文件，文件大小为 $3 \text{MSS}$，由于 HTTP/1.1 是串行传输，需要分 3 个 TCP 段发送，每段耗时 $0.5 \times RTT = 5 \text{ms}$，总耗时 $1.5 \times RTT = 15 \text{ms}$。
   • 总耗时 $2 \times RTT = 20 \text{ms}$。

4. 总时间计算：

   • 建立连接：$15 \text{ms}$。
   • 请求 news408.html：$10 \text{ms}$。
   • 请求图像文件：$20 \text{ms}$。
   • 总计：$15 + 10 + 20 - 5 = 40 \text{ms}$（减去重叠的 $0.5 \times RTT$，因为请求图像文件的 HTTP 请求可以与 news408.html 的最后一个 ACK 重叠）。

正确答案：B

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

对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0] 中：当某结点保存在 SqBiTNode[i] 中时，若有左孩子，则其值保存在 SqBiTNode[2i+1]中；若有右孩子，则其值保存在 SqBiTNode[2i+2] 中；若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2] 中。

二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子树中的全部结点值。中序遍历二叉搜索树得到一个升序序列。

使用整型变量 val 记录中序遍历过程中已遍历结点的最大值，初值为一个负整数，对二叉树进行中序遍历。若当前遍历的结点值小于等于 val，则算法返回 false，否则，将 val 的值更新为当前结点的值。

2）算法实现

// val 存储中序遍历中访问到的最大值
// 返回值：当前子树是否为 BST
bool solve(SqBiTree *tree, int k, int *val) {
  if (k >= tree->ElemNum) {
    // 空结点
    return true;
  }
  // 判断左子树是否为 BST
  bool ret = solve(tree, 2*k+1, val);
  if (!ret) {
    return false;
  }
  int cur_val = tree->SqbiTNode[k];
  if (cur_val == -1) {
    // 空结点
    return true;
  }
  // 判断中序序列是否递增
  if (cur_val > *val) {
    *val = cur_val;
  } else {
    return false;
  }
  // 判断右子树是否为 BST
  ret = solve(tree, 2*k+2, val);
  if (!ret) {
    return false;
  }
  return true;
}

题目详解：
【答案 1】

定义含 10 个元素的数组 $A$，初始时元素值均为该数组类型能表示的最大数 $MAX$。

for M 中的每个元素 s
    if (s < A[9]) 丢弃 A[9]并将 s 按升序插入到 A 中；

当数据全部扫描完毕，数组 $A[0]$~$A[9]$保存的即是最小的 10 个数。

【答案 2】

定义含 10 个元素的大根堆 $H$，元素值均为该堆元素类型能表示的最大数 $MAX$。

for M 中的每个元素 s
    if (s < H 的堆顶元素)
        删除堆顶元素并将 s 插入到 H 中；

当数据全部扫描完毕，堆 $H$ 中保存的即是最小的 10 个数。

2)算法平均情况下的时间复杂度是0(n),空间复杂度是0(1)。

题目详解：
1）符号标志 $SF$ 表示运算结果的正负性，因此 $SF = F_{15}$。

对于加法运算 $A + B \rightarrow F$，若 $A$、$B$ 为负，且 $F$ 为正，则说明发生溢出；或者，若 $A$、$B$ 为正，且 $F$ 为负，也说明发生溢出。因此，加运算时，溢出标志 $OF = \overline{A_{15}} \cdot \overline{B_{15}} \cdot F_{15} + A_{15} \cdot B_{15} \cdot \overline{F_{15}}$。

对于减法运算 $A - B \rightarrow F$，若 $A$ 为负、$B$ 为正，且 $F$ 为正，则说明发生溢出；或者，若 $A$ 为正、$B$ 为负，且 $F$ 为负，也说明发生溢出。因此，减运算时，溢出标志 $OF = \overline{A_{15}} \cdot B_{15} \cdot F_{15} + A_{15} \cdot \overline{B_{15}} \cdot \overline{F_{15}}$。

2）因为在单总线结构中，每一时刻总线上只有一个数据有效，而 $ALU$ 有两个输入端和一个输出端。因此，当 $ALU$ 运算时，需要先用暂存器 $Y$ 缓存其中一个输入端的数据，再通过总线传送另一个输入端的数据。与此同时，$ALU$ 的输出端产生运算结果，但由于总线正被占用，因此需要暂存器 $Z$，以缓存 $ALU$ 的输出端数据。

3）由图可知，$rs$ 和 $rd$ 都是 4bit，因此 $GPRs$ 中最多有 $2^{4} = 16$ 个通用寄存器；$rs$ 和 $rd$ 来自指令寄存器 $IR$；$rd$ 表示寄存器编号，应连接地址译码器。

4）取指阶段需要根据程序计数器 $PC$ 取出主存中的指令，并将指令写入指令寄存器 $R$ 中。控制信号序列如下：

① $PC_{out}, MAR_{in}$ // 将指令的地址写入 $MAR$
② $Read$ // 读主存，并将读出的数据写入 $MDR$
③ $MDR_{out}, R_{in}$ // 将 $MDR$ 的内容写入指令寄存器 $R$

步骤①需要 1 个时钟周期，步骤②需要 5 个时钟周期，步骤③需要 1 个时钟周期，因此取指令阶段至少需要 7 个时钟周期。

5）图中控制信号由控制部件（$CU$）产生。指令寄存器 $IR$ 和标志寄存器 $FR$ 的输出信号会连到控制部件的输入端。

题目详解：
1）3 个字段的名称为柱面号（或磁道号）、磁头号（或盘面号）、扇区号。由于每个盘面有 20000 个磁道，因此该磁盘共有 20000 个柱面，柱面号字段至少占 $\lceil \log_{2}20000 \rceil = 15$ 位；由于该磁盘共有 4 个盘片，每个盘片有 2 个盘面，因此磁头号字段至少占 $\log_{2}(4 \times 2) = 3$ 位；由于每个磁道有 500 个扇区，因此扇区号字段至少占 $\lceil \log_{2}500 \rceil = 9$ 位。

2）一个扇区的访问时间由寻道时间、延迟时间、传输时间三部分组成。平均寻道时间为 5ms，平均延迟时间等于磁盘转半圈所需要的时间，平均传输时间等于一个扇区划过磁头下方所需要的时间。而该磁盘转一圈的时间为 $60 \times 10^{3}/7200 \approx 8.33$ ms，因此一个扇区的平均访问时间约为 $5 + 8.33/2 + 8.33/500 \approx 9.18$ ms。

3）磁盘控制器中的数据缓冲区每充满一次，DMA 控制器就需要发出一次总线请求，将这 64bit 数据通过总线传送到主存，因此，在一个扇区读写过程中，DMA 控制器向 CPU 发送了 $512B/64bit = 64$ 次总线请求。由于采用周期挪用 DMA 方式，因此当 CPU 和 DMA 控制器都需要访问主存时，DMA 控制器可以优先获得总线使用权。因为一旦磁盘开始读写，就必须按时完成数据传送，否则数据缓冲区中的数据会发生丢失。

题目详解：
1）在该文件系统中，目录项由文件名和索引结点号构成。由图 a 可知，stu 目录下有两个文件，分别是 course 和 doc。由图 b 可知，这两个文件分别对应索引结点号 2 和 10。因此，目录文件 stu 中两个目录项的内容是

2）由图 b 可知，文件 doc 和文件 course1 对应的索引结点号都是 10。说明 doc 和 course1 两个目录项共享同一个索引结点，本质上对应同一个文件。而文件 course1 存储在 30 号磁盘块，因此文件 doc 占用的磁盘块的块号 $x$ 为 30。

3）需要读 2 个磁盘块。先读 course1 的索引结点所在的磁盘块，再读 course1 的内容所在的磁盘块。目录文件 course 的内容已在内存中，即 course1、course2 对应的目录项已在内存中，根据 course1 对应的目录项可以知道其索引结点号，即可读入 course1 的索引结点所在的磁盘块；根据 course1 的索引结点可知该文件存储在 30 号磁盘块，因此可再读入 course1 的内容所在的磁盘块。

4）存取 course2 需要使用索引结点的一级和二级间接地址项。6MB 大小的文件需要占用 $6MB/4KB=1536$ 个磁盘块。直接地址项可以记录 10 个磁盘块号，一级间接地址块可以记录 $4KB/4B=1024$ 个磁盘块号，二级间接地址块可以记录 $1024 \times 1024$ 个磁盘块号，而 $10 + 1024 < 1536 < 10 + 1024 + 1024 \times 1024$。因此，6MB 大小的文件，需要使用一级间接地址项和二级间接地址项（拓展：若文件的总大小超出 $10 + 1024 + 1024 \times 1024$ 块，则还需使用三级间接地址项）。

题目详解：
进程 T1 要依次执行 A、E、F。进程 T2 要执行 B、C、D。由图可知，T2 执行 C 必须在 T1 执行完 A 之后；T1 执行 E 必须在 T2 执行完 C 之后。因此，有两对同步关系。信号量的定义和同步关系的描述如下：

semaphore AC = 0;
semaphore CE = 0;

T1() {
    A;
    signal(AC);
    wait(CE);
    E;
    F;
}

T2() {
    B;
    wait(AC);
    C;
    signal(CE);
    D;
}

题目详解：
1）设备 1 选择 100 BaseT 以太网交换机，设备 2 选择 100 BaseT 集线器。因为物理层设备既不能隔离冲突域也不能隔离广播域，链路层设备可以隔离冲突域但不能隔离广播域。

2）假设 H2 与 H3 之间的最远距离是 $D$，根据 CSMA/CD 协议的限制条件：

最短帧长 $= 总线传播时延 \times 数据传输速率 \times 2$