2020 年真题

将一个 10*10 对称矩阵 M 的上三角部分的元素 $m_{i,j}(1\le i\le j\le 10)$ ，按列优先存入 C 语言的一维数组 N 中，元素 $m_{7,2}$ 在 N 中的下标是（ ）

对空栈 S 进行 Push 和 Pop 操作入栈序列 a,b,c,d,e 经过 Push,Push,Pop,Push,Pop,Push,Push,Pop 操作后得到的出栈序列是（  ）。

对于任意一棵高度为 5 且有 10 个节点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是（ ）。

已知森林 F 及与之对应的二叉树 T，若 F 的先根遍历序列是 a,b,c,d,e,f，中根遍历序列是 b,a,d,f,e,c，则 T 的后根遍历序列是（ ）。

下列给定的关键字输入序列中，不能生成如下二叉排序树的是（ ）。

修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）定点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点，则输出的顶点序列是 G 的（ ）。

已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是（ ）。

若使 AOE 网估算工程进度则下列叙述中正确的是（ ）。

下列关于大根堆（至少含 2 个元素）的叙述中正确的是（ ）。

I. 可以将堆看成一颗完全二叉树；II. 可采用顺序存储方式保存堆；

III. 可以将堆看成一棵二叉排序树；IV. 堆中的次大值一定在根的下一层。

依次将关键字 5, 6, 9, 13, 8, 2, 12, 15 插入初始为空的 4 阶 B 树后, 根节点中包含的关键字是（ ）。

对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是（ ）。

I. 直接插入排序过程中元素之间的比较次数更少

II. 直接插入排序过程中所需要的辅助空间更少

III. 直接插入排序过程中元素的移动次数更少

下列给出的部件中其位数（宽度）一定与机器字长相同的是（ ）。

I、ALU
II、指令寄存器
III、通用寄存器
IV、浮点寄存器

已知带符号整数用补码表示，float 型数据用 IEEE 754 标准表示，假定变量 x 的类型只能是 int 或 float。当 x 的机器数为 C800 0000H 时，x 的值可能是（ ）。

在按字节编址，采用小端方式的 32 位计算机中，按边界对齐方式为以下 C 语言结构型变量 a 分配存储空间。

struct record {
    short x1;
    int x2;
} a;

若 a 的首地址为 2020FE00H，a 的成员变量 x2 的机器数为 12340000H，则其中 34H 所在存储单元的地址是（ ）。

下列关于 TLB 和 Cache 的叙述中，错误的是（ ）。

某计算机采用 16 位定长指令字格式，操作码位数和寻址方式位数固定，指令系统有 48 条指令，支持直接、间接、立即、相对 4 种寻址方式，单地址指令中直接寻址方式可寻址范围是（ ）。

下列给出的处理器类型中理想情况下 CPI 为 1 的是（ ）。

I、单周期 CPU；
II、多周期 CPU；
III、基本流水线 CPU；
IV、超标量流水线 CPU

下列关于“自陷”（Trap，也称陷阱）的叙述中错误的是（ ）。

QPI 总线是一种点对点全工双同步串行总线，总线上的设备可同时接收和发送信息，每个方向可同时传输 20 位信息（16 位数据 + 4 位校验位），每个 QPI 数据包有 80 位信息，分 2 个时钟周期传送，每个时钟周期传递 2 次，因此 QPI 总线带宽为每秒传送次数×2B×2。若 QPI 时钟频率为 2.4GHz，则总线带宽为（ ）。

下列事件中属于外部中断事件的是（ ）。

I、访存时缺页；

II、定时器到时；

III、网络数据包到达；

外部中断包括不可屏蔽中断（NMI）和可屏蔽中断，下列关于外部中断的叙述中错误的是（ ）。

若设备采用周期挪用 DMA 方式进行输入输出，每次 DMA 传送的数据块大小为 512 字节，相应的 I/O 接口中有一个 32 位数数据缓冲寄存器，对于数据输入过程，下列叙述中错误的是（ ）。

若多个进程共享同一个文件 F，则下列叙述中，正确的是（ ）。

下列选项中，支持文件长度可变、随机访问的磁盘存储空间分配方式是（ ）。

下列与中断相关的操作中，由操作系统完成的是（）。

Ⅰ、保存被中断程序的中断点

Ⅱ、提供中断服务

Ⅲ、初始化中断向量表

Ⅳ、保存中断屏蔽字

下列与进程调度有关的因素中，在设计多级反馈队列调度算法时需要考虑的是（ ）。

Ⅰ. 就绪队列的数量

Ⅱ. 就绪队列的优先级

Ⅲ. 各就绪队列的调度算法

Ⅳ. 进程在就绪队列间的迁移条件

某系统中有 A、B 两类资源各 6 个，t 时刻资源分配及需求情况如下表所示。

t 时刻安全性检测结果是（ ）。

下列因素中，影响请求分页系统有效（平均）访存时间的是（ ）。

Ⅰ. 缺页率

Ⅱ. 磁盘读写时间

Ⅲ. 内存访问时间

Ⅳ. 执行缺页处理程序的 CPU 时间

下列关于父进程与子进程的叙述中，错误的是（ ）。

对于具备设备独立性的系统，下列叙述中，错误的是（ ）。

某文件系统的目录项由文件名和索引结点号构成。若每个目录项长度为 64 字节，其中 4 字节存放索引结点号，60 字节存放文件名。文件名由小写英文字母构成，则该文件系统能创建的文件数量的上限为（ ）。

下列准则中，实现临界区互斥机制必须遵循的是（ ）。

Ⅰ、两个进程不能同时进入临界区

Ⅱ、允许进程访问空闲的临界资源

Ⅲ、进程等待进入临界区的时间是有限的

Ⅳ、不能进入临界区的执行态进程立即放弃 CPU

下图描述的协议要素是 (  )。

Ⅰ、语法；Ⅱ、语义；Ⅲ、时序

下列关于虚电路网络的叙述中错误的是（ ）。

下图所示的网络冲突域和广播域的个数分别是（ ）。

假设主机采用停等协议向主机乙发送数据帧，数据帧长与确认帧长均为 1000B。数据传输速率是 10kbps，单项传播延时是 200ms。则甲的最大信道利用率（ ）。

某 IEEE 802.11 无线局域网中主机 H 与 AP 之间发送或接收 CSMA/CA 帧的过程如下图所示，在 H 或 AP 发送帧前所等待的帧间间隔时间（IFS）中最长的是（ ）。

若主机甲与主机乙已建立一条 TCP 连接，最大段长（MSS）为 1KB，往返时间（RTT）为 2ms，则在不出现拥塞的前提下，拥塞窗口从 8KB 增长到 32KB 所需的最长时间是：

若主机甲与主机乙建立 TCP 连接时发送的 SYN 段中的序号为 1000，在断开连接时，甲发送给乙的 FIN 段中的序号为 5001，则在无任何重传的情况下，甲向乙已经发送的应用层数据的字节数为：

假设下图所示网络中的本地域名服务器只提供递归查询服务，其他域名的服务器均只提供迭代查询服务；局域网内主机访问 Internet 上各服务器的往返时间（RTT）均为 10ms，忽略其他各种时延，若主机 H 通过超链接 http://www.abc.com/index.html，请求浏览纯文本 Web 页 index.html，则从点击 超链接开始到浏览器接收到 index.html 页面为止，所需最短、最长时间分别是：

定义三元组 $(a,b,c)$ （ $a,b,c$ 均为正数）的距离 $D=|a-b|+|b-c|+|c-a|$ 。给定 $3$ 个非空整数集合 $S_1,S_2,S_3$ ，按升序分别存储在 $3$ 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组 $(a,b,c)$ （ $a\in S_1,b\in S_2,c\in S_3$ ）中的最小距离。例如 $S_1=\{-1,0,9\},S_2=\{-25,-10,10,11\},S_3=\{2,9,17,30,41\}$ 。则最小距离为 $2$ ，相应的三元组为 $(9,10,9)$ 。

要求：

（1）给出算法的基本设计思想；

（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释；

（3）说明你所设计算法的时间复杂度和空间复杂度

查看答案与解析

分析，由 $D=|a-b|+|b-c|+|c-a|\ge 0$ 得：

① 当 $a=b=c$ 时，距离最小。

② 其余情况。不失一般性，假设观察下面的数轴：

$L_1=|a-b|$ ， $L_2=|b-c|$ ， $L_3=|c-a|$ ， $D=|a-b|+|b-c|+|c-a|=L_1+L_2+L_3=2L_3$

由 $D$ 的表达式可知，事实上决定 $D$ 大小的关键是 $a$ 和 $c$ 之间的距离，于是问题就可以简化

为每次固定 $c$ 找一个 $a$ 使得 $L_3=|c-a|$ 最小。

1）算法的基本设计思想

• 使用 $D_{min}$ 记录所有已处理过的三元组的最小距离，初值为一个足够大的整数。
• 集合 $S_1$ 、 $S_2$ 和 $S_3$ ，分别保存在数组 $A$ 、 $B$ 、 $C$ 中。数组的下标变量 $i=j=k=0$ ，当 $i<S_1$ 、 $j<S_2$ 且 $k<S_3$ 时（ $|S|$ 表示集合 $S$ 中的元素个数），循环执行以下过程：
  • 计算（ $A[i]$ ， $B[j]$ ， $C[j]$ ）的距离 $D$ ；（计算 $D$ ）
  • 若 $D<D_{min}$ ，则 $D_{min}=D$ ；（更新 $D$ )
  • 将 $A[i]$ ， $B[i]$ ， $C[j]$ 中的最小值的下标 $+1$ ；（对照分析：最小值为 $a$ ，最大值为 $c$ ，这里 $c$ 不变而更新 $a$ ，试图寻找更小距离 $D$ ）
• 输出 $D_{min}$ ，结束。

2）算法实现

void solve(int S1[], int n1, int S2[], int n2, int S3[], int n3) {
  int i = 0, j = 0, k = 0;
  int res = INT32_MAX;
  while (i < n1 && j < n2 && k < n3) {
    int a = S1[i], b = S2[j], c = S3[k];
    int D = abs(a-b) + abs(b-c) + abs(a-c);
    res = min(res, D);
    int v = min3(a, b, c);
    if (v == a) {
      i++;
    } else if (v == b) {
      j++;
    } else {
      k++;
    }
  }
  return res;
}

3）设 $n=|S_1|+|S_2|+|S_3|$ ，时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$ 。

任一个字符的编码都不是其它字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数≥2）的不等长编码，每个字符的编码均为二进制的 0、1 序列，最长为 L 位，且具有前缀特性。请回答下列问题：

⑴ 哪种数据结构适宜保存上述具有前缀特性的不等长编码？

⑵ 基于你所设计的数据结构，简述从 0/1 串到字符串的译码过程。

⑶ 简述判定某字符集的不等长编码是否具有前缀特性的过程。

有实现 $x\times y$ 的两个 C 语言函数如下：

unsigned umul (unsigned x, unsigned y) { return x*y; }
int imul (int x, int y) { return x * y; }

假定某计算机 M 中 ALU 只能进行加减运算和逻辑运算。请回答下列问题。

(1) 若 M 的指令系统中没有乘法指令，但有加法、减法和移位等指令，则在 M 上也能实现上述两个函数中的乘法运算，为什么？

(2) 若 M 的指令系统中有乘法指令，则基于 ALU、移位器、寄存器以及相应控制逻辑实现乘法指令时，控制逻辑的作用是什么？

(3) 针对以下三种情况：
①没有乘法指令；
②有使用 ALU 和移位器实现的乘法指令；
③有使用阵列乘法器实现的乘法指令，
函数 umul() 在哪种情况下执行时间最长？哪种情况下执行的时间最短？说明理由。

(4) $n$ 位整数乘法指令可保存 $2n$ 位乘积，当仅取低 $n$ 位作为乘积时，其结果可能会发生溢出。当 $n=32$ 、 $x=2^{31}-1$  、 $y=2$ 时，带符号整数乘法指令和无符号整数乘法指令得到的 $x\times y$ 的 $2n$ 位乘积分别是什么（用十六进制表示）？此时函数 umul() 和 imul() 的返回结果是否溢出？对于无符号整数乘法运算，当仅取乘积的低位作为乘法结果时，如何用 $2n$ 位乘积进行溢出判断

假定主存地址为 32 位，按字节编址，指令 Cache 和数据 Cache 与主存之间均采用 8 路组相联映射方式，直写（WriteThrough）写策略和 LRU 替换算法，主存块大小为 64B，数据区容量各为 32KB。开始时 Cache 均为空。请回答下列问题。

(1) Cache 每一行中标记（Tag）、LRU 位各占几位？是否有修改位？

(2) 有如下 C 语言程序段：

for(k = 0; k < 1024; k++)
    s[k] = 2 * s[k];

若数组 s 及其变量 k 均为 int 型，int 型数据占 4B，变量 k 分配在寄存器中，数组 s 在主存中的起始地址为 008000C0H，则该程序段执行过程中，访问数组 s 的数据 Cache 缺失次数为多少？

(3) 若 CPU 最先开始的访问操作是读取主存单元 00010003H 中的指令，简要说明从 Cache 中访问该指令的过程，包括 Cache 缺失处理过程。

现有 5 个操作 A、B、C、D 和 E，操作 C 必须在 A 和 B 完成后执行，操作 E 必须在 C 和 D 完成后执行，请使用信号量的 wait()、signal() 操作（P、V 操作）描述上述操作之间的同步关系，并说明所用信号量及其初值。

semaphore SAC = 0; // 实现 A 是 C 的前驱关系
semaphore SBC = 0; // 实现 B 是 C 的前驱关系
semaphore SCE = 0; // 实现 C 是 E 的前驱关系
semaphore SDE = 0; // 实现 D 是 E 的前驱关系

A() {
  操作A;
  V(SAC);
}

B() {
  操作B;
  V(SBC);
}

C() {
  P(SAC);
  P(SBC);
  操作C;
  V(SCE);
}

D() {
  操作D;
  V(SDE);
}

E() {
  P(SCE);
  P(SDE);
  操作E;
}

某 32 位系统采用基于二级页表的请求分页存储管理方式，按字节编址，页目录项和页表项长度均为 4 字节，虚拟地址结构如下所示。

某 C 程序中数组 a[1024][1024]的起始虚拟地址为 1080 0000H，数组元素占 4 字节，该程序运行时，其进程的页目录起始物理地址为 0020 1000H，请回答下列问题。

(1) 数组元素 a[1][2]的虚拟地址是什么？对应的页目录号和页号分别是什么？对应的页目录项的物理地址是什么？若该目录项中存放的页框号为 00301H，则 a[1][2]所在页对应的页表项的物理地址是什么？

(2) 数组 a 在虚拟地址空间中所占区域是否必须连续？在物理地址空间中所占区域是否必须连续？

(3) 已知数组 a 按行优先方式存放，若对数组 a 分别按行遍历和按列遍历，则哪一种遍历方式的局部性更好？

某校园网有两个局域网，通过路由器 R1、R2 和 R3 互联后接入 Internet，S1 和 S2 为 以太网交换机，局域网采用静态 IP 地址配置，路由器部分接口以及各主机的 IP 地址如图所示：

假设 NAT 转换表结构为：

请回答下列问题：

1）为使 H2 和 H3 能够访问 Web 服务器（使用默认端口号），需要进行什么配置？

2）若 H2 主动访问 Web 服务器时，将 HTTP 请求报文封装到 IP 数据报 P 中发送，则 H2 发送 P 的源 IP 地址和目的 IP 地址分别是？经过 R3 转发后，P 的源 IP 地 址和目的 IP 地址分别是？经过 R2 转发后，P 的源 IP 地址和目的 IP 地址分别是？