2017年408真题

题目详解：
我们需要分析函数 func 的时间复杂度。函数的主要操作是一个 while 循环，循环条件是 sum < n，每次循环中 sum 累加 ++i 的值。具体步骤如下：

1. 初始化时，i = 0，sum = 0。
2. 每次循环中，i 先自增 1，然后 sum 累加 i 的值。因此，sum 的值实际上是前 $i$ 个自然数的和，即：$sum = 1 + 2 + 3 + \cdots + i = \frac{i(i + 1)}{2}$
3. 循环终止条件是 sum >= n，即：$\frac{i(i + 1)}{2} \geq n$
   由于 $i^2$ 是主导项，可以近似为：$i^2 \approx 2n \implies i \approx \sqrt{2n}$
4. 因此，循环的次数 $i$ 与 $\sqrt{n}$ 成正比，时间复杂度为 $O(\sqrt{n})$，即 $O(n^{1/2})$。

正确答案是 B。

题目详解：
关于栈的叙述，我们逐一分析各选项的正确性：

I. 采用非递归的方式重写递归程序时必须用栈
这一叙述是错误的。并非所有递归程序都需要用栈来实现非递归版本。例如，尾递归可以通过迭代直接实现，不需要栈。只有非尾递归的情况才需要栈来保存调用信息。

II. 函数调用时，系统要用栈保存必要的信息
这一叙述是正确的。函数调用时，系统使用调用栈（call stack）保存返回地址、局部变量等信息。

III. 只要确定了入栈次序，就可确定出栈次序
这一叙述是错误的。入栈次序相同的情况下，可能有多种合法的出栈次序。例如，入栈序列为 $1, 2, 3$，出栈序列可以是 $3, 2, 1$ 或 $2, 1, 3$ 等。

IV. 栈是一种受限的线性表，允许在其两端进行操作
这一叙述是错误的。栈是一种后进先出（LIFO）的线性表，只允许在栈顶（一端）进行插入和删除操作。

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

正确答案：C

题目详解：
稀疏矩阵是指矩阵中绝大多数元素为零的矩阵。为了高效存储稀疏矩阵，通常采用以下两种存储结构：

1. 三元组表：将稀疏矩阵中的非零元素按行、列、值的形式存储为一个三元组 $(i, j, value)$，其中 $i$ 表示行号，$j$ 表示列号，$value$ 表示元素值。这种存储方式节省了空间，但不利于快速访问。

2. 十字链表：也称为正交链表，是一种链式存储结构。每个非零元素用一个节点表示，节点中包含行号、列号、值以及指向同行和同列下一个非零元素的指针。十字链表适合频繁插入和删除操作的场景。

其他选项分析：

• 邻接矩阵：通常用于表示图的连接关系，不适合存储稀疏矩阵，因为会浪费大量空间存储零元素。
• 二叉链表：通常用于表示树结构，与稀疏矩阵的存储无关。

因此，正确答案是 A. 三元组表和十字链表。

题目详解：
要理解这个问题，我们需要分析二叉树的先序遍历和中序遍历的特点：

1. 先序遍历（Pre-order）：访问顺序为 $\text{根} \rightarrow \text{左子树} \rightarrow \text{右子树}$。
2. 中序遍历（In-order）：访问顺序为 $\text{左子树} \rightarrow \text{根} \rightarrow \text{右子树}$。

为了使先序序列和中序序列相同，必须确保在访问根结点时，没有左子树的存在。否则，中序遍历会先访问左子树，从而导致序列不同。具体分析如下：

• 如果非叶结点 只有左子树（选项A），中序遍历会先访问左子树，再访问根结点，导致序列与先序不同。
• 如果非叶结点 只有右子树（选项B），先序和中序的访问顺序均为 $\text{根} \rightarrow \text{右子树}$，序列相同。
• 如果结点的度均为 1（选项C），可能是只有左子树或只有右子树，但只有右子树的情况才满足条件，因此选项C不全面。
• 如果结点的度均为 2（选项D），意味着每个非叶结点都有左右子树，中序会先访问左子树，导致序列与先序不同。

因此，唯一满足条件的选项是 B，即所有非叶结点 只有右子树。

正确答案：B

题目详解：
后序序列是先左子树，接着右子树，最后父结点，递归进行。根结点左子树的叶结点首先被访问，它是 e。接下来是它的父结点 a, 然后是 a 的父结点 c。接着访问根结点的右子树。它的叶结点 b 首先被访问，然后是 b 的父结点 d, 再者是 d 的父结点 g。最后是根结点 f。因此 d 与 a 同层，B 正确。

题目详解：
哈夫曼编码是前缀编码，各个编码的前缀各不相同，因此直接拿编码序列与哈夫曼编码一一比对即可。序列可分割为 0100 011 001 001 011 11 0101，译码结果是 a f e e f g d，选项 D 正确。

正确答案：D

题目详解：
根据图论中的握手定理，无向图中所有顶点的度数之和等于边数的两倍。设图 $G$ 的顶点总数为 $n$，其他顶点的度数和为 $D$。

已知：

• 边数 $|E| = 16$，所以度数之和为 $2 \times 16 = 32$。
• 度为 $4$ 的顶点有 $3$ 个，贡献的度数为 $3 \times 4 = 12$。
• 度为 $3$ 的顶点有 $4$ 个，贡献的度数为 $4 \times 3 = 12$。
• 其他顶点的度均小于 $3$，即最大可能为 $2$。

设其他顶点数为 $k$，则 $D \leq 2k$。

根据握手定理：
$12 + 12 + D = 32$
$D = 8$

由于 $D \leq 2k$，所以：
$8 \leq 2k$
$k \geq 4$

因此，总顶点数：
$n = 3 + 4 + k \geq 3 + 4 + 4 = 11$

所以，图 $G$ 所含的顶点个数至少是 $11$。

正确答案：B

题目详解：
折半查找判定树实际上是一棵 二叉排序树，它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素，符合折半查找规则的树即是所求。

B 选项 4、5 相加除 2 向上取整，7、8 相加除 2 向下取整，矛盾。C 选项，3、4 相加除 2 向上取整，6、7 相加除 2 向下取整，矛盾。D 选项，1、10 相加除 2 向下取整，6、7 相加除 2 向上取整，矛盾。A 符合折半查找规则，因此正确。

题目详解：
B+树是一种多路平衡查找树，具有以下特点使其特别适合作为关系数据库系统中的索引：

1. 高扇出性：B+树的每个节点可以包含大量子节点（通常上百个），这使得树的高度保持在很低的水平。例如，一个4层的B+树可以索引 $10^8$ 条记录。

2. 顺序访问优势：B+树的所有数据都存储在叶子节点，并且叶子节点通过指针连接成链表，非常适合范围查询（如SQL中的 BETWEEN 或 > 操作）。

3. 磁盘I/O优化：B+树的节点大小通常设计为磁盘块大小（如4KB），通过 $O(\log_d n)$ 的I/O复杂度（其中 $d$ 为扇出系数）实现高效查找，显著减少磁盘访问次数。

其他选项分析：

• A：词法分析通常使用有限自动机或正则表达式，不需要树结构。
• C：路由表快速查找通常采用Trie树或哈希表，而非B+树。
• D：磁盘空闲块管理通常使用位图或链表，B+树的维护开销不必要。

正确答案：B

题目详解：
在比较归并排序和插入排序时，我们需要从多个角度分析两者的差异：

1. 程序代码长度：归并排序通常需要递归或迭代的分治策略，代码实现比插入排序复杂，因此 $I$ 是错误的。

2. 占用空间：归并排序的空间复杂度为 $O(n)$，因为需要额外的临时数组来合并子序列；而插入排序是原地排序，空间复杂度为 $O(1)$。因此 $II$ 是错误的。

3. 运行效率：归并排序的时间复杂度为 $O(n \log n)$，而插入排序的时间复杂度为 $O(n^2)$。对于大规模数据，归并排序的效率更高，因此 $III$ 是正确的。

综上所述，只有 $III$ 是正确的，因此正确答案是 $B$。

正确答案：B

题目详解：
排序算法在顺序存储和链式存储下的时间效率差异主要取决于算法对数据访问方式的要求：

1. 插入排序（I）：在链式存储中，插入操作的时间复杂度仍为 $O(1)$，但查找插入位置需要顺序访问，平均时间复杂度仍为 $O(n^2)$，与顺序存储相同，因此时间效率不会显著降低。

2. 选择排序（II）：无论顺序还是链式存储，都需要顺序扫描未排序部分找到最小（或最大）元素，时间复杂度均为 $O(n^2)$，因此时间效率不会显著降低。

3. 起泡排序（III）：通过相邻元素比较和交换完成排序，链式存储可以高效实现，时间复杂度仍为 $O(n^2)$，因此时间效率不会显著降低。

4. 希尔排序（IV）：依赖于顺序存储的随机访问特性（通过增量跳跃访问元素），链式存储无法高效实现这种访问，时间复杂度会显著提高。

5. 堆排序（V）：完全依赖于顺序存储的随机访问特性（如通过下标计算父子节点位置），链式存储无法高效实现堆调整操作，时间复杂度会显著提高。

综上，希尔排序和堆排序在链式存储下时间效率会明显降低。

正确答案：D

题目详解：
程序运行时间的计算公式为：
$运行时间 = \frac{指令数 \times CPI}{主频}$

设程序P的指令数为 $N$，则：

在M1上的运行时间 $T_1$ 为：
$T_1 = \frac{N \times 2}{1.5 \times 10^9}$

在M2上的运行时间 $T_2$ 为：
$T_2 = \frac{N \times 1}{1.2 \times 10^9}$

运行时间的比值 $\frac{T_1}{T_2}$ 为：
$\frac{T_1}{T_2} = \frac{\frac{2N}{1.5 \times 10^9}}{\frac{N}{1.2 \times 10^9}} = \frac{2}{1.5} \times \frac{1.2}{1} = \frac{2 \times 1.2}{1.5 \times 1} = \frac{2.4}{1.5} = 1.6$

因此，程序P在M1和M2上运行时间的比值是1.6。

正确答案：C

题目详解：
首先，我们需要分析计算机主存的结构和编址方式：

1. 主存由 4 个 $64M \times 8$ 位的 DRAM 芯片构成，采用交叉编址方式。这意味着：

   • 每个芯片的容量为 $64M \times 8$ 位，即 $64$ MB。
   • 4 个芯片总容量为 $4 \times 64$ MB $= 256$ MB。
   • 交叉编址意味着地址空间被均匀分布到 4 个芯片上。

2. 存储器总线宽度为 $32$ 位，主存每次最多读写 $32$ 位数据。因此，每次存储周期可以读取 $4$ 字节数据。

3. $double$ 型变量 $x$ 的大小为 $8$ 字节，因此需要分多次读取：

   • 每次读取 $4$ 字节，所以至少需要 $\lceil \frac{8}{4} \rceil = 2$ 次存储周期。

4. 但是题目中给出的 $x$ 的主存地址为 $804001AH$，我们需要分析其对齐情况：

   • 地址的低 $2$ 位（$1AH$ 的低 $2$ 位是 $10$）表示 $x$ 的起始地址不是 $4$ 字节对齐的（因为对齐地址的低 $2$ 位应为 $00$）。
   • 因此，第一次存储周期只能读取 $804001AH$ 开始的 $2$ 字节（因为起始地址 $1AH \mod 4 = 2$），第二次读取接下来的 $4$ 字节，第三次读取最后的 $2$ 字节。
   • 总共需要 $3$ 次存储周期。

综上所述，读取 $x$ 需要的存储周期数是 $3$。

正确答案：C

题目详解：
在分析数组 a 的访问局部性时，我们需要考虑时间局部性和空间局部性两个维度。

1. 时间局部性：指的是同一个数据项在短时间内被多次访问的特性。在代码中，数组元素 a[j] 在内部循环中被反复访问（temp *= a[j]）。特别是对于较小的 j 值，a[j] 会在多次外层循环中被重复访问（例如 a[0] 在每次 i 增加时都会被访问）。因此，数组 a 的访问具有时间局部性。

2. 空间局部性：指的是程序倾向于访问邻近于最近访问过的数据项的特性。代码中，数组 a 的访问顺序是 a[0], a[0], a[1], a[0], a[1], a[2], ..., a[0], ..., a[9]。可以看到，每次访问的 a[j] 都是按顺序连续访问的，且数组元素在内存中是连续存储的。因此，数组 a 的访问具有空间局部性。

综上所述，数组 a 的访问同时具有时间局部性和空间局部性。

正确答案：A

题目详解：
在计算机体系结构中，寻址方式的选择对数组访问的效率有很大影响。题目问的是最适合按下标顺序访问一维数组元素的寻址方式，我们需要分析每种寻址方式的特点：

1. A. 相对寻址：通过基地址加上一个偏移量来计算有效地址，适用于访问局部变量或跳转指令，但不太适合数组的顺序访问，因为每次都需要重新计算偏移量。

2. B. 寄存器寻址：操作数直接存放在寄存器中，适用于高速访问，但寄存器数量有限，无法直接用于数组元素的顺序访问。

3. C. 直接寻址：指令中直接给出操作数的内存地址，适用于访问固定地址的数据，但无法灵活地按顺序访问数组元素。

4. D. 变址寻址：通过基地址（数组起始地址）加上变址寄存器（存放数组下标）的值来计算有效地址，非常适合按下标顺序访问一维数组元素。变址寄存器可以方便地递增或递减，实现顺序访问。

因此，变址寻址是最适合按下标顺序访问一维数组元素的寻址方式。

正确答案：D

题目详解：
首先，我们需要分析指令格式和地址字段的分配情况。

1. 指令格式分析：

   • 该计算机有 两种指令格式：三地址指令和二地址指令。
   • 三地址指令有 $29$ 条，二地址指令有 $107$ 条。
   • 每个地址字段为 $6$ 位。

2. 三地址指令的编码：

   • 三地址指令包含 3个地址字段，每个地址字段占 $6$ 位，因此地址部分共占 $3 \times 6 = 18$ 位。
   • 假设三地址指令的操作码部分占 $OP_1$ 位，则三地址指令的总长度为 $OP_1 + 18$ 位。
   • 由于三地址指令有 $29$ 条，需要满足 $2^{OP_1} \geq 29$，因此 $OP_1 \geq 5$ 位（因为 $2^5 = 32 \geq 29$）。

3. 二地址指令的编码：

   • 二地址指令包含 2个地址字段，每个地址字段占 $6$ 位，因此地址部分共占 $2 \times 6 = 12$ 位。
   • 假设二地址指令的操作码部分占 $OP_2$ 位，则二地址指令的总长度为 $OP_2 + 12$ 位。
   • 由于二地址指令有 $107$ 条，且需要与三地址指令的操作码区分开，因此需要满足 $2^{OP_2} \geq 107$，因此 $OP_2 \geq 7$ 位（因为 $2^7 = 128 \geq 107$）。

4. 指令字长的确定：

   • 为了保证两种指令格式的操作码部分能够区分开，我们需要统一指令字长。
   • 三地址指令的最小长度为 $5 + 18 = 23$ 位。
   • 二地址指令的最小长度为 $7 + 12 = 19$ 位。
   • 为了统一指令字长，我们需要取两者的最大值，即 $23$ 位。但由于计算机按字节编址，指令字长应为字节的整数倍（即 $8$ 的倍数），因此至少需要 $24$ 位。

综上所述，指令字长至少为 $24$ 位。

正确答案：A

题目详解：
超标量流水线是一种通过增加硬件资源来提高指令级并行性的技术。下面对各个叙述进行分析：

1. 叙述I：能缩短流水线功能段的处理时间
   这是错误的。超标量流水线并不能缩短单个功能段的处理时间，它只是通过在一个时钟周期内发射多条指令 来提升并行度。功能段的处理时间由硬件设计和电路延迟决定，与是否超标量无关。

2. 叙述II：能在一个时钟周期内同时发射多条指令
   这是正确的。超标量流水线的核心特性就是通过多套功能部件 和多发射逻辑 实现每个周期发射多条指令（如 $n$ 条指令，$n > 1$）。

3. 叙述III：能结合动态调度技术提高指令执行并行性
   这是正确的。超标量流水线常与动态调度（如 Tomasulo 算法）结合，通过乱序执行 和寄存器重命名 等技术解决数据冲突，进一步提高并行性。

综上，仅叙述II和III正确。

正确答案：C

题目详解：
主存储器（MM, Main Memory）和控制存储器（CS, Control Store）是计算机系统中的两种重要存储部件，它们在功能、位置和访问方式上有显著区别：

1. 位置：

   • MM 位于CPU 外部，用于存储程序指令和数据，CPU 通过总线访问MM。
   • CS 位于CPU 内部，是微程序控制器的组成部分，用于存储微指令（控制信号序列）。
   • 因此，选项A（MM 在CPU 外，CS 在CPU 内）是正确的。

2. 访问方式：

   • MM 通过地址访问（即按地址寻址），CPU 提供地址总线来读取或写入数据。
   • CS 也是按地址访问的，微程序的执行通过微地址顺序访问CS 中的微指令。
   • 按内容访问（如相联存储器）是另一种访问方式，但CS 并不采用这种方式。因此，选项B（MM 按地址访问，CS 按内容访问）是错误的。

3. 存储内容：

   • MM 存储用户程序和相关的数据。
   • CS 存储微指令，用于控制CPU 的硬件操作。
   • 因此，选项C（MM 存储指令和数据，CS 存储微指令）是正确的。

4. 实现技术：

   • MM 通常由RAM（随机存取存储器）和ROM（只读存储器）实现，RAM 用于临时存储，ROM 用于固化程序（如BIOS）。
   • CS 通常由ROM 实现，因为微指令在制造时就被固定，但现代CPU 也可能使用可写的CS（如EPROM）。
   • 因此，选项D（MM 用RAM 和ROM 实现，CS 用ROM 实现）是正确的。

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

正确答案：B

题目详解：
在指令流水线数据通路的分析中，我们需要明确其组成部分和功能：

1. 控制部件：指令流水线的数据通路主要负责数据的流动和处理，而生成控制信号的部件属于控制单元（Control Unit），它不属于数据通路的一部分。因此，选项A的描述是错误的。

2. 通用寄存器组和取指部件：数据通路确实包含通用寄存器组（如 $\text{REG}$ 文件）和取指部件（如 $\text{PC}$ 和指令存储器），这些是数据通路的核心组件。因此，选项C的描述是正确的。

3. 电路组成：数据通路通常由组合逻辑电路（如ALU、多路选择器）和时序逻辑电路（如寄存器、存储器）组合而成，以实现指令的流水执行。因此，选项D的描述是正确的。

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

正确答案：A

题目详解：
多总线结构是计算机系统中常用的一种总线架构，其特点如下：

1. 总线速度与CPU距离的关系：选项A提到“靠近CPU的总线速度较快”，这是正确的。因为CPU需要高速访问某些关键部件（如缓存），所以靠近CPU的总线通常设计为高速总线，例如前端总线（FSB）。

2. 算术逻辑运算部件（ALU）的位置：选项B提到“包含算术逻辑运算部件（ALU）”，这是错误的。ALU是CPU的核心部件，位于CPU内部，并不属于多总线结构的组成部分。多总线结构主要涉及总线层级和连接方式，与ALU无关。

3. 存储器总线的突发传送方式：选项B（第二个B）提到“存储器总线可支持突发传送方式”，这是正确的。突发传送（Burst Transfer）是一种高效的数据传输方式，允许连续传输多个数据单元而无需重复发送地址。

4. 总线之间的连接方式：选项C提到“总线之间须通过桥接器相连”，这是正确的。在多总线结构中，不同速度的总线（如高速总线和低速总线）通常通过桥接器（如北桥、南桥）连接，以实现数据转发和协议转换。

5. PCI-Express×16的传输方式：选项D提到“PCI-Express×16采用并行传输方式”，这是错误的。PCI-Express（PCIe）采用串行传输方式，通过多通道（如×1、×4、×8、×16）实现高带宽，而非并行传输。并行传输是传统总线（如PCI）的特点。

正确答案：D

题目详解：
I/O 指令主要用于实现 CPU 和 I/O 设备之间的数据传送。具体来说，I/O 指令执行时，数据通常在 CPU 的 $通用寄存器$ 和 $I/O 端口$ 之间进行传送。$I/O 端口$ 是 CPU 与外部设备进行通信的接口，每个 $I/O 设备$ 都有一个或多个 $I/O 端口$ 与之对应。当 CPU 执行输入指令时，数据从 $I/O 端口$ 传送到 $通用寄存器$；执行输出指令时，数据从 $通用寄存器$ 传送到 $I/O 端口$。因此，I/O 指令实现的数据传送通常发生在 $通用寄存器$ 和 $I/O 端口$ 之间。

正确答案：D

题目详解：
在多重中断系统中：

A. 在一条指令执行结束时响应中断：这是正确的。CPU通常会在当前指令执行完成后检查中断请求，以确保指令的原子性。

B. 中断处理期间CPU 处于关中断状态：这是错误的。在多重中断系统中，CPU在处理一个中断时可能会允许更高优先级的中断（即开中断），而不是始终处于关中断状态。因此，这个叙述是错误的。

C. 中断请求的产生与当前指令的执行无关：这是正确的。中断请求通常由外部设备或内部异常触发，与当前执行的指令无直接关系。

D. CPU 通过采样中断请求信号检测中断请求：这是正确的。CPU会定期采样中断请求线（如$IRQ$）来检测是否有中断请求。

正确答案：B

题目详解：
在 $t = 2$ 时，系统开始作业调度。此时各作业的状态如下：

1. 先来先服务 (FCFS) 调度算法：

   • 按照作业到达的顺序进行调度。
   • 在 $t = 2$ 时，已到达的作业有 $J_1$ (到达时刻 $0$ )、$J_2$ (到达时刻 $1$ ) 和 $J_3$ (到达时刻 $1$ )。
   • $J_1$ 最先到达，因此被选中执行。

2. 短作业优先 (SJF) 调度算法：

   • 优先调度运行时间最短的作业。
   • 在 $t = 2$ 时，已到达的作业有 $J_1$ (运行时间 $3$ )、$J_2$ (运行时间 $3$ )、$J_3$ (运行时间 $2$ ) 和 $J_4$ (运行时间 $1$ )。
   • $J_4$ 的运行时间最短，但它尚未到达（到达时刻为 $3$ ），因此选择次短的 $J_3$ (运行时间 $2$ )。

综上，先来先服务选中 $J_1$ ，短作业优先选中 $J_3$ 。正确答案是 D。

正确答案：D

题目详解：
执行系统调用的过程遵循以下顺序：

1. 首先需要 传递系统调用参数 （步骤③），将用户态的参数传递给内核态，通常通过寄存器或栈来传递。

2. 接着执行 陷入（trap）指令 （步骤②），该指令会触发一个软中断，将CPU从用户态切换到内核态，并跳转到内核的中断处理程序。

3. 然后在内核态 执行相应的服务程序 （步骤④），根据系统调用号找到对应的内核函数并执行。

4. 最后 返回用户态 （步骤①），将CPU从内核态切换回用户态，并将结果返回给用户程序。

因此，正确的顺序是 $③ \rightarrow ② \rightarrow ④ \rightarrow ①$。

正确答案：C

题目详解：
首先，我们需要分析当前的空闲分区链和回收操作的影响。

1. 初始空闲分区链（按起始地址升序排列）：

   • 分区1：起始地址 $20K$，大小 $40KB$
   • 分区2：起始地址 $200K$，大小 $200KB$
   • 分区3：起始地址 $500K$，大小 $80KB$
   • 分区4：起始地址 $1000K$，大小 $100KB$

2. 回收操作：回收起始地址为 $60K$、大小为 $140KB$ 的分区。我们需要检查该分区是否可以与相邻的空闲分区合并：

   • 检查前一个分区：分区1的起始地址为 $20K$，大小为 $40KB$，其结束地址为 $20K + 40KB = 60K$，恰好与回收分区的起始地址 $60K$ 相邻。因此，分区1可以与回收分区合并。
   • 合并后的分区：起始地址 $20K$，大小 $40KB + 140KB = 180KB$。
   • 检查后一个分区：下一个空闲分区的起始地址为 $200K$，而回收分区的结束地址为 $60K + 140KB = 200K$，恰好与分区2的起始地址 $200K$ 相邻。因此，合并后的分区可以进一步与分区2合并。
   • 最终合并的分区：起始地址 $20K$，大小 $180KB + 200KB = 380KB$。

3. 合并后的空闲分区链：

   • 分区1：起始地址 $20K$，大小 $380KB$
   • 分区2：起始地址 $500K$，大小 $80KB$
   • 分区3：起始地址 $1000K$，大小 $100KB$

4. 重新排序：题目说明采用最佳适应算法，因此空闲分区链需要按分区大小升序排列：

   • 分区2：起始地址 $500K$，大小 $80KB$
   • 分区3：起始地址 $1000K$，大小 $100KB$
   • 分区1：起始地址 $20K$，大小 $380KB$

5. 结果：

   • 空闲分区的数量为 $3$。
   • 空闲分区链的第一个分区是起始地址 $500K$、大小 $80KB$ 的分区。

正确答案：B

题目详解：
在文件系统中，磁盘空间分配的最小单位是簇。题目中给出的簇大小为 $1KB$（即 $1024B$），而磁盘扇区大小为 $512B$。文件的大小为 $1026B$。

1. 首先，计算文件大小占用的簇数量：

   • 每个簇的大小为 $1024B$。
   • 文件大小为 $1026B$，因此需要分配的簇数为：
     $\lceil \frac{1026}{1024} \rceil = 2 \text{ 个簇}$

2. 计算分配的磁盘空间大小：

   • 分配的簇数为 $2$，每个簇为 $1024B$，因此总空间为：
     $2 \times 1024B = 2048B$

因此，系统分配给该文件的磁盘空间大小是 $2048B$。

正确答案：D

题目详解：
在基于时间片的进程调度中：

• 选项A：时间片越短，意味着每个进程获得CPU的时间减少，导致进程切换的频率增加。每次切换都会带来上下文切换的开销，因此系统开销会增大。该叙述正确。

• 选项B：当前进程的时间片用完后，进程调度器会剥夺其CPU使用权，并将其状态从 执行态 改为 就绪态，而非 阻塞态。阻塞态通常是由于等待I/O或其他事件而进入的状态。因此该叙述错误。

• 选项C：时钟中断是时间片调度的重要机制。每次时钟中断发生时，系统会检查当前进程的时间片剩余时间，并更新该值。该叙述正确。

• 选项D：时间片大小的设置需要权衡多个因素，例如：

  • 响应时间：时间片越小，响应时间越短。
  • 系统开销：时间片越小，切换越频繁，开销越大。
  • 进程数量：进程越多，时间片通常需要更小以保证公平性。
    因此该叙述正确。

正确答案：B

题目详解：
与单道程序系统相比，多道程序系统的优点主要体现在以下几个方面：

1. CPU 利用率高（I）：多道程序系统可以同时在内存中装入多个程序，当一个程序因 I/O 操作而等待时，CPU 可以立即切换到另一个程序执行，避免了 CPU 空闲，从而提高了 CPU 的利用率。单道程序系统在同一时间只能运行一个程序，CPU 利用率较低。

2. 系统吞吐量大（III）：由于多道程序系统能够并行执行多个程序，单位时间内完成的作业数量（即吞吐量）显著增加。而单道程序系统一次只能处理一个作业，吞吐量较小。

3. I/O 设备利用率高（IV）：多道程序系统中，当一个程序进行 I/O 操作时，CPU 可以执行其他程序，使得 I/O 设备和 CPU 都能保持较高的利用率。单道程序系统中，I/O 操作期间 CPU 处于空闲状态，设备利用率较低。

关于 系统开销小（II）：多道程序系统由于需要管理多个程序的并发执行，涉及进程调度、内存管理、资源分配等复杂机制，其系统开销通常比单道程序系统更大，因此这一项不是多道程序系统的优点。

综上所述，多道程序系统的优点是 I、III、IV，即 CPU 利用率高、系统吞吐量大、I/O 设备利用率高。

正确答案：D

题目详解：
磁盘逻辑格式化程序（也称为高级格式化）主要完成以下工作：

1. 建立文件系统的根目录（II）：这是逻辑格式化的核心任务之一，为文件系统创建初始的目录结构。

2. 对保存空闲磁盘块信息的数据结构进行初始化（IV）：例如初始化位示图或空闲块链表，用于管理磁盘空间的分配。

而其他选项的描述不属于逻辑格式化的范畴：

• 对磁盘进行分区（I）：这是低级格式化或分区工具（如fdisk）的工作，发生在逻辑格式化之前。
• 确定磁盘扇区校验码所占位数（III）：这是磁盘控制器或低级格式化阶段完成的任务，与物理扇区特性相关。

因此，只有选项II和IV是逻辑格式化程序的工作内容。

正确答案：B

题目详解：
为了计算表示文件权限所需的最少二进制位数，我们需要分析用户类别和访问权限的组合情况。

1. 用户类别：共有 4 类用户：

   • 安全管理员
   • 文件主
   • 文件主的伙伴
   • 其他用户

2. 访问权限：共有 5 种权限：

   • 完全控制
   • 执行
   • 修改
   • 读取
   • 写入

3. 权限表示：每个用户类别需要独立分配访问权限。因此，每个用户类别需要一个二进制位串来表示其权限组合。对于 5 种权限，至少需要 $\lceil \log_2 5 \rceil = 3$ 位二进制数来表示（因为 $2^2 = 4 < 5$，而 $2^3 = 8 \geq 5$）。

4. 总位数计算：由于有 4 类用户，每类用户需要 3 位二进制数表示其权限，因此总位数为：
   $4 \text{（用户类别）} \times 3 \text{（权限位数）} = 12 \text{ 位}$
   然而，题目中的选项没有 12 位（选项 C 是 12，但题目要求的是“至少”），因此可能需要更精确的表示方法。如果采用位掩码（每个权限用 1 位表示），则每种权限需要 5 位（每位对应一种权限），4 类用户需要的总位数为：
   $4 \text{（用户类别）} \times 5 \text{（权限位数）} = 20 \text{ 位}$
   这样，可以更灵活地为每类用户分配任意权限组合。

综上所述，描述文件权限的位数至少应为 20 位。

正确答案：D

题目详解：
在Unix/Linux系统中，硬链接（hard link）是指多个文件名指向同一个 inode（索引结点）。因此，$f1$ 和 $f2$ 是同一个文件的硬链接时，它们共享同一个 inode，即内存索引结点。以下是各选项的分析：

1. I. $f1$ 和 $f2$ 的读写指针位置保持相同
   这个叙述是错误的。虽然 $f1$ 和 $f2$ 共享同一个 inode，但每个进程打开文件时会创建独立的文件描述符（file descriptor），每个文件描述符会维护自己的读写指针位置。因此，$fd1$ 和 $fd2$ 的读写指针是独立的，不会同步。

2. II. $f1$ 和 $f2$ 共享同一个内存索引结点
   这个叙述是正确的。硬链接的本质是多个文件名指向同一个 inode，因此 $f1$ 和 $f2$ 共享同一个内存索引结点。

3. III. $fd1$ 和 $fd2$ 分别指向各自的用户打开文件表中的一项
   这个叙述是正确的。每个进程打开文件时，会在自己的用户打开文件表中创建一项，因此 $fd1$ 和 $fd2$ 分别属于各自的进程，指向各自的表项。

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

正确答案：B

题目详解：
系统将数据从磁盘读到内存的过程涉及 DMA（Direct Memory Access，直接内存访问）机制，其正确执行顺序如下：

1. 初始化DMA控制器并启动磁盘（②）：首先需要配置 DMA 控制器的参数（如内存起始地址、传输数据长度等），然后启动磁盘，准备数据传输。

2. 从磁盘传输一块数据到内存缓冲区（③）：DMA 控制器接管总线控制权，将数据从磁盘直接传输到内存缓冲区，无需 CPU 干预。

3. DMA控制器发出中断请求（①）：当数据传输完成后，DMA 控制器向 CPU 发出中断信号，通知 CPU 数据传输已完成。

4. 执行“DMA结束”中断服务程序（④）：CPU 响应中断，执行中断服务程序进行后续处理（如校验数据、更新状态等）。

因此，正确的执行顺序是 $② \rightarrow ③ \rightarrow ① \rightarrow ④$。

正确答案：B

题目详解：
在 OSI 参考模型中，数据从应用层向下传输时，每层都会添加自己的头部信息（额外开销）。题目中给出以下条件：

1. 应用层原始数据大小为 $400B$。
2. 除物理层和应用层外，其他五层（表示层、会话层、传输层、网络层、数据链路层）每层引入 $20B$ 的额外开销。
3. 物理层不添加额外开销。

因此，总额外开销为：
$5 \times 20B = 100B$。

数据传输效率的计算公式为：
$\text{传输效率} = \frac{\text{应用层原始数据大小}}{\text{应用层原始数据大小} + \text{总额外开销}} \times 100\%$

将数值代入公式：
$\text{传输效率} = \frac{400B}{400B + 100B} \times 100\% = \frac{400}{500} \times 100\% = 80\%$

正确答案：A

题目详解：
可用 奈奎斯特定理 计算无噪声情况下的极限数据传输速率，用 香农定理 计算有噪信道极限数据传输速率。$2W \log_{2}N \ge W \log_{2}(1 + S/N)$，$W$ 是信道带宽，$N$ 是信号状态数，$S/N$ 是信噪比，将数据代入计算可得 $N \ge 32$，选 D。分贝数 $= 10 \log_{10}(S/N)$。

正确答案：D

题目详解：
IEEE 802.11数据帧有四种子类型，分别是 IBSS、From AP、ToAP、WDS。这里的数据帧 F 是从笔记本电脑发送往访问接入点（AP），所以属于 To AP 子类型。这种帧地址 l 是 RA (BSSID)，地址 2 是 SA，地址 3 是 DA。RA 是 Receiver Address 的缩写，BSSID 是 basic service set identifier 的缩写，SA 是 source address 的缩写，DA 是 destination address 的缩写。因此地址 1 是 AP 的 MAC，地址 2 是 H 的 MAC，地址 3 是 R 的 MAC，选 B。

题目详解：
在IP地址中，有几个特殊的保留地址具有特定的用途：

1. $0.0.0.0$ 是一个特殊的IP地址，称为“未指定地址”或“默认路由”。它通常用作源IP地址，表示“本网络上的本主机”，但不能作为目的IP地址使用。当主机在启动时尚未分配IP地址时，可能会使用 $0.0.0.0$ 作为源地址。

2. $127.0.0.1$ 是环回地址，用于主机自我通信。它可以作为源IP地址或目的IP地址使用，通常用于测试网络协议栈是否正常工作。

3. $200.10.10.3$ 是一个普通的单播IP地址，可以作为源IP地址或目的IP地址使用。

4. $255.255.255.255$ 是受限广播地址，用于向本地网络中的所有主机发送广播消息。它通常只能作为目的IP地址使用，而不能作为源IP地址。

因此，题目中只能作为源IP地址但不能作为目的IP地址的是 $0.0.0.0$ 。

正确答案：A

题目详解：
RIP、OSPF 和 BGP 是三种常见的路由协议，它们分别使用不同的传输协议进行报文封装：

1. RIP（Routing Information Protocol）：

   • RIP 使用 $UDP$ 作为传输协议，端口号为 $520$。
   • RIP 报文直接封装在 $UDP$ 数据报中。

2. OSPF（Open Shortest Path First）：

   • OSPF 直接运行在 $IP$ 之上，协议号为 $89$。
   • OSPF 报文直接封装在 $IP$ 数据包中，不依赖 $TCP$ 或 $UDP$。

3. BGP（Border Gateway Protocol）：

   • BGP 使用 $TCP$ 作为传输协议，端口号为 $179$。
   • BGP 报文通过 $TCP$ 连接可靠传输。

因此，直接封装 RIP、OSPF、BGP 报文的协议分别是 $UDP$ 、 $IP$ 、 $TCP$ 。

正确答案：D

题目详解：
首先，原始网络是 $21.3.0.0/16$，这意味着网络前缀是 $16$ 位，主机部分是 $32 - 16 = 16$ 位，可分配的 IP 地址总数是 $2^{16} - 2 = 65534$（减去全 0 和全 1 的地址）。

现在需要将该网络划分为 $128$ 个规模相同的子网。因为 $128 = 2^7$，所以需要从主机部分借用 $7$ 位作为子网位。新的子网掩码长度是 $16 + 7 = 23$ 位。

剩下的主机部分是 $32 - 23 = 9$ 位，因此每个子网可分配的 IP 地址个数是 $2^9 - 2 = 512 - 2 = 510$（减去全 0 和全 1 的地址）。

正确答案：C

题目详解：
在TCP连接建立后，发送窗口会通过慢启动算法逐渐增大。慢启动阶段，发送窗口大小 $cwnd$ 从1个MSS开始，每经过一个RTT时间，$cwnd$ 会翻倍。具体过程如下：

1. 初始时，$cwnd = 1 \text{ MSS} = 1 \text{ KB}$。
2. 经过1个RTT（5ms），$cwnd$ 翻倍为 $2 \text{ KB}$。
3. 经过2个RTT（10ms），$cwnd$ 翻倍为 $4 \text{ KB}$。
4. 经过3个RTT（15ms），$cwnd$ 翻倍为 $8 \text{ KB}$。
5. 经过4个RTT（20ms），$cwnd$ 翻倍为 $16 \text{ KB}$。
6. 经过5个RTT（25ms），$cwnd$ 翻倍为 $32 \text{ KB}$。

因此，甲从连接建立成功至发送窗口达到 $32 \text{ KB}$，至少需要经过 $5 \times \text{RTT} = 5 \times 5 \text{ ms} = 25 \text{ ms}$。

正确答案：A

题目详解：
FTP（文件传输协议）使用两个独立的TCP连接：控制连接和数据连接。以下是各选项的详细分析：

A. 数据连接在每次数据传输完毕后就关闭
这是正确的。FTP的数据连接是“按需建立”的，每次传输文件时建立，传输完成后立即关闭。

B. 控制连接在整个会话期间保持打开状态
这是正确的。控制连接用于传输命令和响应，在整个FTP会话期间始终保持打开。

C. 服务器与客户端的TCP 20 端口建立数据连接
这是错误的。在主动模式（Active Mode）下，服务器确实从TCP 20端口发起数据连接，但客户端会随机选择一个端口（非20）来接收数据连接。在被动模式（Passive Mode）下，服务器会随机选择一个端口（非20）用于数据连接。因此，数据连接的端口并不固定为20。

D. 客户端与服务器的TCP 21 端口建立控制连接
这是正确的。控制连接默认使用服务器的TCP 21端口。

正确答案：C

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

表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。（3 分）

表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层（对应根结点）及操作数（对应叶结点）不需要添加括号。（2 分）

2、算法实现（10 分）

void preorder(node *root, int depth) {
  if (!root) {
    return;
  }
  bool isRoot = (depth == 1);
  bool isLeaf = (!root->left && !root->right);
  if (!isRoot && !isLeaf) {
    printf("(");
  }
  preorder(root->left, depth+1);
  printf("%s", root->data);
  preorder(root->right, depth+1);
  if (!isRoot && !isLeaf) {
    printf(")");
  }
}

void solve(node *root) {
  preorder(root, 1);
}

将二叉树的中序遍历递归算法稍加改造即可得本题答案。除根结点和叶结点外，遍历到其他结点时在遍历其左子树之前加上左括号，在遍历完右子树后加上右括号。

【评分说明】①若考生设计的算法满足题目的功能要求，则（1)、(2) 根据所实现算法的策略及输出结果给分，评分标准见下表。

②若考生采用其他方法得到正确结果，可参照①的评分标准给分。

③如果程序中使用了求结点深度等辅助函数，但没有给出相应的实现过程，只要考生进 行了必要的说明，可不扣分。

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

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

题目详解：
1）Prim 算法属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为止。算法每一步在连接树集合 $S$ 中顶点和其他顶点的边中，选择一条使得树的总权重增加最小的边加入集合 $S$。当算法终止时，$S$ 就是最小生成树。

1. $S$ 中顶点为 $A$，候选边为 $(A,D),(A,B),(A,E)$，选择 $(A,D)$ 加入 $S$。
2. $S$ 中顶点为 $A,D$，候选边为 $(A,B),(A,E),(D,E),(C,D)$，选择 $(D,E)$ 加入 $S$。
3. $S$ 中顶点为 $A,D,E$，候选边为 $(A,B),(C,D),(C,E)$，选择 $(C,E)$ 加入 $S$。
4. $S$ 中顶点为 $A,D,E,C$，候选边为 $(A,B),(B,C)$，选择 $(B,C)$ 加入 $S$。
5. $S$ 就是最小生成树。

依次选出的边为 $(A,D),(D,E),(C,E),(B,C)$（4 分）

【评分说明】每正确选对一条边且次序正确，给 1 分。若考生选择的边正确，但次序不完全正确，酌情给分。

2）图 $G$ 的 MST 是唯一的。（2 分）第一小题的最小生成树包括了图中权值最小的四条边，其他边都比这四条边大，所以此图的 MST 唯一。

3）当带权连通图的任意一个环中所包含的边的权值均不相同时，其 MST 是唯一的。（2 分）此题不要求回答充分必要条件，所以回答一个限制边权值的充分条件即可。

【评分说明】①若考生答案中给出的是其他充分条件，例如“带权连通图的所有边的权值均不相同”，同样给分。

②若考生给出的充分条件对图的顶点数和边数做了某些限制，例如，限制了图中顶点的个数（顶点个数少于 3 个）、限制了图的形状（图中没有环）等，则最高给 1 分。

③答案部分正确，酌情给分。

题目详解：
1）由于 ii 和 nn 是 unsigned 型，故 i ≤ n - l 是无符号数比较，n = 0 时，n - 1 的机器数为全 1，值是 $2^{32} - 1$，为 unsigned 型可表示的最大数，条件 i ≤ n - 1 永真，因此出现死循环。（2 分）

若 ii 和 nn 改为 int 类型则不会出现死循环。（1 分）

因为 i ≤ n - 1 是带符号整数比较，n = 0 时，n - 1 的值是 $-1$，当 i = 0 时条件 i ≤ n - 1 不成立，此时退出 for 循环。（1 分）

2）f1(23) 与 f2(23) 的返回值相等。（1 分）f(23) = $2^{23+1} - 1 = 2^{24} - 1$，它的二进制形式是 $24$ 个 $1$。int 占 $32$ 位，没有溢出。float 有 $1$ 个符号位，$8$ 个指数位，$23$ 个底数位，$23$ 个底数位可以表示 $24$ 位的底数。所以两者返回值相等。

f1(23) 的机器数是 00FF FFFFH。（1 分）

f2(23) 的机器数是 4B7F FFFFH。（1 分）

显而易见前者是 $24$ 个 $1$，即 0000 0000 1111 1111 1111 1111 1111 1111_{(2)}，后者符号位是 $0$，指数位为 $23 + 127_{10} = 1001 0110_{2}$，底数位是 111 1111 1111 1111 1111 1111_{2}。

3）当 n = 24 时，f(24) = 1 1111 1111 1111 1111 1111 1111 B，而 float 型数只有 $24$ 位有效位，舍入后数值增大，所以 f2(24) 比 f1(24) 大 $1$。（1 分）

【评分说明】只要说明 f2(24) 需舍入处理即可给分。

4）显然 f(31) 已超出了 int 型数据的表示范围，用 f1(31) 实现时得到的机器数为 $32$ 个 $1$，作为 int 型数解释时其值为 $-1$，即 f1(31) 的返回值为 $-1$。（1 分）

因为 int 型最大可表示数是 $0$ 后面加 $31$ 个 $1$，故使 f1(n) 的返回值与 f(n) 相等的最大 $n$ 值是 $30$。（1 分）

【评分说明】对于第二问，只要给出 $n = 30$ 即可给分。

5）IEEE754 标准用“阶码全 $1$、尾数全 $0$”表示无穷大。f2 返回值为 float 型，机器数 7F800000H 对应的值是 $+\infty$。（1 分）

当 $n = 126$ 时，f(126) = $2^{127} - 1 = 1.1…1 \times 2^{126}$，对应阶码为 $127 + 126 = 253$，尾数部分舍入后阶码加 $1$，最终阶码为 $254$，是 IEEE754 单精度格式表示的最大阶码。故使 f2 结果不溢出的最大 $n$ 值为 $126$。（1 分）

当 $n = 23$ 时，f(23) 为 $24$ 位 $1$，float 型数有 $24$ 位有效位，所以不需舍入，结果精确。故使 f2 获得精确结果的最大 $n$ 值为 $23$。（1 分）

【评分说明】对于第二问，只要给出 $n = 23$，即可给分。对于第三问，只要给出 $n = 126$，即可给分。

题目详解：
(1) 判断 M 的指令系统类型

• 答案: M 为 CISC。(1 分)
• 理由: M 的指令长短不一，不符合 RISC 指令系统特点。(1 分)

(2) 计算 f1 的机器代码长度

• 答案: f1 的机器代码占 96B。(1 分)
• 计算过程:
  f1 的第一条指令 push ebp 的虚拟地址为 0040 1020H，最后一条指令 ret 的虚拟地址为 0040 107FH。
  因此，机器指令代码长度为：
  0040 107FH - 0040 1020H + 1 = 60H = 96 字节。(1 分)

(3) 确定 CF 的值

• 答案: CF = 1。(1 分)
• 分析:
  cmp 指令实现 i 与 n - 1 的比较功能（减法运算）。
  执行 f1(0) 时，n = 0，i = 0 时：
  • i = 0000 0000H
  • n - 1 = FFFF FFFFH
    执行第 20 条指令时，补码运算器计算 0 减 FFFF FFFFH，即：
    0000 0000H + 0000 0001H = 0000 0001H
    此时进位输出 C = 0，减法借位标志 CF = C ⊕ 1 = 1。(2 分)

(4) 解释 f2 中不能用 shl 指令实现 power*2

• 答案: f2 中不能用 shl 指令实现 power*2。(1 分)
• 理由:
  shl 指令用于将整数的所有有效位整体左移；而 power 是 float 类型，其机器数包含阶码部分而非最高有效位。
  将 float 类型整体左移无法实现“乘 2”功能，因此不能用 shl 指令。(2 分)
  补充: 浮点数运算比整型运算更复杂且耗时更长。

题目详解：
1）函数 1 的代码段中所有指令的虚拟地址的高 20 位相同，因此 1 的机器指令代码在同 一页中，仅占用 1 页。（1 分）页目录号用于寻找页目录的表项，该表项包含页表的位置。页表 索引用于寻找页表的表项，该表项包含页的位置。

2）push ebp 指令的虚拟地址的最高 10 位（页目录号）为 0000000001，中间 10 位（页 表索引）为 0000000001，所以，取该指令时访问了页目录的第 1 个表项，（1 分）在对应的页 表中访问了第 1 个表项。（1 分）

3）在执行 scanf0 的过程中，进程 P 因等待输入而从执行态变为阻塞态。（1 分）输入结束 时，P 被中断处理程序唤醒，变为就绪态。（1 分）P 被调度程序调度，变为运行态。（1 分）CPU 状态会从用户态变为内核态。（1 分）

题目详解：
先找出线程对在各个变量上的互斥、并发关系。如果是一读一写或两个都是写，那么这就是互斥关系。每一个互斥关系都需要一个信号量进行调节。

// 冲突：
// t1 和 t3 关于 y 有读写冲突
// t2 和 t3 关于 y, z 都有读写冲突

// 解决 t1 和 t3 关于 y 读写冲突
semaphore y_mutex1 = 1;

semaphore y_mutex2 = 1;
semaphore z_mutex = 1;


// 全局变量 x y z
cnum x, y, z;

thread1()
{
  cnum w;
  // 读 x, y
  P(y_mutex1);
  w = add(x, y);
  V(y_mutex1);
  // ...
}

thread2()
{
  cnum w;
  // 读 y, z
  P(z_mutex);
  P(y_mutex2);
  w = add(y, z);
  V(y_mutex2);
  V(z_mutex);
  // ...
}

thread3()
{
  cnum w;
  w.a = 1;
  w.b = 1;
  // 写 z
  P(z_mutex);
  z = add(z, w);
  V(z_mutex);
  // 写 y
  P(y_mutex1);
  P(y_mutex2);
  y = add(y, w);
  V(y_mutex2);
  V(y_mutex1);
  // ...
}

【评分标准】

① 各线程与变量之间的互斥、并发情况及相应评分见下表。

② 考生仅使用一个互斥信号量，互斥代码部分的得分最多给 2 分。

③ 答案部分正确，酌情给分。

题目详解：
1）$t_0$ 时刻到 $t$ 时刻期间，甲方可以断定乙方已正确接收了 3 个数据帧（1 分），分别是 $S_{0,0}$、$S_{1,0}$、$S_{2,0}$（1 分）。$R_{3,3}$ 说明乙发送的数据帧确认号是 3，即希望甲发送序号 3 的数据帧，说明乙已经接收了序号为 0~2 的数据帧。

2）从 $t_1$ 时刻起，甲方最多还可以发送 5 个数据帧（1 分），其中第一个帧是 $S_{5,2}$（1 分），最后一个数据帧是 $S_{1,2}$（1 分）。发送序号 3 位，有 8 个序号。在 GBN 协议中，序号个数 ≥ 发送窗口 + 1，所以这里发送窗口最大为 7。此时已发送了 $S_{3,0}$ 和 $S_{4,1}$，所以最多还可以发送 5 个帧。

3）甲方需要重发 3 个数据帧（1 分），重发的第一个帧是 $S_{2,3}$（1 分）。在 GBN 协议中，接收方发送了 N 帧后，检测出错，则需要发送出错帧及其之后的帧。$S_{2,0}$ 超时，所以重发的第一帧是 $S_2$。已收到乙的 $R_2$ 帧，所以确认号应为 3。

$$\frac{7 \times \frac{8 \times 1000}{100 \times 10^6}}{0.96 \times 10^{-3} + 2 \times \frac{8 \times 1000}{100 \times 10^6}} \times 100\% = 50\%$$

4）甲方可以达到的最大信道利用率是

$$U = 发送数据的时间/从开始发送第一帧到收到第一个确认帧的时间 = \frac{N \cdot T_d}{T_d + RTT + T_a}$$

$U$ 是信道利用率，$N$ 是发送窗口的最大值，$T_d$ 是发送一数据帧的时间，$RTT$ 是往返时间，$T_a$ 是发送一确认帧的时间。这里采用捎带确认，$T_d = T_a$。

【评分说明】答案部分正确，酌情给分。