2023 年 408 真题

选择题

数据结构

1

下列对顺序存储的有序表（长度为 n）实现给定操作的算法中平均时间复杂度为 O(1) 的是（ ）。

2

现有非空双向链表 L，其结点结构为：

prev 是指向前直接前驱结点的指针，next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点（非尾结点）之后插入指针 s 指向的新结点，则在执行了语句序列： s->next=p->next; p->next=s，后，还要执行（ ）。

3

若采用三元组表存储结构存储系数矩阵 M。则除三元组外，下列数据中还需要保存的是（ ）。

I. M 的行数

II. M 中包含非零元素的行数

III. M 的列数

IV. M 中包含非零元素的列数

4

在有 6 个字符组成的字符集 S 中，各个字符出现的频次分别为 3, 4, 5, 6, 8, 10，为 S 构造的哈夫曼树的加权平均长度为（ ）

5

已知一棵二叉树的树形如图，若其后序遍历为 f,d,b,e,c,a，则其先序序列为（ ）。

6

已知无向连通图 G 中各边的权值均为 1，下列算法中，一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是（ ）。

I. 普利姆算法

II. 克鲁斯卡尔算法

III. 图的广度优先搜索

7

下列关于非空 B 树的叙述中，正确的是（ ）

I. 插入操作可能增加树的高度

II. 删除操作一定会导致叶结点的变化

III. 查找某关键字一定是要查找到叶结点

IV. 插入的新关键字最终位于叶结点中

8

对含有 600 个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是（ ）。

9

现有长度为 5，初始为空的散列表 HT，散列表函数 H(k) = (k+4) % 5 用线性探查再散列法解决冲突。若将关键字序列 2022,12,25 依次插入 HT 中，然后删除关键字 25，则 HT 中查找失败的平均查找长度（  ）。

10

下列排序算法中，不稳定的是（ ）

I. 希尔排序

II. 归并排序

III. 快速排序

IV. 堆排序

V. 基数排序

11

使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88，则该次划分的轴枢（ ）。

组成原理

12

若机器 M 的主频为 1.5Ghz，在 M 上执行程序 p 的指令条数为 $5 \times 10^5$ 次方，p 的平均 CPI 为 1.2，则 p 在 M 上的指令执行速度和用户 CPU 时间分别为（ ）

13

若 short 型变量 x = -8190，则 x 的机器数为（ ）

14

已知 float 型变量用 IEEE754 单精度浮点数格式表示。若 float 型变量 x 的机器数为 8020000H，则 x 的值（ ）

15

某计算机的 CPU 有 30 根地址线，按字节编址，CPU 和主存芯片连接时，要求主存芯片占满所有可能存储地址空间，并且 RAM 区和 ROM 区所分配的容量大小比为 3:1，若 RAM 在连续低地址区，ROM 在连续高地址区，则 ROM 的地址范围（ ）

16

已知 x、y 为 int 类型，当 x=100，y=200 时，执行 x-y 指令的到的溢出标志 OF 和借位标志 CF 分别为 0,1，那么当 x=10，y=-20 时，执行该指令得到的 OF 和 CF 分别是（ ）

17

某运算类型指令中有一个地址码为通用寄存器编号，对应通用寄存器中存放的是操作数或操作数地址，CPU 区分两者的依据是（ ）

18

数据通路由组合逻辑元件（操作元件）和时序逻辑元件（状态元件）组成。下列给出的元件中，属于操作元件的是（ ）。

I. 算术逻辑部件（ALU）

II. 程序计数器（PC）

III. 通用寄存器组（GPRs）

IV. 多路选择题（MUX）

19

在采用“取指、译码/取数、执行、访存、写回”5 段流水线的 RISC 处理器中，执行如下指令序列（第一列为指令序号），其中 s0、s1、s2、s3 和 t2 表示寄存器编号。

I1     add s2, s1, s0   // R[s2] ← R[s1] + R[s0]
I2     load s3, 0(s2)   // R[s3] ← M[R[s2] + 0]
I3     beq t2, s3, L1   // if R[t2] = R[s3] jump to L1
I4     addi t2, t2, 20  // R[t2] ← R[t2] + 20
I5 L1:

若采用转发（旁路）技术处理数据冒险，采用硬件阻塞方式处理控制冒险，则在 I1~I4 执行过程中，发生流水线阻塞的指令有（ ）。

A. 仅 I3 B. 仅 I2、I4 C. 仅 I3、I4 D. 仅 I2、I3、I4

查看答案与解析

正确答案：C

在以下指令序列中：

• I1：写寄存器 R[s2]
• I2：使用 R[s2] 计算访存地址
• I3：使用 R[s3] 进行比较跳转
• I4：紧跟在 beq 指令之后执行

1. I2 与 I1 之间：写后读数据冒险（RAW Hazard）

指令 I1 将结果写入寄存器 R[s2]，但这个值直到 I1 的 写回（WB）阶段 才会更新。而 I2 在其 执行（EX）阶段 就需要用到 R[s2] 来计算访存地址，因此存在写后读的数据冒险。

幸运的是，I1 在 EX阶段末尾 就已生成结果并存储在 EX→M 流水段寄存器中。此时如果使用 旁路转发，可以直接将这个值从流水段寄存器中转发到 I2 的 ALU 输入端，避免等待 WB 阶段，从而解决了这个 RAW 冒险。

2. I3 与 I2 之间：装入-使用 数据冒险（Load-Use Hazard）

I2 是一条 load 指令，它需要从内存中将数据装入寄存器 R[s3]。而 I3 在它的 EX 阶段就要用到 R[s3] 的值。如果像前面那样尝试用旁路技术从 I2 的 EX→M 寄存器转发数据，会失败——因为此时的数据尚未从内存中读出。

只有等到 I2 的 访存（M）阶段结束，数据才真正从内存中取回，存放在 M→WB 流水段寄存器。因此，仅靠转发线路无法解决装入-使用冒险。

需要采取的办法是：对 I3 硬件阻塞一个周期，等待 I2 的 M 阶段完成，然后通过转发将 R[s3] 的新值从 M→WB 段寄存器送入 I3 的 ALU，以确保其操作正确。

3. I4 与 I3 之间：控制冒险（Control Hazard）

I3 是一条 beq 分支指令。该指令在 EX 阶段比较寄存器值，在 M 阶段才判断跳转是否成立并更新 PC（程序计数器）。因此，在得知是否跳转前，I4 的取指（IF）阶段必须等待 I3 的 M 阶段完成。

这就导致 I4 的执行被 阻塞 3 个时钟周期，以确保其是否被执行是基于正确的控制流判断。

最终，系统采用 硬件阻塞机制 来处理上述数据和控制冒险，下图展示了指令执行过程中各阶段的具体安排：

20

某存储器总线宽度为 64 位，总线时钟频率为 1GHZ，在总线上传输一个数据或地址需要一个的时钟周期，不支持突发传送方式，若通过该总线连接 CPU 和主存，主存每次准备一个 64 位数据需要 6ns，主存块大小为 32B，则读取一个主存块需要的时间为（ ）。

21

下列关于硬件和异常/中断关系的叙述中，错误的是（ ）。

22

下列关于 I/O 控制方式的叙述中，错误的是（ ）。

操作系统

23

与宏内核操作系统相比，下列特征中微内核操作系统具有的是（ ）。

Ⅰ. 较好的性能

Ⅱ. 较高的可靠性

Ⅲ. 较高的安全性

Ⅳ. 较强的可扩展性

24

在操作系统内核中，中断向量表适合采用的数据结构是（ ）。

25

某系统采用页式存储管理，用位图管理空闲页框。若页大小为 4 KB，物理内存大小为 16 GB，则位图所占空间的大小是（ ）。

26

下列操作完成时，导致 CPU 从内核态转为用户态的是（ ）。

27

下列出当前线程引起的事件或执行的操作中，可能导致该线程由执行态变为就绪态的是（ ）。

28

对于采用虚拟内存管理方式的系统，下列关于进程虚拟地址空间的叙述中，错误的是（ ）。

29

进程 P1、P2 和 P3 进入就绪队列的的时刻，优先值（越大优先权越高）以及 CPU 的执行时间如下表所示。

系统采用基于优先权的抢占式 CPU 调度算法，从 0ms 时刻开始进行调度，则 P1、P2 和 P3 的平均周转时间为（ ）。

30

进程 R 和 S 共享数据 data，若 data 在 R 和 S 中所在页的页号分别为 p1 和 p2，两个页所对应的页框号分别为 f1 和 f2，则下列叙述中，正确的是（ ）。

31

若文件 F 仅被进程 P 打开并访问，则当进程 P 关闭 F 时，下列操作中，文件系统需要完成的是（ ）。

32

下列因素中，设备分配需要考虑的是（ ）。

Ⅰ. 设备的类型

Ⅱ. 设备的访问权限

Ⅲ. 设备的占用状态

Ⅳ. 逻辑设备与物理设备的映射关系

计算机网络

33

如图，2 段链路的数据传输速率为 100Mbps，时延带宽积（即单向传播时延*带宽）均为 1000bit。若 H1 向 H2 发送 1 个大小为 1MB 的文件，分组长度为 1000B，则从 H1 开始发送时刻起到 H2 收到文件全部数据时刻止，所需的时间至少是（注：$M = 10^6$）?

34

某无噪声理想信道带宽为 4MHz，采用 QAM 调制，若该信道的最大数据传输率是 48Mbps，则该信道采用的 QAM 调制方案是（）

35

假设通过同一信道，数据链路层分别采用停等协议、GBN 协议和 SR 协议（发送窗口和接收窗口相等）传输数据，三个协议数据帧长相同，忽略确认帧长度，帧序号位数为 3 比特。若对应三个协议的发送方最大信道利用率分别是 U1、U2 和 U3，则 U1、U2 和 U3 满足的关系是（ ）

36

已知 10BaseT 以太网的争用时间片为 51.2us。若网卡在发送某帧时发生了连续 4 次冲突，则基于二进制指数退避算法确定的再次尝试重发该帧前等待的最长时间是（ ）

37

若甲向乙发送数据时采用 CRC 校验，生成多项式为 $G(x)=x^4+x+1$（即 G=10011），则乙接收到下列比特串时，可以断定其在传输过程中未发生错误的是（ ）

38

某网络拓扑如下图所示，其中路由器 R2 实现 NAT 功能。若主机 H 向 Inernet 发送一个 IP 分组，则经过 R2 转发后，该 IP 分组的源 IP 地址是（ ）

39

主机 168.16.84.24/20 所在子网的最小可分配地址和最大可分配地址分别是（ ）

40

下列关于 ipv6 和 ipv4 的叙述中，正确的是（ ）

I. ipv6 地址空间是 ipv4 地址空间的 96 倍

II. ipv4 和 ipv6 的基本首部的长度均可变

III.ipv4 向 ipv6 过渡可以采用双协议栈和隧道技术

IV. ipv6 首部的 Hop-Limit 等价于 ipv4 首部的 TTL 字段

解答题

数据结构

41

已知有向图 G 采用邻接矩阵存储，类型定义如下：

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

将图中出度大于入度的顶点称为 K 顶点。例如在题 41 图中，顶点 a 和 b 都是 K 顶点。

设计算法 int printVertices(MGraph G) 对给定任意非空有向图 G，输出 G 中所有 K 顶点的算法，并返回 K 顶点的个数。

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

(2) 根据算法思想，写出 C/C++ 描述，并注释。

int printVertices(MGraph G) {
    // K 顶点的个数
    int count = 0;
    for (int v = 0; v < numVertices; v++) {
        // v 顶点的入度和出度
        int indegree = 0;
        int outdegree = 0;
        // 统计出度
        for (int i = 0; i < numVertices; i++) {
            outdegree += G.Edge[v][i];
        }
        // 统计入度
        for (int i = 0; i < numVertices; i++) {
            indegree += G.Edge[i][v];
        }
        if (outdegree > indegree) {
            printf("%s ", G.VerticesList[v]);
            count++;
        }
    }
    return;
}

42

对含有 n（n > 0）个记录的文件进行外部排序，采用置换 - 选择排序生成初始归并段时需要使用一个工作，工作区中能保存 m 个记录，请回答下列问题，

(1) 如果文件中由 19 个记录，其关键字是 51, 94, 37,14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 8, 90, 166, 100；当 m=4 时，可以生成几个初始归并段，各是什么？

(2) 对任意的 m 个（n > m > 0），生成的第一个初始归并段的长度最大值和最小值分别是多少？

组成原理

43

已知计算机 M 字长为 32 位，按字节编址，采用请求调页策略的虚拟存储管理方式，虚拟地址为 32 位，页面大小为 4KB；数据 Cache 采用 4 路组相联映射，数据区大小为 8KB，主存块大小为 32B。现有 C 语言程序段如下：

for (i = 0; i < 24; i++)
    for (j = 0; j < 64; j++) a[i][j] = 10;

已知二维数组 a 按行优先存放，在虚拟地址空间中分配的起始地址为 0042 2000H，sizeof(int)=4，假定在 M 上执行上述程序段之前数组 a 不在主存，且在该程序段执行过程中不会发生页面置换。请回答下列问题。

(1) 数组 a 分为几个页面存储？对于数组 a 的访问，会发生几次缺页异常？页故障地址各是什么？

(2) 不考虑变量 i 和 j，该程序段的数据访问是否具有时间局部性？为什么？

(3) 计算机 M 的虚拟地址（A31~A0）中哪几位用作块内地址？哪几位用作 Cache 组号？a[1][0] 的虚拟地址是多少？其所在主存块对应的 Cache 组号是多少？

(4) 数组 a 占用多少主存块？假设上述程序段执行过程中数组 a 的访问不会和其他数据发生 Cache 访问冲突，则数组 a 的 Cache 命中率是多少？若将循环中 i 和 j 的次序按如下方式调换：

for (j = 0; j < 64; j++)
    for (i = 0; i < 24; i++) a[i][j] = 10;

则数组 a 的 Cache 命中率又是多少？

44

上题中 C 程序段在计算机 M 上的部分机器级代码如下，每个机器级代码行中依次包含指令序号、虚拟地址、机器指令和汇编指令。

for (i = 0; i < 24; i++)
1   00401072  C7 45 F8 00 00 00 00              mov[ebp-8], 0
2   00401079  EB 09                             jmp 00401084h
3   0040107B  8B 55 F8                          mov eax, [ebp-8]
    ...       ...                               ...
7   00401088  7D 32                             jge 004010bch
    for (j = 0; j < 64; j++)
8   0040108A  C7 45 FC 00 00 00 00              mov[ebp-4], 0
    ...       ...                               ...
        a[i][j] = 10;
    ...       ...                               ...
19  004010AE  C7 84 82 00 20 42 00 0A 00 00 00  mov[ecx+edx*4+00422000h], 0Ah
20  ...       ...

请回答下列问题。

(1) 第 20 条指令的虚拟地址是多少？

(2) 已知第 2 条 jmp 和第 7 条 jge 都是跳转指令，其操作码分别是 EBH 和 7DH，跳转地址分别为 0040 1084H、0040 10BCH，这两条指令都采用什么寻址方式？给出第 2 条指令 jmp 的跳转目标地址计算过程。

(3) 已知第 19 条 mov 指令的功能是“a[i][j]←10”，其中 ecx 和 edx 为寄存器名，0042 2000H 是数组 a 的首地址，指令中源操作数采用什么寻址方式？已知 edx 中存放的是变量 j，ecx 中存放的是什么？根据该指令的机器码判断计算机 M 采用的是大端还是小端方式。

(4) 第一次执行第 19 条指令时，取指令过程中是否会发生缺页异常？为什么？

操作系统

45

现要求学生使用 swap 指令和布尔型变量 lock 实现临界区互斥。lock 为线程间共享的变量。lock 的值为 TRUE 时线程不能进入临界区，为 FALSE 时线程能够进入临界区。某同学编写的实现临界区互斥的伪代码如题 45(a) 图所示。

(1) 题 45(a) 图中伪代码中哪些语句存在错误？将其改为正确的语句（不增加语句条数）。

(2) 题 45(b) 图中给出了两个变量值的函数 newSwap() 的代码是否可以用函数调用语句“newSwap(&key, &lock)”代替指令“swap key, lock”以实现临界区的互斥？为什么？

46

进程 P 通过执行系统调用从键盘接收一个字符的输入，已知此过程中与进程 P 相关的操作包括：①将进程 P 插入就绪队列；②将进程 P 插入阻塞队列；③将字符从键盘控制器读入系统缓冲区；④启动键盘中断处理程序；⑤进程 P 从系统调用返回；⑥用户在键盘上输入字符。以上编号①~⑥仅用于标记操作，与操作的先后顺序无关。请回答下列问题。

(1) 按照正确的操作顺序，操作①的前一个和后一个操作分别是上述操作中的哪一个？操作⑥的后一个操作上述操作中的哪一个？

(2) 在上述哪个操作之后 CPU 一定从进程 P 切换到其他进程？在上述哪个操作之后 CPU 调度程序才能选择进程 P 执行？

(3) 完成上述哪个操作的代码属于键盘驱动程序？

(4) 键盘中断处理程序执行时，进程 P 处于什么状态？CPU 处于内核态还是用户态？

计算机网络

47

如图，主机 H 登录到 FTP 服务器后，自服务器上下载一个大小为 18000B 的文件 F，假设 H 传输 F 建立数据链接是，选择的初始序号为 100，MTU=1000B，拥塞控制的初始阈值是 4MSS，RTT=100ms，忽略 TCP 的传输时延，在 F 的传送过程中，H 以 MSS 段向服务器发送数据，且始终没有错误，丢包和乱序。

(1) FTP 的控制连接是持久的还是非持久的？FTP 的数据连接是持久的还是非持久的？H 登录服务器时，建立的 FTP 连接是数据连接还是控制连接。

(2) H 通过数据连接发送 F 时，F 的第一个字节序号是多少？在断开数据连接的过程中，FTP 发达的第二次挥手的 ACK 序号是？

(3) F 发送过程中，当 H 收到确认序号为 2101 的确认时，H 的拥塞调整为多少？收到确认序号为 7101 的确认段时，H 的拥窗口调整为多少

(4) H 从请求建立数据连接开始，到确认 F 已被服务全部接收为止，至少要多长时间？期间应用层数平均发送速率是多少？