2024 年 408 真题

代码分解分析：

q = p->next;

现在 q 指向的是 p 的下一个结点。

p->next = q->next;

这一步将 q 从链表中“摘除”：原本是 p -> q -> q->next，现在变成了 p -> q->next，也就是说 q 不再出现在链表的原位置。

q->next = h->next;

这一步将 q->next 指向当前链表的第一个有效结点（注意是 h->next，即第一个结点，不是头结点）。

h->next = q;

把 q 接到头结点之后，也就是插入到链表头部（第一个有效结点之前）。

操作的效果是：

从链表中间删除了 q，然后把它插入到了头结点之后，也就是插入到链表第一个有效结点之前。

所以这段代码的功能是：

把 q 指向的结点插入到 h 的后面

正确答案选择 D。

本题有两种解法：第一种是使用栈 将中序转后序。 第二种方式是先将中序表达式转换为二叉树，然后再对二叉树进行后序遍历，得到后续表达式。

这里建议使用第二种方式，对于选择题比较高效。

根据邻接多重表还原图，由下图可知，b 的度为 2，d 的图为 4。

本题参考 修正后的 next 数组，传统 KMP 使用 next 数组，不过会存在 j=next[j]的情况，因此采用 next_val[] 来优化，处理 好 next[] 和 next_val[] 后，举例即可，比如倒数第二个元素 a 匹配失败，会回到 -1 的位置，从 -1 的位 置走到 4 的位置需要右滑的距离为 5 位。

本题考察 堆的删除操作，先根据初始序列建堆，然后依次删除堆项元素，过程如下图：

本题考察 多路归并 的原理，二路归并排序将相邻的有序子序列两两合并，得到合并后有序子序列。重复此过程，直到所有子序列合并为一个有序序列。

第一轮归并：将升序序列两两分组，(3,5) 和 (7,9) 分为一组，(6) 分为一组。(3,5) 和 (7,9) 的归并过程如下：

第二轮归并：将升序序列两两分组，(3,5,7,9) 和 (6) 分为一组。(3,5,7,9) 和 (6) 的归并过程如下：

到此，二路归并排序执行完毕。

上述过程中第一轮归并关键字之间比较 2 次，第二轮归并关键字之间比较 3 次，因此，关键字之间的总比较次数为 2 + 3 = 5。

本题选 C。

在外排序的多路归并中，败者树（Loser Tree）是一种优化的数据结构，用于快速找出多个归并段中当前最小的关键字。它是一个完全二叉树，每个非叶子节点保存的是“败者”，而整棵树的根节点保存的是当前“冠军” —— 即：

当前最小关键字所在的归并段号。

所以答案选择 D。

伪指令：伪指令不是真正的 CPU 指令，而是由汇编器识别和执行的一些特殊指令。

微指令：微指令是计算机硬件级别指令，一条机器指令所完成的操作划分成若干条微指令来完成。

机器指令：CPU 可以直接解析和执行的二进制代码。

汇编指令：低级别的编程语言，与机器指令一一对应，不过需要汇编器转换为机器指令，CPU 才能执行。

这些概念的关系参考 该节。

参考 该节，我们逐项分析：

A. 用阵列乘法器实现乘运算可以在一个时钟周期完成 ✅

阵列乘法器（array multiplier）是一种并行结构，硬件资源充足的情况下，确实可以在一个时钟周期内完成乘法运算（代价是面积大）。因此这个说法是正确的。

B. 用 ALU 和移位器实现的乘运算无法在一个时钟周期内完成 ✅

这种方式对应的是串行乘法器，通过不断地移位与加法模拟乘法过程，至少需要多个时钟周期完成，因此正确。

C. 变量与常数的乘运算可编译优化为若干条移位及加/减运算指令 ✅

例如 x * 10 可编译为 (x << 3) + (x << 1)，这是常见的编译器优化技术，因此此项正确。

D. 两个变量的乘运算无法编译为移位及加法等指令的循环实现 ❌

这项是错误的。事实上，若没有硬件乘法器，编译器或低级代码确实可以将变量之间的乘法（如 a * b）转换为循环移位加法实现。比如使用 Booth 算法、加移法（shift-and-add） 等。因此选项 D 的说法是错误的。

主存 - 外存层次的映射方式通常采用页式映射，而不是直接映射。页式映射是一种将虚拟地址空间分割为固定大小的单元（页）的映射方式，它将页映射到物理地址的空间的相应单元（页框）中。页式映射的优点是减少了内外存之间的交换次数，提高了空间利用率，缺点是增加了地址转换的开销，需默维护页表。

想一想，如果主存 - 外存页面采用直接映射的话，那么替换算法都直接没用了，所以 D 肯定是错误的。

根据题意可知，虚拟地址为 32 位，主存地址为 30 位，页大小为 1KB，因此，虚拟页号为 32-10=22 位，物理页号为 30-10=20 位。TLB 共有 32 个表项，采用 4 路组相联映射方式。因此，TLB 共有 32/4=8 组，每组有 4 路。索引字段为 $log_{2}8 = 3$ 位。标记字段位数 = 虚拟页号位数 - 索引字段位数=22-3=19 位。

具体原理可以参考 TLB 一节。

本题考查 数据冒险。

• A 选项正确，比如第一条指令写寄存器，下一条马上读同一个寄存器，就可能发生数据冒险。
• B 选项正确，“气泡”本质上是插入一条空操作（nop），让数据有时间准备好，避免错误读取。
• C 选项错误，Load-use hazard（加载 - 使用冒险）：加载指令的数据在内存访问阶段（MEM）才准备好，而后续指令可能在执行阶段（EX）就需要使用数据，这种情况即使有旁路电路也可能无法避免，通常还需要插入一个“气泡”。
• D 选项正确，插入气泡即推迟指令后续阶段执行，可以避免所有数据冒险。

中断是指外部设备或者程序需要 CPU 的服务时，向 CPU 发出一个信号，请求 CPU 暂停当前的任务，转而处理中断请求的情况。

中断响应顺序是指当同时有多个中断请求时，CPU 按照一定的优先级顺序来选择响应哪个中断的规则。

中断屏蔽字只能控制中断的开关，而不能控制中断的顺序，中断的顺序由中断的优先级决定，优先级高的中断洗被响应，优先级低的中断后被响应。

本题考查 中断和异常。

• A 错误。中断或异常发生时，CPU 处于用户态。当中断或异常发生时，CPU 会从用户态切换到内核态，然后开始执行相应的中断处理程序或异常处理程序。
• B 正确。操作系统为每种系统调用提供了对应的内核服务例程，这些例程负责处理用户程序发起的系统调用，以及管理内核资源和执行相应的操作。当用户程序发起系统调用时，处理器会从用户态切换到内核态，并执行与该系统调用对应的内核服务例程。
• C 正确。当中断发生时，CPU 会从用户态切换到内核态，并开始执行相应的中断处理程序。因为中断处理程序需要访问和操作受保护的内核资源，如管理设备、执行特权指令等，所以中断处理程序必须在内核态下执行。
• D 正确。系统添加新类型设备时，需注册相应的中断服务例程。因为许多设备在发生特定事件时会触发中断，需要相应的中断处理程序来进行处理，该中断处理程序就是中断服务例程。

Ⅰ. 更新程序计数器的值：程序计数器存储了下一条要执行的指令的地址。当进程切换时 ，操作系统需要更新程序计数器的值，以便于新的进程能从正确的位置开始执行。

Ⅱ. 更新栈基址寄存器的值：栈基址寄存器存储了当前进程栈的基址。当进程切换时，操作系统 需要更新栈基址寄存器的值，以确保新的进程使用正确的栈。

Ⅲ. 更新页表基址寄存器值：页基址寄存器存储了当前进程的页表基址。当进程切换时，操作系 统需要更新页基址寄存器的值，以确保新的进程能正确地访问其内存空间。

A. 文件系统需要额外的外存空间记录空闲块的位置，占用外存空间大小与当前空闲块数 量无关的是位示图。位示图是一种常用的记录空闲块位置的方法，它使用一个位来表示一个块是 否空闲。位示图的大小取决于磁盘的总块数，而与当前的空闲块数量无关。

B. 空闲表：空闲表是一种记录磁盘空闲块位置的方法它使用一个表来记录空闲块的位置。空闲 表的大小会随着空闲块的数量的变化而变化。

C. 成组链接：成组链接是一种记录该组中其他块的位置。成组链接的大小会随着空闲块数量的变 化而变化。

D. 空闲链表：空闲链表是一种记录酸盘空闲块位置的方法，它使用一个链表来记录所有空闲块的 位置。空闲链表的大小会随着空闲块数量的变化而变化。

A. 伙伴算法 是一种特殊的内存分配算法，他在分配和回收内存时，只合并大小相等的空 闲分区。这种算法的优点是简单且执行速度快，但可能会导致内存碎片：

B. 最佳适应算法：它在分配内存时，会选择大小最接近所需的空闲分区。这种算法的优点是可以 减少内存的浪费，但可能会导致大量的小碎片。

C. 最坏适应算法：它在分配内存时，会选择最大的空闲分区。这种算法的优点是可以减沙内存的 碎片，但可能会导致大量的大碎片。

D.首次适应算法：它在分配内存时，会选择第一个满足所需的空闲分区。这种算法的优点是简单 且执行速度快，但可能会导致内存的碎片。

动态分区分配算法具体参考该节。

Ⅰ. 进程 P 的地址空间：在同一进程中的所有线程共享该进程的地址空间。这意味着，线程 Ta 和 Tb 可以访问进程 P 的全局变量，因为这些变量存储在进程的地址空间中。此外，如果线程 T 在堆上分配了内存，那么线程 T 和 Tb 也可以访问这些内存，因为堆是存储在进程的地址空间中的。

Ⅱ. 线程 T 的栈：每个线程都有自己的栈，这是线程的私有资源，不会被其他线程共享。栈用于存储函数调用的局部变量和返回地址。由于每个线程可能有不同的函数调用序列，因此每个线程需要由自己的栈，因此，线程 Ta 和 Tb 不能访问线程 T 的栈。

Ⅲ. 文件描述符 fd：同进程中的所有线程共享该进程打开的文件描述符。文件描述符是一个整数，用于表示进程打开的文件。当线程打开一个文件时，操作系统会返回一个文件描述符，然后线程 T、T 和 Tb 都可以使用这个文件描述符来读写该文件，这是因为，尽管每个线程有自己的栈，但是它们共享其余的进程资源，包括文件描述符。

A. open() 系统调用用于打开一个文件。它需要一个文件名作为参数，因此它包含了按名 查找文件的功能。如果文件存在并且进程有足够的权限，open() 会成功打开文件并返回一个文件 描述符，否则，它会返回一个错误。

B. read() 系统调用用于从已打开的文件中读取数据。

C. write() 系统调用用于向已打开的文件中写入数据。

D. close() 系统调用用于关闭已打开的文件。

当键盘输入数据时，首先会将数据发送到键盘控制器的数据寄存器中。当键盘控制器的数据寄存器接收到数据后，它会触发一个中断请求 (IRQ1)，通知 CPU 有数据等待处理。CPU 响应中断请求后，会执行键盘中断服务例程。在中断服务例程中，CPU 从键盘控制器的数据寄存器读取输入数据，并将其存放到内核缓冲区中。

A 错误。用户缓冲区通常指的是应用程序为接收输入数据而分配的缓冲区。在键盘中断服务例程执行结束时，输入数据并不会直接存放在用户缓冲区中，而是先存放在内核缓冲区中。应用程序可以通过系统调用或其他机制从内核缓冲区读取输入数据，并将其复制到用户缓冲区中。

B 错误。CPU 中的通用寄存器并不是输入数据的最终存放位置。在键盘中断服务例程执行过程中，输入数据可能会暂时存放在 CPU 的通用寄存器中，但最终会被存放到内核缓冲区中。

C 正确。内核缓冲区是操作系统用于暂存输入数据的内存区域。在键盘中断服务例程执行过程中，输入数据被读取并存入内核缓冲区，以便后续的系统调用或应用程序访问。内核缓冲区通常由操作系统管理，确保数据的正确性和一致性。

D 错误。键盘控制器的数据寄存器是输入数据的初始存放位置，但并不是中断服务例程执行结束时的最终存放位置。

本题选 C。

在 CSCAN 中，磁头会在一个方向上移动，直到达到磁道的一端，然后立即返回到另一端，再次开始扫描。

首先磁头会移动到 160 号磁道，然后依次是 120 号、110 号、0 号，接着磁头移动到开头，然后向磁道号减少的方向移动：依次移动到 399 号、300 号、210 号，完成所有请求后，磁头移动的总距离为：

200-160=40；160-110=50；110-0=110；399-0=399；399-300=90；300-210=90；

磁头移动的总距离为 40+50+110+399+99+90=788

本题考查 调制方法：

选项 A：ASK (Amplitude Shift Keying) 幅移键控，这种调制方式是利用载波幅度的变化来传送数字信息的。因此排除选项 A。

选项 B：PSK (Phase Shift Keying) 相移键控，这种调制方式是利用载波振荡相位的变化来传送数字信息的。因此排除选项 B。

选项 C：FSK (Frequency Shift Keying) 频移键控，这种调制方式是利用载波频率的变化来传送数字信息的。在二进制数字调制中，常见的是二进制 0 和 1 对应不同的频率。因此选项 C 为正确选项。

选项 D：DPSK (Differential Phase Shift Keying) 差分相移键控，它不是利用载波相位的绝对数值传送数字信息，而是用前后码元的相对载波相位值传送数字信息。因此排除选项 D。

本题选 C。

VLAN (Virtual Local Area Network) 虚拟局域网技术可以把同一物理局域网内的不同用户逻辑地划分成不同的广播域。位于同一 VLAN 的主机之间可以相互通信，位于不同 VLAN 的主机之间不能直接通信。

ARP (Address Resolution Protocol) 地址解析协议，是根据 IP 地址获取物理地址的一个 TCP/IP 协议。主机发送信息时将包含目标 IP 地址的 ARP 请求广播到局域网络上的所有主机，并接收返回消息，以此确定目标的物理地址；收到返回消息后将该 IP 地址和物理地址存入本机 ARP 缓存中并保留一定时间，下次请求时直接查询 ARP 缓存以节约资源。

因此，ARP 协议可以在同一 VLAN 中起作用。

由图可知，VLAN1 中包含 H1、H2、H3 和 H4；VLAN2 中包含 H5；VLAN3 中包含 H6 和 H7。

A 和 H2 有关，H2 和 H4 都位于 VLAN1 中，因此该项会出现在 H4 的 ARP 表中。

B 和 H1 有关，H1 和 H4 都位于 VLAN1 中，因此该项会出现在 H4 的 ARP 表中。

C 和 H3 有关，H3 和 H4 都位于 VLAN1 中，因此该项会出现在 H4 的 ARP 表中。

D 和 H6 有关，H6 位于 VLAN3 中，而 H4 都位于 VLAN1 中，两者不在同一个 VLAN 中，因此该项不会出现在 H4 的 ARP 表中。

本题选 D。

在 CSMA/CA 的 802.11 无线局域网中，网路分配向量（NAV）是用来告诉其他节点预计要占用无线媒体多长时间的一种机制。在发送 RTS（请求发送）和 CTS（清除发送）帧时，发送节点会在帧头中包含一个持续时间字段，这个字段表示从发送当前帧到接收到最后一个 ACK 帧所需的时间。其他节点在接收到 RTS 或 CTS 帧后，会根据这个持续时间字段设置自己的 NAV，从而避免在这段时间内发送数据，防止发生冲突。

NAV 的时间就是其他节点推迟访问的时间，约等于 SIFS 时间 + 数据发送时间 + SIFS 时间 + ACK 帧传播时延。

根据题目中的信息，我们可以计算出设置 NAV 的值。首先，我们需要计算发送数据顿所需的时间数据帧的总长度为 1998B，无线链路带宽为 54bps，所以发送数据帧所需的时间为：1998B/54Mbps=296μs，则总时间=28μs+296μs+28μs+2μs=354μs

在 TCP 连接中，从建立连接到关闭连接的过程包括以下步骤：

1. 建立链接：这个过程通常为称为 三次握手，SYN、SYN-ACK、ACK，需要一个往返时间 RTT。
2. 数据传输：主机日向服务器发送长度为 3000B 的报文。由于最大报文段长度 MSS=1000B，第一 次拥塞窗口为 1 发送 1000B，第二次拥塞窗口为 2 发送 2000B，所以一共消耗 2 个最长报文段寿 命，2 个 RTT。
3. 关闭连接：这个过程通常称为 四次挥手 FIN、ACK、FIN、ACK。

第一次挥手和第三次挥手构成一个 RTT，第二次和第三次是连续发送的，第四次发出去的时候和客户端等待的 2SL 时间重叠，所以需要 1 个 RTT。

所需时间 1RTT+2RTT+1RTT+2MSL=4RTT+2MSL。

将 RTT=10ms=0.01s 和 MSL=30s 代入上式，得到 60.04s。

UDP 是一种传输层协议，UDP 校验和 计算的步骤如下：

将 UDP 首部和 UDP 数据字段合并成一个伪首部和一个伪数据字段。伪首部的内容包括源 IP 地址、目 的 IP 地址、协议类型、UDP 数据长度。伪数据字段的内容 UDP 首部和数据字段本身。

对伪首部和伪数据字段进行 16 位的字节级求和，得到一个结果。

对结果进行反码运算，得到最终的校验和。

  1011 1001 1011 0110
+ 0110 0101 1100 0101
---------------------
 10001 1111 0111 1011

最高位产生进位所以需要在末尾加 1，可得：0001111101111100。

取反可得：1110 0000 1000 0011