2024年全国硕士研究生招生考试计算机学科专业基础试题（408）详细解析

说明：本文基于2024年408真题及标准答案整理，逐题给出答案、知识点、详细解析与计算过程。部分题目中的图片、表格在扫描版中可能有缺失，本文根据历年真题通用版本补全。全文可按 Markdown 复制到 Word 中保存为博文。

---

一、单项选择题（1～40 小题，每小题 2 分，共 80 分）

第1题

题目： 一个带头结点的链表 L，指针 p 指向链表 L 中间的某个结点（非首尾结点）。对于以下代码段：

q = p->next;
p->next = q->next;
q->next = L->next;
L->next = q;

其功能是（ ）。

A. 将 p 指向结点移到 q 指向结点后
B. 将 q 指向结点移到 p 指向结点后
C. 将 p 指向结点插入头结点后
D. 将 q 指向结点插入头结点后

答案：D

解析：
代码执行过程：

1. q = p->next; 让 q 指向 p 的后继结点。
2. p->next = q->next; 将 q 从原位置删除，p 的后继改为 q 的后继。
3. q->next = L->next; 让 q 的后继指向原第一个元素结点。
4. L->next = q; 让头结点的后继指向 q。

因此，功能是将 q 指向的结点插入到头结点之后，即成为新的第一个元素结点。答案 D。

知识点： 单链表结点移动、指针操作。

---

第2题

题目： 中缀表达式 x + y * (z - u) / v 对应的后缀表达式是（ ）。

A. xyzu-*v/+
B. xyzu-v/*+
C. +x/*y-zuv
D. +x*y/-zuv

答案：A

解析：
中缀表达式运算顺序：先算 (z-u)，再算 y * (z-u)，再算 /v，最后 x + ...。
后缀表达式（逆波兰式）为：x y z u - * v / +，即 xyzu-*v/+。答案 A。

知识点： 中缀转后缀、栈的应用。

---

第3题

题目： p、q、v 都是二叉树 T 中的结点，其中结点 v 有两个孩子结点，二叉树 T 的中序遍历为：…，p，v，q，…，则（ ）。

A. p 没有右孩子，q 没有左孩子
B. p 没有右孩子，q 有左孩子
C. p 有右孩子，q 没有左孩子
D. p 有右孩子，q 有左孩子

答案：A

解析：
中序遍历顺序为：左子树 → 根 → 右子树。
已知 v 有两个孩子，中序中 p 在 v 前，q 在 v 后。

• p 在 v 之前，说明 p 在 v 的左子树中。若 p 有右孩子，则中序中 p 的右孩子应在 p 和 v 之间，但中序是 p 紧挨着 v，所以 p 没有右孩子。
• q 在 v 之后，说明 q 在 v 的右子树中。若 q 有左孩子，则中序中 q 的左孩子应在 v 和 q 之间，但中序是 v 紧挨着 q，所以 q 没有左孩子。
  因此选 A。

知识点： 二叉树中序遍历、结点关系。

---

第4题

题目： 已知如下是无向图的邻接多重表，请问顶点 b、d 的度分别是（ ）。

A. 0，2
B. 2，4
C. 2，5
D. 3，4

答案：C

解析：
根据邻接多重表（图略），顶点 b 的度为 2，顶点 d 的度为 5。答案 C。

知识点： 邻接多重表、顶点度。

---

第5题

题目： 以下存储结构中，不适用于折半查找的是（ ）。
I. 有序链表
II. 无序数组
III. 有序静态链表
IV. 无序静态链表

A. 仅 I 和 II
B. 仅 II 和 IV
C. 仅 I、II、IV
D. I、II、III、IV

答案：C

解析：
折半查找要求能够随机访问，且元素有序。

• 有序链表不能随机访问，不适用。
• 无序数组虽然可随机访问，但无序，不适用。
• 有序静态链表本质是数组，可随机访问且有序，适用。
• 无序静态链表不适用。
  因此不适用的是 I、II、IV。答案 C。

知识点： 折半查找、存储结构。

---

第6题

题目： KMP 算法使用修正后的 next 数组进行模式匹配，模式串 s = "aabaab"，主串中某个字符失配时，s 右滑最长距离为（ ）。

A. 5
B. 4
C. 3
D. 2

答案：B

解析：
模式串 aabaab，计算 next 数组。失配时右滑距离 = 已匹配长度 - next[j]。最大右滑距离为 4。答案 B。

知识点： KMP 算法、next 数组。

---

第7题

题目： 一棵二叉搜索树如下图所示，k1、k2、k3 分别是对应结点保存的关键字，图中三角形表示子树。则图中子树 T 中任意结点保存的关键字 x 满足（ ）。

A. x < k1
B. x > k2
C. k1 < x < k3
D. k3 < x < k2

答案：C

解析：
根据二叉搜索树性质，左子树所有结点小于根，右子树所有结点大于根。图中子树 T 位于 k1 和 k3 之间，因此 k1 < x < k3。答案 C。

知识点： 二叉搜索树、关键字范围。

---

第8题

题目： 使用快速排序算法对含 n（n≥3）个元素的数组 M 进行排序，若第一趟排序将 M 中除枢轴外的 n-1 个元素划分为均不为空的 P 和 Q 两块，则下列叙述中，正确的是（ ）。

A. P 与 Q 块间有序
B. P 与 Q 均块内有序
C. P 和 Q 的元素个数大致相等
D. P 中和 Q 中均不存在相等的元素

答案：A

解析：
快速排序一趟划分后，枢轴左边的 P 块所有元素 ≤ 枢轴，右边的 Q 块所有元素 ≥ 枢轴，因此 P 与 Q 块间有序。块内不一定有序，元素个数不一定相等，可能存在相等元素。答案 A。

知识点： 快速排序、划分。

---

第9题

题目： 大根堆初始序列为：28，22，20，19，8，12，15，5。对该堆进行两次删除操作后，得到的新堆是（ ）。

A. 20，19，15，12，8，5
B. 20，19，15，5，8，12
C. 20，19，12，15，8，5
D. 20，19，8，12，15，5

答案：A

解析：
第一次删除 28：将 5 放到根，向下调整：5 与 22、20 比较，22 大，交换；5 与 19、8 比较，19 大，交换；5 与 15 比较，15 大，交换。得到 22,19,20,15,8,12,5。
第二次删除 22：将 5 放到根，调整：5 与 20、19 比较，20 大，交换；5 与 12、15 比较，15 大，交换。得到 20,19,15,12,8,5。答案 A。

知识点： 堆删除、向下调整。

---

第10题

题目： 对如下三个升序序列 {3,5}、{7,9}、{6}，按从左至右的次序选择有序序列进行二路归并排序，关键字之间的总比较次数是（ ）。

A. 3
B. 4
C. 5
D. 6

答案：C

解析：
先合并 {3,5} 和 {6}：比较 3 和 6，取 3；比较 5 和 6，取 5；然后 6。比较 2 次。
再合并 {3,5,6} 和 {7,9}：比较 3 和 7，取 3；比较 5 和 7，取 5；比较 6 和 7，取 6；然后 7,9。比较 3 次。
总比较次数 = 2 + 3 = 5。答案 C。

知识点： 二路归并、比较次数。

---

第11题

题目： 在外排序中，利用败者树对初始为升序的归并段进行多路归并，败者树中记录“冠军”的结点保存的是（ ）。

A. 最大关键字
B. 最大关键字所在的归并段号
C. 最小关键字
D. 最小关键字所在的归并段号

答案：D

解析：
败者树中，冠军结点保存最小关键字所在的归并段号。答案 D。

知识点： 败者树、多路归并。

---

第12题

题目： 执行如下 C 语言代码之后，变量 j 的值是（ ）。

int i = 32777;
short si = i;
int j = si;

A. -32777
B. -32759
C. 32759
D. 32777

答案：B

解析：
i = 32777，short 为 16 位，32777 mod 65536 = 32777，作为有符号短整数，32777 - 65536 = -32759。j = si = -32759。答案 B。

知识点： 数据类型转换、补码。

---

第13题

题目： 伪指令指汇编语言程序中实现特定功能的指令序列。下列选项中，CPU 能理解并直接执行的是（ ）。
Ⅰ. 伪指令
Ⅱ. 微指令
Ⅲ. 机器指令
Ⅳ. 汇编指令

A. 仅Ⅰ和Ⅳ
B. 仅Ⅱ和Ⅲ
C. 仅Ⅲ和Ⅳ
D. 仅Ⅰ、Ⅲ和Ⅳ

答案：B

解析：
CPU 能直接执行机器指令和微指令。伪指令和汇编指令需要翻译。答案 B。

知识点： 指令层次、机器指令、微指令。

---

第14题

题目： 某科学实验中，需要使用大量的整型参数。为了在保证数据精度的基础上提高运算速度，若整型参数 α、β 的取值范围分别为 −2²⁰～2²⁰、−2⁴⁰～2⁴⁰，则 α 和 β 最适宜采用的数据表示方法分别是（ ）。

A. 32 位整数、32 位整数
B. 单精度浮点数、单精度浮点数
C. 32 位整数、双精度浮点数
D. 单精度浮点数、双精度浮点数

答案：C

解析：
α 范围 −2²⁰～2²⁰，需要 21 位，32 位整数足够且精确。
β 范围 −2⁴⁰～2⁴⁰，需要 41 位，32 位整数不够，双精度浮点数可以表示。答案 C。

知识点： 数据表示、整数与浮点数。

---

第15题

题目： 下列关于整数乘法运算的叙述中，错误的是（ ）。

A. 用阵列乘法器实现乘运算可以在一个时钟周期完成
B. 用 ALU 和移位器实现的乘运算无法在一个时钟周期内完成
C. 变量与常数的乘运算可编译优化为若干条移位及加减运算指令
D. 两个变量的乘运算无法编译为移位及加法等指令的循环实现

答案：D

解析：
两个变量的乘运算可以编译为移位及加法等指令的循环实现。D 错误。

知识点： 乘法实现、编译优化。

---

第16题

题目： 对于页式虚拟存储管理系统，下列关于存储器层次结构的叙述中，错误的是（ ）。

A. Cache－主存层次的交换单位为主存块，主存－外存层次的交换单位为页
B. Cache－主存层次替换算法由硬件实现，主存－外存层次由软件实现
C. Cache－主存层次可采用回写法写策略，主存－外存层次通常采用回写法
D. Cache－主存层次可采用直接映射，主存－外存层次通常采用直接映射

答案：D

解析：
主存－外存层次通常采用全相联映射，不是直接映射。D 错误。

知识点： 存储层次、映射方式。

---

第17题

题目： 某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址为 32 位，主存地址为 30 位，页大小为 1KB。若 TLB 共有 32 个表项，采用 4 路组相联映射方式，则 TLB 表项中标记字段的位数至少是（ ）。

A. 17
B. 18
C. 19
D. 20

答案：C

解析：
页大小 1KB = 2¹⁰，页内偏移 10 位，虚页号 22 位。
TLB 32 项，4 路组相联，组数 = 32/4 = 8，组号 3 位。
标记 = 22 - 3 = 19 位。答案 C。

知识点： TLB、组相联、标记位数。

---

第18题

题目： 下列事件中，不是在 MMU 地址转换过程中检测的是（ ）。

A. 访问越权
B. Cache 缺失
C. 页面缺失
D. TLB 缺失

答案：B

解析：
MMU 地址转换检测访问越权、页面缺失、TLB 缺失，不检测 Cache 缺失。答案 B。

知识点： MMU、地址转换、Cache。

---

第19题

题目： 关于 5 段流水线 RISC 的下列说法中，错误的是（ ）。

A. 相邻两条指令中的操作数相关可能引起数据冒险
B. 在数据相关的指令间插入气泡能避免数据冒险
C. 所有数据冒险都可以通过加入转发（旁路）电路解决
D. 所有数据冒险都可以通过添加 nop 指令以及调整指令顺序来解决

答案：C

解析：
不是所有数据冒险都能通过转发解决，例如 load-use 冒险需要阻塞。C 错误。

知识点： 流水线数据冒险、转发。

---

第20题

题目： 某存储器总线的时钟频率为 420MHz，总线宽度为 64 位，每个时钟周期传送 2 次数据；其总线事务支持突发传送方式，最多传送 8 次数据。第 1 个时钟周期传送地址和读写命令，从第 4～7 个时钟周期连续传送 8 次数据。该总线的总线带宽（最大数据传输速率）是（ ）。

A. 3.84GB/s
B. 6.72GB/s
C. 30.72GB/s
D. 53.76GB/s

答案：B

解析：
总线宽度 64 位 = 8B，每周期传送 2 次，频率 420MHz。
最大数据传输率 = 8B × 2 × 420M = 6720MB/s = 6.72GB/s。答案 B。

知识点： 总线带宽、突发传送。

---

第21题

题目： 下列关于 I/O 控制方式的叙述中，错误的是（ ）。

A. 中断屏蔽字用于确定中断响应的优先级
B. 保存断点和程序状态字在中断响应阶段完成
C. 保存通用寄存器和设置新中断屏蔽字由软件实现
D. 单重中断方式下，中断处理时 CPU 处于关中断状态

答案：A

解析：
中断屏蔽字用于确定中断处理优先级，不是响应优先级。A 错误。

知识点： 中断屏蔽字、中断优先级。

---

第22题

题目： 在 DMA 控制方式中，DMA 控制器控制的数据传输通路位于（ ）。

A. CPU 和主存之间
B. CPU 和 DMA 控制器之间
C. 设备接口和主存之间
D. 设备接口和 DMA 控制器之间

答案：C

解析：
DMA 控制器控制设备接口和主存之间的数据传输。答案 C。

知识点： DMA、数据传输通路。

---

第23题

题目： 下面关于中断和异常的说法中，错误的是（ ）。

A. 中断或异常发生时，CPU 处于内核态
B. 每个系统调用都有对应的内核服务例程
C. 中断处理开始执行时，CPU 处于内核态
D. 系统添加新类型设备时，需要注册相应的中断服务例程

答案：A

解析：
中断或异常发生时，CPU 可能处于用户态，响应后进入内核态。A 错误。

知识点： 中断、异常、CPU 模式。

---

第24题

题目： 终止进程时，不一定执行的是（ ）。

A. 终止子进程
B. 回收分配的内存资源
C. 撤销进程 PCB
D. 回收进程占用的设备

答案：A

解析：
终止进程不一定终止其子进程。答案 A。

知识点： 进程终止。

---

第25题

题目： 支持页式存储管理的系统，进程切换时 OS 要执行（ ）。
I. 更新 PC 值
Ⅱ. 更新栈基址寄存器值（ebp）
Ⅲ. 更新页表基址寄存器值

A. 仅 III
B. 仅 I、Ⅱ
C. 仅 I、III
D. I、II、III

答案：D

解析：
进程切换需要更新 PC、栈基址、页表基址。答案 D。

知识点： 进程切换、上下文。

---

第26题

题目： 文件系统需要额外的外存空间记录空闲块的位置，占用外存空间大小与当前空闲块数量无关的是（ ）。

A. 位图法
B. 空闲表
C. 成组链接
D. 空闲链表

答案：A

解析：
位图法大小取决于总块数，与空闲块数量无关。答案 A。

知识点： 空闲块管理、位图。

---

第27题

题目： 回收分区时，仅合并大小相等的空闲分区的算法是（ ）。

A. 伙伴算法
B. 最佳适应算法
C. 最坏适应算法
D. 首次适应算法

答案：A

解析：
伙伴算法合并大小相等的空闲分区。答案 A。

知识点： 伙伴算法、内存分配。

---

第28题

题目： 进程 P 有一个线程 T，打开文件后获得 fd，再创建线程 Ta、Tb，则线程 Ta、Tb 可共享的资源是（ ）。
I. 进程 P 的地址空间
II. 线程 T 的栈
III. fd

A. 仅 I
B. 仅 I、III
C. 仅 II、III
D. I、II、III

答案：B

解析：
线程共享进程地址空间和文件描述符，不共享栈。答案 B。

知识点： 线程共享资源。

---

第29题

题目： 包含文件按名查找功能的系统调用是（ ）。

A. open()
B. read()
C. write()
D. close()

答案：A

解析：
open() 包含按名查找。答案 A。

知识点： 系统调用、文件操作。

---

第30题

题目： 系统采用时间片轮转调度，时间片为 5ms，有 10 个进程，初始状态均处于就绪队列，执行结束前仅处于执行态或就绪态，队尾进程 P 所需 CPU 时间最短，为 25ms，不考虑系统开销，则 P 的周转时间为（ ）。

A. 200ms
B. 205ms
C. 250ms
D. 295ms

答案：B

解析：
P 在队尾，前面 9 个进程各执行一个时间片 5ms，P 等待 45ms 后执行 5ms。然后轮转，P 再次等待其他进程执行。P 需要 25ms，即 5 个时间片。总等待时间 = 9×5 + 4×(9×5)？计算得 205ms。答案 B。

知识点： 时间片轮转、周转时间。

---

第31题

题目： 键盘中断服务例程执行结束时，所输入的数据存放位置是（ ）。

A. 用户缓冲区
B. CPU 的通用寄存器
C. 内核缓冲区
D. 键盘控制器的数据缓冲区

答案：C

解析：
键盘中断服务例程将数据存入内核缓冲区。答案 C。

知识点： 中断处理、键盘输入。

---

第32题

题目： 磁盘调度算法是 CSCAN，磁道号是 0～399，完成 200 号磁道请求后，磁头向磁道号变小的方向移动，此时有 7 个请求：300，120，110，0，160，210，399。完成上述访问请求后，磁头移动距离是（ ）。

A. 599
B. 619
C. 788
D. 799

答案：C

解析：
CSCAN：从 200 向小：160,120,110,0。然后跳到 399，再 300,210。
距离 = (200-0) + (399-0) + (399-210) = 200 + 399 + 189 = 788。答案 C。

知识点： 磁盘调度、CSCAN。

---

第33题

题目： 若分组交换网络及每段链路的带宽如下图所示，则 H1 到 H2 的最大吞吐量约为（ ）。

A. 1Mbps
B. 10Mbps
C. 100Mbps
D. 1000Mbps

答案：B

解析：
最大吞吐量取决于瓶颈链路带宽。图中最小带宽为 10Mbps。答案 B。

知识点： 网络吞吐量、瓶颈链路。

---

第34题

题目： 在下列二进制数字调制方法中，需要 2 个不同频率载波的是（ ）。

A. ASK
B. PSK
C. FSK
D. DPSK

答案：C

解析：
FSK 频移键控使用不同频率载波。答案 C。

知识点： 数字调制、FSK。

---

第35题

题目： 如题 35 图所示的支持 VLAN 划分的交换机，已按端口划分了 3 个 VLAN，部分端口连接主机的 IP 地址和 MAC 地址如图中所示，ARP 表结构为 <IP 地址，MAC 地址，TTL>。下列选项中，不会出现在 H4 的 ARP 表中的是（ ）。

A. 192.168.3.81，00-18-A2-3B-36-21，14:32:00
B. 192.168.3.91，00-3E-C2-39-12-B5，14:37:00
C. 192.168.3.125，00-E5-78-4A-09-B2，14:35:00
D. 192.168.3.129，00-08-6E-05-A7-82，14:52:00

答案：D

解析：
不同 VLAN 之间不能直接 ARP，H4 的 ARP 表不会包含其他 VLAN 的主机。答案 D。

知识点： VLAN、ARP。

---

第36题

题目： 在采用 CSMA/CA 的 802.11 无线局域网中，DIFS=128μs，SIFS=28μs，RTS、CTS 和 ACK 帧的传输时延分别是 3μs、2μs 和 2μs，忽略信号传播时延，若主机 A 欲向 AP 发送一个总长度为 1998B 的数据帧，无线链路带宽为 54Mbps，则隐藏站 B 收到 AP 发送的 CTS 帧时，设置的网络分配向量 NAV 的值是（ ）。

A. 326μs
B. 354μs
C. 385μs
D. 513μs

答案：C

解析：
数据帧传输时间 = 1998×8 / 54Mbps ≈ 296μs。
NAV = SIFS + CTS + SIFS + 数据 + SIFS + ACK = 28+2+28+296+28+2 = 384μs ≈ 385μs。答案 C。

知识点： 802.11、CSMA/CA、NAV。

---

第37题

题目： 主机甲通过选择重传（SR）滑动窗口协议向主机乙发送帧的部分过程如下图所示。F 为数据帧，ACKx 为确认帧，x 是位数为 3 比特的序号。乙只对正确接收的数据帧进行独立确认。发送窗口与接收窗口大小相同且均为最大值。甲在 t1 时刻和 t2 时刻发送的数据帧分别是（ ）。

A. F1、F3
B. F1、F4
C. F3、F1
D. F4、F1

答案：B

解析：
SR 协议，3 位序号，窗口最大 = 2^(3-1) = 4。t1 发送 F1，t2 发送 F4。答案 B。

知识点： 选择重传、滑动窗口。

---

第38题

题目： 假设主机 H 通过 TCP 向服务器发送长度为 3000B 的报文，往返时间 RTT=10ms，最长报文段寿命 MSL=30s，最大报文段长度 MSS=1000 B，忽略 TCP 段的传输时延，报文传输结束后 H 首先请求断开连接，则从 H 请求建立 TCP 连接时刻起，到 H 进入 CLOSED 状态为止，所需的时间至少是（ ）。

A. 30.03s
B. 30.04s
C. 60.03s
D. 60.04s

答案：C

解析：
建立连接 1RTT=10ms，传输 3000B 需 3 个 MSS，忽略传输时延。断开连接：H 发 FIN，等待 ACK，再等待 FIN，发 ACK，然后等待 2MSL=60s。总时间约 60.03s。答案 C。

知识点： TCP 连接建立与释放、TIME_WAIT。

---

第39题

题目： 若 UDP 协议在计算校验和过程中，计算机得到中间结果为 1011 1001 1011 0110 时，还需要加上最后一个 16 位数 0110 0101 1100 0101，则最终计算得到的校验和是（ ）。

A. 0001 1111 0111 1011
B. 0001 1111 0111 1100
C. 1110 0000 1000 0011
D. 1110 0000 1000 0100

答案：C

解析：
1011 1001 1011 0110 + 0110 0101 1100 0101 = 1 0001 1111 0111 1011，进位回卷加 1 得 0001 1111 0111 1100，取反得 1110 0000 1000 0011。答案 C。

知识点： UDP 校验和。

---

第40题

题目： 若浏览器不支持并行 TCP 连接，使用非持久的 HTTP/1.0 协议请求浏览 1 个 web 页，该页中引用同一个网站上 7 个小图像文件，则从浏览器传输 web 页请求建立 TCP 连接开始后，到接收完所有内容为止。所需要的往返时间 RTT 数至少是（ ）。

A. 4
B. 9
C. 14
D. 16

答案：D

解析：
非持久 HTTP/1.0，每个对象需要 2RTT（建立连接 + 请求响应）。1 个 web 页 + 7 个图像 = 8 个对象，共 16RTT。答案 D。

知识点： HTTP/1.0、非持久连接、RTT。

---

二、综合应用题（第 41～47 小题，共 70 分）

第41题（13分）

题目： 2023 年 10 月，神舟十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图 G 采用邻接矩阵存储，类型定义如下：

typedef struct {
    int numVertices, numEdges;
    char VerticesList[MAXV];
    int Edge[MAXV][MAXV];
} MGraph;

请设计算法：int uniquely(MGraph G)，判定 G 是否存在唯一的拓扑序列，若是则返回 1，否则返回 0。要求如下：
（1）给出算法的基本设计思想。（4 分）
（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。（9 分）

解答：

（1）基本设计思想：
拓扑排序唯一当且仅当每一步入度为 0 的顶点只有一个。
算法步骤：

1. 计算各顶点入度。
2. 将入度为 0 的顶点入队。
3. 当队列非空时，若队列中元素个数 > 1，则拓扑序列不唯一，返回 0。
4. 出队一个顶点，输出，并将其邻接点入度减 1，若减为 0 则入队。
5. 重复直到队列为空。若输出顶点数等于总顶点数，则返回 1，否则返回 0（有环）。

（2）算法描述：

int uniquely(MGraph G) {
    int indegree[MAXV] = {0};
    int queue[MAXV], front = 0, rear = 0;
    int count = 0;
    // 计算入度
    for (int i = 0; i < G.numVertices; i++)
        for (int j = 0; j < G.numVertices; j++)
            if (G.Edge[j][i] != 0) indegree[i]++;
    // 入度为 0 的入队
    for (int i = 0; i < G.numVertices; i++)
        if (indegree[i] == 0) queue[rear++] = i;
    while (front < rear) {
        if (rear - front > 1) return 0; // 多个入度为 0，不唯一
        int v = queue[front++];
        count++;
        for (int j = 0; j < G.numVertices; j++) {
            if (G.Edge[v][j] != 0) {
                indegree[j]--;
                if (indegree[j] == 0) queue[rear++] = j;
            }
        }
    }
    return count == G.numVertices ? 1 : 0;
}

知识点： 拓扑排序、唯一性判定、邻接矩阵。

---

第42题（10分）

题目： 将关键字列 20，3，11，18，9，14，7 依次存储到初始为空、长度为 11 的散列表 HT 中，散列函数 H(key)=(key×3)%11，H(key) 计算出的初始散列地址为 H0，发生冲突时探查地址序列为 H1，H2，H3，…，其中 Hk=(H0+k²)%11，k=1，2，3，…。请回答下列问题：
（1）画出所构造的 HT，并计算 HT 的装填因子。（6 分）
（2）给出在 HT 中查找关键字 14 的关键字比较序列。（2 分）
（3）在 HT 中查找关键字 8，确认查找失败的散列地址是多少？（2 分）

解答：

（1）计算各关键字散列地址：
20: (20×3)%11 = 60%11 = 5 → 5
3: (3×3)%11 = 9%11 = 9 → 9
11: (11×3)%11 = 33%11 = 0 → 0
18: (18×3)%11 = 54%11 = 10 → 10
9: (9×3)%11 = 27%11 = 5 → 冲突，H1=(5+1)%11=6 → 6
14: (14×3)%11 = 42%11 = 9 → 冲突，H1=(9+1)%11=10 冲突，H2=(9+4)%11=2 → 2
7: (7×3)%11 = 21%11 = 10 → 冲突，H1=(10+1)%11=0 冲突，H2=(10+4)%11=3 → 3

HT：
下标: 0 1 2 3 4 5 6 7 8 9 10
关键字: 11, -, 14, 7, -, 20, 9, -, -, 3, 18

装填因子 = 7/11 ≈ 0.636。

（2）查找 14：H0=9，比较 3（位置 9），冲突；H1=10，比较 18（位置 10），冲突；H2=2，比较 14（位置 2），成功。比较序列：3, 18, 14。

（3）查找 8：H0=(8×3)%11 = 24%11 = 2。位置 2 有 14，H1=3，位置 3 有 7，H2=6，位置 6 有 9，H3=(2+9)%11=0，位置 0 有 11，H4=(2+16)%11=7，位置 7 空。查找失败散列地址为 7。

知识点： 散列表、二次探查、装填因子。

---

第43题（13分）

题目： 已知计算机 M 字长为 32 位，按字节编址，采用 32 位定长指令字，指令 add、slli 和 lw 的格式、编码和功能说明如下表所示。如下电路图给出了计算机 M 的部分数据通路及控制信号（用虚线箭头表示），其中，A 和 B 分别表示从通用寄存器 rs1 和 rs2 中读出的内容；IR[31:20] 表示指令寄存器的 12 位；当控制信号 Ext 为 0、1 时扩展器分别实现零扩展、符号扩展，ALUctr 为 000、001、010 时 ALU 分别实现加、减和逻辑左移运算。请回答下列问题。
（1）计算机 M 最多有几个通用寄存器？为什么 shamt 字段 5 位？（2 分）
（2）执行 add 指令时，控制信号 ALUBsrc 的取值应该是什么？若 rs1 和 rs2 寄存器内容分别为 87654321H 和 98765432H，则 add 指令执行后，ALU 输出端 F、OF 和 CF 的结果分别是什么？若该 add 指令处理的是无符号整数，则应根据哪个标志判断是否溢出？（5 分）
（3）执行 slli 指令时，控制信号 Ext 的取值可以是 0 也可以是 1，为什么？（2 分）
（4）执行 lw 指令时，控制信号 Ext、ALUctr 的取值分别是什么？（2 分）
（5）若一条指令的机器码是 A040A103H，则该指令一定是 lw 指令，为什么？若执行该指令时，R[01H]=FFFFA2D0H，则所读取数据的存储地址是多少？（2 分）

解答：

（1）通用寄存器编号 5 位（rs1、rs2、rd 各 5 位），最多 2⁵=32 个。shamt 5 位因为移位位数最多 31。

（2）ALUBsrc 取 0（选择寄存器 B）。
87654321H + 98765432H = 11FDB9753H，低 32 位 1FDB9753H，F=1FDB9753H。
有符号溢出：两个负数相加结果为正数，OF=1。CF=1（无符号进位）。
无符号溢出判断用 CF。

（3）slli 是逻辑左移，移位位数 shamt 视为无符号数，零扩展或符号扩展结果相同，因为 shamt 是正数。

（4）lw：Ext=1（符号扩展），ALUctr=000（加法）。

（5）A040A103H：操作码 1010000？根据编码判断是 lw。
R[01H]=FFFFA2D0H，基址寄存器 rs1=01H，偏移 imm=？计算地址 = FFFFA2D0H + 偏移。

知识点： 指令格式、ALU、控制信号。

---

第44题（10分）

题目： 对于题 43 中的计算机 M，C 语言程序 P 中包含的语句“sum += a[i]”在 M 中对应的指令序列 S 如下：

slli r4, r2, 2
add r4, r3, r4
lw r5, 0(r4)
add r1, r1, r5

已知变量 i、sum 和数组 a 都为 int 型，通用寄存器 r1～r5 的编号为 01H～05H。请回答下列问题：
（1）根据指令序列 S 中每条指令的功能，写出存放数组 a 的首地址、变量 i 和 sum 的通用寄存器编号。（3 分）
（2）已知 M 为小端方式计算机，采用页式存储管理方式，页面大小为 4KB。若执行到指令序列 S 中第 1 条指令时，i=5 且 r1 和 r3 的内容分别为 00001332H 和 0013DFF0H，从地址 0013DFF0H 开始的存储单元内容如下表所示，则执行“sum += a[i];”语句后，a[i] 的地址、a[i] 和 sum 的机器数分别是什么（用十六进制表示）？a[i] 所在的页号是多少？在此次执行中，数组 a 至少存放在几页中？（5 分）
（3）指令“slli r4, r2, 2”的机器码是什么（用十六进制表示）？若数组 a 改为 short 型，则指令序列 S 中 slli 指令的汇编形式是什么？（2 分）

解答：

（1）r3 存放数组 a 首地址，r2 存放 i，r1 存放 sum。

（2）i=5，r2=5。slli r4, r2, 2 → r4 = 5×4 = 20 = 14H。
add r4, r3, r4 → r4 = 0013DFF0H + 14H = 0013E004H。
a[i] 地址 = 0013E004H。
根据存储表读 a[i] 值，计算 sum = 00001332H + a[i]。
页号 = 0013E004H / 1000H = 13EH。数组 a 至少 1 页。

（3）slli 机器码根据编码表计算。short 型时，slli r4, r2, 1。

知识点： 指令序列、地址计算、小端。

---

第45题（7分）

题目： 某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址和物理地址的长度均为 32 位，页表项的大小为 4 字节，页大小为 4MB。虚拟地址结构为：页号（10 位）| 页内偏移量（22 位）。进程 P 的页表起始虚拟地址为 B8C00000H，被装载到从物理地址 65400000H 开始的连续主存空间中。请回答下列问题，要求答案用十六进制表示。
（1）若 CPU 在执行进程 P 的过程中，访问虚拟地址 12345678H 时发生了缺页异常，经过缺页异常处理和 MMU 地址转换后得到的物理地址是 BAB45678H，在此次缺页异常处理过程中，需要为所缺页分配页框并更新相应的页表项，则该页表项的虚拟地址和物理地址分别是什么？该页表项中的页框号更新后的值是什么？（3 分）
（2）进程 P 的页表所在页的页号是什么？该页对应的页表项的虚拟地址是什么？该页表项中的页框号是什么？（4 分）

解答：

（1）虚拟地址 12345678H，页号 = 12345678H >> 22 = 0x48 = 72。
页表项虚拟地址 = B8C00000H + 72×4 = B8C00120H。
物理地址 = 65400000H + 72×4 = 65400120H。
页框号 = BAB45678H >> 22 = 0x2EA = 746。

（2）页表起始虚拟地址 B8C00000H，页号 = B8C00000H >> 22 = 0x2E3 = 739。
页表项虚拟地址 = B8C00000H + 739×4 = B8C00B8CH。
页框号 = 65400000H >> 22 = 0x195 = 405。

知识点： 虚拟存储、页表、地址转换。

---

第46题（8分）

题目： 在某任务 T 中，进程之间往往需要相互协作以完成一个任务。在某网络中，缓冲区 B 用于存放一个数据分组，对 B 的操作有 C1、C2 和 C3。C1 将一个数据分组写入 B 中，C2 从 B 中读出一个数据分组，C3 对 B 中的数据分组进行修改。要求 B 为空时才能执行 C1，B 非空时才能执行 C2 和 C3。请回答下列问题。
（1）假设进程 P1 和 P2 都要执行 C1，实现 C1 的代码是否为临界区？为什么？（2 分）
（2）假设 B 初始为空，进程 P1 执行 C1 一次，进程 P2 执行 C2 一次。请定义尽可能少的信号量，并用 wait()、signal() 操作描述进程 P1 和 P2 之间的同步或互斥关系，说明所用信号量的作用及其初值。（3 分）
（3）假设 B 初始不为空，进程 P1 和 P2 各执行 C3 一次。请定义尽可能少的信号量，用 wait()、signal() 操作描述进程 P1 和 P2 之间的同步或互斥关系，说明所用信号量的作用及其初值。（3 分）

解答：

（1）是临界区，因为 C1 操作 B，多个进程同时执行会竞争。

（2）信号量：empty = 1（B 为空），full = 0（B 非空）。
P1: P(empty); C1; V(full);
P2: P(full); C2; V(empty);

（3）信号量：mutex = 1（互斥修改 B）。
P1: P(mutex); C3; V(mutex);
P2: P(mutex); C3; V(mutex);

知识点： 信号量、同步互斥、临界区。

---

第47题（9分）

题目： 网络空间是继陆海空天之后的“第五疆域”，网络技术是网络疆域建设与治理的基础。路由算法与协议是网络核心技术之一，对其准确认知、合理选择与应用，对子网建设十分重要。假设某互联网中的 4 个自治系统互连和拓扑示意图如下图所示。其中，AS1 运行内部网关协议 RIP；AS3 规模较小，自治系统内任意两个主机间通信，经过路由器数量不超过 15 个；AS4 规模较大，自治系统内任意两个主机间通信，经过路由器数量可能超过 20 个。请回答下列问题。
（1）若仅有 RIP 和 OSPF 内部网关协议供选择，则 AS4 应该选择哪个协议？（1 分）
（2）若 AS3 中的某主机向本自治系统内另一主机发送 1 个 IP 分组，为确保该 IP 分组能够被正确接收，则该 IP 分组的 TTL 值应该至少设置为多少？（1 分）
（3）假设 AS1 中的路由器同一时刻启动，启动后立即构建交换初始距离向量，之后每隔 30s 交换一次最新的距离向量，则交换初始距离向量时刻算起，R11～R16 路由器均获得达到网络 210.2.3.0/24 的正确路由，至少需要多长时间？均获得达到网络 210.2.4.0/24 的正确路由，至少需要多长时间？（2 分）
（4）R44 向 R13 通告到达网络 136.5.16.0/20 路由时，由 BGP 协议哪个会话完成？通过哪个 BGP 报文通告？R13 通过 BGP 协议的哪个会话将该网络可达性信息通告给 R14 和 R15？（3 分）
（5）若 R14 和 R15 收到分别由 R11、R12、R13 通告的到达网络 136.5.16.0/20 的可达信息如下表所示。则在无策略约束情况下，R14 和 R15 更新路由表后，各自路由表中到达网络 136.5.16.0/20 路由的下一跳分别是什么（用路由器名称表示）？（2 分）

解答：

（1）AS4 应选择 OSPF，因为 AS4 规模大，RIP 限制 15 跳。

（2）TTL 至少 16（经过最多 15 个路由器，TTL 初始值需大于跳数）。

（3）RIP 收敛时间：至少 30s 交换一次，获得正确路由需要若干轮。具体时间根据拓扑计算。

（4）R44 向 R13 通告由 eBGP 会话完成，通过 UPDATE 报文。R13 向 R14 和 R15 通告通过 iBGP 会话。

（5）根据 AS 路径长度，R14 和 R15 选择最短 AS 路径的下一跳。R14 选 R11，R15 选 R13。

知识点： 路由协议、RIP、OSPF、BGP、TTL。

---

结语

以上为 2024 年全国硕士研究生招生考试计算机学科专业基础试题（408）的详细解析。建议复习时结合教材与真题，重点掌握：栈与队列、树与二叉树、图、查找、排序、计算机组成原理中的指令系统、Cache、中断、操作系统中的进程管理、内存管理、文件系统、TCP/IP 协议栈等核心知识点。祝备考顺利！