2020 年 408 真题

选择题

数据结构

1

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

2

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

3

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

4

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

5

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

6

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

7

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

8

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

9

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

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

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

10

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

11

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

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

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

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

组成原理

12

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

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

13

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

14

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

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

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

15

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

16

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

17

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

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

18

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

19

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

20

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

I、访存时缺页；

II、定时器延时；

III、网络数据包到达；

21

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

22

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

操作系统

23

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

24

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

25

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

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

Ⅱ、提供中断服务

Ⅲ、初始化中断向量表

Ⅳ、保存中断屏蔽字

26

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

Ⅰ. 就绪队列的数量

Ⅱ. 就绪队列的优先级

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

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

27

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

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

28

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

Ⅰ. 缺页率

Ⅱ. 磁盘读写时间

Ⅲ. 内存访问时间

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

29

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

30

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

31

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

32

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

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

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

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

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

计算机网络

33

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

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

34

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

35

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

36

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

37

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

38

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

39

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

40

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

解答题

数据结构

41

定义三元组 $(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 \lt S_1$、$j \lt S_2$ 且 $k \lt S_3$ 时（$|S|$ 表示集合 $S$ 中的元素个数），循环执行以下过程：
  • 计算（$A[i]$，$B[j]$，$C[j]$）的距离 $D$；（计算 $D$）
  • 若 $D \lt 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)$。

42

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

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

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

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

组成原理

43

有实现 $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$ 位乘积进行溢出判断

44

假定主存地址为 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 缺失处理过程。

操作系统

45

现有 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;
}

46

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

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

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

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

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

计算机网络

47

某校园网有两个局域网，通过路由器 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 地址分别是？