2021 年 408 真题

选择题

数据结构

1

已知头指针 h 指向一个带头结点的非空单循环链表，结点结构为

其中 next 是指向直接后继结点的指针，p 是尾指针，q 是临时指针。现要删除该链表的第一个元素，正确的语句序列是（ ）。

2

已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1, 2, 3, 4, 5 , 则不能得到的出队序列是（ ）。

3

已知二维数组 A 按行优先方式存储，每个元素占用 1 个存储单元。若元素 A[0][0] 的存储地址是 100, A[3][3] 的存储地址是 220 , 则元素 A[5][5] 的存储地址是（ ）。

4

某森林 F 对应的二叉树为 T , 若 T 的先序遍历序列是 a, b, d, c, e, g, f , 中序遍历序列是 b, d, a, e, g, c, f , 则 F 中树的棵数是（ ）。

5

若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度（WPL）是（ ）。

         89
      /      \
     52      37
   /   \    /  \
  22   30  16  21
 /  \
10  12

6

给定平衡二叉树如下图所示，插入关键字 23 后，根中的关键字是（ ）。

    25
   /  \
  20   30
 /  \    \
16  23    40

7

给定如下有向图，该图的拓扑有序序列的个数是（ ）。

8

使用 Dijkstra 算法求下图中从顶点 1 到其余各顶点的最短路径，将当前找到的从顶点 1 到顶点 2, 3, 4, 5 的最短路径长保存在数组 dist 中，求出第二条最短路径后，dist 中的内容更新为（ ）

9

在一棵高度为 3 的 3 阶 B 树中，根为第 1 层，若第 2 层中有 4 个关键字，则该树的结点个数最多是（ ）。

10

设数组 S[] = {93, 946, 372, 9, 146,151, 301, 485, 236, 327, 43, 892}, 采用最低位优先（LSD）基数排序将 S 排列成升序序列。第 1 趟分配、收集后，元素 372 之前、之后紧邻的元素分别是 (  )

11

将关键字 6, 9, 1, 5, 8, 4, 7 依次插入到初始为空的大根堆 H 中，得到的 H 是（  ）。

组成原理

12

2017 年公布的全球超级计算机 TOP500 排名中，我国“神威·太湖之光”超级计算机蝉联第一，其浮点运算速度为 93.0146PFLOPS，说明该计算机每秒钟完成的浮点操作次数为（ ）。

13

已知带符号整数用补码表示，变量 x，y，z 的机器数分别为 FFFDH，FFDFH，7FFCH，下列结论中，正确的是（ ）。

14

下列数值中，不能用 IEEE754 浮点格式精确表示的（ ）。

15

某计算机的存储器总线中有 24 位地址线和 32 位数据线，按字编址，字长为 32 位。若 000000H~3FFFFFH 为 RAM 区，则需要 512K×8 位的 RAM 芯片数为（ ）。

16

若计算机主存地址为 32 位，按字节编址，Cache 数据区大小为 32KB，主存块大小为 32B，采用直接映射方式和回写（Write Back）策略，则 Cache 行的位数至少是（ ）。

17

下列存储器中，汇编语言程序员可见的是（ ）。

Ⅰ. 指令寄存器

Ⅱ. 微指令寄存器

Ⅲ. 基址寄存器

Ⅳ. 标志状态寄存器

18

下列关于数据通路的叙述中，错误的是（ ）。

19

下列关于总线的叙述中，错误的是（ ）。

20

下列选项中不属于 I/O 接口的是（ ）。

21

异常事件在当前指令执行过程中进行检测，中断请求则在当前指令执行后进行检测。下列事件中，相应处理程序执行后，必须回到当前指令重新执行的是（ ）。

22

下列是关于多重中断系统中 CPU 响应中断的叙述，其中错误的是（ ）。

操作系统

23

下列指令中，只能在内核态执行的是（ ）。

24

下列操作中，操作系统在创建新进程时，必须完成的是（ ）。

I. 申请空白的进程控制块

II. 初始化进程控制块

III. 设置进程状态为执行态

25

下列内核的数据结构或程序中，分时系统实现时间片轮转调度需要使用的是（ ）。

I. 进程控制块

II. 时钟中断处理程序

III. 进程就绪队列

IV. 进程阻塞队列

26

某系统中磁盘的磁道数为 200 (0~199), 磁头当前在 184 号磁道上。用户进程提出的磁盘访问请求对应的磁道号依次为 184, 187, 176, 182, 199。若采用最短寻道时间优先调度算法 (SSTF) 完成磁盘访问，则磁头移动的距离（磁道数）是（ ）。

27

下列事件中，可能引起进程调度程序执行的是（ ）。

I. 中断处理结束

II. 进程阻塞

III. 进程执行结束

IV. 进程的时间片用完

28

某请求分页存储系统的页大小为 4KB，按字节编址。系统给进程 P 分配 2 个固定的页框并采用改进型 Clock 置换算法，进程 P 页表的部分内容如下表所示：

若 P 访问虚拟地址为 02A01H 的存储单元，则经地址变换后得到的物理地址是（）。

29

在采用二级页表的分页系统中，CPU 页表基址寄存器中的内容是（ ）。

30

若目录 dir 下有文件 file1，则为删除该文件内核不必完成的工作是（ ）。

31

若系统中有 n (n≥2) 个进程，每个进程均需要使用某类临界资源 2 个，则系统不会发生死锁所需的该类资源总数至少是（ ）。

32

下列选项中，通过系统调用完成的操作是（ ）。

计算机网络

33

在 TCP/IP 参考模型中，由传输层相邻的下一层实现的主要功能是（ ）。 

34

若下图为一段差分曼彻斯特编码信号波形，则其编码的二进制位串是（ ）

35

现将一个 IP 网络划分为 3 个子网，若其中一个子网是 192.168.9.128/26, 则下列网络中，不可能是另外两个子网之一的是（ ）

36

若路由器向 MTU = 800B 的链路转发一个总长度为 1580B 的 IP 数据报（首部长度为 20B）时，进行了分片，且每个分片尽可能大，则第 2 个分片的总长度字段和 MF 标志位的值分别是（  ）

37

某网络中的所有路由器均采用距离向量路由算法计算路由。若路由器 E 与邻居路由器 A,B,C 和 D 之间的直接链路距离分别是 8, 10, 12 和 6 , 且 E 收到邻居路由器的距离向量如下表所示，则路由器 E 更新后的到达目的网络 Netl~Net4 的距离分别是（ ）。

38

若客户首先向服务器发送 FIN 段请求断开 TCP 连接，则当客户收到服务器发送的 FIN 段并向服务器发送了 ACK 段后，客户的 TCP 状态转换为（ ）。

39

若大小为 12B 的应用层数据分别通过 1 个 UDP 数据报和 1 个 TCP 段传输，则该 UDP 数据报 和 TCP 段实现的有效载荷（应用层数据）最大传输效率分别是（ ）。

40

设主机甲通过 TCP 向主机乙发送数据，部分过程如下图所示。甲在 $t_0$ 时刻发送一个序号 seq=501、封装 200B 数据的段，在 $t_1$ 时刻收到乙发送的序号 seq = 601、确认序号 ack_seq = 501、接收窗口 rcvwnd = 500B 的段，则甲在未收到新的确认段之前，可以继续向乙发送的数据序号范围是（ ）。

解答题

数据结构

41

已知无向连通图 G 由顶点集 V 和边集 E 组成，|E| > 0，当 G 中度为奇数的顶点个数为不大于 2 的偶数时，G 存在包含所有边且长度为|E|的路径（称为 EL 路径）。设图 G 采用邻接矩阵存储，类型定义如下：

typedef struct {                    // 图的定义
    int numVertices, numEdges;      // 图中实际的顶点数和边数
    char VerticesList[MAXV];        // 顶点表，MAXV 为已定义常量
    int Edge[MAXV][MAXV];           // 邻接矩阵
} MGraph;

请设计算法 int IsExistEL(MGraph G)，判断 G 是否存在 EL 路径，若存在，则返回 1，否则返回 0。要求：

(1) 给出算法的基本设计思想。

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

(3) 说明你所设计算法的时间复杂度和空间复杂度。

int isExistEL(MGraph G) {
  // 统计度为奇数的定点个数
  int count = 0;
  for (int v = 0; v < numVertices; v++) {
    // 该顶点的度
    int degree = 0;
    for (int e = 0; e < numEdges; e++) {
      if (Edge[v][e] == 1) {
        degree++;
      }
    }
    if (degree % 2 == 1) {
      count++;
    }
  }
  if (count == 2 || count == 2) {
    return 1;
  }
  return 0;
}

42

已知某排序算法如下：

void cmpCountSort(int a[], int b[], int n)
{
    int i, j, *count;
    count = (int *) malloc(sizeof(int) * n) //C++ 语言：count = new int[n];
    for (i = 0; i < n; i++) count[i] = 0;
    for (i = 0; i < n - 1; i++)
        for (j = i + 1; j < n; j++)
            if (a[i] < a[j]) count[j]++;
            else count[i]++;
    for (i = 0; i < n; i++) b[count[i]]= a[i];
    free(count); // C++ 语言：delete count;
}

请回答下列问题。

(1) 若有 int a[] = {25, -10, 25, 10, 11, 19}, b[6]; ，则调用 cmpCountSort(a, b, 6) 后数组 b 中的内容是什么？

(2) 若 a 中含有 n 个元素，则算法执行过程中，元素之间的比较次数是多少？

(3) 该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法。

if(a[i]<=a[j]) count[j]++;
else count[i]++;

组成原理

43

假定计算机 M 字长为 16 位，按字节编址，连接 CPU 和主存的系统总线中地址线为 20 位、数据线为 8 位，采用 16 位定长指令字，指令格式及其说明如下：

其中，op1~op3 为操作码，rs、rt 和 rd 为通用寄存器编号，R[r] 表示寄存器 r 的内容，imm 为立即数，target 为转移目标的形式地址。请回答下列问题。

(1) ALU 的宽度是多少位？可寻址主存空间大小为多少字节？指令寄存器、主存地址寄存器（MAR）和主存数据寄存器（MDR）分别应有多少位？

(2) R 型格式最多可定义多少种操作？I 型和 J 型格式总共最多可定义多少种操作？通用寄存器最多有多少个？

(3) 假定 op1 为 0010 和 0011 时，分别表示带符号整数减法和带符号整数乘法指令，则指令 01B2H 的功能是什么（参考上述指令功能说明的格式进行描述）？若 1、2、3 号通用寄存器当前内容分别为 B052H、0008H、0020H，则分别执行指令 01B2H 和 01B3H 后，3 号通用寄存器内容各是什么？各自结果是否溢出？

(4) 若采用 I 型格式的访存指令中 imm（偏移量）为带符号整数，则地址计算时应对 imm 进行零扩展还是符号扩展？

(5) 无条件转移指令可以采用上述哪种指令格式？

44

假设计算机 M 的主存地址为 24 位，按字节编址；采用分页存储管理方式，虚拟地址为 30 位，页大小为 4KB；TLB 采用 2 路组相联方式和 LRU 替换策略，共 8 组。请回答下列问题。

(1) 虚拟地址中哪几位表示虚页号？哪几位表示页内地址？

(2) 已知访问 TLB 时虚页号高位部分用作 TLB 标记，低位部分用作 TLB 组号，M 的虚拟地址中哪几位是 TLB 标记？哪几位是 TLB 组号？

(3) 假设 TLB 初始时为空，访问的虚页号依次为 10、12、16、7、26、4、12 和 20，在此过程中，哪一个虚页号对应的 TLB 表项被替换？说明理由。

(4) 若将 M 中的虚拟地址位数增加到 32 位，则 TLB 表项的位数增加几位？

操作系统

45

下表给出了整型信号量 S 的 wait() 和 signal() 操作的功能描述，以及采用开/关中断指令实现信号量操作互斥的两种方法。

Semaphore S;

wait(S) {
    while (S <= 0);
    S = S-1;
}






signal(S) {
    S = S+1;
}

Semaphore S;


wait(S) {
    关中断；
    while(S <= 0);
    S = S-1;
    开中断；
}


signal(S) {
    关中断；
    S = S+1;
    开中断；
}

Semaphore S;

wait(S) {
    关中断；
    while(S <= 0) {
        开中断；
        关中断；
    }
    S = S-1;
    开中断；
}

signal(S) {
    关中断；
    S = S+1;
    开中断；
}

请回答下列问题。

(1) 为什么在 wait() 和 signal() 操作中对信号量 S 的访问必须互斥执行？

(2) 分别说明方法 1 和方法 2 是否正确。若不正确，请说明理由。

(3) 用户程序能否使用开/关中断指令实现临界区互斥？为什么？

46

某计算机用硬盘作为启动盘，硬盘第一个扇区存放主引导记录，其中包含磁盘引导程序和分区表。磁盘引导程序用于选择要引导哪个分区的操作系统，分区表记录硬盘上各分区的位置等描述信息。硬盘被划分成若干个分区，每个分区的第一个扇区存放分区引导程序，用于引导该分区中的操作系统。系统采用多阶段引导方式，除了执行磁盘引导程序和分区引导程序外，还需要执行 ROM 中的引导程序。请回答下列问题。

(1) 系统启动过程中操作系统的初始化程序、分区引导程序、ROM 中的引导程序、磁盘引导程序的执行顺序是什么？

(2) 把硬盘制作为启动盘时，需要完成操作系统的安装、磁盘的物理格式化、逻辑格式化、对磁盘进行分区，执行这 4 个操作的正确顺序是什么？

(3) 磁盘扇区的划分和文件系统根目录的建立分别是在第 (2) 问的哪个操作中完成的？

计算机网络

47

某网络拓扑如题 47 图所示，以太网交换机 S 通过路由器 R 与 Internet 互联。路由器部分接口、本地域名服务器、H1、H2 的 IP 地址和 MAC 地址如图中所示。在 t0 时刻 H1 的 ARP 表和 S 的交换表均为空，H1 在此刻利用浏览器通过域名 www.abc.com 请求访问 Web 服务器，在 t1 时刻（t1→t0）S 第一次收到了封装 HTTP 请求报文的以太网帧，假设从 t0 到 t1 期间网络未发生任何与此次 Web 访问无关的网络通信。

请回答下列问题。

(1) 从 t0 到 t1 期间，H1 除了 HTTP 之外还运行了哪个应用层协议？从应用层到数据链路层，该应用层协议报文是通过哪些协议进行逐层封装的？

(2) 若 S 的交换表结构为 <MAC 地址，端口>，则 t1 时刻 S 交换表的内容是什么？

(3) 从 t0 到 t1 期间，H2 至少会接收到几个与此次 Web 访问相关的帧？接收到的是什么帧？帧的目的 MAC 地址是什么？