2020 年真题

上三角矩阵 按列优先存储，先存储仅 1 个元素的第一列，再存储有 2 个元素的第二列，以此类推。加 7,2 位于左下角，对应右上角的元素为加 2, 7 , 在加 2,7 之前存有

• 第 1 列：1
• 第 2 列：2
• ……
• 第 6 列：6
• 第 7 列：1

前面共存有 1 + 2 + 3 + 4 + 5 + 6 + 1 = 2 2 个 元 素（数组下标范围为 0〜21）, 注意数组下标 从 0 开始，故加工 7 在数组 N 中的下标为 2 2 , 即加 7,2 在数组 N 中的下标为 22。

按题意，出入栈操作的过程如下：

故出栈序列为 c,e。

本题考察的是 森林的遍历， 森林 F 的先根遍历序列对应其二叉树 T 的先序遍历序列，森林 F 的中根遍历序列对应其二叉树 T 的中序遍历序列。即 T 的先序遍历序列为 a,b,c,d,e,f，中序遍历序列为 b,a,d,f,e,c。根据二叉树 T 的先序序列和中序序列可以唯一确定它的结构，构造过程如下：

可以得到二叉树 T 的后序序列为 b,f,e,d,c,a。

选项 B 生成二叉排序树的过程如下，显然 B 选项错误：

kruskal 算法 依次将当前 不会导致环路的最短边 加入最小生成树中：

一 个 4 阶 B 树 的任意非叶结点至多含有加 4-1=3 个关键字，在关键字依次插入的过程中，会导致结点的不断分裂，插入过程如下所示。

得到根结点包含的关键字为 6, 9。

机器字长 是指 CPU 内部用于整数运算的数据通路的宽度。CPU 内部数据通路是指 CPU 内部的数据流经的路径及路径上的部件，主要是 CPU 内部进行数据运算、存储和传送的部件，这些部件的宽度基本上要一致才能相互匹配。因此，机器字长等于 CPU 内部用于整数运算的运算器位数和通用寄存器宽度。

ALU（算术逻辑单元）

• 功能：执行加减乘除、位运算等。
• 分析：ALU 的宽度必须和机器字长一致，才能对一个机器字进行运算。

✅ 一定与机器字长相同

指令寄存器（IR）

• 功能：存放当前正在执行的指令。
• 分析：
  • 指令寄存器的宽度取决于指令长度，而不是机器字长。
  • 指令长度可能为 16 位、32 位、64 位等，不一定等于机器字长。

❌ 不一定相同

通用寄存器

• 功能：存放数据、地址、中间计算结果。
• 分析：通用寄存器通常与机器字长相等，以便完整存储一个字。

✅ 通常与机器字长相同

浮点寄存器

• 功能：专门存储浮点数（如 IEEE 754 格式）
• 分析：
  • 浮点寄存器的宽度通常和浮点数格式有关（如 32 位单精度，64 位双精度）。
  • 这与机器字长无固定关系，有的机器字长是 32 位，但支持 64 位浮点数。

❌ 不一定相同

所以 I、III 正确，答案选择 B。

C800 0000H = 1100 1000 0000 0000 0000 0000 0000 0000

将其转换为对应的 float 或 int：

1. 为 float 型时，尾数隐藏最高位 1 ,数符为 1 表示负数，阶码 $10010000=2^7+2^4=128+16$ , 再减去偏置值 127 得到 17 ,算出 x 值为 $-2^{17}$ 。

2. 为 int 型时，带符号补码，为负数，数值部分取反加 1 ,得 011 1000 0000 0000 0000 0000 0000 0000 ,算出 x 值为 $-7\times 2^{27}$ 。

在 32 位计算机中，按字节编址，根据 小端序 和按 边界对齐 的定义，给出变量 a 的存放方式如下：

参考 指令格式，48 条指令需要 6 位操作码字段 ( $2^5<48<2^6$ ), 4 种寻址方式需要 2 位寻址特征位 ( $4=2^2$ ), 还剩 16 - 6 - 2 = 8 位作为地址码，故直接寻址范围为 0 ~ 255。注意，主存地址不能为负。

🚫 常见误区说明：

• 在 相对寻址 中，可能会有有符号偏移，比如 -128 ~ 127 或 -512 ~ 511，那是针对偏移字段的符号解释；
• 直接寻址不需要符号位，它就是一个无符号绝对地址。

CPI 表示执行指令所需的时钟周期数。对于一个程序或一台机器来说，其 CPI 指执行该程序或机器指令集中的所有指令所需的平均时钟周期数。

对于单周期 CPU，令指令周期 = 时钟周期，CPI=1，I 正确。

对于多周期 CPU，CPU 的执行过程分成几个阶段，每个阶段用一个时钟去完成，每种指令所用的时钟数可以不同，CPI > 1 , II 错误。

对于基本流水线 CPU，让每个时钟周期流出一条指令，CPI = 1, III 正确。

超标量流水线 CPU 在每个时钟周期内并发执行多条独立的指令，每个时钟周期流出多条指令，CPI < 1, IV 错误。

每个时钟周期传送 2 次，故每秒传送的次数= 时钟频率 x2 = 2.4Gx2/s。

总线带宽 = 每秒传送次数×2B×2 = 2.4G×2×2B×2/s=19.2GB/s。

题中已给出总线带宽公式，降低了难度。公式中的“x2B”是因为每次传输 16 位数据，“x2”

是因为采用点对点全双工总线，两个方向可同时传输信息。

由 CPU 内部产生的异常称为 内中断，内中断都是 不可屏蔽中断。通过中断请求线 INTR 和 NMI 从 CPU 外部发出的中断请求为外中断，通过 INTR 信号线发出的外中断是可屏蔽中断，而通过 NMI 信号线发出的是不可屏蔽中断。不可屏蔽中断不受中断标志位的影响，使在关中断的情况下也会被响应，选项 A 正确。

不可屏蔽中断的处理优先级最高，任何时候只要发生不可屏蔽中断，都要中止现行程序的执行，转到不可屏蔽中断处理程序执行，选项 C 正确。

可屏蔽中断 可以通过中断屏蔽字来设定优先级，选项 D 正确。

CPU 响应中断需要满足 3 个条件：① 中断源有中断请求；② CPU 允许中断 及开中断；③ 一条指令执行完毕，且没有更紧迫的任务。故选项 B 错误。

题目考查 周期挪用法 的基本概念和过程。

我们先简单回顾一下 周期挪用 DMA 的基本特点：

• 每当 I/O 设备准备好一个字（比如 32 位）数据 时，就向 DMA 控制器请求一次传送；
• DMA 控制器申请一次总线使用权，占用一个内存周期，进行数据的读/写；
• 每次传输只占用一个周期，不会长时间占用总线；
• CPU 运行被打断（因为 DMA 抢占了总线），但只影响一个周期；
• 数据块传送完后会产生一次 DMA 中断，通知 CPU 处理。

各选项逐一分析：

A 正确。题中说数据缓冲寄存器是 32 位，那么每准备好 32 位，就要进行一次 DMA 请求。这符合周期挪用方式的基本操作流程。

B 正确。周期挪用的机制就是 DMA 控制器能优先抢占主存总线，在不影响整个系统效率的前提下完成数据传输。

C 错误。这是正确答案。

在周期挪用方式下，CPU 是可以访问主存的，只是当 DMA 传输发生的那个特定周期，CPU 被暂停一个周期，因为 DMA 暂时挪用了总线资源。

也就是说，CPU 的访问会被“打断一下”，而不是整个传输过程中都无法访问主存。

D 正确。DMA 会在一整个数据块（比如 512 字节）传送完毕后，产生一次中断，通知 CPU“数据传送完成”，此时 CPU 可以进行下一步操作（如处理数据等）。

所以正确答案选择 C，因为在周期挪用 DMA 方式下，CPU 在数据传送过程中可以访问主存，只是会偶尔被暂停一个周期，不是整个过程都被阻止。

多个进程可同时以“读”或“写”方式打开文件，操作系统并不保证写操作的互斥性，进程可通过系统调用对文件加锁，保证互斥写（读者 - 写者问题），选项 A 错误。

整个系统只有一个 系统文件打开表，同一个文件打开多次只需改变引用计数，选项 B 正确。

用户进程的打开文件表关于同一个文件不一定相同，例如读写指针位置不一定相同，选项 C 错误。

进程关闭文件时，文件的引用计数减 1 , 引用计数变为 0 时才删除系统打开文件表中的表项，选项 D 错误。

本题考查 网络协议要素。协议 由语法、语义和时序（又称同步）三部分组成：

• 语法 规定了通信双方彼此“如何讲”，即规定了传输数据的格式。
• 语义 规定了通信双方彼此“讲什么”，规定了所要完成的功能，如通信双方要发出什么控制信息、执行的动作和返回的应答。
• 时序 规定了信息交流的次序。

由图可知发送方与接收方依次交换信息，体现了协议三要素中的时序要素。

发送数据帧和确认帧的时间均为 t= 1000x8b/10kbps = 800ms。

发送周期 T = 800ms + 200ms + 800ms + 200ms = 2000ms。

信道利用率 = t/T x 100% = 800/2000x100% = 40%。

为了尽量避免碰撞，IEEE 802.11 规定，所有站在完成发送后，必须等待一段很短的时间（继续 监听）才能发送下一帧。这段时间称为帧间间隔（InterFrame Space, IFS）。帧间间隔的长 短取决于该站要发送的帧的类型。IEEE 802.11 使 用 3 种帧间间隔：

• DIFS（分布式协调 IFS）：最长的 IFS , 优先级最低，用于异步帧竞争访问的时延。
• PIFS（点协调 IFS）：中等长度的 IFS , 优先级居中，在 PC F 操作中使用。
• SIFS（短 IFS）：最短的 IFS , 优先级最高，用于需要立即响应的操作。

网络中的控制帧及所接收数据的确认帧都采用 SIFS 作为发送之前的等待时延。当结点要发 送数据帧时，载波监听到信道空闲时，需等待 DIFS 后发送 RTS 预约信道，图中 IFS1 对应 的是帧间间隔 DIFS，时间最长，图中 IFS2、IFS3、IFS4 对应 SIFS。

题中 RTT 均为局域网内主机（主机 H、本地域名服务器）访 问 Internet 上各服务器的往返时间，且忽略其他时延，因此主机 H 向本地域名服务器的查询时延忽略不计。

最短时间：本地主机中有该域名到 IP 地址对应的记录，因此不需要 DNS 查询时延，直接和 www.abc.com 服务器建立 TCP 连接再进行资源访问，TCP 连接建立需要 1 个 RTT，接着发送访问请求并收到服务器资源响应需要 1 个 RTT，共计 2 个 RTT，即 20ms；

最长时间：本地主机 递归查询 本地域名服务器（延时忽略），本地服务器依次迭代查询根域名服务器、com 顶级域名服务器、abc.com 域名服务器，共 3 个 RTT，查询到 IP 地址后，将该映射返回给主机 H，主机 H 和 www.abc.com 服务器建立 TCP 连接再进行资源访问，共 2 个 RTT，因此最长时间需要 3+2=5 个 RTT，即 50ms。