2022 整卷 · 四〇八档案室

BOK 数据结构

数据结构

2022-01

选择题2 分

下列程序段的时间复杂度是（）。

int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

单题查看 1

BOK 数据结构

数据结构

2022-02

选择题2 分

给定有限符号集 S，in 和 out 均为 S 中所有元素的任意排列。对于初始为空的栈 ST，下列叙述中，正确的是（）。

单题查看 2

BOK 数据结构

数据结构

2022-03

选择题2 分

若结点 p 与 q 在二叉树 T 的中序遍历序列中相邻，且 p 在 q 之前，则下列 p 与 q 的关系中，不可能的是（）。

I. q 是 p 的双亲
II. q 是 p 的右孩子
III. q 是 p 的右兄弟
IV. q 是 p 的双亲的双亲

单题查看 3

BOK 数据结构

数据结构

2022-04

选择题2 分

若三叉树 T 中有 244 个结点（叶结点的高度为 1），则 T 的高度至少是（）。

单题查看 4

BOK 数据结构

数据结构

2022-05

选择题2 分

对任意给定的含 n（n>2）个字符的有限集合 S，用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。下列叙述中，正确的是（）。

单题查看 5

BOK 数据结构

数据结构

2022-06

选择题2 分

对于无向图 G=（V,E），下列选项中，正确的是（）。

单题查看 6

BOK 数据结构

数据结构

2022-07

选择题2 分

下图是一个有10个活动的AOE网，时间余量最大的活动是（）。

单题查看 7

BOK 数据结构

数据结构

2022-08

选择题2 分

在下图所示的5阶B树中，删除关键字260之后需要进行必要的调整，得到新的B树T1。下列选项中，不可能是T1根结点中关键字序列的是（）。

单题查看 8

BOK 数据结构

数据结构

2022-09

选择题2 分

下列因素中，影响散列（哈希）方法平均查找长度的是（）。

I. 装填因子
II. 散列函数
III. 冲突解决策略

单题查看 9

BOK 数据结构

数据结构

2022-10

选择题2 分

使用二路归并排序对含n个元素的数组M进行排序时，二路归并操作的功能是（）。

单题查看 10

BOK 数据结构

数据结构

2022-11

选择题2 分

对数据进行排序时，若采用直接插入排序而不采用快速排序，则可能的原因是（）。
I. 大部分元素已有序 II. 待排序元素数量很少
III. 要求空间复杂度为O(1) IV. 要求排序算法是稳定的

单题查看 11

BOK 组成原理

组成原理

2022-12

选择题2 分

某计算机主频为1 GHz，程序P运行过程中，共执行了10000条指令，其中，80%的指令执行平均需1个时钟周期，20%的指令执行平均需10个时钟周期。程序P的平均CPI和CPU执行时间分别是（）。

单题查看 12

BOK 组成原理

组成原理

2022-13

选择题2 分

32位补码所能表示的整数范围是（）。

单题查看 13

BOK 组成原理

组成原理

2022-14

选择题2 分

-0.4375的IEEE 754单精度浮点数表示为（）。

单题查看 14

BOK 组成原理

组成原理

2022-15

选择题2 分

某计算机主存地址为24位，采用分页虚拟存储管理方式，虚拟地址空间大小为4 GB，页大小为4 KB，按字节编址。某进程的页表部分内容如下表所示。

当CPU访问虚拟地址0008 2840H时，虚-实地址转换的结果是（）。

单题查看 15

BOK 组成原理

组成原理

2022-16

选择题2 分

若计算机主存地址为32位，按字节编址，某Cache的数据区容量为32 KB，主存块大小为64 B，采用8路组相联映射方式，该Cache中比较器的个数和位数分别为（）。

单题查看 16

BOK 组成原理

组成原理

2022-17

选择题2 分

某内存条包含8个8192×8192×8位的DRAM芯片，按字节编址，支持突发（burst）传送方式，对应存储器总线宽度为64位，每个DRAM芯片内有一个行缓冲区（row buffer）。下列关于该内存条的叙述中，不正确的是（）。

单题查看 17

BOK 组成原理

组成原理

2022-18

选择题2 分

下列选项中，属于指令集体系结构（ISA）规定的内容是（）。
I. 指令字格式和指令类型 II. CPU的时钟周期
III. 通用寄存器个数和位数 IV. 加法器的进位方式

单题查看 18

BOK 组成原理

组成原理

2022-19

选择题2 分

设计某指令系统时，假设采用16位定长指令字格式，操作码使用扩展编码方式，地址码为6位，包含零地址、一地址和二地址3种格式的指令。若二地址指令有12条，一地址指令有254条，则零地址指令的条数最多为（）。

单题查看 19

BOK 组成原理

组成原理

2022-20

选择题2 分

将高级语言源程序转换为可执行目标文件的主要过程是（）。

单题查看 20

BOK 组成原理

组成原理

2022-21

选择题2 分

下列关于中断 I/O 方式的叙述中，不正确的是（）。

单题查看 21

BOK 组成原理

组成原理

2022-22

选择题2 分

下列关于并行处理技术的叙述中，不正确的是（）。

单题查看 22

BOK 操作系统

操作系统

2022-23

选择题2 分

下列关于多道程序系统的叙述中，不正确的是（）。

单题查看 23

BOK 操作系统

操作系统

2022-24

选择题2 分

下列选项中，需要在操作系统进行初始化过程中创建的是（）。

单题查看 24

BOK 操作系统

操作系统

2022-25

选择题2 分

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

若系统采用基于优先权的抢占式进程调度算法，则从 0 ms 时刻开始调度，到 4 个进程都运行结束为止，发生进程调度的总次数为（）。

单题查看 25

BOK 操作系统

操作系统

2022-26

选择题2 分

系统中有三个进程 P0、P1、P2 及三类资源 A、B、C。若某时刻系统分配资源的情况如下表所示，则此时系统中存在的安全序列的个数为（）。

单题查看 26

BOK 操作系统

操作系统

2022-27

选择题2 分

下列关于 CPU 模式的叙述中，正确的是（）。

单题查看 27

BOK 操作系统

操作系统

2022-28

选择题2 分

下列事件或操作中，可能导致进程 P 由执行态变为阻塞态的是（）。
I. 进程 P 读文件
II. 进程 P 的时间片用完
III. 进程 P 申请外设
IV. 进程 P 执行信号量的 wait() 操作

单题查看 28

BOK 操作系统

操作系统

2022-29

选择题2 分

某进程访问的页 b 不在内存中，导致产生缺页异常，该缺页异常处理过程中不一定包含的操作是（）。

单题查看 29

BOK 操作系统

操作系统

2022-30

选择题2 分

下列选项中，不会影响系统缺页率的是（）。

单题查看 30

BOK 操作系统

操作系统

2022-31

选择题2 分

执行系统调用的过程涉及下列操作，其中由操作系统完成的是（）。
I. 保存断点和程序状态字
II. 保存通用寄存器的内容
III. 执行系统调用服务例程
IV. 将 CPU 模式改为内核态

单题查看 31

BOK 操作系统

操作系统

2022-32

选择题2 分

下列关于驱动程序的叙述中，不正确的是（）。

单题查看 32

BOK 计算机网络

计算机网络

2022-33

选择题2 分

在 ISO/OSI 参考模型中，实现两个相邻结点间流量控制功能的是（）。

单题查看 33

BOK 计算机网络

计算机网络

2022-34

选择题2 分

在一条带宽为 200 kHz 的无噪声信道上，若采用 4 个幅值的 ASK 调制，则该信道的最大数据传输速率是（）。

单题查看 34

BOK 计算机网络

计算机网络

2022-35

选择题2 分

若某主机的 IP 地址是 183.80.72.48，子网掩码是 255.255.192.0，则该主机所在网络的网络地址是（）。

单题查看 35

BOK 计算机网络

计算机网络

2022-36

选择题2 分

下图所示网络中的主机 H 的子网掩码与默认网关分别是（）。

单题查看 36

BOK 计算机网络

计算机网络

2022-37

选择题2 分

在 SDN 网络体系结构中，SDN 控制器向数据平面的 SDN 交换机下发流表时所使用的接口是（）。

单题查看 37

BOK 计算机网络

计算机网络

2022-38

选择题2 分

假设主机甲和主机乙已建立一个 TCP 连接，最大段长 MSS = 1 KB，甲一直有数据向乙发送，当甲的拥塞窗口为 16 KB 时，计时器发生了超时，则甲的拥塞窗口再次增长到 16 KB 所需要的时间至少是（）。

单题查看 38

BOK 计算机网络

计算机网络

2022-39

选择题2 分

假设客户 C 和服务器 S 已建立一个 TCP 连接，通信往返时间 RTT = 50 ms，最长报文段寿命 MSL = 800 ms，数据传输结束后，C 主动请求断开连接。若从 C 主动向 S 发出 FIN 段时刻算起，则 C 和 S 进入 CLOSED 状态所需的时间至少分别是（）。

单题查看 39

BOK 计算机网络

计算机网络

2022-40

选择题2 分

假设主机 H 通过 HTTP/1.1 请求浏览某 Web 服务器 S 上的 Web 页 news408.html，news408.html 引用了同目录下的 1 幅图像，news408.html 文件大小为 1 MSS（最大段长），图像文件大小为 3 MSS，H 访问 S 的往返时间 RTT = 10 ms，忽略 HTTP 响应报文的首部开销和 TCP 段传输时延。若 H 已完成域名解析，则从 H 请求与 S 建立 TCP 连接时刻起，到接收到全部内容止，所需的时间至少是（）。

单题查看 40

BOK 数据结构

数据结构

2022-41

综合题13 分

已知非空二叉树 T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：

typedef struct {
    int SqBiTNode[MAX_SIZE]; // 保存二叉树结点值的数组
    int ElemNum;            // 实际占用的数组元素个数
} SqBiTTree;

T 中不存在的结点在数组 SqBiTNode 中用 -1 表示。例如，对于下图所示的两棵非空二叉树 T1 和 T2，

请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回 true，否则，返回 false。要求：

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

答案

（1）建立两个与顺序存储数组等长的辅助数组 pmin 和 pmax，分别记录以各结点为根的子树中的最小值和最大值。先用结点值初始化两个数组，再从最后一个结点向根逆序扫描：左子树的最大值必须小于双亲值，右子树的最小值必须大于双亲值；满足时把相应的最小值或最大值向双亲传播，否则立即返回 false。

（2）

bool judgeBST(SqBiTree bt) {
    int k, m, *pmin, *pmax;
    pmin = (int *)malloc(sizeof(int) * (bt.ElemNum));
    pmax = (int *)malloc(sizeof(int) * (bt.ElemNum));
    for (k = 0; k < bt.ElemNum; k++) { // 辅助数组初始化
        pmin[k] = pmax[k] = bt.SqBiTNode[k];
    }
    for (k = bt.ElemNum - 1; k > 0; k--) { // 从最后一个叶结点向根遍历
        if (bt.SqBiTNode[k] != -1) {
            m = (k - 1) / 2; // 双亲
            if (k % 2 == 1 && bt.SqBiTNode[m] > pmax[k]) { // 左孩子
                pmin[m] = pmin[k];
            } else if (k % 2 == 0 && bt.SqBiTNode[m] < pmin[k]) { // 右孩子
                pmax[m] = pmax[k];
            } else return false;
        }
    }
    return true;
}

时间复杂度为 $O(n)$ ，辅助空间复杂度为 $O(n)$ 。

单题查看 41

BOK 数据结构

数据结构

2022-42

综合题10 分

现有 n (n > 100000) 个数保存在一维数组 M 中，需要查找 M 中最小的 10 个数。请回答下列问题。

设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简述其算法思想（不需要程序实现）。
说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

单题查看 42

BOK 组成原理

组成原理

2022-43

综合题15 分

某 CPU 中部分数据通路如题 43 图所示，其中，GPRs 为通用寄存器组；FR 为标志寄存器，用于存放 ALU 产生的标志信息；带箭头虚线表示控制信号，如控制信号 Read、Write 分别表示主存读、主存写，MDRin 表示内部总线上数据写入 MDR，MDRout 表示 MDR 的内容送内部总线。

请回答下列问题。

1）设 ALU 的输入端 A、B 及输出端 F 的最高位分别为 A15、B15 及 F15，FR 中的符号标志和溢出标志分别为 SF 和 OF，则 SF 的逻辑表达式是什么？A 加 B、A 减 B 时 OF 的逻辑表达式分别是什么？要求逻辑表达式的输入变量为 A15、B15 及 F15。

2）为什么要设置暂存器 Y 和 Z？

3）若 GPRs 的输入端 rs、rd 分别为所读、写的通用寄存器的编号，则 GPRs 中最多有多少个通用寄存器？rs 和 rd 来自图中的哪个寄存器？已知 GPRs 内部有一个地址译码器和一个多路选择器，rd 应连接地址译码器还是多路选择器？

4）取指令阶段（不考虑 PC 增量操作）的控制信号序列是什么？若从发出主存读命令到主存读出数据并传送到 MDR 共需 5 个时钟周期，则取指令阶段至少需要几个时钟周期？

5）图中控制信号由什么部件产生？图中哪些寄存器的输出信号会连到该部件的输入端？

单题查看 43

BOK 组成原理

组成原理

2022-44

综合题8 分

假设某磁盘驱动器中有 4 个双面盘片，每个盘面有 20000 个磁道，每个磁道有 500 个扇区，每个扇区可记录 512 字节的数据，盘片转速为 7200 RPM(转/分)，平均寻道时间为 5 ms。请回答下列问题。

1）每个扇区包含数据及其地址信息，地址信息分为 3 个字段。这 3 个字段的名称各是什么？对于该磁盘，各字段至少占多少位？
2）一个扇区的平均访问时间约为多少？
3）若采用周期挪用 DMA 方式进行磁盘与主机之间的数据传送，磁盘控制器中的数据缓冲区大小为 64 位，则在一个扇区读写过程中，DMA 控制器向 CPU 发送了多少次总线请求？若 CPU 检测到 DMA 控制器的总线请求信号时也需要访问主存，则 DMA 控制器是否可以获得总线使用权？为什么？

单题查看 44

BOK 操作系统

操作系统

2022-45

综合题7 分

某文件系统的磁盘块大小为 4 KB，目录项由文件名和索引结点号构成，每个索引结点占 256 字节，其中包含直接地址项 10 个，一级、二级和三级间接地址项各 1 个，每个地址项占 4 字节。该文件系统中子目录 stu 的结构如题 45(a)图所示，stu 包含子目录 course 和文件 doc，course 子目录包含文件 course1 和 course2。各文件的文件名、索引结点号、占用磁盘块的块号如题 45(b)图所示。请回答下列问题。
1）目录文件 stu 中每个目录项的内容是什么？
2）文件 doc 占用的磁盘块的块号 $x$ 的值是多少？
3）若目录文件 course 的内容已在内存，则打开文件 course1 并将其读入内存，需要读几个磁盘块？说明理由。
4）若文件 course2 的大小增长到 6 MB，则为了存取 course2 需要使用该文件索引结点的哪几级间接地址项？说明理由。

答案

文件名	索引结点号
course	2
doc	10

（2） $x=30$ 。

（3）需要读 2 个磁盘块：先读 course1 的索引结点所在块，再读其内容所在的 30 号磁盘块。

（4）需要使用一级和二级间接地址项。6 MB 文件占 $1536$ 个块，直接地址项和一级间接地址项共能记录 $10+1024=1034$ 个数据块，还需使用二级间接地址项。

单题查看 45

BOK 操作系统

操作系统

2022-46

综合题8 分

某进程的两个线程 T1 和 T2 并发执行 A、B、C、D、E 和 F 共 6 个操作，其中 T1 执行 A、E 和 F，T2 执行 B、C 和 D。题 46 图表示上述 6 个操作的执行顺序所必须满足的约束：C 在 A 和 B 完成后执行，D 和 E 在 C 完成后执行，F 在 E 完成后执行。请使用信号量的 wait()、signal() 操作描述 T1 和 T2 之间的同步关系，并说明所用信号量的作用及其初值。

答案

信号量 S_AC 描述 A、C 之间的同步关系，初值为 0，保证 C 在 A 完成后执行；信号量 S_CE 描述 C、E 之间的同步关系，初值为 0，保证 E 在 C 完成后执行。

semaphore S_AC = 0;  // 描述 A、C 之间的同步关系
semaphore S_CE = 0;  // 描述 C、E 之间的同步关系

T1:                  T2:
A;                   B;
signal(S_AC);        wait(S_AC);
wait(S_CE);          C;
E;                   signal(S_CE);
F;                   D;

单题查看 46

BOK 计算机网络

计算机网络

2022-47

综合题9 分

某网络拓扑如题 47 图所示，R 为路由器，S 为以太网交换机，AP 是 802.11 接入点，路由器的 E0 接口和 DHCP 服务器的 IP 地址配置如图中所示；H1 与 H2 属于同一个广播域，但不属于同一个冲突域；H2 和 H3 属于同一个冲突域；H4 和 H5 已经接入网络，并通过 DHCP 动态获取了 IP 地址。现有路由器、100BaseT 以太网交换机和 100BaseT 集线器（Hub）三类设备各若干台。

请回答下列问题。
1）设备 1 和设备 2 应该分别选择哪类设备？
2）若信号传播速度为 2×10^8 m/s，以太网最小帧长为 64 B，信号通过设备 2 时会产生额外的 1.51 μs 的时间延迟，则 H2 与 H3 之间可以相距的最远距离是多少？
3）在 H4 通过 DHCP 动态获取 IP 地址过程中，H4 首先发送了 DHCP 报文 M，M 是哪种 DHCP 报文？路由器 E0 接口能否收到封装 M 的以太网帧？S 向 DHCP 服务器转发的封装 M 的以太网帧的目的 MAC 地址是什么？
4）若 H4 向 H5 发送一个 IP 分组 P，则 H5 收到的封装 P 的 802.11 帧的地址 1、地址 2 和地址 3 分别是什么？

单题查看 47

计算机学科专业基础2022 真题档案