2026 年 408 真题

【解析】
题意澄清

• 双向链表结点结构为 [p2, p1]

  • p1：后继指针（next）
  • p2：需要被重新设置

• 目标： 让每个结点的 p2 指向“p1 所指结点的直接后继” 即：

[ cu->p2 = cu->p1->p1 ]

• 若 cu->p1 == NULL（尾结点），则： [ cu->p2 = NULL ]

• 同时，遍历过程中必须始终推进 cu，否则死循环

逐项分析

❌ A

while(cu!=NULL) {
    cu->p2=cu->p1->p1;
    cu=cu->p1;
}

• 问题： 当 cu 是尾结点时，cu->p1 == NULL → cu->p1->p1 非法访问

❌ B

while(cu!=NULL && cu->p2!=NULL) {
    cu->p2 = cu->p1->p1;
    cu = cu->p1;
}

• 问题 1：cu->p2 作为循环条件毫无意义（它正是要被修改的）
• 问题 2：仍然没有防止 cu->p1 == NULL

❌ C

while(cu!=NULL) {
    if(cu->p1!=NULL) {
        cu->p2=cu->p1->p1;
        cu=cu->p1;
    }
}

• 致命问题：

  • 当 cu->p1 == NULL（尾结点）
  • cu 不会更新
  • → 死循环

✅ D（唯一正确）

while(cu!=NULL) {
    if(cu->p1!=NULL) {
        cu->p2=cu->p1->p1;
    } else {
        cu->p2=NULL;
    }
    cu=cu->p1;
}

• ✔ 正确处理尾结点（p2 = NULL）
• ✔ 每一轮都推进 cu
• ✔ 无非法指针访问
• ✔ 完全符合题意

虽然选项排版里 cu=cu->p1 写在 else 后，但按标准理解应在 if-else 之后统一执行，这是此类考题的常见写法。

【解析】
首先，根据层序遍历序列 $a,b,g,c,d,e,f$ 可知根节点为 $a$ 。结合中序遍历 $b,e,d,f,c,a,g$ ，确定左子树包含节点 $b,e,d,f,c$ ，右子树仅包含 $g$ 。

左子树的层序序列为 $b,c,d,e,f$ ，中序序列为 $b,e,d,f,c$ ，因此左子树的根为 $b$ 。由于 $b$ 在中序中为首，故无左子树，其右子树的根为层序中下一个节点 $c$ 。

对于以 $c$ 为根的子树，中序为 $e,d,f,c$ ，故 $c$ 无右子树，其左子树的根为层序中的 $d$ 。对于以 $d$ 为根的子树，中序为 $e,d,f$ ，故 $d$ 的左子节点为 $e$ ，右子节点为 $f$ 。

因此树的结构为：

• $a$ 的左子节点为 $b$ ，右子节点为 $g$ ；
• $b$ 的左子节点为空，右子节点为 $c$ ；
• $c$ 的左子节点为 $d$ ，右子节点为空；
• $d$ 的左子节点为 $e$ ，右子节点为 $f$ 。

后序遍历顺序为：左子树的后序、右子树的后序、根节点。左子树的后序依次为 $e,f,d,c,b$ ，右子树的后序为 $g$ ，根为 $a$ ，故后序遍历序列为 $e,f,d,c,b,g,a$ ，对应选项 C。

【解析】
这是一道 森林 → 二叉树（左孩子 - 右兄弟表示法） 的经典题。

关键结论（必须掌握）

把森林转换为二叉树（左孩子 - 右兄弟）后：

二叉树的高度 = max( 第 i 棵树的高度 + (i − 1) )

其中

• 第 $i$ 棵树是森林中从左到右的顺序；
• $(i-1)$ 来自“右兄弟”链；
• 为了最小高度，应当把高度最大的树放在最前面。

先算每棵树的最小可能高度

一棵有 $n$ 个结点的普通树，其最小高度为：

排序（从大到小）：

计算二叉树最小高度

按最优顺序依次计算：

最大值 = 6

【解析】
为了最小化带权路径长度（WPL），需构建哈夫曼树。节点权值依次为 1, 2, 4, 5, 8, 10, 12。
构建过程如下：

1. 合并权值 1 和 2，得到新节点 3；
2. 合并 3 和 4，得到新节点 7；
3. 合并 5 和 7，得到新节点 12；
4. 合并 8 和 10，得到新节点 18；
5. 合并原始权值 12（节点 g）与内部节点 12，得到新节点 24；
6. 最后合并 18 和 24，得到根节点 42。

由此树结构可知，节点 e（权值 8）深度为 2（路径长度），同时节点 f（权值 10）和 g（权值 12）深度也为 2，而其他节点深度均不同（d 深度为 3，c 深度为 4，a、b 深度为 5）。
因此，与节点 e 处于相同深度的节点是 f 和 g。

【解析】
对于选项 A：若图 G 无环，则任意路径不能重复经过顶点，否则会形成环，因此最长路径的边数不超过 $n-1$ 。由于图是有限的，所有可能的路径数量有限，每条路径对应一个字符串（可能重复），但字符串集合 S 由有限个字符串组成，故 S 是有限集。A 正确。

对于选项 B：若图 G 无环，则任意路径最多经过 $n$ 个不同的顶点，因此边数最多为 $n-1$ ，对应的字符串长度最多为 $n-1$ 。所以 S 中不可能存在长度为 $n$ 的字符串。B 错误。

对于选项 C：若图 G 有环，则存在一个环，可以从环上某点出发沿环行走任意多圈，得到任意长的路径，从而产生长度大于 $n$ 的字符串。C 正确。

对于选项 D：若图 G 有环，S 中至少包含空字符串（长度为 $0$ ），而 $0<2n$ （ $n\ge 1$ ），因此存在长度小于 $2n$ 的字符串。D 正确。

综上，说法错误的是 B。

【解析】
平衡二叉树高度为 4（根节点高度为 1），因此左右子树的高度组合为：

• 两者均为 3，或
• 一个为 3、另一个为 2。

为最大化节点数之差，应使较高子树取最大节点数，较低子树取最小节点数。

• 高度 3 的平衡二叉树最大节点数为 7（满二叉树），
• 高度 2 的最小节点数为 2（根节点加一个子节点），
  此时节点数之差为 $7-2=5$ 。

若左右子树高度均为 3，节点数之差最大为 $7-4=3$ 。
因此，根节点的左右子树节点数之差最多为 5。

【解析】 直接插入排序的比较次数取决于序列的初始有序程度。对于每个序列，从第二个元素开始，将其与前面已排序的元素从后往前比较，直到找到正确位置，记录比较次数。

• 选项 A：序列 30, 27, 56, 41, 80, 95, 69 的总比较次数为 $1+1+2+1+1+3=9$ 次。
• 选项 B：序列 31, 43, 26, 55, 63, 99, 77 的总比较次数为 $1+2+1+1+1+2=8$ 次。
• 选项 C：序列 61, 84, 51, 23, 34, 91, 40 的总比较次数为 $1+2+3+4+1+5=16$ 次。
• 选项 D：序列 93, 32, 48, 81, 50, 21, 72 的总比较次数为 $1+2+2+3+5+3=16$ 次。

比较次数最少的是选项 B，共 8 次。

【解析】 在外部排序的 k 路归并过程中，归并趟数 $d$ 与初始归并段数 $m$ 满足关系 $d=\lceil {\log }_{k}m\rceil$ 。

• 对于说法Ⅰ： $k$ 越大， ${\log }_{k}m$ 越小，因此 $d$ 越小，正确。
• 对于说法Ⅱ： $d$ 直接依赖于 $m$ ，初始归并段数变化会影响 $d$ ，错误。
• 对于说法Ⅲ：生成初始归并段时，数据需读入内存进行内部排序，因此初始归并段的最大长度受内存大小限制，正确。

综上，Ⅰ和Ⅲ正确，对应选项 C。

【解析】
机器数 1010 0110B 是一个 8 位有符号数（二进制补码表示）。先执行算术右移 3 位，再执行算术左移 2 位。

• 算术右移 3 位：符号位（最高位为 1）被保留并向左扩展。
  原始位从高位到低位记为 $A_0$ 到 $A_7$ （ $A_0$ 为符号位），右移后得到 $B_0$ 到 $B_7$ ，其中 $B_0$ 到 $B_3$ 均填充为 $A_0$ （1）， $B_4$ 到 $B_7$ 依次为 $A_1$ （0）、 $A_2$ （1）、 $A_3$ （0）、 $A_4$ （0），结果为 1111 0100B（即 -12 的二进制补码）。

• 算术左移 2 位：将 1111 0100B 左移 2 位，高位丢弃，低位补 0，得到 1101 0000B（即 -48 的二进制补码）。

最终结果为 1101 0000B，对应选项 A。

【解析】
1. 确定数量级（指数部分）

• 符号位：0
• 指数：(3 + 127 = 130 = 1000,0010_2)

2. 计算尾数

把 1.5125 转成二进制小数：

对小数部分反复乘 2：

得到二进制近似：

1.10000001100110011001100…₂

3. 就近舍入（中间值取偶）

IEEE 754 单精度尾数 23 位，截断时：

…10011001100110011001100 1100…

• 被舍弃部分 > 0.5 ULP
• 或者正好在中间且最低位为奇数

👉 需要进 1

因此尾数末位变为 …10011010

4. 拼装 IEEE 754 单精度

转换为十六进制：

0 | 10000010 | 10000011001100110011010
↓
4141999A₁₆

最终答案

B 4141 999AH

【解析】
由 8 个 64M×8bit 的 DRAM 芯片按交叉编址方式构成主存储器，每个芯片容量为 64MB，总容量为 512MB。按字节编址，地址线共 29 位。交叉编址时，地址的低位用于选择芯片，高位用于芯片内地址。由于有 8 个芯片，地址的低 3 位（模 8）决定芯片编号。

给定地址 0018 001DH 的十六进制值为 0x0018001D，低 3 位二进制为 101（因为 0x1D 的低 3 位为 101），即模 8 余 5。因此，与它位于同一芯片的地址必须模 8 余 5。

• 选项 A：0000 01D5H，低 3 位为 101（0xD5 的低 3 位为 101），余 5，符合。
• 选项 B：000F A020H，低 3 位为 000，余 0，不符合。
• 选项 C：0018 001EH，低 3 位为 110（0x1E 的低 3 位为 110），余 6，不符合。
• 选项 D：0101 0011B 为二进制数，低 3 位为 011，余 3，不符合。

故只有选项 A 与给定地址位于同一芯片。

【解析】
Cache 共有 1024 行，采用 4 路组相联映射，因此组数为 $1024/4=256$ 组。
主存块大小为 32 B，块内偏移地址占 5 位（ $2^5=32$ ）。
访问主存地址为 1028（十进制），按字节编址。
组号由块地址对组数取模得到：块地址为地址除以块大小的整数部分，即

组索引

因此，该数据所在主存块对应的组号为 32。

【解析】
虚拟地址为 16 位，页大小为 256 B，因此页内偏移占 8 位，页号占 8 位。
TLB 为 4 路组相联，共 16 个表项，故分为 4 组，组索引占 2 位，标记占 6 位。

页号 22 的二进制为 00010110，高 6 位标记为 05H，低 2 位组索引为 10（即 2），因此页号 22 属于组 2。

已知主存页表中页号 22 对应的表项 P=0、PPN=2AH，同步后 TLB 中若存在该页表项，则有效位 V 应与 P 一致（即 V=0），且 PPN 应为 2AH。

选项 A 的标记为 05H，对应页号 22，但 V=1、PPN=1CH，与页表项冲突，不可能出现在组 2 的 TLB 中。
其他选项对应不同页号（如 B 对应页号 26，C 对应页号 90，D 对应页号 106），其页表项未知，故可能出现在 TLB 中。

【解析】
在不考虑异常中断处理和访存的额外开销下，单周期数据通路中每条指令在一个时钟周期内完成，因此 CPI 等于 1。

多周期数据通路中每条指令需要多个时钟周期执行，因此 CPI 大于 1。

流水线数据通路在理想情况下（无冒险和停顿）可以实现每个时钟周期完成一条指令，因此 CPI 等于 1。

故 I、II、III 均正确。

注意：II 在理想情况下（完美的 overlap，运行的时间无限长)，CPI 是趋向于 1 的，但是这一题显然不是考察的理想情况，所以 II 是正确的。

【解析】
在计算机系统中，特权指令是指只能在操作系统内核态下执行的指令，用于保护系统资源和稳定性。

A 项 I/O 指令直接控制外设操作，若用户程序随意执行可能干扰系统，因此属于特权指令；
B 项关中断指令用于禁用中断，防止关键代码被中断打断，若用户程序可随意关闭中断会导致系统无法响应关键事件，故为特权指令；
C 项中断返回指令用于从中断处理程序返回，涉及处理器状态恢复和权限切换，通常需在内核态执行，也属于特权指令。

D 项系统调用指令（如 syscall 或 int 指令）是用户程序请求操作系统服务的接口，该指令本身可在用户态执行，通过触发陷入机制切换到内核态，由操作系统内核处理具体操作，因此不属于特权指令。

【解析】
在中断控制 I/O 方式下，中断响应和处理需要硬件和软件协同工作。

• 保存断点（即程序计数器的值）必须由硬件自动完成。因为中断发生时需立即保存返回地址，以确保后续能正确恢复执行。
• 开中断是通过软件指令实现的，用于允许或禁止中断嵌套。
• 中断请求由硬件设备产生，但响应和处理过程涉及软硬件配合。
• 保存通用寄存器通常由中断服务程序（软件）完成，以保护原程序的上下文。

因此，只有保存断点必须由硬件完成。

【解析】
在进程并发执行中，不发生错误（即避免数据竞争和冲突）的充要条件基于 Bernstein 条件。Bernstein 条件指出，两个进程 $P$ 和 $Q$ 可安全并发执行当且仅当满足以下三个条件：

1. $W(P)\cap R(Q)=\varnothing$ （避免写后读冲突）；
2. $R(P)\cap W(Q)=\varnothing$ （避免读后写冲突）；
3. $W(P)\cap W(Q)=\varnothing$ （避免写后写冲突）。

读 - 读冲突（即 $R(P)\cap R(Q)$ ）不会导致数据不一致，因此不是必要条件。

对比题目中的条件：
I 对应 $W(P)\cap R(Q)=\varnothing$ ，
III 对应 $W(P)\cap W(Q)=\varnothing$ ，
IV 对应 $R(P)\cap W(Q)=\varnothing$ ，
而 II 是 $R(P)\cap R(Q)=\varnothing$ ，无需满足。

因此，充要条件是 I、III 和 IV，对应选项 C。

在三级虚拟分页存储管理方式中，虚拟地址结构包括一级页表索引（9 位）、二级页表索引（9 位）、三级页表索引（9 位）和页内偏移（12 位）。
页内偏移 12 位对应页面大小为 4 KB（ $2^{12}$ 字节）。
每个页表索引为 9 位，因此每个页表有 $2^9=512$ 个页表项。
假设每个页表项大小为 8 字节（典型 64 位系统），则每个页表大小为 $512\times 8=4096$ 字节，恰好占用一个页框。

三级页表的数量由一级和二级页表决定：

• 一级页表有 512 个条目，每个条目指向一个二级页表，因此最多有 512 个二级页表；
• 每个二级页表有 512 个条目，每个条目指向一个三级页表，因此三级页表的最大数量为 $512\times 512=262144$ 个。

每个三级页表占用一个页框，所以三级页表总共占用的页框数为 262144，即 256 K（因为 $256\times 1024=262144$ ）。
因此，正确答案为 C。

【解析】
进程 P1 和 P2 共享文件 R，这意味着它们通过各自的页表项 R1 和 R2 将虚拟地址 W1 和 W2 映射到相同的物理内存区域，因此 W1 和 W2 映射的物理地址相同。

• 选项 A 错误，因为页表项 R1 和 R2 至少物理地址部分相同，内容并非完全不同；
• 选项 C 错误，由于共享物理内存，P1 对 W1 的修改会影响 P2 对 W2 的访问；
• 选项 D 错误，虚拟地址是进程独立的，W1 和 W2 不一定相同。

【解析】
首先，根据香农定理，信道容量为

其中带宽 $B=200\text{kHz}=2\times 10^5\text{Hz}$ ，信噪比 $S/N=1023$ 。
计算 $1+1023=1024$ ，且 ${\log }_2(1024)=10$ ，因此

分组长度为 $1500\text{B}$ ，即 $1500\times 8=12000\text{bits}$ 。
传输时延是分组长度除以数据传输速率，在理想情况下，最大速率为信道容量，故最小传输时延为

因此，发送该分组的传输时延至少是 6 ms。

【解析】
在 IEEE 802.11 CSMA/CA 协议中，主机 H 发送数据帧的过程为：先等待 DIFS（本题中起始点从“开始发送数据帧”算起，故 DIFS 已过，不包含在计算内），然后传输数据帧，之后接收方等待 SIFS 后发送 ACK 确认帧。根据题目，忽略除数据帧外的其他帧传输时延（即 ACK 帧传输时延为 0），且忽略信号传播时延。数据帧长度为 1500 B，数据传输速率为 300 Mbps。

数据帧传输时间

SIFS = 28 μs.

从数据帧开始发送到发送方收到 ACK 的时间

因此，所需时间至少为 68 μs。

【解析】
1. 主机和端口的对应关系

• VLAN 1（左半部分）
  • 端口范围：1–7、13–19
  • H1 → 端口 13 → MAC …-01
  • H2 → 端口 2 → MAC …-02
  • H3 → 端口 5 → MAC …-03 ✅（我们关心的主机）
• VLAN 2（右半部分）
  • 端口范围：8–12、20–24
  • H4 → 端口 8 → MAC …-04
  • H5 → 端口 9 → MAC …-05
  • H6 → 端口 12 → MAC …-06

👉 H3 位于 VLAN 1 中。

2. 交换机与 VLAN 的转发规则

1. 单播帧
   • 仅在源端口所属的 VLAN 内查询 MAC 地址表并进行转发。
   • 若目的 MAC 地址不在本 VLAN 的地址表中，则不会转发该帧。
2. 广播帧
   • 仅在本 VLAN 内的所有端口（除源端口）进行广播。
3. VLAN 间完全隔离
   • 在没有三层设备的情况下，不同 VLAN 之间无法直接通信。

3. 逐帧判断 H3 能否收到

• F1
  • 目的地址（DA）= …-03（H3）
  • 源地址（SA）= …-01（H1，属于 VLAN 1）
  • 分析：帧源自 VLAN 1，目的 MAC 地址正是 H3。属于同 VLAN 单播通信。
  • ✅ H3 会接收此帧。
• F2
  • 目的地址（DA）= …-04（H4，属于 VLAN 2）
  • 源地址（SA）= …-05（H5，属于 VLAN 2）
  • 分析：整个帧的源和目的均位于 VLAN 2 内，该帧的通信被限制在 VLAN 2 中。
  • ❌ H3 接收不到此帧。
• F3
  • 目的地址（DA）= FF-FF-FF-FF-FF-FF（广播地址）
  • 源地址（SA）= …-02（H2，属于 VLAN 1）
  • 分析：这是一个广播帧，且源位于 VLAN 1。广播范围仅限于 VLAN 1 内的所有端口（发送端口除外）。
  • ✅ H3 位于 VLAN 1，因此会收到此广播帧。
• F4
  • 目的地址（DA）= …-06（H6，属于 VLAN 2）
  • 源地址（SA）= …-03（H3，属于 VLAN 1）
  • 分析：帧源自 VLAN 1，但目的 MAC 地址属于 VLAN 2。交换机在 VLAN 1 的 MAC 地址表中查不到该目的地址，且单播帧不会跨 VLAN 进行泛洪。
  • ❌ H3 收不到此帧（实际上这是 H3 自己发出的帧）。

最终结论

H3 能够接收到的帧是：

• ✅ F1
• ✅ F3

对应选项为：B 仅 F1、F3

【解析】 在链路状态路由算法中，每个路由器维护全网的拓扑信息。当 $R_1$ 检测到与 $R_2$ 之间的链路断开后，会更新链路状态数据库并重新计算最短路径树。根据给定的网络拓扑（图中显示）， $R_1$ 直连多个网络，并通过其他路由器学习到远程网络的路由。重新计算后，由于链路断开，部分路由的路径发生变化，但所有网络仍可达。进行充分路由聚合时，可以将多个连续子网汇总为一个路由条目，从而减少路由表规模。根据拓扑结构、子网划分以及聚合原则，聚合后路由表结构如下：

所以路由表的个数仍然为 5，答案选择 C。

【解析】
1. 原始网络信息

给定网络： 123.4.4.0/22

• /22 表示网络位共有 22 位
• 主机位 = 32 − 22 = 10 位
• 地址总数 = (2^{10} = 1024)

该 /22 网络覆盖范围是：

123.4.4.0  ～  123.4.7.255

2. 划分为 32 个规模均衡的子网

需要 32 个子网：

⇒ 从主机位中 再借 5 位作为子网位

• 新前缀长度： $22+5=27$

子网前缀为 /27

3. /27 子网的地址块大小

/27：

• 主机位 = 5 位
• 每个子网地址数 = (2^5 = 32)

也就是说，每个子网 步长是 32。

4. 确定 123.4.5.11 属于哪个 /27 子网

看第三个字节为 5 的情况：

123.4.5.0     ~ 123.4.5.31     （第一个 /27）
123.4.5.32    ~ 123.4.5.63     （第二个 /27）

IP 地址 123.4.5.11 落在：

123.4.5.0 ~ 123.4.5.31

5. 结论

该 IP 所在子网是：

123.4.5.0/27