2025 年 408 真题

栈的容量为 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 个未匹配括号，错误。

完全二叉树的特性：

• 按层填充，从左到右。
• 除最后一层外，所有层必须填满。
• 最后一层如果有空位，必须在右侧。

选项 D：-1 出现在中间，不符合完全二叉树，因为在非最后一层有空缺。

完全二叉树中，度为 1 的结点可能存在。比如一颗完全二叉树只有两个结点，那么根结点的度就是 1。A 选项错误。

森林转二叉树 有固定的方法，B 选项正确。

按照 哈夫曼树 构造：频次为 2, 3, 4, 6, 10, 11

1. 合并 2+3=5
2. 合并 4+5=9
3. 合并 6+9=15
4. 合并 10+11=21
5. 合并 15+21=36

可以得到以下二叉树：

            [36]
           /    \
        [15]    [21]
       /   \    /   \
    [6]   [9] [10] [11]
          / \
        [4] [5]
            / \
          [2] [3]

编码长度不小于 3 的字符：2, 3, 4 答案：B（3 个字符）

逐个选项来看：

• A. 错误，考虑一个有向图的环，每个顶点的入度都为 1。
• B. 错误，拓扑排序不一定是唯一的，在计算拓扑排序序列的过程中，如果有多个入度为 0 的顶点，则拓扑序列的数量大于 1。
• C. 正确，无环的图至少有一个顶点的度为 1，如果所有顶点的度都大于 1 了，那图中肯定存在环。
• D. 错误，BFS 不能求 带权图 的最短路径，求最短路径是使用 Djkstra 算法。

设块大小为 $m$，块数为 $\frac{n}{m}$。查找复杂度为 $O(n/m + m)$。

根据高中数学的知识可以得知，$m = \sqrt{n} = 20$ 时，查找复杂度最低，所以 $m = 20$。

• 树高为 3：每个节点内关键字个数最少取 1 时，B 树 高度为 3（类似满二叉树）——仅一种结构；
• 树高为 2:
  • 根节点关键字个数取 1，第二层两节点关键字个数均取 3——一种结构；
  • 根节点关键字个数取 2，则第二层内三个节点关键字个数分别可取 221、212、122、311、131、113 共计六种结构；
  • 根节点关键字个数取 3，则第二层显然只有四个节点各含一个关键字此一种结构。

综上，共计 9 种可能的结构。

在散列（哈希）方法中，同义词 是指不同的元素通过哈希函数映射到同一个哈希值（或哈希地址)。这意味着这些元素在散列表中会发生冲突，因为它们试图占用相同的位置。

非同义词 指的是通过哈希函数映射到不同哈希值的元素，它们通常不会在初始哈希地址上发生冲突。

对于题目中的选项：

A. 只要散列表不满，线性探查再散列一定能找到一个空闲位置。

线性探查是在发生冲突时，按顺序查找下一个可用位置。例如，如果发生冲突，就逐一检查下一个位置，直到找到空闲位置。只要散列表有空位，线性探查一定能找到一个空闲位置。因此，这个选项是正确的。

B. 只要散列表不满，二次探查再散列一定能找到一个空闲位置。

二次探查是通过二次函数（如平方）来决定下一个检查的位置。虽然理论上在某些情况下可能会更快找到空位，但由于散列表的装填因子和特定的探查序列，可能会有探查不到空闲位置的情况，因此这个选项不一定总是正确。

C. 线性探查再散列处理的冲突，一定是发生在同义词之间。

线性探查处理的冲突可能发生在同义词之间（即初始哈希值相同的元素），但也可能发生在非同义词之间（即由于探查过程而导致的冲突）。因此，这个选项是不正确的。

D. 二次探查再散列处理的冲突，一定是发生在非同义词之间。

二次探查可能会导致同义词和非同义词之间的冲突。因此，这个选项是不正确的。

本题考察 无符号数 和 有符号数 的补码表示。

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$。

本题考察 IEEE 单精度浮点数表示。首先将十六进制转化为二进制：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}$

x 的补码二进制表示为 1010 0011。y 的补码二进制表示为 0111 0101。

x-y = x+(-y) = 1010 0011 + 1000 1011 = 0010 1110 = 32 + 8 + 4 + 2 = 46.

二进制加法时最高位有进位，所以 OF = 1。

在 小端方式 下，数据的存放顺序是从最低有效字节到最高有效字节。例如，对于一个 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。

指令体系结构主要规定的是计算机系统中硬件和软件之间的接口，即指令的格式、操作码、操作数及寻址方式等。ISA 是软件开发人员和编译器设计者需要了解的部分，而硬件实现的具体细节通常由计算机体系结构的实现部分决定，而不是由 ISA 直接规定。

选项中：

• A. 是否采用阵列乘法器：这是实现层面的细节，属于硬件设计实现的一部分，不由 ISA 规定。
• B. 是否采用定长指令字格式：这是指令集架构的一部分，因为它直接影响指令的格式和解码过程，是由 ISA 规定的。
• C. 是否采用微程序控制器：这也是实现层面的细节，是关于如何实现控制单元的，不由 ISA 规定。
• D. 是否采用单总线数据通路：这是实现层面的细节，与具体的硬件设计有关，不由 ISA 规定。

• A. 不同类型指令的 CPI 可能不一样：这是正确的，不同类型的指令由于其复杂度和执行步骤的不同，可能会有不同的 CPI（每条指令的平均时钟周期数）。✅
• B. 程序的 CPI 会受到 Cache 缺失率的影响，因为 Cache 缺失会导致额外的内存访问延迟，从而增加访存型指令比如 LOAD 执行的平均时钟周期数。❌
• C. 在单周期 CPU 设计中，每条指令在一个时钟周期内完成，所以时钟周期必须足够长以涵盖最耗时的指令。✅
• D. 因为在流水线 CPU 中，时钟周期必须能够满足流水线中所有阶段的时间要求，因此时钟周期通常以最长的流水段为基准。✅

• A. 程序计数器（PC）是一个专用寄存器，用于存储下一条要执行指令的地址，它不属于通用寄存器组。通用寄存器组通常是用于算术、逻辑和数据存储等操作的寄存器，而程序计数器有其专门的用途和存储。❌
• B. 控制器中一定包含指令操作码的译码电路：这是正确的。控制器需要对指令操作码进行译码，以确定应执行的操作和控制信号。✅
• C. 单周期 CPU 的每条指令在一个时钟周期内完成，控制逻辑较为简单，而多周期 CPU 需要复杂的控制逻辑来管理每个周期的操作。✅
• D. 流水线 CPU 由于同时处理多条指令，会遇到数据冒险、控制冒险等问题，需要通过转发、暂停、分支预测等技术来解决。✅

总线带宽 = 总线频率 × 每次传输的数据量 × 传输次数

• 总线工作频率为 1333 MHz（即 1333 MT/s，每秒传输 1333 百万次）。
• 每个总线时钟周期传输 4 次数据（quadpumped 技术）。
• 总线宽度为 64 位即 8 字节。

所以总线每秒传输的数据量为 1333M × 8B × 4 ≈ 42.66G，答案选 B。

A. 操作系统可以在虚拟机上运行 ✅
正确。虚拟机（VM）提供了一个与真实硬件类似的环境，操作系统可以像在物理机上一样运行在虚拟机中。

B. 一台主机可以支持多个虚拟机 ✅
正确。虚拟化的核心能力之一就是在同一物理主机上运行多个虚拟机实例，每个实例看起来像是一台独立的机器。

C. VMM 与操作系统特权级相同 ❌
错误。VMM（虚拟机监控器或 Hypervisor）通常运行在比普通操作系统更高的特权级，因为它需要控制底层硬件资源，并管理多个客户操作系统。例如在 x86 架构中，VMM 通常在Ring -1（即硬件支持的更低层）运行，而操作系统在 Ring 0。 即使是某些 Type 2 Hypervisor（如 VMware Workstation）运行在宿主操作系统上，也会通过硬件辅助（如 Intel VT-x）获得高特权级访问。

D. 通过虚拟机技术，可以用一台主机上模拟多种 ISA ✅
正确，尽管这项功能涉及更多的是 仿真（emulation） 而非传统虚拟化。例如使用 QEMU 可以在 x86 主机上模拟 ARM、MIPS 等架构。不过现代虚拟化系统也可以部分结合硬件虚拟化技术来提高效率。

所以正确答案是：C。

在 优先级调度 中，如果我们采用单链表来保存进程就绪队列，并且高优先级进程在队头，那么：

• 插入进程时，需要根据优先级找到合适的位置插入，因此时间复杂度为 O(n)。
• 选出进程（即从队头选出最高优先级的进程）是一个 O(1) 的操作，因为高优先级的进程总是在队头。

在 LRU 算法中，每当需要访问一个不在当前内存中的页面时，就需要进行置换操作，并选择当前内存中最久未使用的页面进行替换。我们按照给定的页面访问序列进行模拟：

初始状态：内存中页面为 {0, 1, 2}，访问序列：

1. 访问 0：命中
2. 访问 1：命中
3. 访问 2：命中
4. 访问 0：命中
5. 访问 5：缺页，替换页面 2，内存中页面为 {0, 1, 5}
6. 访问 1：命中
7. 访问 4：缺页，替换页面 0，内存中页面为 {4, 1, 5}
8. 访问 3：缺页，替换页面 5，内存中页面为 {4, 1, 3}
9. 访问 0：缺页，替换页面 1，内存中页面为 {4, 0, 3}
10. 访问 2：缺页，替换页面 4，内存中页面为 {2, 0, 3}
11. 访问 3：命中
12. 访问 2：命中
13. 访问 0：缺页，替换页面 3，内存中页面为 {2, 0, 3}

总计缺页次数为 6 次。

代码段长，是指程序中机器指令部分（即代码段）的大小。操作系统要让程序至少能运行，就必须将它的关键指令（至少部分代码段）加载进内存。所以代码段越长，理论上需要的页框数越多。A 选项正确。

虚拟地址空间定义了进程可能使用的地址范围，但不代表实际需要这么多物理页框。B 选项错误。

物理地址空间大小是整个系统的内存容量，与某一进程最少需要多少页框无直接关系。C 选项错误。

指令系统支持的寻址方式是硬件层面的设计，影响寻址能力，但不是决定进程所需最小页框数的直接因素。D 选项错误。

虚拟文件系统 是一个抽象层，提供了一种统一的接口，使操作系统能够支持不同类型的文件系统。它通过这种抽象，使得上层应用程序可以通过统一的接口访问不同的底层文件系统，而不需要关心底层文件系统的具体实现细节。

• A 是错误的：虚拟文件系统不是运行在虚拟内存的文件系统，而是一个抽象层。
• B 是错误的：VFS 的主要目的是提供统一接口，而不是直接加快访问速度，尽管统一接口可以间接提升开发效率。
• D 是错误的：VFS 能够支持访问包括本地和网络文件系统在内的多种文件系统类型。

当用户在目录中新建文件 F 时，文件系统通常会执行以下操作：

• A. 初始化文件 F 的 索引节点：为新文件创建一个索引节点，并初始化相关信息。
• B. 在 目录文件 中写入 F 的索引节点号：在目录中为文件 F 创建一个目录项，该目录项包含文件名和其对应的索引节点号。
• D. 在目录文件中增加一条文件 F 对应的目录项：在目录中增加一个新的目录项来表示新文件 F。

选项 C 是错误的，因为访问权限信息通常存储在文件的索引节点中，而不是在目录文件中。目录文件只记录文件名及其对应的索引节点号。

本题考察 内存映射文件，现对选项进行逐一分析：

• I. 内存映射文件可以用于进程间通信，因为多个进程可以将同一个文件映射到各自的虚拟地址空间，从而共享数据。✅
• II. 内存映射文件确实实现了页面到磁盘块的映射。操作系统会将文件内容映射到内存页面，并在需要时将页面与磁盘块进行交换。✅
• III. 内存映射文件的核心概念就是将文件映射到进程的虚拟地址空间，使得进程可以通过访问内存来操作文件。✅
• IV. 内存映射文件是将文件映射到进程的虚拟地址空间，而不是直接映射到物理地址空间。虚拟地址空间最终会通过操作系统的内存管理单元（MMU）映射到物理地址空间。❌

所以正确的是 I、II、III，选择 D。

文件分配表（FAT）是文件系统用来记录磁盘块（簇）使用情况的数据结构。它记录了哪些磁盘块是空闲的，哪些已经被文件占用，因此文件系统可以通过 FAT 来管理空闲空间。

• A. 目录用于存储文件和子目录的元数据（如文件名、位置等），但不直接管理空闲空间。
• B. 系统打开文件表：用于记录当前打开的文件及其状态，与空闲空间管理无关。
• D. 进程控制块（FCB）：用于记录进程的状态信息，与文件系统的空闲空间管理无关。

关于文件系统能为温彻斯特硬盘（HDD）和固态硬盘（SSD）提供的功能，分析如下：

A. 划分扇区‌
扇区是磁盘物理结构的固有属性，由硬盘制造商在出厂时划分，文件系统不参与扇区的物理划分。

B. 确定盘块大小‌
文件系统通过逻辑格式化设定文件存储的基本单位（如 4KB 的块大小），这是文件系统对物理存储的逻辑抽象，适用于 HDD 和 SSD。

C. 降低寻道时间‌
寻道时间是 HDD 特有的机械性能指标，文件系统无法直接优化；而 SSD 无机械部件，不存在寻道时间问题。

D. 实现均衡磨损‌
这是 SSD 特有的功能，由 SSD 控制器通过磨损均衡算法实现，文件系统仅能通过 Trim 指令辅助，并非直接控制。

正确答案：B（确定盘块大小）‌ 文件系统通过逻辑格式化统一管理存储空间，为 HDD 和 SSD 定义逻辑块大小，这是两者共有的功能。

参考 传输时间计算：

• 电路交换的时间 $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}$。

先求这 4 个 8 位码字的两两 海明距离（统计对应位不同的个数）：

最小汉明距离 $d_{min} = 4$。

• 检错能力：最多可保证检测到 $d_{min} – 1 = 3$ 位错误（检错率 100 %）。
• 纠错能力：可保证纠正 $⌊(d_{min} – 1)/2⌋ = ⌊3/2⌋ = 1$ 位错误。

因此正确选项为 C：

可以检测不超过 3 位错，检错率 100%；可纠正不超过 1 位错

在以太网中，当发生冲突时，发送节点将执行 指数退避算法。在这个算法中，节点在重传之前会等待一个随机的时间间隔，这个时间间隔是以时隙（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$$

DHCP 的 REQUEST 报文：

目的 IP 地址：DHCP 服务器的 IP 地址或者广播地址（255.255.255.255），因为主机可能不知道 DHCP 服务器的确切 IP 地址，尤其是在初始请求阶段，广播地址确保网络中的所有 DHCP 服务器都能接收到请求。

源 IP 地址：0.0.0.0，因为主机还未获得正式的 IP 地址，在这个阶段它使用 0.0.0.0 作为源地址来表示“没有 IP 地址”。

• I. 源端口号：在 NAT 实现中，路由器可能会修改源端口号以便在多个内部主机使用相同外部 IP 地址时区分不同的会话。因此，源端口号可能会被修改。
• II. 目的端口号：通常不会被 NAT 修改，因为目的端口号用于指明接收方应用程序的端口。
• III. 总长度：UDP 报文段的总长度字段通常不会因为 NAT 而改变，因为 NAT 主要修改 IP 地址和源端口号，数据包的总长度保持不变。
• IV. 校验和：如果 NAT 修改了源 IP 地址或源端口号，导致 UDP 报文段的内容发生变化，UDP 校验和需要重新计算，因此校验和字段可能会被修改。

因此，路由器在转发封装该 UDP 报文段的过程中，可能会修改的字段是源端口号和校验和，答案选 B。

发送窗口取拥塞窗口和接收窗口之间的较小值，即 swnd = min(cwnd, rwnd)。

根据 ack_seq = 3001 可知，目前乙已经接收到了 1000B 的数据即一个 1 个 MSS，seq = 3001 的 MSS 仍然在发送中，并且此时乙的接收窗口（swnd）为 4 个 MSS。

此外，由于甲目前仍然在慢开始阶段（发送窗口没有达到阈值），所以接收到乙的确认后，拥塞窗口要 +1，此时 cwnd = 3 MSS。

所以发送窗口 swmd = min(3, 4) = 3 MSS。

另外需要注意这个公式：

发送窗口 的大小（swnd） = 已经发送但还没有确认数据（inflight） + 还没有发送的数据。这一题问的是甲还可以向乙发送多少个 TCP 段，这要减去那些之前已经发送但还没有确认的数据（1 MSS）。

所以还可以发送 3 - 1 = 2 MSS，答案选择 B。

本题考察 POP3 协议，对题目提供的选项进行逐一分析：

• I. 支持用户代理从邮件服务器读取邮件：✅。POP3 的主要功能就是支持客户端（用户代理）从邮件服务器读取邮件。
• II. 支持用户代理向邮件服务器发送邮件：❌。发送邮件的功能通常由 SMTP（Simple Mail Transfer Protocol）负责，而不是 POP3。
• III. 支持邮件服务器之间发送与接收邮件：❌。邮件服务器之间的邮件传输通常由 SMTP 协议处理，而不是 POP3。
• IV. 支持一条 TCP 连接收取多封邮件：✅。POP3 可以在一个会话中通过一条 TCP 连接获取用户邮箱中的多封邮件。

所以 I、IV 是正确的，本题答案为 A。