2022 整卷 · 四〇八档案室

BOK 数据结构

数据结构

2022-01

选择题2 分

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

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

A. $O(log n)$
B. $O(n)$
C. $O(nlog n)$
D. $O(n 2)$

单题查看 1

BOK 数据结构

数据结构

2022-02

选择题2 分

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

A. 若 in 是 ST 的入栈序列，则不能判断 out 是否为其可能的出栈序列
B. 若 out 是 ST 的出栈序列，则不能判断 in 是否为其可能的入栈序列
C. 若 in 是 ST 的入栈序列，out 是对应 in 的出栈序列，则 in 与 out 一定不同
D. 若 in 是 ST 的入栈序列，out 是对应 in 的出栈序列，则 in 与 out 可能互为倒序

单题查看 2

BOK 数据结构

数据结构

2022-03

选择题2 分

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

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

A. 仅 I
B. 仅 III
C. 仅 II、III
D. 仅 II、IV

单题查看 3

BOK 数据结构

数据结构

2022-04

选择题2 分

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

A. 8
B. 7
C. 6
D. 5

单题查看 4

BOK 数据结构

数据结构

2022-05

选择题2 分

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

A. T1 与 T2 的结点数相同
B. T1 的高度大于 T2 的高度
C. 出现频次不同的字符在 T1 中处于不同的层
D. 出现频次不同的字符在 T2 中处于相同的层

单题查看 5

BOK 数据结构

数据结构

2022-06

选择题2 分

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

A. 当 |V| > |E| 时，G 一定是连通的
B. 当 |V| < |E| 时，G 一定是连通的
C. 当 |V| = |E| - 1 时，G 一定是不连通的
D. 当 |V| > |E| + 1 时，G 一定是不连通的

单题查看 6

BOK 数据结构

数据结构

2022-07

选择题2 分

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

A. c
B. g
C. h
D. j

单题查看 7

BOK 数据结构

数据结构

2022-08

选择题2 分

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

A. 60, 90, 280
B. 60, 90, 350
C. 60, 85, 110, 350
D. 60, 90, 110, 350

单题查看 8

BOK 数据结构

数据结构

2022-09

选择题2 分

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

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

A. 仅 I、II
B. 仅 I、III
C. 仅 II、III
D. I、II、III

单题查看 9

BOK 数据结构

数据结构

2022-10

选择题2 分

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

A. 将两个有序表合并为一个新的有序表
B. 将M划分为两部分，两部分的元素个数大致相等
C. 将M划分为n个部分，每个部分中仅含有一个元素
D. 将M划分为两部分，一部分元素的值均小于另一部分元素的值

单题查看 10

BOK 数据结构

数据结构

2022-11

选择题2 分

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

A. 仅I、II
B. 仅III、IV
C. 仅I、II、IV
D. I、II、III、IV

单题查看 11

BOK 组成原理

组成原理

2022-12

选择题2 分

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

A. 2.8, 28 μs
B. 28, 28 μs
C. 2.8, 28 ms
D. 28, 28 ms

单题查看 12

BOK 组成原理

组成原理

2022-13

选择题2 分

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

A. $-2 32 sim2 31 -1$
B. $-2 31 sim2 31 -1$
C. $-2 32 sim2 32 -1$
D. $-2 31 sim2 32 -1$

单题查看 13

BOK 组成原理

组成原理

2022-14

选择题2 分

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

A. BEE0 0000H
B. BF60 0000H
C. BF70 0000H
D. C0E0 0000H

单题查看 14

BOK 组成原理

组成原理

2022-15

选择题2 分

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

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

A. 得到主存地址02 4840H
B. 得到主存地址18 0840H
C. 得到主存地址01 8840H
D. 检测到缺页异常

单题查看 15

BOK 组成原理

组成原理

2022-16

选择题2 分

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

A. 8, 20
B. 8, 23
C. 64, 20
D. 64, 23

单题查看 16

BOK 组成原理

组成原理

2022-17

选择题2 分

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

A. 内存条的容量为512 MB
B. 采用多模块交叉编址方式
C. 芯片的地址引脚为26位
D. 芯片内行缓冲有8192×8位

单题查看 17

BOK 组成原理

组成原理

2022-18

选择题2 分

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

A. 仅I、II
B. 仅I、III
C. 仅II、IV
D. 仅I、III、IV

单题查看 18

BOK 组成原理

组成原理

2022-19

选择题2 分

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

A. 0
B. 2
C. 64
D. 128

单题查看 19

BOK 组成原理

组成原理

2022-20

选择题2 分

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

A. 预处理→编译→汇编→链接
B. 预处理→汇编→编译→链接
C. 预处理→编译→链接→汇编
D. 预处理→汇编→链接→编译

单题查看 20

BOK 组成原理

组成原理

2022-21

选择题2 分

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

A. 适用于键盘、针式打印机等字符型设备
B. 外设和主机之间的数据传送通过软件完成
C. 外设准备数据的时间应小于中断处理时间
D. 外设为某进程准备数据时 CPU 可运行其他进程

单题查看 21

BOK 组成原理

组成原理

2022-22

选择题2 分

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

A. 多核处理器属于 MIMD 结构
B. 向量处理器属于 SIMD 结构
C. 硬件多线程技术只可用于多核处理器
D. SMP 中所有处理器共享单一物理地址空间

单题查看 22

BOK 操作系统

操作系统

2022-23

选择题2 分

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

A. 支持进程的并发执行
B. 不必支持虚拟存储管理
C. 需要实现对共享资源的管理
D. 进程数越多 CPU 利用率越高

单题查看 23

BOK 操作系统

操作系统

2022-24

选择题2 分

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

A. 中断向量表
B. 文件系统的根目录
C. 硬盘分区表
D. 文件系统的索引结点表

单题查看 24

BOK 操作系统

操作系统

2022-25

选择题2 分

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

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

A. 4
B. 5
C. 6
D. 7

单题查看 25

BOK 操作系统

操作系统

2022-26

选择题2 分

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

A. 1
B. 2
C. 3
D. 4

单题查看 26

BOK 操作系统

操作系统

2022-27

选择题2 分

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

A. CPU 处于用户态时只能执行特权指令
B. CPU 处于内核态时只能执行特权指令
C. CPU 处于用户态时只能执行非特权指令
D. CPU 处于内核态时只能执行非特权指令

单题查看 27

BOK 操作系统

操作系统

2022-28

选择题2 分

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

A. 仅 I、IV
B. 仅 II、III
C. 仅 III、IV
D. 仅 I、III、IV

单题查看 28

BOK 操作系统

操作系统

2022-29

选择题2 分

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

A. 淘汰内存中的页
B. 建立页号与页框号的对应关系
C. 将页 b 从外存读入内存
D. 修改页表中页 b 对应的存在位

单题查看 29

BOK 操作系统

操作系统

2022-30

选择题2 分

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

A. 页置换算法
B. 工作集的大小
C. 进程的数量
D. 页缓冲队列的长度

单题查看 30

BOK 操作系统

操作系统

2022-31

选择题2 分

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

A. 仅 I、III
B. 仅 II、III
C. 仅 II、IV
D. 仅 II、III、IV

单题查看 31

BOK 操作系统

操作系统

2022-32

选择题2 分

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

A. 驱动程序与 I/O 控制方式无关
B. 初始化设备是由驱动程序控制完成的
C. 进程在执行驱动程序时可能进入阻塞态
D. 读/写设备的操作是由驱动程序控制完成的

单题查看 32

BOK 计算机网络

计算机网络

2022-33

选择题2 分

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

A. 物理层
B. 数据链路层
C. 网络层
D. 传输层

单题查看 33

BOK 计算机网络

计算机网络

2022-34

选择题2 分

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

A. 200 kbps
B. 400 kbps
C. 800 kbps
D. 1600 kbps

单题查看 34

BOK 计算机网络

计算机网络

2022-35

选择题2 分

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

A. 183.80.0.0
B. 183.80.64.0
C. 183.80.72.0
D. 183.80.192.0

单题查看 35

BOK 计算机网络

计算机网络

2022-36

选择题2 分

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

A. 255.255.255.192, 192.168.1.1
B. 255.255.255.192, 192.168.1.62
C. 255.255.255.224, 192.168.1.1
D. 255.255.255.224, 192.168.1.62

单题查看 36

BOK 计算机网络

计算机网络

2022-37

选择题2 分

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

A. 东向接口
B. 南向接口
C. 西向接口
D. 北向接口

单题查看 37

BOK 计算机网络

计算机网络

2022-38

选择题2 分

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

A. 4 RTT
B. 5 RTT
C. 11 RTT
D. 16 RTT

单题查看 38

BOK 计算机网络

计算机网络

2022-39

选择题2 分

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

A. 850 ms, 50 ms
B. 1650 ms, 50 ms
C. 850 ms, 75 ms
D. 1650 ms, 75 ms

单题查看 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 连接时刻起，到接收到全部内容止，所需的时间至少是（）。

A. 30 ms
B. 40 ms
C. 50 ms
D. 60 ms

单题查看 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 真题档案