2025 年 408 真题
选择题
数据结构
1
以下 C 代码的时间复杂度是多少？
int count = 0;
for (int i=0; i*i<n; i++)
for (int j=0; j<i; j++)
count++;
外层循环的条件是 $i^2 < n$，因此 i 的最大值为 $\sqrt{n}$。 内层循环的的次数同样与 i 相同。所以总的循环次数为 $\sqrt{n} \sqrt{n} = n$， 时间复杂度为 $O(n)$。
2
对于括号匹配问题，符号栈初始为空，容量为 3，哪个表达式不能实现？
栈的容量为 3，意味着在任何时候，栈中的元素数量不能超过 3。需要选择一个在某些时刻栈的深度超过 3 的表达式。通过分析各个选项的嵌套深度，可以发现：
- A.
(a+[b+(c+d)e]+f)+g-h- 最深嵌套：
[(+)]，最多 2 个未匹配括号 ✅
- 最深嵌套：
- B.
[a*((b+c)/(d-e)+f/g)]-h- 最深嵌套：
[(())]，最多 3 个未匹配括号 ✅
- 最深嵌套：
- C.
[a*(b-(c-d)*e/(f+g))-h]- 最深嵌套：
[()()]，最多 3 个未匹配括号 ✅
- 最深嵌套：
- D.
[a-(b+[c*(d+e)-f]+g+h)]- 最深嵌套：
[([])]，最多 4 个未匹配括号 ❌
- 最深嵌套：
3
以下数组不能作为完全二叉树的是？
完全二叉树的特性：
- 按层填充，从左到右。
- 除最后一层外，所有层必须填满。
- 最后一层如果有空位，必须在右侧。
选项 D：-1 出现在中间，不符合完全二叉树，因为在非最后一层有空缺。
4
下列关于二叉树及森林的叙述中，正确的是？
5
设字符集 S 包含 7 个字符，各字符出现的频次分别是 2, 3, 4, 6, 10, 11。 为 S 中的各字符构造哈夫曼编码，编码长度不小于 3 的字符个数是：
按照哈夫曼树构造： 频次为 2, 3, 4, 6, 10, 11
- 合并 2+3=5
- 合并 4+5=9
- 合并 6+9=15
- 合并 10+11=21
- 合并 15+21=36
编码长度不小于 3 的字符：2, 3, 4, 6 答案：C （4 个字符）
6
下列关于图的叙述中，正确的是
逐个选项来看：
- A. 错误，考虑一个有向图的环，每个顶点的入度都为 1。
- B. 错误，拓扑排序不一定是唯一的，在计算拓扑排序序列的过程中，如果有多个入度为 0 的顶点，则拓扑序列的数量大于 1。
- C. 正确，所有顶点度 ≥2，则至少有一个环
- D. 错误，BFS 不能求 带权图 的最短路径
7
已知查找表中有 400 个元素，查找元素概率相同。采用分块查找法且均匀分块。 若采用顺序查找法确定元素所在块，且块内也采用顺序查找法，为效率最高， 每块包含元素应为
设块大小为 $m$，块数为 $\frac{n}{m}$。查找复杂度为 $O(n/m + m)$。
根据高中数学的知识可以得知，$m = \sqrt{n} = 20$ 时，查找复杂度最低，所以 $m = 20$。
8
给 7 个不同的关键字，能够构成不同 4 阶 B 树的个数为
- 树高为 3：每个节点内关键字个数最少取 1 时，B 树高度为 3（类似满二叉树）——仅一种结构；
- 树高为 2:
- 根节点关键字个数取 1，第二层两节点关键字个数均取 3——一种结构；
- 根节点关键字个数取 2，则第二层内三个节点关键字个数分别可取 221、212、122、311、131、113 共计六种结构；
- 根节点关键字个数取 3，则第二层显然只有四个节点各含一个关键字此一种结构。
综上，共计 9 种可能的结构。
9
下列关于散列法处理冲突的叙述中，正确的是
在散列（哈希）方法中，“同义词” 是指不同的元素通过哈希函数映射到同一个哈希值（或哈希地址）。这意味着这些元素在散列表中会发生冲突，因为它们试图占用相同的位置。
“非同义词”指的是通过哈希函数映射到不同哈希值的元素，它们通常不会在初始哈希地址上发生冲突。
对于题目中的选项：
A. 只要散列表不满，线性探查再散列一定能找到一个空闲位置。
线性探查是在发生冲突时，按顺序查找下一个可用位置。例如，如果发生冲突，就逐一检查下一个位置，直到找到空闲位置。只要散列表有空位，线性探查一定能找到一个空闲位置。因此，这个选项是正确的。
B. 只要散列表不满，二次探查再散列一定能找到一个空闲位置。
二次探查是通过二次函数（如平方）来决定下一个检查的位置。虽然理论上在某些情况下可能会更快找到空位，但由于散列表的装填因子和特定的探查序列，可能会有探查不到空闲位置的情况，因此这个选项不一定总是正确。
C. 线性探查再散列处理的冲突，一定是发生在同义词之间。
线性探查处理的冲突可能发生在同义词之间（即初始哈希值相同的元素），但也可能发生在非同义词之间（即由于探查过程而导致的冲突）。因此，这个选项是不正确的。
D. 二次探查再散列处理的冲突，一定是发生在非同义词之间。
二次探查可能会导致同义词和非同义词之间的冲突。因此，这个选项是不正确的。
10
下列排序算法中，最坏情况下元素移动最少的是
- 冒泡排序：最坏情况下，每个元素都需要交换，移动较多
- 直接插入排序：最坏情况下，每个元素要后移
- 快速排序：最坏情况需要大量交换
- 简单选择排序：最少交换，每次只交换一次
11
对含 9 个关键字的初始序列进行排序，若序列的变化情况如下表所示，则下列排序算法中，采用的是
| 初始序列 | 5, 25, 40, 30, 10, 20, 45, 15, 35 |
| 第 1 趟排序后的序列 | 5, 10, 20, 30, 15, 35, 45, 25, 40 |
| 第 2 趟排序后的序列 | 5, 10, 15, 25, 20, 30, 40, 35, 45 |
第一次排序后，下标相差 4 的子序列有序。 第二次排序后，下标相差 2 的子序列有序。 由此判断是希尔排序。
组成原理
12
在 32 位计算机上执行下列 C 语言代码：
short si = -32767
unsigned int ui = si;
则 ui 的真值为
16 位的 short 类型的 -32767 的二进制表示为 1000 0000 0000 0001，将其转化为 32 位的 unsigned 时，需要在最高位扩展 16 位。由于 -32767 (short) 的最高位为 1，所以扩展的高位全部为 1。
由此得到 32 位的 unsigned 的二进制是 1111 1111 1111 1111 1000 0000 0000 0001，其值为 $1 + 2^{15} + 2^{16} + \cdots + 2^{31} = 2^{32} - 2^{15} + 1$。
13
已知 float 型变量用 IEEE754 单精度浮点数格式表示。若 float 型变量 x 的机器数为 4730 0000H；则 x 的值为
将十六进制转化为二进制：0100 0111 0011 0000 0000 0000 0000 0000。
然后从中分解符号位、指数位和尾数位：
- 符号位：
0。 - 指数位：
1000 1110。 - 尾数位：
011 0000 0000 0000 0000 0000。
计算阶码：$1 × 2^7 + 0 × 2^6 + 0 × 2^5 + 0 × 2^4 + 1 × 2^3 + 1 × 2^2 + 1 × 2^1 + 0 × 2^0 = 128 + 8 + 4 + 2 = 142$。
计算尾数：$1 × 2^0 + 0 × 2^{-1} + 1 × 2^{-2} + 1 × 2^{-3} = 1 + 0 + 0.25 + 0.125 = 1.375$。
计算浮点数的值：$(-1)^{符号位} × 尾数 × 2^{指数} = 1 × 1.375 × 2^{15}$
14
假设 8 位字长的计算机中，两个带符号整数 x 和 y 的补码表示分别为 $x_{补} = A3H$， $y_{补} = 75H$，则通过补码加减运算器得到的 x-y 的值及 OF 标志分别为
x 的补码二进制表示为 1010 0011。y 的补码二进制表示为 0111 0101。
x-y = x+(-y) = 1010 0011 + 1000 1011 = 0010 1110 = 32 + 8 + 4 + 2 = 46。
二进制加法时最高位有进位，所以 OF = 1。
15
某 32 计算机按字节编址，采用小端方式存放数据，编译器按边界对齐方式为下列 C 语言结构型数组变量 employce 分配储存空间。
struct record {
int id;
char name[10];
int salary;
} employee[200];
数组 employee 的起始地址为 0000A0B0H，employee[1].id 的机器数为 12345678H，问 56H 的地址是多少？
在小端方式下，数据的存放顺序是从最低有效字节到最高有效字节。例如，对于一个 4 字节的整数 12345678H，存放顺序为 78H 56H 34H 12H。
首先，我们需要计算 struct record 的大小。根据定义：
int id; 占用 4 字节。char name[10]; 占用 10 字节。int salary; 占用 4 字节。
总共需要 18 字节。然而，由于编译器按边界对齐方式分配存储空间，通常会对齐到最接近的 4 字节边界。因此，struct record 实际上会占用 20 字节（因为 18 需要向上对齐到 20）。
数组 employee 的起始地址为 0000A0B0H。employee[1] 的起始地址为 0000A0B0H + 20 = 0000A0C4H
在 employee[1] 中，id 的值为 12345678H，存储在小端模式下：
- 地址 0000A0C4H 存放 78H
- 地址 0000A0C5H 存放 56H
- 地址 0000A0C6H 存放 34H
- 地址 0000A0C7H 存放 12H
因此，56H 的地址是 0000A0C5H。
16
下列选项中，由指令体系结构（ISA）规定的是
指令体系结构（ISA，Instruction Set Architecture）主要规定的是计算机系统中硬件和软件之间的接口，即指令的格式、操作码、操作数及寻址方式等。ISA 是软件开发人员和编译器设计者需要了解的部分，而硬件实现的具体细节通常由计算机体系结构的实现部分决定，而不是由 ISA 直接规定。
选项中：
- A. 是否采用阵列乘法器：这是实现层面的细节，属于硬件设计实现的一部分，不由 ISA 规定。
- B. 是否采用定长指令字格式：这是指令集架构的一部分，因为它直接影响指令的格式和解码过程，是由 ISA 规定的。
- C. 是否采用微程序控制器：这也是实现层面的细节，是关于如何实现控制单元的，不由 ISA 规定。
- D. 是否采用单总线数据通路：这是实现层面的细节，与具体的硬件设计有关，不由 ISA 规定。
17
下列关于 RISC 的叙述中，错误的是
RISC 设计的一个显著特点是易于采用流水线技术，从而提高指令执行的吞吐量。因此，RISC 体系结构并不难以采用流水线数据通路，因此 C 选项错误。
18
下列关于 CPI 和 CPU 时钟周期的叙述中，错误的是
- A. 不同类型指令的 CPI 可能不一样：这是正确的，不同类型的指令由于其复杂度和执行步骤的不同，可能会有不同的 CPI（每条指令的平均时钟周期数）。✅
- B. 程序的 CPI 会受到 Cache 缺失率的影响，因为 Cache 缺失会导致额外的内存访问延迟，从而增加指令执行的平均时钟周期数。❌
- C. 在单周期 CPU 设计中，每条指令在一个时钟周期内完成，所以时钟周期必须足够长以涵盖最耗时的指令。✅
- D. 因为在流水线 CPU 中，时钟周期必须能够满足流水线中所有阶段的时间要求，因此时钟周期通常以最长的流水段为基准。✅
19
下列关于 CPU 中的数据通路和控制器的叙述中，错误的是
- A. 程序计数器（PC）是一个专用寄存器，用于存储下一条要执行指令的地址，它不属于通用寄存器组。通用寄存器组通常是用于算术、逻辑和数据存储等操作的寄存器，而程序计数器有其专门的用途和存储。❌
- B. 控制器中一定包含指令操作码的译码电路：这是正确的。控制器需要对指令操作码进行译码，以确定应执行的操作和控制信号。✅
- C. 单周期 CPU 的每条指令在一个时钟周期内完成，控制逻辑较为简单，而多周期 CPU 需要复杂的控制逻辑来管理每个周期的操作。✅
- D. 流水线 CPU 由于同时处理多条指令，会遇到数据冒险、控制冒险等问题，需要通过转发、暂停、分支预测等技术来解决。✅
20
某处理器总线采用同步，并行传输方式，每个总线时钟周期传送 4 次数据 （quadpumped 技术），若该总线的工作频率为 1333MHz（实际单位是 MT/s，表示 每秒传送 1333M/次），总线宽度为 64 位，则总线带宽约为
题目中没告诉你总线的时钟频率，而是告诉你了总线的工作频率（每秒传送 1333M 个字）， 然后总线宽度等于字长为 8B，所以总线带宽 = 1333M/s * 8B = 10.66GB/s。
21
下列设备中，适合采用 DMA 输入输出的设备是
I. 键盘
II. 网卡
III. 固态硬盘
IV. 针十式打印机
网卡和固态硬盘通常适合采用DMA（直接内存访问）进行输入输出，因为它们需要处理大量的数据传输，DMA可以有效地提高数据传输效率而不占用CPU资源。键盘和针式打印机的数据传输量较小，通常不需要使用DMA。
22
下列选项中，会触发外部中断请求的事件是
外部中断请求通常是由外部设备或硬件事件触发的。DMA传送结束是由DMA控制器发出的中断请求，用于通知CPU数据传输已经完成，这属于外部中断。而其他选项通常与内部事件或软件处理相关，不属于外部中断。
操作系统
23
在采用页式虚拟存储管理方式的系统中，当发生上下文切换时，下列寄存器中操作 系统不需要更新的是
在上下文切换时，操作系统需要保存和恢复与当前进程相关的状态信息。通用寄存器、页表基址寄存器和程序计数器通常会在上下文切换时更新，以切换到新进程的上下文。然而，内核中断向量表基址寄存器通常是系统级的，通常不会在每次上下文切换时更改，因此操作系统不需要在上下文切换时更新该寄存器。
24
关于虚拟化技术，下列说法错误的是
虚拟机监控器（VMM，或虚拟机管理程序）通常运行在更高的特权级别，以便管理和控制虚拟机的运行。它需要比普通操作系统更高的权限来有效地虚拟化硬件资源。因此，VMM与操作系统特权级相同的说法是错误的。其他选项均是虚拟化技术的正确描述。
25
优先权调度，采用单链表保存进程就绪队列，高优先级进程在队头。就绪队列长度为 n，则插入进程、选出进程的时间复杂度
在优先权调度中，如果我们采用单链表来保存进程就绪队列，并且高优先级进程在队头，那么：
- 插入进程时，需要根据优先级找到合适的位置插入，因此时间复杂度为 O(n)。
- 选出进程（即从队头选出最高优先级的进程）是一个 O(1) 的操作，因为高优先级的进程总是在队头。
26
现有一 LRU 算法，固定分配局部置换，已为进程分配 3 个页框，页面访问序列为 {0,1,2,0,5,1,4,3,0,2,3,2,0}，其中 0,1,2 已调入内存。则缺页次数是
在 LRU（Least Recently Used）算法中，每当需要访问一个不在当前内存中的页面时，就需要进行置换操作，并选择当前内存中最久未使用的页面进行替换。我们按照给定的页面访问序列进行模拟：
初始状态：内存中页面为 {0, 1, 2}，访问序列：
- 访问 0：命中
- 访问 1：命中
- 访问 2：命中
- 访问 0：命中
- 访问 5：缺页，替换页面 2，内存中页面为 {0, 1, 5}
- 访问 1：命中
- 访问 4：缺页，替换页面 0，内存中页面为 {4, 1, 5}
- 访问 3：缺页，替换页面 5，内存中页面为 {4, 1, 3}
- 访问 0：缺页，替换页面 1，内存中页面为 {4, 0, 3}
- 访问 2：缺页，替换页面 4，内存中页面为 {2, 0, 3}
- 访问 3：命中
- 访问 2：命中
- 访问 0：缺页，替换页面 3，内存中页面为 {2, 0, 3}
总计缺页次数为 6 次。
27
确定进程运行所需的最少页框数时，要考虑的指标是
28
关于虚拟文件系统，下列说法正确的是
虚拟文件系统（VFS）是一个抽象层，提供了一种统一的接口，使操作系统能够支持不同类型的文件系统。它通过这种抽象，使得上层应用程序可以通过统一的接口访问不同的底层文件系统，而不需要关心底层文件系统的具体实现细节。
- A 是错误的：虚拟文件系统不是运行在虚拟内存的文件系统，而是一个抽象层。
- B 是错误的：VFS 的主要目的是提供统一接口，而不是直接加快访问速度，尽管统一接口可以间接提升开发效率。
- D 是错误的：VFS 能够支持访问包括本地和网络文件系统在内的多种文件系统类型。
29
某文件系统采用索引节点方式。用户在目录中新建文件 F 时，文件系统不会做的是
当用户在目录中新建文件 F 时，文件系统通常会执行以下操作：
- A. 初始化文件 F 的索引节点：为新文件创建一个索引节点，并初始化相关信息。
- B. 在目录文件中写入 F 的索引节点号：在目录中为文件 F 创建一个目录项，该目录项包含文件名和其对应的索引节点号。
- D. 在目录文件中增加一条文件 F 对应的目录项：在目录中增加一个新的目录项来表示新文件 F。
选项 C 是错误的，因为访问权限信息通常存储在文件的索引节点中，而不是在目录文件中。目录文件只记录文件名及其对应的索引节点号。
30
关于内存映射文件，下列说法正确的是
I. 可实现进程间通信
II. 实现了页面到磁盘块的映射
III. 将文件映射到进程的虚拟地址空间
IV. 将文件映射到系统的物理地址空间
- I. 内存映射文件可以用于进程间通信，因为多个进程可以将同一个文件映射到各自的虚拟地址空间，从而共享数据。✅
- II. 内存映射文件确实实现了页面到磁盘块的映射。操作系统会将文件内容映射到内存页面，并在需要时将页面与磁盘块进行交换。✅
- III. 内存映射文件的核心概念就是将文件映射到进程的虚拟地址空间，使得进程可以通过访问内存来操作文件。✅
- IV. 内存映射文件是将文件映射到进程的虚拟地址空间，而不是直接映射到物理地址空间。虚拟地址空间最终会通过操作系统的内存管理单元（MMU）映射到物理地址空间。❌
所以正确的是 I、II、III
31
下列选项中，文件系统能知道外存空闲空间使用情况的是
文件分配表（FAT）是文件系统用来记录磁盘块（簇）使用情况的数据结构。它记录了哪些磁盘块是空闲的，哪些已经被文件占用，因此文件系统可以通过 FAT 来管理空闲空间。
- A. 目录用于存储文件和子目录的元数据（如文件名、位置等），但不直接管理空闲空间。
- B. 系统打开文件表：用于记录当前打开的文件及其状态，与空闲空间管理无关。
- D. 进程控制块（FCB）：用于记录进程的状态信息，与文件系统的空闲空间管理无关。
32
下列选项中，文件系统能为温彻斯特硬盘和固态硬盘提供的功能是
文件系统负责管理存储设备上的数据，其中一个重要功能是确定盘块（或簇）的大小。无论是温彻斯特硬盘还是固态硬盘，文件系统都可以根据其特性选择合适的盘块大小来优化存储和访问效率。
- A. 划分扇区：扇区是硬盘的物理特性，由硬件决定，文件系统不负责划分扇区。
- C. 降低寻道时间：这是针对温彻斯特硬盘的优化，文件系统可以通过优化数据布局来减少磁头的移动，但这不适用于固态硬盘（SSD），因为 SSD 没有机械寻道过程。
- D. 实现均衡磨损：这是针对固态硬盘的特性，由 SSD 的固件或控制器负责，文件系统通常不直接参与。
因此正确选项是 B。
计算机网络
33
如下图所示，主机 H1 向 H2 发送一个 2MB（1MB = $10^6$B）文件有三种方式：① 电路交换，建立时间为 32us，速度为 10Mbps；② 分组交换，分组长度为 400B，忽略首部；③ 报文交换。电路交换的时间为 $T_{cs}$，报文交换的时间为 $T_{ms}$，分组交换的时间为 $T_{ps}$，则三者的大小关系是
电路交换的时间 $T_{cs}$ = 连接建立时间 + 数据传输时间 = 32us + 2MB / 10Mbps
报文交换的时间 $T_{ms}$ = 各链路传输时间之和 = 2MB/10Mbps + 2MB/100Mbps + 2MB/1000Mbps
分组交换的时间 $T_{ps}$ = 考虑分组传输 overlap 的时间 = 2MB/10Mbps + 400B/100Mbps + 400B/1000Mbps
经计算可知 $T_{ms} > T_{ps} > T_{cs}$。
34
某差错编码的编码集为{ 10011010，01011100，11110000，00001111 }，其检错和纠错能力是
要判断一个编码集的检错和纠错能力，我们需要了解码字之间的汉明距离（Hamming distance）。汉明距离是指两个等长字符串之间不同位的数量。
首先，我们计算编码集中每对码字之间的汉明距离：
- 10011010 和 01011100 的汉明距离是 6。
- 10011010 和 11110000 的汉明距离是 4。
- 10011010 和 00001111 的汉明距离是 6。
- 01011100 和 11110000 的汉明距离是 6。
- 01011100 和 00001111 的汉明距离是 4。
- 11110000 和 00001111 的汉明距离是 8。
编码集中最小的汉明距离是 4。
对于一个编码集：
- 如果最小汉明距离为 d，那么该编码可以检测到不超过 d-1 位的错误。
- 该编码可以纠正 ⌊(d-1)/2⌋ 位错误。
在这个例子中，最小汉明距离 d = 4。
因此，该编码集可以：
- 检测不超过 3 位的错误。
- 纠正 ⌊(4-1)/2⌋ = 1 位的错误。
综上所述，正确答案是 C。
35
现有一 10BaseT 以太网，甲乙处于同一个冲突域，连续发生 11 次冲突，甲再次发送的最大时间间隔为
在以太网中，当发生冲突时，发送节点将执行指数退避算法（Exponential Backoff Algorithm）。在这个算法中，节点在重传之前会等待一个随机的时间间隔，这个时间间隔是以时隙（slot time）为单位计算的。
对于10BaseT以太网，时隙时间（slot time）为 51.2 微秒（0.0512 毫秒）。
在指数退避算法中，第 n 次重传时，节点会从 $0$ 到 $2^n - 1$ 的范围内随机选择一个整数 k，然后等待 k 个时隙的时间。需要注意的是，当 n 达到 10 或更大时，退避范围的上限固定为 1023（即 $2^{10} - 1$）。
在题目中，已经发生了 11 次冲突，意味着这是第 12 次重传尝试。因此，n = 11，但因为 $n \ge 10$ 的时候，k 的范围是 0 到 1023。
因此，甲再次发送的最大时间间隔为 1023 个时隙时间，即：
$$1023 \times 51.2 us = 52.4288ms$$
36
一台新接入网络的主机 H 通过 DHCP 服务器动态请求 IP 地址过程中，与 DHCP 服 务器交换 DHCP 报文过程如下图所示。封装 DHCP 的 REQUEST 报文的 P 数据报 的目的 IP 地址和源 IP 地址分别是
目的 IP 地址：DHCP 服务器的 IP 地址或者广播地址（255.255.255.255），因为主机可能不知道 DHCP 服务器的确切 IP 地址，尤其是在初始请求阶段，广播地址确保网络中的所有 DHCP 服务器都能接收到请求。
源 IP 地址：0.0.0.0，因为主机还未获得正式的 IP 地址，在这个阶段它使用 0.0.0.0 作为源地址来表示“没有 IP 地址”。
37
假设路由器实现 NAT 功能，内网中主机 H 的 IP 地址为 192.168.1.5/24。若 H 运行 某应用向 internet 发送一个 UDP 报文段，则路由器在转发封装该 UDP 报文段的 IP 数据报的过程中，UDP 报文的首部字段会被修改的是
I 源端口号
II 目的端口号
III 总长度
IV 校验和
- I. 源端口号：在 NAT 实现中，路由器可能会修改源端口号以便在多个内部主机使用相同外部 IP 地址时区分不同的会话。因此，源端口号可能会被修改。
- II. 目的端口号：通常不会被 NAT 修改，因为目的端口号用于指明接收方应用程序的端口。
- III. 总长度：UDP 报文段的总长度字段通常不会因为 NAT 而改变，因为 NAT 主要修改 IP 地址和源端口号，数据包的总长度保持不变。
- IV. 校验和：如果 NAT 修改了源 IP 地址或源端口号，导致 UDP 报文段的内容发生变化，UDP 校验和需要重新计算，因此校验和字段可能会被修改。
因此，路由器在转发封装该 UDP 报文段的过程中，可能会修改的字段是源端口号和校验和，答案选 B。
38
主机甲通过 TCP 向主机乙发送数据的部分过程如下图，seq 为序号，ack-seq 为确 认序号，rcwnd 为接收窗口。甲在 $t_0$ 时刻的拥塞窗口和发送窗口均为 2000B，拥塞 控制阈值为 8000B，MSS=1000B。甲始终以 MSS 发送 TCP 段。若甲在 $t_1$ 时刻收到 如图所示的确认段，则甲在未收到新的确认段之前，还可以继续向乙发送的 TCP 段数是
根据 ack_seq = 3001 可知，目前乙已经接收到了 1000B 的数据即一个 1 个 MSS，seq = 3001 的 MSS 仍然在发送中。 此时乙的接收窗口为 4 个 MSS，所以仍然可以发送的 MSS 个数为 4-2=2。
39
Time 是一个提供时间查询服务的 C/S 架构网络应用，支持客户通过 UDP 和 TCP 向 Time 服务器请求时间。若某客户与 Time 服务器通信往返时间为 8ms，则该客户分 别通过 UDP 和 TCP 向该服务器请求服务，所需的最少时间分别是
读题可知，RTT = 8ms，使用 UDP 进行传输只需要一个 RTT，而使用 TCP 三次握手需要两个 RTT 共 16ms。
40
关于 POP3，正确的是（）
I 支持用户代理从邮件服务器读取邮件
II 支持用户代理向邮件服务器发送邮件
III 支持邮件服务器之间发送与接收邮件
IV 支持一条 TCP 连接收取多封邮件
- I. 支持用户代理从邮件服务器读取邮件：✅。POP3 的主要功能就是支持客户端（用户代理）从邮件服务器读取邮件。
- II. 支持用户代理向邮件服务器发送邮件：❌。发送邮件的功能通常由 SMTP（Simple Mail Transfer Protocol）负责，而不是 POP3。
- III. 支持邮件服务器之间发送与接收邮件：❌。邮件服务器之间的邮件传输通常由 SMTP 协议处理，而不是 POP3。
- IV. 支持一条 TCP 连接收取多封邮件：✅。POP3 可以在一个会话中通过一条 TCP 连接获取用户邮箱中的多封邮件。
所以 I、IV 是正确的。
解答题
数据结构
41
设有两个长度均为 n 的一维整型数组 A 和 res，对数组 A 中的每个元素 A[i]，计算 A[i]
与 A[j]（0 ≤ i ≤ j ≤ n-1）乘积的最大值，并将其保存到 res[i]中。
例如，若 A[i] = {1, 4, -9, 6}，则得到 res[i] = {6, 24, 81, 36}。
现给定数组 A，请设计一个时间和空间上尽可能高效的算法 calMulMax，
求 res 中各元素的值。函数原型为：void calMulMax(int A[], int res[], int n)，
要求：
(1) 给出算法的基本设计思想：（4 分）
(2) 根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释：（7 分）
(3) 说明你所设计算法的时间复杂度和空间复杂度。（2 分）
42
AOE 网，描述 12 个工程活动及持续时间
(1) 完成该工程的最短时间是多少？哪些是关键活动？
(2) 若以最短时间完成工程，则与活动 e 同时进行的活动可能有哪些？
(3) 时间余量最大的活动是哪个？其时间余量是多少？
(4) 假设工程从时刻 0 启动，因某种原因，活动 b 在时刻 6 开始，为保证工程不延期，在其它活动持续时间保持不变的情况下， b 的持续时间最多是多少？若不改变 b 的持续时间，则压缩哪个活动的持续时间也能保证工程不延期？
组成原理
43
计算机 M 字长为 32 位，按字节编址，数据 cache 的数据区大小为 32KB，采 8 路组相联，主存块大小为 64B，cache 命中时间为 2 个时钟周期，缺失损失为 200 个时钟周期，采用页式虚拟存储，页大小为 4KB。数组 d 的起始地址为 0180 0020H(VA31~VA0)
(1) 主存地址中的 Cache 组号，块内地址分别占几位？VA 中哪些位可以作为 Cache 索引。
(2) d[100] 的 VA 是多少？d[100]所在主存块中对应的 Cache 组号是多少？
(3) 设代码已经在 cache 中，i,x 已装入内存，但不在 cache，则 d[0]在其主存块内的偏移量是多少？执行 for 的过程中，访问 d 的 Cache 缺失率和数组元素的平均访问时间分别是多少？（缺失率用百分比表示，保留两位小数）
(4) d 分布在几个页中？若代码已在主存，d 不在主存，则执行 for 的过程中，访问 d 所引起的缺页次数是？
int x, d[2048], i;
for (i = 0; i < 2048; i++)
d[i] = d[i]/x;
44
接上题，R0~R4 为通用寄存器，SEXT 表示按符号扩展，M 中补码除法器，逻辑结构图如下：
机器级代码：
// x 在 R2 中，i 在 R4 中
// 数组 d 的首地址在 R3 中
mov R1,(R3+R4*4) // R1 ← d[i]
scov R1 // {R0,R1} ← SEXT(R1)
idiv R1 // R1<-({R0,R1}/R2)
(1) 若执行 idiv 指令时，d[i]=0x87654321，x=0xff，则补码除法器中 R、Q、Y 的初始值分别为多少（用十六进制表示）？ 图 b 中哪个部分包含计数器？在补码除法器执行过程中，ALUop 所控制的 ALU 运算有哪几种？
(2) 假设 idiv 执行过程中会检测并触发除法异常，则执行 idiv 指令时，哪些情况下会发生除法异常（要求给出此时 d[i] 和 x 的十六进制机器数）。 发生除法异常时，在异常响应过程中，CPU 需要完成哪些操作？
操作系统
45
三个人一起植树，甲挖坑，乙放树苗入坑并填土，丙负责为新种树苗浇水。步骤依次为：挖树坑，放树苗，填土和浇水。现在有铁锹和水桶各一个，铁锹用于挖树坑，填土。水桶用于浇水。当树坑数量小于 3 时，甲才可以挖树坑。设初始坑 = 0，铁锹水桶均可用，定义尽可能少的信号量，用 wait() 和 signal() 操作描述植树过程中三人的同步互斥关系，并说明所用信号量的作用及其初值。
46
某进程的虚拟地址空间如图，阴影部分为未占用区域，有 C 程序：
char * ptr;
void main() {
int length;
ptr=(char*) malloc(100);
scanf("%s", ptr);
length = strlen(ptr);
printf("length=%d\n", length);
free(ptr) ;
}
(1) 上述程序执行时，PCB 位于哪个区域，执行 scanf ()等待键盘输入时，该进程处于什么状态？
(2) main() 函数的代码位于哪个区域？其直接调用的哪些函数的功能需要通过执行驱动程序实现？
(3) 变量 ptr 被分配在哪个区域？若变量 length 没有被分配在寄存器中，则会被分配在哪个区域？ptr 指向的字符串位于哪个区域？
计算机网络
47
(1) 忽略卫星信号中继，TR1，TR2 调制解调开销，则 R1 到 R2 之间的卫星链路单向传播时延是多少？主机 H 向总部服务器传输数据时可达到的最大吞吐量是多少？若忽略各层协议首部开销，以及以太网的传播时延，则 H → server 上传一个 4000B 的文件，至少需要多长时间？
(2) 基于 GBN 为卫星链路设计单向可靠的链路层协议 SLP，支持 R1 → R2 发送数据。SLP 数据帧长 1500B，忽略 ACK 帧长度，要求 SLP 单向信道利用率不低于 80%，则发送窗口至少为？SLP 帧序号至少为多少？
(3) 总部给工程部分配 IP 地址空间 10.10.10.0/24，再划分为 3 个子网，生活区子网不少于 120 个，作业子网，管理区子网 IP 均不少于 60 个，H 已正确配置 IP。问作，管，生子网地址各是多少？