2022 年真题

正确答案：B

正确答案：B
当外层循环的变量 $i$ 取不同值时，内层循环就执行多少次，因此总循环次数为 的所有取值之和。假设外层循环共执行 $k$ 次，当 $i=1,2,4,8,\cdots ,2^{k-1}(2^{k-1}<n\le 2^k)$ 时，内层循 环执行 $i$ 次，因此总循环次数 $T=1+2+4+8+\cdots +2^{k-1}=2^k-1$ 即 $n<T<2n$ ，时间复杂度为 $O(n)$ 。

正确答案：D

正确答案：D
参考 入栈出栈序列，如果给定一个入栈序列，我们可以得到其所有可能的出栈序列，所以当给定一个出栈序列时，我们可以判断其是否正确，所以 A、B、C 均为错误选项。

正确答案：B

正确答案：B

对于此类题，每种情况只需举出一个反例即可。如图 1 所示，q 是 p 的双亲，中 序遍历序列为 {p, q}，I 可能。如图 2 所示，q 是 p 的右孩子，中序遍历序列为 {p, q}，Ⅱ可能。 如图 4 所示，q 是 p 的双亲的双亲，中序遍历序列为 {x, p, q}，IV 可能。如图 3 所示，q 是 p 的右兄弟，F 是 q 和 p 的父结点，中序遍历要求先遍历左子树，再访问根结点，最后遍历右 子树，因此一定先访问 p，再访问 F，最后访问 q，p 和 q 不可能相邻出现，II 不可能。

正确答案：C

正确答案：C
高度为 $n$ 的二叉树最多有 $1+2+\cdots +2^{n-1}=2^n-1$ 个结点，高度为 $n$ 的三叉树最多有 $f(n)=1+3+\cdots +3^{n-1}=\frac{3^n-1}{3-1}-\frac{3^n-1}{2}$ 。 $f(5)=121$ $f(6)=364$ 因为 $121<244<364$ ，所以高度至少为 6。

正确答案：D

正确答案：D

可以画一个简单的特例来证明。图 1 是满足条件的二叉树 T1，图 2 是满足条件的二叉树 T2，结点中有值表示这个结点是编码字符。T1 和 T2 的结点数不同，A 错误。T1 的高度等于 T2 的高度，B 错误。出现频次不同的字符在 T1 中也可能处于相同的层，C 错误。对于定长编码码集，所有字符一定都在 T2 中处于相同的层，而且都是叶子结点。

正确答案：D

正确答案：D

注意，E 是图的边数，V 是图的顶点数。A 和 B 明显错误，如图 1 所示，|V| < |E|，但图 G 不连通；如图 2 所示，|V| > |E|，但图 G 不连通。如图 3 所示，在无向图中至少要有 |V| - 1 个顶点才可能连通，顶点数小于 |V| - 1 一定不可能连通，C 错误，D 正确。

正确答案：B

正确答案：B

在 AOE 网中，活动的时间余量 = 结束顶点的最迟开始时间 - 开始顶点的最早开始时间 - 该活动的持续时间。根据关键路径算法得到下表：

结点编号	1	2	3	4	5	6
最早开始时间 ve(i)	0	2	5	8	9	12
最迟开始时间 vl(i)	0	4	5	8	11	12

• c 的时间余量 = vl(3) - ve(2) - 1 = 5 - 2 - 1 = 2
• g 的时间余量 = vl(6) - ve(3) - 1 = 12 - 5 - 1 = 6，
• h 的时间余量 = vl(5) - ve(4) - 1 = 11 - 8 - 1 = 2
• j 的时间余量 = vl(6) - ve(5) - 1 = 12 - 9 - 1 = 2，

时间余量最大的活动是 g。

正确答案：D

正确答案：D

参考 B 树插入操作，在 5 阶 B 树中，除根结点外的非叶子结点的关键字数 k 需要满足 2 ≤ k ≤ 4。当被删关键字 x 不在终端结点（最底层非叶子结点）时，可以用 x 的前驱（或后继) 关键字 y 来替代 x，然后在相应结点中删除 y。

情况①：删除 260，将其前驱 110 放入 260 处，删除 110 后的结点 不满足 5 阶 B 树定义，从左兄弟中借 85，将 85 放入根中，将根中的 90 移入结点 变为 <90, 100>。

情况②：删除 260，将其后继 280 放入 260 处，结点 不满足 5 阶 B 树定义且左右兄弟都不够借，结点 可以和左兄弟 <100, 110> 以及关键字 280 合并成一个新的结点 <100, 110, 280, 300>。

情况③：在情况②中，结点 也可以和右兄弟 <400, 500> 以及关键字 350 合并成一个新的结点 <300, 350, 400, 500>。综上，T1 根结点中的关键字序列可能是 <60, 85, 110, 350> 或 <60, 90, 350> 或 <60, 90, 280>，仅 D 不可能。

正确答案：D

正确答案：D
三者都会影响：装填因子越大，说明 哈希表 中存储的元素越满，发生冲突的可能性越大，平均查找长度也越大。散列函数、突解决策略会影响发生冲突的可能性。

正确答案：A

正确答案：A
概念题，归并针对的对象是序列，二路归并就是将两个有序序列合并成一个。

正确答案：D

正确答案：D

直接插入排序 和 快速排序 的特点如下表所示：

	适合初始序列情况	适合元素数量	空间复杂度	稳定性
直接插入排序	大部分元素有序	较少	$O(1)$	稳定
快速排序	基本无序	较多	$O(lo{g}_{2}n)$	不稳定

I. 大部分元素已有序

✅ 正确。 直接插入排序在序列基本有序的情况下表现非常好，接近 O(n) 的时间复杂度，而快速排序在此场景下仍需要递归处理。因此此项成立。

II. 待排序元素数量很少

✅ 正确。 当元素数量较少时，插入排序的常数因子小、实现简单，实际运行效率往往优于快速排序，这是实际工程中的常见优化策略（如许多库排序在小规模时使用插入排序）。

III. 要求空间复杂度为 O(1)

✅ 正确。 插入排序是原地排序，空间复杂度为 O(1)；而快速排序虽然通常也是原地排序，但某些实现（尤其是递归调用）存在 O(log n) 的栈空间。若对空间要求极严，插入排序更适合。

IV. 要求排序算法是稳定的

✅ 正确。 插入排序是稳定排序，而快速排序是不稳定的（原始版本）。如果应用场景要求排序后相等元素的相对顺序不变，选择插入排序是合理的。

综上，所有说法都正确，正确答案选择 D。

正确答案：A

正确答案：A
参考 指令执行指标，CPI 指平均每条指令的执行需要多少个时钟周期。由于 80% 的指令执行平均需要 1 个时钟周期，20% 的指令执行平均需要 10 个时钟周期，因此 CPI = $80\%\times 1+20\%\times 10=2.8$ 。 计算机主频为 1GHz，程序 P 共执行 10000 条指令，平均每条指令需要 2.8 个时钟周期，因此， CPU 执行时间= $(10000\times 2.8)/10^9=2.8\times 10^{-5}s=28\mu s$ 。

正确答案：B

正确答案：B
32 位 补码 的最大值为 0x7fffffff = $2^{31}-1$ （最高位为 0，其他位为 1），最小值为 0x80000000 = $-2^{31}$ （最高位为 1，其他位为 0)。

正确答案：A

正确答案：A
IEEE754 单精度浮点数格式 中依次为数符 1 位、阶码 8 位（偏置值 127)、尾数 23 位（隐藏 1 位）。 $-0.4375=-1.75\times 2^{-2}$ ，保证小数点前是 1。根据单精度浮点数格式，数符 为 1；阶码为移码表示，-2+127=125，写成 8 位二进制数为 01111101；尾数隐藏小数点前 的 1，剩下的 0.75 写成二进制数为 0.11，所以尾数部分是 1100…0。该浮点数的二进制格式为 1011111011100000000000000000000，对应的十六进制格式为 BEE00000H。

正确答案：C

正确答案：C
本题考察 通过单级页表的地址翻译过程。 页大小为 4KB = $2^{12}$ B，按字节编址，故页内地址为 12 位。虚拟地址空间大小为 4GB=23，故虚拟地址共 32 位，其中低 12 位为页内地址，高 20 位为虚页号。题中给出的 虚拟地址为 00082840H，虚页号为高 20 位即 00082H（页内地址为低 12 位即 840H），82H 对 应的十进制数为 130（注意题中页表的虚页号部分末尾未写 H，所以是十进制数，故查找时要 先将虚页号转换为十进制数），查页表命中，且存在位为 1，对应页框号为 018H。将查找到的 页框号 018H 和页内地址 840H 拼接，得到主存地址为 018840H。

正确答案：A

正确答案：A

Cache 采用 组相联映射，主存地址结构应分为 Tag 标记、组号、块内地址三部分。 主存块大小 = Cache 块大小 = 64B = $2^6$ B，因此块内地址占 6 位。Cache 数据区容量为 32KB, 每个 Cache 块大小为 64B，则 Cache 总块数 = 32KB/64B = $2^9$ ，由于采用 8 路组相联映射，即 每 8 个 Cache 块为一个分组，因此总共被分为 $2^9/8=2^6$ 组，因此，组号占 6 位。除了块内地 址和组号，剩余的位为 Tag 标记，占 32-6-6=20 位。地址结构如下所示。

Cache 采用 8 路组相联映射，因此在访问一个物理地址时，要先根据组号定位到某一分组，然 后用物理地址的高 20 位（Tag 标记）与分组中 8 个 Cache 行的 Tag 标记做并行比较（用 8 个 20 位“比较器”实现），若某个 Cache 行的 Tag 标记与物理地址的高 20 位完全一致，则选 中该 Cache 行。综上所述，在组相联映射的 Cache 中，“比较器”用于并行地比较分组中所 有 Cache 行的 Tag 标记位与欲访问物理地址的 Tag 标记位，因此比较器的个数就是分组中的 Cache 行数 8，比较器的位数就是 Tag 标记位数 20。

正确答案：C

正确答案：C

本题考察 主存容量的扩展。

• 8×8192×8192×8bit=512MB，内存条的容量为 512MB，A 正确。
• 存储器总线宽度 64=8×8bit，而每个芯片一次只能传输 8bit，需要 8 体多模块交叉编址才能实现，B 正确。
• DRAM 芯片是矩阵样式的行列存储结果，行地址和列地址 复用一个地址，根据题意，DRAM 芯片的行数和列数都是 8192，所以引脚个数为 ${\log }_{2}8192=13$ ，C 错误。
• 芯片内行数是 8192，一行的大小是 8192×8bit，行缓冲长度就是一行的大小，D 正确。

正确答案：B

正确答案：B
指令集处于软硬件的交界面上。指令字和指令格式、通用寄存器个数和位数都与 机器指令有关，由 指令体系结构 规定。两个 CPU 可以有不同的时钟周期，但指令集可以相同，CPU 的 时钟周期不由 ISA 规定。加法器的进位方式涉及电路设计，也不由指令集规定。

正确答案：D

正确答案：D

本题考察 N 地址指令 如下图所示：零地址指令的 OP 字段位数相比一地址和二地址指令更短，但是需要注意的是，零地址指令的 OP 字段前缀与一地址和二地址指令的 OP 字段不能相同。

所以零地址指令的条数为 $2^{16}-254\times 2^6-12\times 2^{12}=128$ 。

正确答案：A

正确答案：A
将源程序转换为可执行目标文件的 过程分为预处理、编译、汇编、链接四个阶段

正确答案：C

正确答案：C
中断 I/O 方式 适用于字符型设备，此类设备的特点是数据传输速率慢，以字符或 字为单位进行传输，A 正确。若采用中断 VO 方式，当外设准备好数据后，向 CPU 发出中断 请求，CPU 暂时中止现行程序，转去运行中断服务程序，由中断服务程序完成数据传送，B 正确。若外设准备数据的时间小于中断处理时间，则可能导致数据丢失，以输入设备为例， 设备为进程准备的数据会先写入设备控制器的缓冲区（缓冲区大小有限，通常只能暂存几个 字节），缓冲区每写满一次，就会向 CPU 发出一次中断请求，CPU 响应并处理中断的过程， 就是将缓冲区中的数据“取走”的过程，因此若外设准备数据的时间小于中断处理时间，则 可能导致外设往缓冲区写入数据的速度快于 CPU 从缓冲区取走数据的速度，从而导致缓冲区 的数据被覆盖，进而导致数据丢失。C 错误。若采用中断 I/O 方式，则外设为某进程准备数据 时，可令该进程阻塞，CPU 运行其他进程，D 正确。

正确答案：C

正确答案：C
本题考察 多处理器， MIMD 结构分为多计算机系统和多处理器系统，A 正确。向量处理器是 SIMD 的 变体，属于 SIMD 结构，B 正确。硬件多线程技术是在一个核中处理多个线程，可用于单核 处理器，C 错误。共享内存多处理器 (SMP) 具有共享的单一物理地址空间，所有核都可通 过存取指令来访问同一片主存地址空间，D 正确。

正确答案：D

正确答案：D
操作系统的 基本特点：并发、共享、虚拟、异步，其中最基本、一定要实现的是并发和共享，A、C 正确。早期的多道批处理操作系统会将所有进程的数据全部调入主存，再让多道程序并发执行，即使不支持虚拟存储管理，也能实现“多道程序并发”，B 正确。进程多并不意味着 CPU 利用率高，进程数量越多，进程之间的资源竞争越激烈，甚至可能因为资源竞争而出现死锁现象，导致 CPU 利用率低，D 错误。

正确答案：A

正确答案：A

解析：

• 中断向量表：在操作系统启动时，必须初始化中断向量表，用于存储中断服务例程的入口地址，以便处理硬件或软件中断。这是操作系统初始化过程中的关键步骤。
• 文件系统的根目录：根目录通常在文件系统格式化时创建，而不是操作系统初始化过程中。
• 硬盘分区表：分区表是在磁盘分区时创建的，通常在安装操作系统之前完成。
• 文件系统的索引节点表：索引节点表（inode 表）是在文件系统创建时生成的，不是操作系统初始化的一部分。

因此，正确答案是 A。

正确答案：C

正确答案：C

本题考察 优先级调度：

• 0 时刻调度进程 P0 获得 CPU；
• 1Oms 时 P2 进入就绪队列，调度 P2 抢占获得 CPU；
• 15ms 时 P3 进入就绪队列，调度 P3 抢占获得 CPU；
• 25ms 时 P3 执行完毕，调度 P2 获得 CPU；
• 40ms 时 P2 执行完毕，调度 P0 获得 CPU；
• 130ms 时 P2 执行完毕，调度 P1 获得 CPU；
• 190ms 时 P2 执行完毕，结束；总共调度 6 次。

正确答案：B

正确答案：B
初始时系统中的可用资源数为 <1,3,2>，只能满足 P0 的需求 <0,2,1>，所以 安全分配序列 第一个只能是 P0， 将资源分配给 P0 后，P0 执行完释放所占资源，可用资源数变为 <1,3,2> + <2,0,1> = <3,3,3>， 此时可用资源数既能满足 P1，也能满足 P2，可以先分配给 P1，P1 执行完释放资源再分配给 P2， 也可以先分配给 P2，P2 执行完释放资源再分配给 P1。 所以安全序列可以是 ①P0、P1、P2 或 ②P0、P2、P1。

正确答案：C

正确答案：C
CPU 在 用户态 时只能执行非特权指令，在 内核态 时可以执行特权指令和非特权指令。

正确答案：D

正确答案：D
参考 状态转化。 进程 P 读文件时，进程从执行态进入阻塞态，等待磁盘 I/O 完成，I 正确。进程 P4 的时间片用完，导致进程从执行态进入就绪态，转入就绪队列等待下次被调度，Ⅱ错误。进 程 P 申请外设，若外设是独占设备且正在被其他进程使用，则进程 P 从执行态进入阻塞态， 等待系统分配外设，Ⅲ 正确。进程 P 执行信号量的 wait() 操作，如果信号量的值小于等于 0，则进程进入阻塞态，等待其他进程用 signal() 操作唤醒，V 正确。

正确答案：A

正确答案：A
缺页异常 需要从磁盘调页到内存中，将新调入的页与页框建立对应关系，并修改 该页的存在位，B、C、D 正确：如果内存中有空闲页框，就不需要淘汰其他页，A 错误。

正确答案：D

正确答案：D
页置换算法会影响缺页率，例如，LRU 算法的缺页率通常要比 FIFO 算法的缺页 率低，排除 A。工作集的大小决定了分配给进程的物理块数，分配给进程的物理块数越多， 缺页率就越低，排除 B。进程的数量越多，对内存资源的竞争越激烈，每个进程被分配的物 理块数越少，缺页率也就越高，排除 C。页缓冲队列是将被淘汰的页面缓存下来，暂时不写 回磁盘，队列长度会影响页面置换的速度，但不会影响缺页率，答案选 D。

正确答案：B

正确答案：B

对四个选项进行逐一分析：

Ⅰ. 保存断点和程序状态字 ❌
参考中断处理过程，保存断点由中断隐指令完成，即由硬件完成。

Ⅱ. 保存通用寄存器的内容 ✅
为了防止系统调用覆盖用户程序中的数据，操作系统在进入系统调用处理程序时会保存用户程序的寄存器内容（这属于上下文切换的一部分）。

Ⅲ. 执行系统调用服务程序 ✅
系统调用就是要求操作系统执行某项服务，服务程序是操作系统的一部分，由操作系统调度执行。

Ⅳ. 将 CPU 模式改为内核态 ❌
这一点不是由操作系统主动完成，而是由硬件自动完成的：

当执行陷阱指令（如 int 0x80）或发生中断时，CPU 自动将模式从用户态切换为内核态，然后跳转到操作系统提供的中断向量地址。

所以，这属于硬件响应的一部分，不是由操作系统“显式”控制的。

所以正确答案选择 B。

正确答案：A

正确答案：A
厂家在设计一个设备时，通常会为该设备编写 设备驱动程序，主机需要先安装驱动程序，才能使用设备。当一个设备被连接到主机时，驱动程序负责初始化设备（如将设备控制器中的寄存器初始化），B 正确。当进程在执行驱动程序时，可能会因为设备忙碌而进入阻塞态，C 正确。设备的读/写操作本质就是在设备控制器和主机之间传送数据，而只有厂家知道 设备控制器的内部实现，因此也只有厂家提供的驱动程序能控制设备的读/写操作，D 正确。厂家会根据设备特性，在驱动程序中实现一种合适的 I/O 控制方式，A 错误。

正确答案：B

正确答案：B
在 ISO/OSI 模型中，数据链路层、网络层、传输层都具有流量控制功能，数据链路层是相邻结点之间的流量控制，网络层是整个网络中的流量控制，传输层是端到端的流量控制。

正确答案：C

正确答案：C
根据 奈奎斯特定理，最大数据传输速率= $2Wlo{g}_{2}V$ ，4 个幅值的 ASK 调制说明有 4 个相位，将 V=4 代入，得 800kbps。

正确答案：B

正确答案：B
主机所在网络的网络地址可以通过主机的 IP 地址和 子网掩码 逐位相与得到。子网掩码 255.255.192.0 的二进制前 18 位为 1、后 14 位为 0，把主机 P 地址的后 14 位变为 0，得 到的结果为 183.80.64.0，即为主机所在网络的网络地址。

正确答案：D

正确答案：D
默认网关 可以理解为离当前主机最近的路由器的端口地址，所以是 192.168.1.62， 而该主机的子网掩码和网关的子网掩码也相同，/27 即为 255.255.255.224。

正确答案：B

正确答案：B
SDN 对上层开发者提供的编程接口称为北向接口，而南向接口则负责控制平面和 数据平面间的通信，所以 SDN 控制器向数据平面的 SDN 交换机下发流表时使用南向接口。

正确答案：C

正确答案：C

时刻 0 发生了超时，门限值 ssthresh 变为拥塞窗口 cwnd 的一半即 8，同时 cwnd 置为 1，执行 慢开始 算法，cwnd 指数增长，经过 3 个 RTT，增长到 ssthresh 值：之后执行 拥塞避免 算法，cwmd 线性增长，再经过 8 个 RTT，增长到 16，共花费 11 个 RTT，如下表所示。

时刻	0	1	2	3	4	5	6	7	8	9	10	11
拥塞窗口	1	2	4	8	9	10	11	12	13	14	15	16

正确答案：D

正确答案：D
TCP 连接的释放过程见 四次挥手。题目问的是最少时间，所以当服务器 S 收到客户 C 发送的 FIN 请求后不再发送数据，而是立马发送 FN 请求（即第②步和第③步同时发生，忽略 FIN-WAIT2 和 CLOSE-WAIT 状态。C 收到 S 发来的 FIN 报文段后，进入 CLOSED 状态还需等到 TIME-WAIT 结束，总用时至少为 1RTT + 2MSL = 50 + 800×2 = 1650ms。S 进入 CLOSED 状态需要经过 3 次报文段的传输时间，即 1.5RTT=75ms。

正确答案：B

正确答案：B
HTTP/1.1 默认使用流水线的 长连接，所有请求都是连续发送的。题目要求最少 时间，最理想的流程是 TCP 在第三次握手的报文段中捎带 HTTP 请求，以及 TCP 连接后慢开 始阶段不考虑拥塞情况。假设接收方有足够大的缓存空间，即发送窗口等同于拥塞窗口，总 共需要经过：第 1 个 RTT，进行 TCP 连接，此时服务器 S 的发送窗口= 1MSS，并在第三次 握手时捎带 HTTP 请求；第 2 个 RTT，服务器 S 发送大小为 1MSS 的 html 文件，主机 C 确认 后服务器 S 的发送窗口变为 2MSS；第 3 个 RTT，服务器 S 发送大小为 2MSS 的图像文件， 主机 C 确认后服务器 S 的发送窗口变为 4MSS；第 4 个 RTT，服务器 S 发送剩下的 1MSS 图 像文件，完成传输，总共需要 4 个 RTT，即 40ms。