2012年408真题

题目详解：
该题目考察的是递归算法的时间复杂度分析。给定的算法是一个计算阶乘的递归函数，其定义如下：

int fact(int n) {
if (n <= 1) return 1;
return n * fact(n - 1);
}

1. 递归调用次数分析：

   • 每次递归调用时，参数 $n$ 减 1，直到 $n \leq 1$ 时停止递归。
   • 因此，递归的深度为 $n$ 次（从 $n$ 递减到 1）。

2. 时间复杂度分析：

   • 每次递归调用只包含一次乘法操作和一次递归调用，因此每次调用的时间复杂度为 $O(1)$。
   • 总的时间复杂度是递归调用次数乘以每次调用的时间复杂度，即 $n \times O(1) = O(n)$。

3. 排除其他选项：

   • A. $O(\log_2 n)$：对数复杂度通常出现在分治或二分搜索中，不适用于线性递归。
   • C. $O(n \log_2 n)$：通常出现在分治算法（如快速排序或归并排序）中，不适用于线性递归。
   • D. $O(n^2)$：平方复杂度通常出现在嵌套循环中，递归深度为 $n$ 且每次操作 $O(1)$ 时不会达到。

综上所述，该算法的时间复杂度为 $O(n)$。

正确答案：B

题目详解：
将中缀表达式转换为后缀表达式的过程中，使用栈来暂存操作符。我们需要跟踪栈中操作符的最大数量。具体步骤如下：

1. 初始化空栈，开始扫描中缀表达式 $a + b - a * ( ( c + d ) / e - f ) + g$。

2. 遇到操作数 $a$，直接输出。栈：$[\ ]$，输出：$a$。

3. 遇到操作符 $+$，压栈。栈：$[ + ]$，输出：$a$。

4. 遇到操作数 $b$，直接输出。栈：$[ + ]$，输出：$a\ b$。

5. 遇到操作符 $-$，$+$ 的优先级不低于 $-$，弹出 $+$ 并输出，压入 $-$。栈：$[ - ]$，输出：$a\ b +$。

6. 遇到操作数 $a$，直接输出。栈：$[ - ]$，输出：$a\ b + a$。

7. 遇到操作符 $*$，$-$ 的优先级低于 $*$，压入 $*$。栈：$[ - * ]$，输出：$a\ b + a$。

8. 遇到 $($，直接压栈。栈：$[ - * ( ]$，输出：$a\ b + a$。

9. 遇到 $($，直接压栈。栈：$[ - * ( ( ]$，输出：$a\ b + a$。

10. 遇到操作数 $c$，直接输出。栈：$[ - * ( ( ]$，输出：$a\ b + a\ c$。

11. 遇到操作符 $+$，压栈。栈：$[ - * ( ( + ]$，输出：$a\ b + a\ c$。

12. 遇到操作数 $d$，直接输出。栈：$[ - * ( ( + ]$，输出：$a\ b + a\ c\ d$。

13. 遇到 $)$，弹出 $+$ 并输出，弹出 $($。栈：$[ - * ( ]$，输出：$a\ b + a\ c\ d +$。

14. 遇到操作符 $/$，压栈。栈：$[ - * ( / ]$，输出：$a\ b + a\ c\ d +$。

15. 遇到操作数 $e$，直接输出。栈：$[ - * ( / ]$，输出：$a\ b + a\ c\ d + e$。

16. 遇到 $)$，弹出 $/$ 并输出，弹出 $($。栈：$[ - * ]$，输出：$a\ b + a\ c\ d + e /$。

17. 遇到操作符 $-$，$*$ 的优先级不低于 $-$，弹出 $*$ 并输出，压入 $-$。栈：$[ - - ]$，输出：$a\ b + a\ c\ d + e / *$。

18. 遇到操作数 $f$，直接输出。栈：$[ - - ]$，输出：$a\ b + a\ c\ d + e / * f$。

19. 遇到 $)$，弹出 $-$ 并输出，弹出 $-$。栈：$[\ ]$，输出：$a\ b + a\ c\ d + e / * f -$。

20. 遇到操作符 $+$，压栈。栈：$[ + ]$，输出：$a\ b + a\ c\ d + e / * f - -$。

21. 遇到操作数 $g$，直接输出。栈：$[ + ]$，输出：$a\ b + a\ c\ d + e / * f - - g$。

22. 表达式结束，弹出 $+$ 并输出。栈：$[\ ]$，输出：$a\ b + a\ c\ d + e / * f - - g +$。

在整个过程中，栈中操作符的最大数量出现在步骤 12，栈中有 $[ - * ( ( + ]$ 共 5 个操作符。

正确答案：A

题目详解：
前序遍历的顺序是：根节点 → 左子树 → 右子树。后序遍历的顺序是：左子树 → 右子树 → 根节点。

根据题目给出的前序遍历序列 $a, e, b, d, c$，可以确定 $a$ 是根节点。后序遍历序列 $b, c, d, e, a$ 也验证了这一点，因为 $a$ 是最后一个节点。

接下来，从前序遍历序列中，根节点 $a$ 的下一个节点是 $e$，说明 $e$ 是 $a$ 的左孩子或右孩子。从后序遍历序列中，$e$ 位于 $a$ 之前，且 $e$ 之后是 $d$ 和 $c$，说明 $e$ 是 $a$ 的唯一孩子（因为如果 $a$ 有多个孩子，后序遍历中 $e$ 之后应该还有其他节点属于 $a$ 的子树）。

进一步分析子树的结构：

1. 前序遍历中 $e$ 之后的序列是 $b, d, c$，说明 $e$ 的子树包含 $b$、$d$ 和 $c$。
2. 后序遍历中 $e$ 之前的序列是 $b, c, d$，说明 $e$ 的子树以 $b$ 开始，以 $d$ 和 $c$ 结束。

结合前序和后序序列，可以推断 $e$ 是 $a$ 的唯一孩子，且 $e$ 的子树结构为：$b$ 是 $e$ 的左孩子，$d$ 是 $e$ 的右孩子，$c$ 是 $d$ 的右孩子。

因此，根节点 $a$ 的孩子结点只有 $e$。

正确答案：A

题目详解：
所有非叶结点的平衡因子均为 1，即平衡二叉树满足平衡的最少结点情况，如下图所示。

对于高度为 N、左右子树的高度分别为 N-1 和 N-2、所有非叶结点的平衡因子均为 1 的平衡二叉树，总结点数的公式为：$C_{N} = C_{N-1} + C_{N-2} + 1$, C1=1C_1 = 1, $C_2 = 2$,$C_3 = 2 + 1 + 1 = 4$，可推出$C_6 = 20$。

正确答案：B

题目详解：
对于一个有 $n$ 个结点和 $e$ 条边的有向图，使用邻接表存储时，广度优先遍历（BFS）的时间复杂度分析如下：

1. 初始化阶段：需要访问所有结点以标记初始状态，时间复杂度为 $O(n)$。

2. 遍历阶段：对于每个结点的邻接表，需要遍历其所有出边。由于邻接表的总边数为 $e$，因此遍历所有边的时间复杂度为 $O(e)$。

3. 总体时间复杂度：由于初始化和遍历阶段是顺序执行的，总时间复杂度为两者之和，即 $O(n + e)$。

因此，正确答案是 $O(n + e)$。

正确答案：C

题目详解：
给定一个有向图，其邻接矩阵的主对角线以下的元素均为零。邻接矩阵的主对角线以下的元素对应的是顶点 $i$ 到顶点 $j$ 的边，其中 $i > j$。如果这些元素均为零，表示图中不存在从编号较大的顶点指向编号较小的顶点的边，即图中不存在后向边。

这种结构类似于有向无环图（DAG）的一种特例，其中顶点的编号满足拓扑序的要求（即所有边都是从编号小的顶点指向编号大的顶点）。因此，该图一定是有向无环图，必然存在拓扑序列。

然而，拓扑序列的唯一性取决于图中是否存在多组不互相依赖的顶点。例如，如果图中存在多个入度为零的顶点，或者存在多个顶点的顺序可以交换而不违反拓扑序的条件，那么拓扑序列就不唯一。因此，拓扑序列可能存在，但不一定唯一。

综上所述，正确的结论是：拓扑序列存在，可能不唯一。

正确答案：C

题目详解：
对如下有向图带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余最短路径的目标顶点依次是（ ）。

从 a 到各顶点的最短路径的求解过程：

后续目标顶点依次为 f, d, e。

【排除法】对于 A，若下一个顶点为 d，路径 a,b,d 的长度5，而 a,b,c,f 的长度仅为4，显然错误。同理可以排除B。将 f 加入集合 S 后，采用上述的方法也可以排除 D。

正确答案：C

题目详解：
关于最小生成树(MST)的叙述逐一分析如下：

I. 正确。最小生成树的代价（即所有边权值之和）是唯一的。虽然图可能存在多个不同的最小生成树（当存在权值相同的边时），但它们的总权值一定相同。

II. 错误。只有当权值最小的边是图中唯一的权值最小边时，它才会出现在所有最小生成树中。如果存在多条权值相同的最小边，某些最小生成树可能不包含其中某些最小边。

III. 错误。普里姆(Prim)算法从不同顶点开始得到的最小生成树可能不同，尤其是在图中存在多条权值相同的边时，算法的选择顺序会导致生成不同的树。

IV. 错误。普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树可能相同，也可能不同，具体取决于图的边权值分布。两种算法的贪心策略不同，但最终生成的都是总权值最小的树。

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

正确答案：A

题目详解：
本题考察 B 树的 删除操作。对于上图所示的 3 阶 B 树，被删关键字 78 所在结点在删除前的关键字个数 = 1 = ⌈3/2⌉-1，且其左兄弟结点的关键字个数 = 2 ≥ ⌈3/2⌉，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。

题目详解：
在内部排序算法中，每一趟排序能够至少确定一个元素的最终位置是一个重要的性质。我们逐一分析各个排序方法：

1. 简单选择排序（I）：每一趟从待排序序列中选择最小的元素，放到已排序序列的末尾。因此，每一趟排序都能确定一个元素的最终位置。

2. 堆排序（IV）：堆排序的每一趟会从堆顶取出最大（或最小）元素，放到已排序序列的末尾。因此，每一趟排序也能确定一个元素的最终位置。

3. 快速排序（III）：每一趟排序会选择一个基准元素（pivot），将其放到最终位置，并使得左边的元素都小于等于它，右边的元素都大于等于它。因此，每一趟排序也能确定一个元素的最终位置。

4. 希尔排序（II）：希尔排序是插入排序的改进版本，每一趟排序会将序列分成若干子序列进行插入排序，但并不能保证每一趟排序都能确定一个元素的最终位置。

5. 二路归并排序（V）：归并排序的核心是分治和合并，每一趟排序只是将两个有序子序列合并为一个有序序列，并不能确定任何元素的最终位置。

综上所述，简单选择排序（I）、**堆排序（IV）和快速排序（III）**每一趟排序都能至少确定一个元素的最终位置。

正确答案：A

题目详解：
折半插入排序和直接插入排序的主要区别在于查找插入位置的方式不同，这会影响元素之间的比较次数，但不会影响其他方面：

1. 排序的总趟数（A）：两种算法都需要进行 $n-1$ 趟插入（$n$ 为序列长度），因此总趟数相同。

2. 元素的移动次数（B）：元素的移动次数取决于初始序列的排列情况，与查找插入位置的方式无关，因此两种算法的移动次数相同。

3. 使用辅助空间的数量（C）：两种算法都只需要常数级别的辅助空间（如临时变量），空间复杂度均为 $O(1)$，因此辅助空间数量相同。

4. 元素之间的比较次数（D）：

   • 直接插入排序使用顺序查找，平均比较次数为 $O(n^2)$。
   • 折半插入排序使用二分查找，平均比较次数为 $O(n \log n)$。
     因此，比较次数不同。

正确答案：D

题目详解：
根据题目描述，基准程序A 的总运行时间为 $100$ 秒，其中：

• CPU 时间为 $90$ 秒
• I/O 时间为 $100 - 90 = 10$ 秒

当 CPU 速度提高 $50\%$ 时，新的 CPU 时间可以通过以下公式计算：
$\text{新 CPU 时间} = \frac{\text{原 CPU 时间}}{1 + \text{速度提升比例}} = \frac{90}{1 + 0.5} = \frac{90}{1.5} = 60 \text{秒}$
I/O 速度不变，因此 I/O 时间仍为 $10$ 秒。

程序的总运行时间为新的 CPU 时间加上 I/O 时间：
$\text{总运行时间} = \text{新 CPU 时间} + \text{I/O 时间} = 60 + 10 = 70 \text{秒}$

正确答案：D

题目详解：
在C语言中，unsigned short和unsigned int分别是无符号的16位和32位整数类型。根据题目描述，unsigned short占用16位，unsigned int占用32位。

1. 初始赋值：

   • unsigned short x = 65530; 表示将x赋值为65530。
   • 65530的二进制表示为 $1111111111111010$（16位），对应的十六进制表示为 $FFFA$。

2. 类型转换：

   • 当将unsigned short类型的x赋值给unsigned int类型的y时，会发生零扩展（zero extension），因为unsigned int的位数更多。
   • 零扩展意味着高位补0，因此16位的 $FFFA$ 扩展为32位的 $0000FFFA$。

3. 机器数表示：

   • 题目要求的是y的机器数，即y在内存中的表示形式。
   • 由于y是32位无符号整数，其值为 $0000FFFA$，对应的十六进制表示即为 $0000FFFAH$。

因此，正确答案是选项B。

正确答案：B

题目详解：
IEEE 754 单精度浮点数（float 类型）的格式由三部分组成：符号位 $S$ （1 位）、指数部分 $E$ （8 位）和尾数部分 $M$ （23 位）。其表示的最大正整数需要满足以下条件：

1. 符号位 $S = 0$ ，表示正数。
2. 指数部分 $E$ 的最大值为 $254$ （因为 $E = 255$ 用于表示无穷大或 NaN）。
3. 尾数部分 $M$ 的所有位均为 $1$ ，即 $M = 1.111\ldots1_2$ （小数点前隐含的 $1$ 加上 23 个 $1$ ）。

浮点数的值计算公式为：

$$(-1)^S \times (1.M)_2 \times 2^{E-127}$$

对于最大正整数：

• $S = 0$ ，所以 $(-1)^0 = 1$ 。
• $E = 254$ ，因此指数部分为 $2^{254-127} = 2^{127}$ 。
• 尾数部分 $1.M$ 的值为 $1 + \sum_{i=1}^{23} 2^{-i} = 2 - 2^{-23}$ 。

因此，最大正整数的值为：

$$(2 - 2^{-23}) \times 2^{127} = 2^{128} - 2^{104}$$

正确答案是 D。

题目详解：
根据题目描述，结构体 record 的内存布局如下：

1. 成员 a（int 型，32 位，4 字节）：

   • 存储值 273，其十六进制表示为 $0x00000111$。
   • 小端方式存储，低字节在前，因此在内存中的存储顺序为 $0x11$、$0x01$、$0x00$、$0x00$。
   • 地址范围：$0xC008$ 到 $0xC00B$。

2. 成员 b（char 型，8 位，1 字节）：

   • 由于数据按边界对齐存储，char 可以紧跟在 int 后面。
   • 地址：$0xC00C$。

3. 成员 c（short 型，16 位，2 字节）：

   • 需要对齐到 2 字节边界，因此 c 的起始地址必须是偶数。
   • 下一个可用地址是 $0xC00D$，但 $0xC00D$ 是奇数，因此填充 1 字节，从 $0xC00E$ 开始存储。
   • 地址范围：$0xC00E$ 到 $0xC00F$。

内存布局总结：

• $0xC008$：$0x11$（a 的第一个字节）
• $0xC009$：$0x01$
• $0xC00A$：$0x00$
• $0xC00B$：$0x00$
• $0xC00C$：b（未赋值，内容不确定）
• $0xC00D$：填充字节（内容不确定）
• $0xC00E$：c 的起始地址

因此：

• 地址 $0xC008$ 的内容是 $0x11$。
• record.c 的地址是 $0xC00E$。

正确答案：D

题目详解：
闪存（Flash Memory）是一种非易失性半导体存储器，其存储元由 $MOS$ 管组成（选项B正确）。闪存的特点是掉电后信息不会丢失（选项C正确），因此广泛应用于存储设备如U盘、SSD等。闪存采用随机访问方式，可以替代计算机的外部存储器（选项D正确）。

关于选项A，闪存的信息可读可写，但读、写速度并不一样快。闪存的写入速度通常比读取速度慢，因为写入时需要先擦除再编程，而读取操作则直接获取数据。因此，选项A的叙述是错误的。

正确答案：A

题目详解：

注意：不同的教材中，组相联映射的讲解不同。主流的为蒋本珊教材中的方式与唐朔飞教材中的方式。

解法一：蒋本珊教材中的方式

地址映射采用 2 路组相联，则主存地址为 0~1、4~5、8~9 可映射到第 0 组 Cache 中，主存地址为 2~3、6~7 可映射到第 1 组 Cache 中。Cache 置换过程如下表所示。

注：“_” 表示当前访问块，“*” 表示本次访问命中。

注意：在不同的《计算机组成原理》教材中，关于组相联映射的介绍并不相同。通常采用唐朔飞教材中的方式，但本题中采用的是蒋本珊教材中的方式。可以推断两次命题的老师应该不是同一位老师，这也给考生答题带来了困扰。

正确答案：C

解法二：唐朔飞教材中的方式

• Cache 有 4 个行，采用 2 路组相联映射，因此分为 2 组（每组 2 行）。
• 主存地址按字编址，块大小为 1 个字，因此主存地址低 1 位表示组号（因为 2 组，组号占 1 位），剩余高位为主存字块标记。
• 主存地址序列：0, 4, 8, 2, 0, 6, 8, 6, 4, 8（均为十进制）。
• 将地址转换为二进制（假设地址位宽足够，这里取低 4 位表示）：
  • 0: 0000B → 组号 0
  • 4: 0100B → 组号 0
  • 8: 1000B → 组号 0
  • 2: 0010B → 组号 0
  • 0: 0000B → 组号 0
  • 6: 0110B → 组号 0
  • 8: 1000B → 组号 0
  • 6: 0110B → 组号 0
  • 4: 0100B → 组号 0
  • 8: 1000B → 组号 0

所有地址均映射到组 0（因为组号由最低位决定，且这些地址的最低二进制位均为 0）。组 0 有 2 行，采用全相联映射，替换策略为 LRU。

仅第 8 次访问（地址 6）命中，因此命中次数为 1。

正确答案：A

题目详解：
在微程序控制方式中，操作控制字段采用字段直接编码法时，每个互斥类的微命令需要独立的字段进行编码。每个互斥类的字段位数取决于该类中微命令的数量。具体计算方法如下：

对于一个包含 $n$ 个微命令的互斥类，需要的编码位数为 $\lceil \log_2 n \rceil$。这是因为 $\lceil \log_2 n \rceil$ 位可以表示 $2^{\lceil \log_2 n \rceil}$ 种状态，足以覆盖 $n$ 个微命令（包括一个无效状态）。

根据题目给出的互斥类及其微命令数量：

1. 包含 7 个微命令的类：$\lceil \log_2 7 \rceil = 3$ 位
2. 包含 3 个微命令的类：$\lceil \log_2 3 \rceil = 2$ 位
3. 包含 12 个微命令的类：$\lceil \log_2 12 \rceil = 4$ 位
4. 包含 5 个微命令的类：$\lceil \log_2 5 \rceil = 3$ 位
5. 包含 6 个微命令的类：$\lceil \log_2 6 \rceil = 3$ 位

将各互斥类所需的位数相加：
$3 + 2 + 4 + 3 + 3 = 15$ 位

因此，操作控制字段至少需要 15 位。

正确答案：C

题目详解：
首先，我们需要理解题目中的关键信息：

1. 时钟频率为 $100MHz$，因此一个时钟周期的时间为：

   $$T = \frac{1}{100 \times 10^6} = 10ns$$

2. 总线宽度为 $32$ 位，即每次可以传输 $32$ 位数据。

3. 地址/数据线复用，意味着传输地址和数据共享同一组线，每传输一个地址或数据占用一个时钟周期。

4. 突发（猝发）传输方式允许在一次总线事务中连续传输多个数据，而无需重复发送地址。

题目要求传输 $128$ 位数据。由于总线宽度为 $32$ 位，每次可以传输 $32$ 位数据，因此需要传输的次数为：

$$\frac{128}{32} = 4 \text{次}$$

在突发传输方式下，一次“主存写”总线事务通常包括以下步骤：

1. 发送地址：占用 $1$ 个时钟周期。
2. 传输数据：占用 $4$ 个时钟周期（每次传输 $32$ 位数据，共传输 $4$ 次）。

因此，总时钟周期数为：

$$1 (\text{地址}) + 4 (\text{数据}) = 5 \text{个时钟周期}$$

总时间为：

$$5 \times 10ns = 50ns$$

正确答案是：C. 50ns

题目详解：
USB（Universal Serial Bus，通用串行总线）是一种广泛使用的总线标准，其特性包括：

1. 即插即用和热拔插（选项A）：USB支持外设的即插即用（Plug and Play）和热拔插（Hot Swapping），用户可以在不关闭电源的情况下连接或断开设备。

2. 级联方式连接多台外设（选项B）：USB可以通过集线器（Hub）进行级联，从而连接多台外设，理论上最多可支持127台设备。

3. 通信总线（选项C）：USB是一种通信总线，用于连接计算机与各种外设（如键盘、鼠标、打印机等），实现数据传输。

4. 数据传输方式（选项D错误）：USB是串行总线，每次传输1位数据，而不是2位。虽然USB的数据传输率较高（如USB 3.0可达5Gbps），但这是通过提高时钟频率和编码效率实现的，而非同时传输多位数据。

正确答案：D

题目详解：
在I/O总线的数据线上传输的信息主要包括以下三类：

1. I/O接口中的命令字：这是CPU发送给I/O设备的控制信息，用于指示设备执行特定操作，例如启动、停止或配置设备。命令字通过数据线传输到I/O接口。

2. I/O接口中的状态字：这是I/O设备向CPU反馈的当前状态信息，例如设备是否忙碌、是否就绪或是否发生错误。状态字通过数据线传输给CPU。

3. 中断类型号：当I/O设备需要CPU处理时，会触发中断。中断类型号用于标识中断源，以便CPU调用相应的中断服务程序。中断类型号也通过数据线传输。

因此，I/O总线的数据线上传输的信息包括：

• I. I/O接口中的命令字
• II. I/O接口中的状态字
• III. 中断类型号

正确答案：D

题目详解：
在响应外部中断的过程中，中断隐指令（由硬件自动执行的操作）主要完成以下关键步骤：

1. 保护断点：将当前程序计数器 $PC$ 的值（即下一条指令的地址）压入堆栈，确保中断返回后能继续执行原程序。

2. 关中断（I）：硬件自动关闭中断允许标志，禁止其他中断请求，避免中断嵌套，保证当前中断处理的原子性。这是中断隐指令的核心操作之一。

3. 形成中断服务程序入口地址并送 $PC$（III）：硬件通过中断向量表或固定地址机制，找到对应中断服务程序的入口地址，并加载到 $PC$ 中，从而跳转到中断服务程序执行。

需要注意的是：

• 保存通用寄存器的内容（II）是由中断服务程序（软件）完成的，而非中断隐指令（硬件）的操作。中断服务程序开始后会手动保存现场（包括通用寄存器），退出前再恢复。

因此，中断隐指令直接完成的操作是 I 和 III。

正确答案：B

题目详解：
在计算机系统中，用户态（User Mode）和内核态（Kernel Mode）是两种不同的执行权限级别。用户态下运行的代码受到限制，不能直接访问硬件或执行特权指令。以下是各选项的分析：

• A. 系统调用：系统调用是用户态程序请求内核服务的接口。用户态程序通过 $\text{int 0x80}$ 或 $\text{syscall}$ 等指令触发系统调用，但实际的系统调用处理是在内核态完成的。尽管如此，系统调用的触发是在用户态发生的。

• B. 外部中断：外部中断由硬件设备触发（如键盘输入、磁盘I/O完成），中断信号会被CPU捕获，无论当前处于用户态还是内核态。中断的发生是异步的，与CPU状态无关，但其处理需要切换到内核态。

• C. 进程切换：进程切换涉及保存当前进程的上下文（如寄存器、程序计数器）并恢复目标进程的上下文，这需要直接操作CPU和内存管理的特权指令（如修改页表寄存器 $\text{CR3}$），因此必须在内核态完成。用户态无法直接触发或执行进程切换。

• D. 缺页：缺页异常（Page Fault）在用户态程序访问未映射的虚拟内存时触发，异常的发生是在用户态，但其处理由内核完成。

综上，进程切换是唯一一个完全不可能在用户态发生的事件。

正确答案：C

题目详解：
在计算机系统中，中断处理和子程序调用都需要保存现场信息，但两者保存的内容有所不同：

1. 程序计数器（PC）：无论是中断处理还是子程序调用，都需要保存 $PC$ 的值，以便后续能正确返回到原程序执行点。

2. 程序状态字寄存器（PSW）：中断处理会保存 $PSW$ 的状态信息（如标志位、中断屏蔽位等），而子程序调用通常不需要保存 $PSW$，除非子程序内部修改了状态位。

3. 通用数据寄存器：子程序调用通常由调用者负责保存需要保护的通用数据寄存器（如 $R0 \sim R7$），中断处理则会自动保存所有通用数据寄存器。

4. 通用地址寄存器：子程序调用不需要保存通用地址寄存器（如基址寄存器、变址寄存器等），因为这些寄存器通常由调用者管理。而中断处理会保存所有通用地址寄存器，以确保中断返回后地址环境不变。

题目问的是“中断处理一定会保存而子程序调用不需要保存”的内容，因此正确答案是通用地址寄存器。

正确答案：D

题目详解：
虚拟存储器是计算机系统内存管理的一种技术，它允许程序像使用内存一样使用外存（如硬盘）。以下是各选项的详细分析：

1. 选项A：虚拟存储只能基于连续分配技术
   这是错误的。虚拟存储器通常基于非连续分配技术（如分页或分段），因为连续分配会导致内存碎片问题，难以实现高效的虚拟内存管理。

2. 选项B：虚拟存储只能基于非连续分配技术
   这是正确的。虚拟存储器通常采用非连续分配技术，例如分页（$Paging$）或分段（$Segmentation$），以更灵活地管理内存和外存之间的数据交换。

3. 选项D：虚拟存储容量只受内存容量的限制
   这是错误的。虚拟存储器的容量不仅受内存容量限制，还受外存（如硬盘）容量和地址总线位数的限制。例如，32位系统的虚拟地址空间上限为 $2^{32} = 4\ GB$。

4. 选项C：虚拟存储容量只受外存容量的限制
   这也是错误的。虽然外存容量是虚拟存储器的重要限制因素之一，但虚拟存储器的最大容量还受系统地址总线位数和内存管理单元（$MMU$）设计的限制。

综上所述，虚拟存储器必须基于非连续分配技术（如分页或分段）实现，因此正确答案是 B。

正确答案：B

题目详解：
操作系统的 I/O 子系统的四个层次按照从高层到低层的合理顺序排列如下：

1. 用户级I/O 软件：这是最上层，负责与用户程序交互，提供友好的 I/O 接口（如库函数 $\text{printf()}$ 或 $\text{scanf()}$）。

2. 设备无关软件：这一层提供统一的接口，屏蔽底层设备的差异，实现设备独立性。例如，文件系统操作（如 $\text{open()}$ 或 $\text{read()}$）在此层处理。

3. 设备驱动程序：直接与硬件设备交互，负责将设备无关的请求转换为设备特定的操作（如控制磁盘控制器或网卡）。

4. 中断处理程序：最底层，负责处理硬件中断信号（如设备完成 I/O 操作后触发的中断），通知上层进一步处理。

因此，正确的层次顺序为：
$\text{用户级I/O 软件} \rightarrow \text{设备无关软件} \rightarrow \text{设备驱动程序} \rightarrow \text{中断处理程序}$。

正确答案：A

题目详解：
首先求得各进程的需求矩阵 Need 与可利用资源矢量 Available：

比较 Need 和 Available 可以发现，初始时进程 P1P_1 与 P3P_3 可满足需求，排除 A、C。尝试给 P1P_1 分配资源，则 P1P_1 完成后 Available 将变为 (6,3,6)，无法满足 P0P_0 的需求，排除 B。尝试给 P3P_3 分配资源，则 P3P_3 完成后 Available 将变为 (4,3,7)，该向量能满足其他所有进程的需求。所以，以 P3P_3 开头的所有序列都是安全序列。

正确答案：D

题目详解：
在用户进程通过 $read$ 系统调用读取磁盘文件数据的过程中，以下分析各选项的正确性：

I. 若该文件的数据不在内存中，则该进程进入睡眠等待状态。
这是正确的。当文件数据不在内存（即未缓存）时，操作系统会触发缺页中断，将数据从磁盘加载到内存。在此期间，进程会被阻塞（进入睡眠等待状态），直到数据准备好。

II. 请求 $read$ 系统调用会导致CPU 从用户态切换到核心态。
这是正确的。系统调用是用户态程序请求操作系统服务的接口，执行 $read$ 时会通过软中断（如 $int 0x80$ 或 $syscall$ 指令）触发从用户态到核心态的切换。

III. $read$ 系统调用的参数应包含文件的名称。
这是错误的。$read$ 系统调用的参数是文件描述符 $fd$、缓冲区地址 $buf$ 和读取字节数 $count$，而文件名称是在打开文件时通过 $open$ 系统调用指定的。

综上，仅I、II正确，对应选项A。

正确答案：A

题目详解：
在多道批处理系统中，作业可以交替使用 CPU 和 I/O 资源以提高系统利用率。我们需要分析 P₁ 和 P₂ 的执行顺序，找到最短完成时间。

1. 时间线分析：

   • $0 \text{ms}$：P₁ 到达并开始计算（60ms）。
   • $5 \text{ms}$：P₂ 到达，但由于 P₁ 正在计算，P₂ 需要等待。
   • $60 \text{ms}$：P₁ 完成计算，开始 I/O 操作（80ms）。此时 P₂ 可以开始计算（120ms）。
   • $140 \text{ms}$：P₁ 完成 I/O 操作，开始计算（20ms）。此时 P₂ 的计算已经执行了 $140 - 60 = 80 \text{ms}$，还剩下 $120 - 80 = 40 \text{ms}$ 的计算。
   • $160 \text{ms}$：P₁ 完成计算，整个 P₁ 完成。此时 P₂ 的计算还剩下 $40 - (160 - 140) = 20 \text{ms}$。
   • $180 \text{ms}$：P₂ 完成剩余计算，开始 I/O 操作（40ms）。
   • $220 \text{ms}$：P₂ 完成 I/O 操作，开始最后计算（40ms）。
   • $260 \text{ms}$：P₂ 完成最后计算，整个 P₂ 完成。

2. 关键时间点：

   • P₁ 的计算和 I/O 操作与其他作业重叠，减少了总时间。
   • P₂ 的计算和 I/O 操作在 P₁ 完成后继续执行。

3. 最短完成时间：

   • 两个作业的总完成时间为 $260 \text{ms}$。

正确答案：B

题目详解：
在单处理器多进程系统中，处理机调度的时机与进程状态变化密切相关。我们逐一分析各选项：

A. 进程结束时，该进程会释放CPU资源，此时调度程序可以立即选择另一个就绪态进程运行。因此该选项描述正确。

B. 创建新进程后，该进程可能进入就绪队列，此时调度程序需要决定是继续运行当前进程还是切换到新创建的进程。因此该选项描述正确。

C. 进程处于临界区时，虽然该进程正在访问共享资源，但并不会阻止调度发生。调度可以在任何时间发生，包括进程处于临界区时。因此该选项描述错误。

D. 系统调用完成并返回用户态时，是一个典型的调度时机。此时操作系统可能根据调度算法决定是否切换到其他进程。因此该选项描述正确。

临界区（critical section）的实现通常通过同步原语（如信号量）保证互斥，但不会影响处理机调度的发生。调度可能在任何时候发生，包括进程处于 $\text{临界区}$ 时。

正确答案：C

题目详解：
进程和线程是操作系统中的重要概念，它们的区别和联系如下：

1. 进程是资源分配的基本单位：无论系统是否支持线程，进程始终是操作系统进行资源（如内存、文件、CPU时间等）分配的基本单位。因此，选项A是正确的。

2. 线程是调度的基本单位：在支持线程的系统中，线程是CPU调度的基本单位，而进程仍然是资源分配的基本单位。因此，选项B的说法是错误的，因为线程不是资源分配的基本单位。

3. 线程切换的依赖：系统级线程（内核级线程）的切换需要内核的支持，而用户级线程的切换不需要内核介入，完全在用户空间完成。因此，选项C的说法是错误的。

4. 线程共享地址空间：同一进程中的各个线程共享相同的地址空间，但它们拥有各自的栈和寄存器等私有数据。因此，选项D的说法是错误的，因为线程不拥有各自不同的地址空间。

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

正确答案：A

题目详解：

• A. 重排I/O 请求次序：通过重新调度I/O请求顺序（如电梯算法），可以减少磁头寻道时间，从而提升I/O性能。
• B. 在一个磁盘上设置多个分区：分区主要用于逻辑管理数据（如隔离系统文件和用户数据），但并不会直接优化磁盘的物理访问性能，甚至可能因数据分散增加寻道时间。
• C. 预读和滞后写：预读（提前加载数据到缓存）减少后续读延迟，滞后写（合并写操作）降低磁盘写入频率，两者均能显著提升I/O性能。
• D. 优化文件物理块的分布：将相关文件块连续存储或就近放置，可减少磁头移动和旋转延迟，改善I/O效率。

因此，B选项不能直接改善磁盘I/O性能，是本题答案。

正确答案：B

题目详解：
在TCP/IP体系结构中，ICMP（Internet Control Message Protocol，互联网控制报文协议）是网络层的一个组成部分，主要用于在IP主机、路由器之间传递控制消息，例如网络通不通、主机是否可达等。ICMP报文是封装在 $IP$ 数据报中传输的，因此直接为ICMP提供服务的协议是 $IP$ 协议。

其他选项分析：

• $PPP$（Point-to-Point Protocol）是数据链路层协议，主要用于点对点通信，不直接为ICMP提供服务。
• $UDP$（User Datagram Protocol）和 $TCP$（Transmission Control Protocol）都是传输层协议，主要用于端到端的通信，也不直接为ICMP提供服务。

正确答案：B

题目详解：
在物理层接口特性中，有四个主要特性，分别是：

1. 机械特性：定义物理连接器的形状、尺寸、引脚数目和排列方式等。例如，RS-232接口的DB-9连接器。

2. 电气特性：规定传输过程中信号的电平、阻抗、速率等电气参数。例如，逻辑1和逻辑0的电压范围。

3. 功能特性：描述各条信号线的功能或用途。例如，数据线、控制线、地线等。

4. 过程特性：定义完成每种功能的事件发生的顺序，即时序关系。例如，通信双方的握手协议、数据传输的步骤等。

题目中问的是“描述完成每种功能的事件发生顺序”，这对应的是 过程特性。

正确答案：C

题目详解：
以太网的MAC（媒体访问控制）协议工作在OSI模型的 数据链路层 ，主要负责帧的封装、寻址和错误检测。在以太网中，MAC协议提供的是 无连接不可靠服务 ，具体表现为：

1. 无连接：通信双方在数据传输前不需要建立连接，MAC帧直接通过物理介质发送，没有握手过程。

2. 不可靠：MAC协议不提供确认机制（ACK）或重传机制。如果帧因冲突或错误丢失，MAC层不会自动重传，而是依赖更高层协议（如TCP）处理可靠性。

关键点：

• 无连接：通过 $MAC$ 地址直接寻址，无需预先建立逻辑连接。
• 不可靠：仅通过 $CRC$ 校验检测错误，但丢弃错误帧后不采取补救措施。

正确答案：A

题目详解：
本题考察回退 N 帧的极限，即求从发送一个帧到接收到这个帧的确认为止的时间内最多可以发送多少数据帧。

要尽可能多发帧，应以短的数据帧计算，首先计算出发送一帧的时间：$8 \times 8 / (16 \times 10^3) = 64 ms$；发送一帧到收到确认为止的总时间：$64 + 270 \times 2 + 64 = 668 ms$；这段时间总共可以发送 $668 / 64 = 10.4$（帧），发送这么多帧至少需要用 4 位比特进行编号。

题目详解：
IP 路由器的主要功能包括以下几个方面：

1. 运行路由协议，设置路由表（I）：路由器通过运行路由协议（如OSPF、RIP、BGP等）与其他路由器交换路由信息，动态更新和维护路由表。路由表用于决定数据包的转发路径。

2. 监测到拥塞时，合理丢弃IP 分组（II）：路由器具备拥塞控制机制，当网络出现拥塞时，会根据策略（如随机早期检测RED）丢弃部分数据包，以缓解拥塞。

3. 对收到的IP 分组头进行差错校验（III）：路由器会对IP 分组头进行校验（如校验和检查），但 不会 确保传输的IP 分组不丢失。数据包的丢失处理由更高层协议（如TCP）负责。

4. 根据收到的IP 分组的目的IP 地址，将其转发到合适的输出线路上（IV）：这是路由器的核心功能。路由器通过查找路由表，将数据包转发到正确的输出接口，使其朝着目的地前进。

综上所述，正确的功能描述是 I、II、IV。III 的描述不完全正确，因为路由器不确保IP 分组不丢失。

正确答案：C

题目详解：
ARP（Address Resolution Protocol，地址解析协议）是一种用于将网络层的 $IP$ 地址解析为数据链路层的 $MAC$ 地址的协议。其主要功能是通过目标设备的 $IP$ 地址查询对应的 $MAC$ 地址，以便在局域网中进行数据帧的传输。

具体过程如下：

1. 当主机需要向同一局域网内的另一台主机发送数据时，它首先检查自己的 $ARP$ 缓存表，查看是否已存在目标 $IP$ 地址对应的 $MAC$ 地址。
2. 如果缓存表中没有对应的条目，主机将广播一个 $ARP$ 请求报文，询问“谁的 $IP$ 地址是 $X.X.X.X$ ？”。
3. 拥有该 $IP$ 地址的主机会回复一个 $ARP$ 响应报文，告知其 $MAC$ 地址。
4. 发起请求的主机收到响应后，将 $IP$ 地址和 $MAC$ 地址的映射关系存入 $ARP$ 缓存表，以便后续使用。

其他选项的功能：

• 选项 B：根据 $MAC$ 地址查询 $IP$ 地址是 $RARP$（Reverse ARP）协议的功能。
• 选项 C：根据域名查询 $IP$ 地址是 $DNS$（Domain Name System）协议的功能。
• 选项 D：根据 $IP$ 地址查询域名是 $DNS$ 反向查询的功能。

正确答案：A

题目详解：
要确定广播地址，首先需要根据给定的 IP 地址和子网掩码计算子网的范围。步骤如下：

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

   • IP 地址：$10110100.01010000.01001101.00110111$
   • 子网掩码：$11111111.11111111.11111100.00000000$

2. 子网掩码中 $255.255.252.0$ 表示前 22 位是网络位（因为 $255.255.252.0$ 的二进制中有 22 个连续的 $1$），后 10 位是主机位。

3. 计算子网的网络地址：

   • 将 IP 地址和子网掩码进行按位与操作：
     $10110100.01010000.01001101.00110111$
     $\& \ 11111111.11111111.11111100.00000000$
     $= \ 10110100.01010000.01001100.00000000$
     转换为点分十进制为 $180.80.76.0$。

4. 广播地址是子网中主机位全为 $1$ 的地址：

   • 网络地址：$180.80.76.0$
     主机位为后 10 位，将后 10 位全部置 $1$：
     $10110100.01010000.01001111.11111111$
     转换为点分十进制为 $180.80.79.255$。

5. 因此，广播地址是 $180.80.79.255$，选项 D 是正确的。

正确答案：D

题目详解：
SMTP采用 “推” 的通信方式，在用户代理向邮件服务器及邮件服务器之间发送邮件时，SMTP 客户主动将邮件“推”送到 SMTP 服务器。而POP3采用 “拉” 的通信方式，当用户读取邮件时，用户代理向邮件服务器发出请求，“拉”取用户邮箱中的邮件。

正确答案：D

题目详解：
1）对于长度分别为 m, n 的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为 m +n-1 次。故最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据哈夫曼树（最佳归并树）思想的启发，可采用如图所示的合并顺序。

根据上图中的哈夫曼树，6 个序列的合并过程为：

第 1 次合并：表 A 与表 B 合并，生成含有 45 个元素的表 AB ;

第 2 次合并：表 AB 与表 C 合并，生成含有 85 个元素的表 ABC;

第 3 次合并：表 D 与表 E 合并，生成含有 110 个元素表 DE;

第 4 次合并：表 ABC 与表 DE 合并，生成含有 195 个元素的表 ABCDE;

第 5 次合并：表 ABCDE 与表 F 合并，生成含有 395 个元素的最终表。

由上述分析可知，最坏清况下的比较次数为：第 1 次合并，最多比较次数 = 10+35-1 = 44；第 2 次合并，最多比较次数 = 45+40-1 = 84；第 3 次合并，最多比较次数 = 50+60-1 = 109；第 4 次合并，最多比较次数 = 85+110-1 = 194；第 5 次合并，最多比较次数 = 195+200-1 = 394。

故比较的总次数最多为：44+84+109+194+394 = 825。

2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。

【评分说明】①对于用类似哈夫曼树（或最佳归并树）思想进行合并，过程描述正确，给 5 分。按其他策略进行合并，过程描述正确，给 3 分。

②正确算出与合并过程一致的总比较次数，给 2 分。若计算过程正确，但结果错误，可给 1 分。

③考生只要说明采用的是类似哈夫曼树（或最佳归并树）的构造方法作为合并策略，即可给 3 分。如果采用其他策略，只要能够完成合并，给 2 分。

题目详解：
顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另 一个链表长 k 个结点，我们先在长链表上遍历 k 个结点，之后同步遍历两个链表，这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的，所以它们肯定同时到达第 一个公共结点。

算法的基本设计思想：

①分别求出 strl 和 str2 所指的两个链表的长度 m 和 n。

②将两个链表以表尾对齐：令指针 p、q 分别指向 strl 和 str2 的头结点，若 $m \ge n$，则使 p 指向链表中的第 m-n+1 个结点；若 $m \lt n$，则使 q 指向链表中的第 n-m+1 个结点，即使指针 p 和 q 所指的结点到表尾的长度相等。

③反复将指针 p 和 q 同步向后移动，并判断它们是否指向同一结点。若 p 和 q 指向同一结点，则该点即为所求的共同后缀的起始位置。

2）算法的 C 语言代码描述：

struct Node {
  int data;
  Node *next;
};

int getLength(Node *h) {
  int length = 0;
  Node *p = h->next;
  while (p) {
    length++;
    p = p->next;
  }
  return length;
}

Node *findCommonSuffix(Node *h1, Node *h1) {
  Node *p1 = h1;
  Node *p2 = h2;
  int m = getLength(h1);
  int n = getLength(h1);
  if (m > n) {
    for (int i = 0; i < m-n; i++) {
      p1 = p1->next;
    }
  } else {
    for (int i = 0; i < n-m; i++) {
      p2 = p2->next;
    }
  }
  while (p1 != p2) {
    p1 = p1->next;
    p2 = p2->next;
  }
  return p1;
}

【评分说明】 ① 若考生所给算法实现正确，且时间复杂度为 O(m+n)，可给 12分；若算法正确，但时间复杂度超过 O(m+n)，则最高可给 9 分。

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

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

③ 时间复杂度为 O(len1+len2) 或 O(max(len1,len2)), 其中 len1、len2 分别为两个链表的长度。

题目详解：
本题综合涉及多个考点：计算机的性能指标、存储器的性能指标、DMA 的性能分析，DMA 方式的特点，多体交叉存储器的性能分析。

1）平均每秒 CPU 执行的指令数为：80M/4 = 20M，故MIPS数为 20；（1 分）平均每条指令访存 1.5 次，故平均每秒 Cache 缺失的次数 = 20M×1.5×(1-99%) = 300k;（1 分）当 Cache 缺失时，CPU 访问主存，主存与 Cache 之间以块为传送单位，此时，主存带宽为16B×300k/s = 4.8MB/s。在不考虑 DMA 传送的情况下，主存带宽至少达到 4.8MB/s 才能满足 CPU 的访存要求。（2 分）

2）题中假定在 Cache 缺失的情况下访问主存，平均每秒产生缺页中断 300000×0.0005% = 1.5 次。因为存储器总线宽度为 32 位，所以每传送 32 位数据，磁盘控制器发出一次 DMA 请求，故平均每秒磁盘 DMA 请求的次数至少为 1.5×4KB/4B = 1.5K = 1536。（2 分）

3）CPU 和 DMA 控制器同时要求使用存储器总线时，DMA 请求优先级更高；（1 分）因为 DMA 请求得不到及时响应，I/O 传输数据可能会丢失。（1 分）

4）四体交叉存储模式能提供的最大带宽为 4×4B/50ns=320MB/s。（2 分）

题目详解：
1）x 的机器码为 $[x]_{补} = 1111 1101 1111 1111B$，即指令执行前 (R1)=FDFFH，右移 1 位后为 1111 1110 1111 1111B，即指令执行后 (R1) = FEFFH。（2 分）

2）每个时钟周期只能有一条指令进入流水线，从第 5 个时钟周期开始，每个时钟周期都会有一条指令执行完毕，故至少需要 4+(5-1)=8 个时钟周期。（2 分）

3）$I_3$ 的 ID 段被阻塞的原因：因为 $I_3$ 与 $I_1$ 和$I_2$ 都存在数据冒险，需等到 $I_1$ 和 $I_2$ 将结果写回寄存器后，$I_3$ 才能读寄存器内容，所以 $I_3$ 的 ID 段被阻塞（1 分）。$I_4$ 的 IF 段被阻塞的原因：因为 $I_4$ 的前一条指令$I_3$ 在 ID 段被阻塞，所以 $I_4$ 的 IF 段被阻塞（1 分）。

注意：要求“按序发射，按序完成”，故 2) 中下一条指令的 IF 必须和上一条指令的 ID 并行，以免因上一条指令发生冲突而导致下一条指令先执行完。

4）因 2*x 操作有左移和加法两种实现，故 x=x*2+a 对应的指令序列为：

I1    LOAD  R1, [x]
I2    LOAD  R2, [a]
I3    SHL   R1       // 或者 ADD R1, R1
I4    ADD   R1, R2
I5    STORE R2, [x]

这 5 条指令在流水线中的执行过程如下表所示：

故 x=x*2+a 语句最少需要 17 个时钟周期。

题目详解：
1）页框号为 21。理由：因为起始 驻留集为空，因此 0 页对应的页框为空闲链表中的第三个空闲页框 21，其对应的页框号为 21。

2）页框号为 32。理由：因 11>10 故发生第三轮扫描，页号为 1 的页框在第二轮已处于空闲页框链表中，此刻该页又被重新访问，因此应被重新放回驻留集中，其页框号为 32。

3）页框号为 41。理由：因为第 2 页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框 41，页框号为 41。

4）合适。理由：如果程序的时间局部性越好，那么从空闲页框链表中重新取回的机会越大，该策略的优势越明显。

(1) 索引表区仅采用直接索引结构

① 索引表项中块号最少占多少字节？

• 文件系统最大容量为 4TB（即$2^{42}$ 字节），磁盘块大小为 1KB（即$2^{10}$ 字节）。

• 磁盘块总数 =$\frac{4\text{TB}}{1\text{KB}} = \frac{2^{42}}{2^{10}} = 2^{32}$ 块。

• 因此，需要至少 32 位（即 4 字节）才能唯一表示所有磁盘块号

  答案：索引表项中块号最少占 4 字节。

② 可支持的单个文件最大长度是多少字节？

• 索引表区大小为 512B，每个索引项占 4B，因此最多可容纳$\frac{512}{4} = 128$ 个索引项。

• 每个索引项对应一个磁盘块（1KB），因此最大文件长度为$128 \times 1\text{KB} = 128\text{KB}$。

  答案：可支持的单个文件最大长度为 128KB。

(2) 索引表区采用混合结构（预分配连续空间 + 直接索引）

① 可支持的单个文件最大长度是多少字节？

• 预分配连续存储空间部分（占 8B）：

  • 起始块号占 6B（可表示$2^{48}$ 块，远超过系统实际块数$2^{32}$，但实际有效位数为 4B，此处仅按给定字节数计算）。
  • 块数占 2B（即 16 位），可表示的最大块数为$2^{16}$ 块。
  • 因此预分配连续空间大小为$2^{16} \times 1\text{KB} = 64\text{MB}$（即$65536\text{KB}$)。

• 直接索引部分（剩余 504B）：

  • 每个索引项占 6B，因此可容纳$\frac{504}{6} = 84$ 个索引项。
  • 每个索引项对应 1KB，因此直接索引部分贡献$84 \times 1\text{KB} = 84\text{KB}$。

• 总最大文件长度 = 预分配连续空间大小 + 直接索引部分大小 =$65536\text{KB} + 84\text{KB} = 65620\text{KB}$。

  答案：可支持的单个文件最大长度为 65620KB。

② 起始块号和块数分别所占字节数的合理值及理由

• 由 (1) ① 可知，块号实际最少需 4B 才能表示所有磁盘块（$2^{32}$ 块）。

• 块数也应至少占 4B，才能表示足够大的连续块数（否则最大连续空间仅$2^{16}\text{KB} = 64\text{MB}$，远小于系统最大容量 4TB）。

• 预分配连续存储空间部分总共 8B，因此合理的分配方案为：

  • 起始块号占 4B，块数占 4B（即 4+4），这样既能充分表示所有块号，又能支持最大连续分配（$2^{32}$ 块，即 4TB）。

• 其他分配方式（如 3+5、2+6、1+7）也可行，但块号少于 4B 时无法表示所有块号（实际需 4B），而块数多于 4B 无必要（因为系统总块数仅$2^{32}$）。因此 4+4 是最优方案。

  答案：起始块号和块数各占 4B 最为合理。理由：块号需 4B 才能覆盖所有磁盘块，块数需 4B 才能支持最大连续分配（达到系统容量上限 4TB）。

说明：

• (2) ① 中预分配部分按给定字节数（块数占 2B）计算，但实际合理设计应调整字节分配（如块数占 4B）。
• (2) ② 强调合理性：需同时满足块号表示和连续分配需求，4+4 方案最均衡。

题目详解：
1）由题 47-a 表看出，源 IP 地址为 IP 分组头的第 13~16 字节。表中 1、3、4 号分组的源 P 地址均为 192.168.0.8（c0a80 008H），所以 1、3、4 号分组是由 H 发送的。

题 47-a 表中，1 号分组封装的 TCP 段的 SYN=1，ACK=0，seq=846b 41c5H；2 号分组封装的 TCP 段的 SYN=1，ACK=1，seq=e059 9fefH，ack=846b 41c6H；3 号分组装的 TCP 段的 ACK=1，seq=846b 41c6H，ack=e059 9ff0H，所以 1、2、3 号分组完成了 TCP 连接的建立过程。

由于快速以太网数据帧有效载荷的最小长度为 46 字节，表中 3、5 号分组的总长度为 40（28H）字节，小于 46 字节，其余分组总长度均大于 46 字节。所以 3、5 号分组通过 以太网快速填充。

2）由 3 号分组封装的 TCP 段可知，发送应用层数据初始序号为 seq=846b 41c6H，由 5 号分组封装的 TCP 段可知，ack 为 seq=846b 41d6H，所以 S 己经收到的应用层数据的字节数为 846b 41d6H - 846b 41c6H = 10H = 16，所以 S 已经接收到了 16 个字节的应用层数据。

3）首先需要确定表 47-a 中的哪一个 IP 分组与表 47-b 中的 IP 分组相对应，这就要根据 IP 分组中的标识字段（第 5-6 个字节），观察可以判断表 47-a 编号为 5 的分组是与表 47-b 的分组相对应的，因为它们的标识字段都是 68H。若要判断 IP 分组经过多少个路由器就要观察 TTL字段（第 9 个字节），发送前来自 S 的分组的 TTL 为 40H，H 接收到的分组的 TTL 为 31H，所以经过路由器的个数为 40H - 31H = 15。