2022 年真题

第 1 题 数据结构复杂度分析

下列程序段的时间复杂度是()。

|nt sum =0;for(Int |=1;|<n;| *=2)

for ( |nt j= 0; j<|;j ++)

sum ++ ;

A.O(log₂n)

B.O(n)

C.O(nlog₂n)

D.O(n²)

[tag_link]

正确答案：B

当外层循环的变量 i 取不同值时，内层循环就执行多少次，因此总循环次数为 的所有取值之和。假设外层循环共执行 k 次，当 i = 1 , 2 , 4 , 8 , ⋯ , 2 k − 1 ( 2 k − 1 < n ≤ 2 k ) 时，内层循 环执行 i 次，因此总循环次数 T = 1 + 2 + 4 + 8 + ⋯ + 2 k − 1 = 2 k − 1 即 n < T < 2 n ，时间复杂度为 O ( n ) 。

第 2 题 数据结构入栈出栈序列

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

A. 若|n是 ST 的入栈序列，则不能判断 out 是否为其可能的出栈序列

B. 若 out 是 ST 的出栈序列，则不能判断|n 是否为其可能的入栈序列

C. 若|n是 ST 的入栈序列，out 是对应|n的出栈序列，则|n与 out 一定不同

D. 若 |n 是 ST 的入栈序列，out 是对应|n的出栈序列，则n|与 out 可能互为倒序

[tag_link]

正确答案：D

参考 入栈出栈序列 ，如果给定一个入栈序列，我们可以得到其所有可能的出栈序列，所以当给定一个出栈序列时，我们可以判断其是否正确，所以 A、B、C 均为错误选项。

第 3 题 数据结构二叉树遍历

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

|.q 是 p 的双亲

l|.q 是 p 的右孩子

q 是 p 的右兄弟

IV.q 是 p 的双亲的双亲

A. 仅| B.仅 Ⅲ

C. 仅 I 、 Ⅲ D. 仅 Ⅱ、IV

[tag_link]

正确答案：B

对于此类题，每种情况只需举出一个反例即可。如图 1 所示，q 是 p 的双亲，中 序遍历序列为 {p, q}，I 可能。如图 2 所示，q 是 p 的右孩子，中序遍历序列为 {p, q}，Ⅱ可能。如图 4 所示，q 是 p 的双亲的双亲，中序遍历序列为 {x, p, q}，IV 可能。如图 3 所示，q 是 p 的右兄弟，F 是 q 和 p 的父结点，中序遍历要求先遍历左子树，再访问根结点，最后遍历右 子树，因此一定先访问 p，再访问 F，最后访问 q，p 和 q 不可能相邻出现，II 不可能。 2018_Q7_3

第 4 题 数据结构树的概念

若三叉树 T 中有244个结点(叶结点的高度为1),则 T 的高度至少是()。

A.8

B.7

C.6

D.5

[tag_link]

正确答案：C

高度为 n 的二叉树最多有 1 + 2 + ⋯ + 2 n − 1 = 2 n − 1 个结点，高度为 n 的三叉树最多有 f ( n ) = 1 + 3 + ⋯ + 3 n − 1 = 3 − 1 3 n − 1 − 2 3 n − 1 。f ( 5 ) = 121 f ( 6 ) = 364 因为 121 < 244 < 364 ，所以高度至少为 6。

第 5 题 数据结构哈夫曼树

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

A. T1 与 T2 的结点数相同

B.T1 的高度大千 T2 的高度

C. 出现频次不同的字符在 T1 中处于不同的层

D. 出现频次不同的字符在 T2 中处于相同的层

[tag_link]

正确答案：D

可以画一个简单的特例来证明。图 1 是满足条件的二叉树 T1，图 2 是满足条件的二叉树 T2，结点中有值表示这个结点是编码字符。T1 和 T2 的结点数不同，A 错误。T1 的高度等于 T2 的高度，B 错误。出现频次不同的字符在 T1 中也可能处于相同的层，C 错误。对于定长编码码集，所有字符一定都在 T2 中处于相同的层，而且都是叶子结点。 2018_Q7_3

第 6 题 数据结构无向图

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

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

[tag_link]

正确答案：D

结论

选项 D 正确：若 (|V|>|E|+1)，则 (|E|<|V|-1)，图不可能连通。

推导

含 (|V|) 个顶点的连通无向图至少需要 (|V|-1) 条边，等号情形就是生成树。D 的条件等价于 (|E|<|V|-1)，违反连通图的必要条件，因此必不连通。

A、B 都不是充分条件：顶点数大于边数时可以有多个孤立顶点；边数大于顶点数时也可以是一个稠密连通分量加孤立顶点。C 也错误，因为 (|E|=|V|-1) 的树就是连通图。

易错点

要区分“连通的必要条件”和“充分条件”。(|E|\ge |V|-1) 只是连通所需的必要条件，不足以保证连通；只有 (|E|<|V|-1) 才能直接推出一定不连通。

2022_Q6_1

第 7 题 数据结构AOE 网

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

2022年408数据结构第7题AOE网络时间余量

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

[tag_link]

正确答案：B

对活动 i→j，时间余量为 vl(j)-ve(i)-w(i,j)，其中 ve、vl 分别是事件最早发生时间和事件最迟发生时间。由图正推、反推可得 ve=(0,2,5,8,9,12)、vl=(0,4,5,8,11,12)。四个候选活动的余量为：c: 5-2-1=2，g: 12-5-1=6，h: 11-8-1=2，j: 12-9-1=2。最大的是活动 g，选 B。

第 8 题 数据结构B树

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

A.60,90,280

B.60,90,350

C.60,85,110,350 D.60,90,110,350

[tag_link]

正确答案：D

参考 B 树插入操作 ，在 5 阶 B 树中，除根结点外的非叶子结点的关键字数 k 需要满足 2 ≤ k ≤ 4。当被删关键字 x 不在终端结点（最底层非叶子结点）时，可以用 x 的前驱（或后继) 关键字 y 来替代 x，然后在相应结点中删除 y。情况①：删除 260，将其前驱 110 放入 260 处，删除 110 后的结点 不满足 5 阶 B 树定义，从左兄弟中借 85，将 85 放入根中，将根中的 90 移入结点 变为 <90, 100>。情况②：删除 260，将其后继 280 放入 260 处，结点 不满足 5 阶 B 树定义且左右兄弟都不够借，结点 可以和左兄弟 <100, 110> 以及关键字 280 合并成一个新的结点 <100, 110, 280, 300>。情况③：在情况②中，结点 也可以和右兄弟 <400, 500> 以及关键字 350 合并成一个新的结点 <300, 350, 400, 500>。综上，T1 根结点中的关键字序列可能是 <60, 85, 110, 350> 或 <60, 90, 350> 或 <60, 90, 280>，仅 D 不可能。

第 9 题 数据结构散列表

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

I. 装填因子

II. 散列函数

II. 冲突解决策略

A. 仅 I 、Ⅱ B. 仅 I 、Ⅲ

C. 仅 I 、Ⅲ D.I 、Ⅱ 、Ⅲ

[tag_link]

正确答案：D

三者都会影响：装填因子越大，说明 哈希表 中存储的元素越满，发生冲突的可能性越大，平均查找长度也越大。散列函数、突解决策略会影响发生冲突的可能性。

第 10 题 数据结构归并排序

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

A. 将两个有序表合并为一个新的有序表

B. 将M 划分为两部分，两部分的元素个数大致相等

C. 将 M 划分为n 个部分，每个部分中仅含有一个元素

D. 将M 划分为两部分，一部分元素的值均小千另一部分元素的值

[tag_link]

正确答案：A

概念题，归并针对的对象是序列，二路归并就是将两个有序序列合并成一个。

第 11 题 数据结构排序算法

对数据进行排序时，若采用直接插入排序而不采用快速排序，则可能的原因是()。

I. 大部分元素已有序

II 待排序元素数量很少

Ⅲ.要求空间复杂度为 O(1)

IV. 要求排序算法是稳定的

A. 仅 I 、Ⅱ

B. 仅Ⅲ、IV

C. 仅 I 、Ⅱ 、IV D.I 、II 、ⅢI 、IV

[tag_link]

正确答案：D

直接插入排序 和 快速排序 的特点如下表所示：

排序算法适合初始序列情况适合元素数量空间复杂度稳定性
直接插入排序大部分元素有序较少O(1)稳定
快速排序基本无序较多O(log₂n)不稳定

I. 大部分元素已有序 ✅ 正确。

直接插入排序在序列 基本有序 的情况下表现非常好，接近 O(n) 的时间复杂度，而快速排序在此场景下仍需要递归处理。

因此此项成立。

II. 待排序元素数量很少 ✅ 正确。

当元素数量较少时，插入排序的常数因子小、实现简单， 实际运行效率往往优于快速排序 ，这是实际工程中的常见优化策略（如许多库排序在小规模时使用插入排序）。

III. 要求空间复杂度为 O(1) ✅ 正确。

插入排序是 原地排序 ，空间复杂度为 O(1)；

而快速排序虽然通常也是原地排序，但某些实现（尤其是递归调用）存在 O(log n) 的栈空间。

若对空间要求极严，插入排序更适合。

IV. 要求排序算法是稳定的 ✅ 正确。

插入排序是 稳定排序 ，而快速排序是 不稳定的 （原始版本）。

如果应用场景要求排序后相等元素的相对顺序不变，选择插入排序是合理的。

综上，所有说法都正确，正确答案选择 D。

组成原理 12 某计算机主频为 1GHz，程序 P 运行过程中，共执行了 10000 条指令，其中，80% 的指令执行平均需 1 个时钟周期，20% 的指令执行平均需 10 个时钟周期。

程序 P 的平均 CPI 和 CPU 执行时间分别是（ ）。

计算机性能指标 A. 2.8，28μs B. 28，28μs C. 2.8，28ms D. 28，28ms 查看答案与解析 收藏 正确答案： 参考 指令执行指标 ，CPI 指平均每条指令的执行需要多少个时钟周期。

由于 80% 的指令执行平均需要 1 个时钟周期，20% 的指令执行平均需要 10 个时钟周期，因此 CPI = 80% × 1 + 20% × 10 = 2.8 。

计算机主频为 1GHz，程序 P 共执行 10000 条指令，平均每条指令需要 2.8 个时钟周期，因此， CPU 执行时间= ( 10000 × 2.8 ) /1 0 9 = 2.8 × 1 0 − 5 s = 28 μ s 。

第 12 题 组成原理计算机性能指标

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

A.2.8,28 us B.28,28 us C.2.8,28ms

D.28,28ms

[tag_link]

正确答案：A

参考 指令执行指标 ，CPI 指平均每条指令的执行需要多少个时钟周期。由于 80% 的指令执行平均需要 1 个时钟周期，20% 的指令执行平均需要 10 个时钟周期，因此 CPI = 80% × 1 + 20% × 10 = 2.8 。计算机主频为 1GHz，程序 P 共执行 10000 条指令，平均每条指令需要 2.8 个时钟周期，因此， CPU 执行时间= ( 10000 × 2.8 ) /1 0 9 = 2.8 × 1 0 − 5 s = 28 μ s 。

第 13 题 组成原理补码

32位补码所能表示的整数范围是()。

A.-2³²~2³¹-1

B.-2³¹~2³¹-1

C.-2³²~2³²-1

D.-2³¹~2³²-1

[tag_link]

正确答案：B

32 位 补码 的最大值为 0x7fffffff = 2 31 − 1 （最高位为 0，其他位为 1），最小值为 0x80000000 = − 2 31 （最高位为 1，其他位为 0)。

第 14 题 组成原理IEEE浮点数表示

-0.4375的 IEEE754单精度浮点数表示为()。

A.BEE00000H

B.BF600000H

C.BF700000H

D.COE00000H

[tag_link]

正确答案：A

IEEE754 单精度浮点数格式 中依次为数符 1 位、阶码 8 位（偏置值 127)、尾数 23 位（隐藏 1 位）。− 0.4375 = − 1.75 × 2 − 2 ，保证小数点前是 1。根据单精度浮点数格式，数符 为 1；阶码为移码表示，-2+127=125，写成 8 位二进制数为 01111101；尾数隐藏小数点前 的 1，剩下的 0.75 写成二进制数为 0.11，所以尾数部分是 1100…0。该浮点数的二进制格式为 1011111011100000000000000000000，对应的十六进制格式为 BEE00000H。

第 15 题 组成原理页表

某计算机主存地址为24位，采用分页虚拟存储管理方式，虚拟地址空间大小为4GB, 页大小为4KB, 按字节编址。某进程的页表部分内容如下表所示。当CPU 访问虚拟地址00082840H, 虚-实地址转换的结 果 是 ( ) 。

2018_Q7_3

A. 得到主存地址024840H

B. 得到主存地址180840H

C. 得到主存地址018840H

D. 检测到缺页异常

[tag_link]

正确答案：C

本题考察 通过单级页表的地址翻译过程 。页大小为 4KB = 2 12 B，按字节编址，故页内地址为 12 位。虚拟地址空间大小为 4GB=23，故虚拟地址共 32 位，其中低 12 位为页内地址，高 20 位为虚页号。题中给出的 虚拟地址为 00082840H，虚页号为高 20 位即 00082H（页内地址为低 12 位即 840H），82H 对 应的十进制数为 130（注意题中页表的虚页号部分末尾未写 H，所以是十进制数，故查找时要 先将虚页号转换为十进制数），查页表命中，且存在位为 1，对应页框号为 018H。将查找到的 页框号 018H 和页内地址 840H 拼接，得到主存地址为 018840H。

第 16 题 组成原理cache映射方式

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

A.8,20

B.8,23

C.64,20

D.64,23

[tag_link]

正确答案：A

Cache 采用 组相联映射 ，主存地址结构应分为 Tag 标记、组号、块内地址三部分。主存块大小 = Cache 块大小 = 64B = 2 6 B，因此块内地址占 6 位。Cache 数据区容量为 32KB, 每个 Cache 块大小为 64B，则 Cache 总块数 = 32KB/64B = 2 9 ，由于采用 8 路组相联映射，即 每 8 个 Cache 块为一个分组，因此总共被分为 2 9 /8 = 2 6 组，因此，组号占 6 位。除了块内地 址和组号，剩余的位为 Tag 标记，占 32-6-6=20 位。地址结构如下所示。Tag 标记 组号 块内地址 20 位 6 位 6 位 Cache 采用 8 路组相联映射，因此在访问一个物理地址时，要先根据组号定位到某一分组，然 后用物理地址的高 20 位（Tag 标记）与分组中 8 个 Cache 行的 Tag 标记做并行比较（用 8 个 20 位“比较器”实现），若某个 Cache 行的 Tag 标记与物理地址的高 20 位完全一致，则选 中该 Cache 行。综上所述，在组相联映射的 Cache 中，“比较器”用于并行地比较分组中所 有 Cache 行的 Tag 标记位与欲访问物理地址的 Tag 标记位，因此比较器的个数就是分组中的 Cache 行数 8，比较器的位数就是 Tag 标记位数 20。

2018_Q7_3

第 17 题 组成原理存储器概念

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

A. 内存条的容量为512MB

B. 采用多模块交叉编址方式

C. 芯片的地址引脚为26位

D. 芯片内行缓冲有8192×8位

[tag_link]

正确答案：C

本题考察 主存容量的扩展 。8×8192×8192×8bit=512MB，内存条的容量为 512MB， A 正确 。存储器总线宽度 64=8×8bit，而每个芯片一次只能传输 8bit，需要 8 体多模块交叉编址才能实现， B 正确 。DRAM 芯片是矩阵样式的行列存储结果，行地址和列地址 复用一个地址 ，根据题意，DRAM 芯片的行数和列数都是 8192，所以引脚个数为 lo g 2 8192 = 13 ， C 错误 。芯片内行数是 8192，一行的大小是 8192×8bit，行缓冲长度就是一行的大小， D 正确 。

第 18 题 组成原理指令体系结构

下列选项中，属于指令集体系结构( ISA) 规定的内容是()。

I. 指令字格式和指令类型 Ⅱ.CPU 的时钟周期

Ⅲ.通用寄存器个数和位数

IV. 加法器的进位方式

A. 仅I 、Ⅱ

B. 仅I 、Ⅲ

C. 仅Ⅱ、IV

D. 仅I 、Ⅲ 、IV

[tag_link]

正确答案：B

指令集处于软硬件的交界面上。指令字和指令格式、通用寄存器个数和位数都与 机器指令有关，由 指令体系结构 规定。两个 CPU 可以有不同的时钟周期，但指令集可以相同，CPU 的 时钟周期不由 ISA 规定。加法器的进位方式涉及电路设计，也不由指令集规定。

第 19 题 组成原理指令种类

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

A.0

B.2

C.64 D.128

[tag_link]

正确答案：D

本题考察 N 地址指令 如下图所示：零地址指令的 OP 字段位数相比一地址和二地址指令更短，但是需要注意的是，零地址指令的 OP 字段前缀与一地址和二地址指令的 OP 字段不能相同。OP ADDR OP ADDR ADDR OP 16 位 10 位 4 位 6 位 6 位 6 位 零地址指令 一地址指令 二地址指令 所以零地址指令的条数为 2 16 − 254 × 2 6 − 12 × 2 12 = 128 。

2018_Q7_3

第 20 题 组成原理编译过程

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

A. 预处理→编译→汇编→链接

B. 预处理 → 汇编 → 编译 → 链接

C. 预处理→编译→链接→汇编

D. 预处理→汇编→链接→编译

[tag_link]

正确答案：A

将源程序转换为可执行目标文件的 过程 分为预处理、编译、汇编、链接四个阶段

第 21 题 组成原理中断IO

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

A. 适用于键盘、针式打印机等字符型设备

B. 外设和主机之间的数据传送通过软件完成

C. 外设准备数据的时间应小于中断处理时间

D. 外设为某进程准备数据时 CPU 可运行其他进程

[tag_link]

正确答案：C

中断 I/O 方式 适用于字符型设备，此类设备的特点是数据传输速率慢，以字符或 字为单位进行传输，A 正确。若采用中断 VO 方式，当外设准备好数据后，向 CPU 发出中断 请求，CPU 暂时中止现行程序，转去运行中断服务程序，由中断服务程序完成数据传送，B 正确。若外设准备数据的时间小于中断处理时间，则可能导致数据丢失，以输入设备为例， 设备为进程准备的数据会先写入设备控制器的缓冲区（缓冲区大小有限，通常只能暂存几个 字节），缓冲区每写满一次，就会向 CPU 发出一次中断请求，CPU 响应并处理中断的过程， 就是将缓冲区中的数据“取走”的过程，因此若外设准备数据的时间小于中断处理时间，则 可能导致外设往缓冲区写入数据的速度快于 CPU 从缓冲区取走数据的速度，从而导致缓冲区 的数据被覆盖，进而导致数据丢失。C 错误。若采用中断 I/O 方式，则外设为某进程准备数据 时，可令该进程阻塞，CPU 运行其他进程，D 正确。

第 22 题 组成原理多处理机

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

A. 多核处理器属于MIMD 结构

B. 向量处理器属于SIMD 结构

C. 硬件多线程技术只可用于多核处理器

D.SMP 中所有处理器共享单一物理地址空间

[tag_link]

正确答案：C

本题考察 多处理器 ， MIMD 结构分为多计算机系统和多处理器系统，A 正确。

向量处理器是 SIMD 的 变体，属于 SIMD 结构，B 正确。

硬件多线程技术是在一个核中处理多个线程，可用于单核 处理器，C 错误。

共享内存多处理器 (SMP) 具有共享的单一物理地址空间，所有核都可通 过存取指令来访问同一片主存地址空间，D 正确。

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

操作系统概念 A. 支持进程的并发执行 B. 不必支持虚拟存储管理 C. 需要实现对共享资源的管理 D. 进程数越多 CPU 利用率越高 查看答案与解析 收藏 正确答案： 操作系统的 基本特点 ：并发、共享、虚拟、异步，其中最基本、一定要实现的是并发和共享，A、C 正确。

早期的多道批处理操作系统会将所有进程的数据全部调入主存，再让多道程序并发执行，即使不支持虚拟存储管理，也能实现“多道程序并发”，B 正确。

进程多并不意味着 CPU 利用率高，进程数量越多，进程之间的资源竞争越激烈，甚至可能因为资源竞争而出现死锁现象，导致 CPU 利用率低，D 错误。

第 23 题 操作系统操作系统概念

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

A. 支持进程的并发执行

B. 不必支持虚拟存储管理

C. 需要实现对共享资源的管理

D. 进程数越多CPU 利用率越高

[tag_link]

正确答案：D

操作系统的 基本特点 ：并发、共享、虚拟、异步，其中最基本、一定要实现的是并发和共享，A、C 正确。早期的多道批处理操作系统会将所有进程的数据全部调入主存，再让多道程序并发执行，即使不支持虚拟存储管理，也能实现“多道程序并发”，B 正确。进程多并不意味着 CPU 利用率高，进程数量越多，进程之间的资源竞争越激烈，甚至可能因为资源竞争而出现死锁现象，导致 CPU 利用率低，D 错误。

第 24 题 操作系统中断IO

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

A. 中断向量表

B. 文件系统的根目录

C.硬盘分区表

D. 文件系统的索引节点表

[tag_link]

正确答案：A

解析： 中断向量表 ：在操作系统启动时，必须初始化中断向量表，用于存储中断服务例程的入口地址，以便处理硬件或软件中断。这是操作系统初始化过程中的关键步骤。文件系统的根目录：根目录通常在文件系统格式化时创建，而不是操作系统初始化过程中。硬盘分区表：分区表是在磁盘分区时创建的，通常在安装操作系统之前完成。文件系统的索引节点表：索引节点表（inode 表）是在文件系统创建时生成的，不是操作系统初始化的一部分。因此，正确答案是 A。

第 25 题 操作系统处理机调度算法

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

进程进入就绪队列的时刻优先级CPU 执行时间
P00ms15100ms
P110 ms2060ms
P210 ms1020ms
P315 ms610ms

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

A.4

B.5

C.6

D.7

[tag_link]

正确答案：C

本题考察 优先级调度 ： 0 时刻调度进程 P0 获得 CPU；1Oms 时 P2 进入就绪队列，调度 P2 抢占获得 CPU；15ms 时 P3 进入就绪队列，调度 P3 抢占获得 CPU；25ms 时 P3 执行完毕，调度 P2 获得 CPU；40ms 时 P2 执行完毕，调度 P0 获得 CPU；130ms 时 P2 执行完毕，调度 P1 获得 CPU；190ms 时 P2 执行完毕，结束；总共调度 6 次。

第 26 题 操作系统银行家算法

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

2018_Q7_3

A.1

B.2

C.3

D.4

[tag_link]

正确答案：B

初始时系统中的可用资源数为 <1,3,2> ，只能满足 P0 的需求 <0,2,1> ，所以 安全分配序列 第一个只能是 P0， 将资源分配给 P0 后，P0 执行完释放所占资源，可用资源数变为 <1,3,2> + <2,0,1> = <3,3,3> ， 此时可用资源数既能满足 P1，也能满足 P2，可以先分配给 P1，P1 执行完释放资源再分配给 P2， 也可以先分配给 P2，P2 执行完释放资源再分配给 P1。所以安全序列可以是 ①P0、P1、P2 或 ②P0、P2、P1。

第 27 题 操作系统用户态和内核态

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

A.CPU 处于用户态时只能执行特权指令

B.CPU 处于内核态时只能执行特权指令

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

[tag_link]

正确答案：C

CPU 在 用户态 时只能执行非特权指令，在 内核态 时可以执行特权指令和非特权指令。

第 28 题 操作系统进程状态

下列事件或操作中，可能导致进程P 由执行态变为阻塞态的是()。

I. 进程P 读文件

Ⅱ.进程P 的时间片用完

Ⅲ.进程P申请外设

IV. 进程P 执行信号量的wait( 操作

A. 仅I 、IV

B. 仅Ⅱ、Ⅲ

C. 仅Ⅲ、IV

D. 仅I 、Ⅲ 、IV

[tag_link]

正确答案：D

参考 状态转化 。进程 P 读文件时，进程从执行态进入阻塞态，等待磁盘 I/O 完成，I 正确。进程 P4 的时间片用完，导致进程从执行态进入就绪态，转入就绪队列等待下次被调度，Ⅱ错误。进 程 P 申请外设，若外设是独占设备且正在被其他进程使用，则进程 P 从执行态进入阻塞态， 等待系统分配外设，Ⅲ 正确。进程 P 执行信号量的 wait() 操作，如果信号量的值小于等于 0，则进程进入阻塞态，等待其他进程用 signal() 操作唤醒，V 正确。

第 29 题 操作系统缺页异常

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

A. 淘汰内存中的页

B. 建立页号与页框号的对应关系

C. 将页b 从外存读入内存

D. 修改页表中页b 对应的存在位

[tag_link]

正确答案：A

缺页异常 需要从磁盘调页到内存中，将新调入的页与页框建立对应关系，并修改 该页的存在位，B、C、D 正确：如果内存中有空闲页框，就不需要淘汰其他页，A 错误。

第 30 题 操作系统缓冲区

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

A. 页面置换算法

B. 工作集的大小

C. 进程的数量

D. 页缓冲队列的长度

[tag_link]

正确答案：D

页置换算法会影响缺页率，例如，LRU 算法的缺页率通常要比 FIFO 算法的缺页 率低，排除 A。工作集的大小决定了分配给进程的物理块数，分配给进程的物理块数越多， 缺页率就越低，排除 B。进程的数量越多，对内存资源的竞争越激烈，每个进程被分配的物 理块数越少，缺页率也就越高，排除 C。页缓冲队列是将被淘汰的页面缓存下来，暂时不写 回磁盘，队列长度会影响页面置换的速度，但不会影响缺页率，答案选 D。

第 31 题 操作系统系统调用

执行系统调用的过程涉及下列操作，其中由操作系统完成的是()。

I. 保存断点和程序状态字

Ⅱ.保存通用寄存器的内容

Ⅲ.执行系统调用服务程序

IV. 将CPU 模式改为内核态

A. 仅I 、Ⅲ B. 仅Ⅱ、Ⅲ C. 仅Ⅱ、 IV D. 仅Ⅱ、Ⅲ、 IV

[tag_link]

正确答案：B

对四个选项进行逐一分析： Ⅰ. 保存断点和程序状态字 ❌ 参考 中断处理过程 ，保存断点由中断隐指令完成，即由硬件完成。Ⅱ. 保存通用寄存器的内容 ✅ 为了防止系统调用覆盖用户程序中的数据，操作系统在进入系统调用处理程序时会保存用户程序的寄存器内容（这属于上下文切换的一部分）。Ⅲ. 执行系统调用服务程序 ✅ 系统调用就是要求操作系统执行某项服务，服务程序是操作系统的一部分，由操作系统调度执行。Ⅳ. 将 CPU 模式改为内核态 ❌ 这一点不是由操作系统主动完成，而是由硬件自动完成的： 当执行陷阱指令（如 int 0x80 ）或发生中断时，CPU 自动将模式从用户态切换为内核态，然后跳转到操作系统提供的中断向量地址。所以，这属于硬件响应的一部分，不是由操作系统“显式”控制的。所以正确答案选择 B。

第 32 题 操作系统IO软件层次

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

A. 驱动程序与/O 控制方式无关

B. 初始化设备是由驱动程序控制完成的

C. 进程在执行驱动程序时可能进入阻塞态

D. 读/写设备的操作是由驱动程序控制完成的

[tag_link]

正确答案：A

厂家在设计一个设备时，通常会为该设备编写 设备驱动程序 ，主机需要先安装驱动程序，才能使用设备。

当一个设备被连接到主机时，驱动程序负责初始化设备（如将设备控制器中的寄存器初始化），B 正确。

当进程在执行驱动程序时，可能会因为设备忙碌而进入阻塞态，C 正确。

设备的读/写操作本质就是在设备控制器和主机之间传送数据，而只有厂家知道 设备控制器的内部实现，因此也只有厂家提供的驱动程序能控制设备的读/写操作，D 正确。

厂家会根据设备特性，在驱动程序中实现一种合适的 I/O 控制方式，A 错误。

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

OSI模型 A. 物理层 B. 数据链路层 C. 网络层 D. 传输层 查看答案与解析 收藏 正确答案： 在 ISO/OSI 模型 中，数据链路层、网络层、传输层都具有流量控制功能，数据链路层是相邻结点之间的流量控制，网络层是整个网络中的流量控制，传输层是端到端的流量控制。

第 33 题 计算机网络OSI模型

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

A. 物理层 B. 数据链路层

C. 网络层 D. 传输层

[tag_link]

正确答案：B

在 ISO/OSI 模型 中，数据链路层、网络层、传输层都具有流量控制功能，数据链路层是相邻结点之间的流量控制，网络层是整个网络中的流量控制，传输层是端到端的流量控制。

第 34 题 计算机网络奈奎斯特定理

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

A.200 kbps

B.400 kbps

C.800kbps

D.1600 kbps

[tag_link]

正确答案：C

根据 奈奎斯特定理 ，最大数据传输速率= 2 W l o g 2 V ，4 个幅值的 ASK 调制说明有 4 个相位，将 V=4 代入，得 800kbps。

第 35 题 计算机网络网络号和主机号

若某主机的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

[tag_link]

正确答案：B

主机所在网络的网络地址可以通过主机的 IP 地址和 子网掩码 逐位相与得到。子网掩码 255.255.192.0 的二进制前 18 位为 1、后 14 位为 0，把主机 P 地址的后 14 位变为 0，得 到的结果为 183.80.64.0，即为主机所在网络的网络地址。

第 36 题 计算机网络网络层

下图所示网络中的主机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

[tag_link]

正确答案：D

默认网关 可以理解为离当前主机最近的路由器的端口地址，所以是 192.168.1.62， 而该主机的子网掩码和网关的子网掩码也相同，/27 即为 255.255.255.224。

第 37 题 计算机网络软件定义网络

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

A. 东向接口 B. 南向接口

C. 西向接口 D. 北向接口

[tag_link]

正确答案：B

SDN 对上层开发者提供的编程接口称为北向接口，而南向接口则负责控制平面和 数据平面间的通信，所以 SDN 控制器向数据平面的 SDN 交换机下发流表时使用南向接口。

第 38 题 计算机网络TCP拥塞控制

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

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

[tag_link]

正确答案：C

时刻 0 发生了超时，门限值 ssthresh 变为拥塞窗口 cwnd 的一半即 8，同时 cwnd 置为 1，执行 慢开始 算法，cwnd 指数增长，经过 3 个 RTT，增长到 ssthresh 值：之后执行 拥塞避免 算法，cwmd 线性增长，再经过 8 个 RTT，增长到 16，共花费 11 个 RTT，如下表所示。

时刻01234567891011
拥塞窗口1248910111213141516
第 39 题 计算机网络TCP四次挥手

假设客户C 和服务器S已建立一个TCP 连接，通信往返时间RTT=50 ms, 最长报文段寿命MSL=

800ms, 数据传输结束后，C 主动请求断开连接。 若从C 主动向S发出FIN段时刻算起，则C 和S 进入 CLOSED 状态所需的时间至少分别是()。

A.850ms,50ms

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

D.1650ms,75 ms

[tag_link]

正确答案：D

TCP 连接的释放过程见 四次挥手 。题目问的是最少时间，所以当服务器 S 收到客户 C 发送的 FIN 请求后不再发送数据，而是立马发送 FN 请求（即第②步和第③步同时发生，忽略 FIN-WAIT2 和 CLOSE-WAIT 状态。C 收到 S 发来的 FIN 报文段后，进入 CLOSED 状态还需等到 TIME-WAIT 结束，总用时至少为 1RTT + 2MSL = 50 + 800×2 = 1650ms。S 进入 CLOSED 状态需要经过 3 次报文段的传输时间，即 1.5RTT=75ms。

第 40 题 计算机网络HTTP

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

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

[tag_link]

正确答案：B

HTTP/1.1 默认使用流水线的 长连接 ，所有请求都是连续发送的。

题目要求最少 时间，最理想的流程是 TCP 在第三次握手的报文段中捎带 HTTP 请求，以及 TCP 连接后慢开 始阶段不考虑拥塞情况。

假设接收方有足够大的缓存空间，即发送窗口等同于拥塞窗口，总 共需要经过：第 1 个 RTT，进行 TCP 连接，此时服务器 S 的发送窗口= 1MSS，并在第三次 握手时捎带 HTTP 请求；

第 2 个 RTT，服务器 S 发送大小为 1MSS 的 html 文件，主机 C 确认 后服务器 S 的发送窗口变为 2MSS；

第 3 个 RTT，服务器 S 发送大小为 2MSS 的图像文件， 主机 C 确认后服务器 S 的发送窗口变为 4MSS；

第 4 个 RTT，服务器 S 发送剩下的 1MSS 图 像文件，完成传输，总共需要 4 个 RTT，即 40ms。

解答题 数据结构 41 已知非空二叉树 T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下： typedef struct { // MAX_SIZE 为已定义常量 Elemtype SqBiTNode [ MAX_SIZE ]; // 保存二叉树结点值的数组 int ElemNum ; // 实际占用的数组元素个数 } SqBiTree ; T 中不存在的结点在数组 SqBiTNode 中用 -1 表示。

例如，对于下图所示的两棵非空二叉树 T1 和 T2： 40 25 80 30 27 40 50 60 35 30 60 二叉树 T1 二叉树 T2 T1 的存储结果如下： 40 25 60 -1 30 -1 80 -1 -1 27 T1.SqlBiTNode T1.ElemNum = 10 T2 的存储结果如下： 40 50 60 -1 30 -1 -1 -1 -1 -1 T2.SqlBiTNode T2.ElemNum = 11 35 请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回 true，否则，返回 false，要求： (1) 给出算法的基本设计思想。

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

二叉排序树 查看答案与解析 收藏 1）算法的基本设计思想 对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0] 中：当某结点保存在 SqBiTNode[i] 中时，若有左孩子，则其值保存在 SqBiTNode[2i+1] 中；

若有右孩子，则其值保存在 SqBiTNode[2i+2] 中；

若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2] 中。

二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子树中的全部结点值。

中序遍历二叉搜索树得到一个升序序列。

使用整型变量 val 记录中序遍历过程中已遍历结点的最大值，初值为一个负整数，对二叉树进行 中序遍历 。

若当前遍历的结点值小于等于 val ，则算法返回 false，否则，将 val 的值更新为当前结点的值。

2）算法实现 // val 存储中序遍历中访问到的最大值 // 返回值：当前子树是否为 BST bool solve ( SqBiTree * tree , int k , int * val ) { if ( k >= tree -> ElemNum ) { // 空结点 return true ; } // 判断左子树是否为 BST bool ret = solve ( tree , 2 * k + 1 , val ); if ( ! ret ) { return false ; } int cur_val = tree -> SqbiTNode [ k ]; if ( cur_val == - 1 ) { // 空结点 return true ; } // 判断中序序列是否递增 if ( cur_val > * val ) { * val = cur_val ; } else { return false ; } // 判断右子树是否为 BST ret = solve ( tree , 2 * k + 2 , val ); if ( ! ret ) { return false ; } return true ; }

第 41 题 数据结构二叉树遍历

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

typedef struct {

Elemtype SqBiTNode[MAX_SIZE]; int ElemNum;

}SqBiTree;

//MAX_SIZE为已定义常量

// 保存二叉树结点值的数组 // 实际占用的数组元素个数

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

T1的存储结果如下：

2018_Q7_3

T2的存储结果如下：

2018_Q7_3

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

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

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

[tag_link]

[tag_link]

1）算法的基本设计思想 对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0] 中：当某结点保存在 SqBiTNode[i] 中时，若有左孩子，则其值保存在 SqBiTNode[2i+1] 中；若有右孩子，则其值保存在 SqBiTNode[2i+2] 中；若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2] 中。 二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子树中的全部结点值。中序遍历二叉搜索树得到一个升序序列。 使用整型变量 val 记录中序遍历过程中已遍历结点的最大值，初值为一个负整数，对二叉树进行 中序遍历 。若当前遍历的结点值小于等于 val ，则算法返回 false，否则，将 val 的值更新为当前结点的值。 2）算法实现 // val 存储中序遍历中访问到的最大值 // 返回值：当前子树是否为 BST bool solve ( SqBiTree * tree , int k , int * val ) { if ( k >= tree -> ElemNum ) { // 空结点 return true ; } // 判断左子树是否为 BST bool ret = solve ( tree , 2 * k + 1 , val ); if ( ! ret ) { return false ; } int cur_val = tree -> SqbiTNode [ k ]; if ( cur_val == - 1 ) { // 空结点 return true ; } // 判断中序序列是否递增 if ( cur_val > * val ) { * val = cur_val ; } else { return false ; } // 判断右子树是否为 BST ret = solve ( tree , 2 * k + 2 , val ); if ( ! ret ) { return false ; } return true ; }

第 42 题 数据结构堆的概念

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

(1) 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简单描述其算法思想，不 需要程序实现。

(2)说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

[tag_link]

[tag_link]

【答案 1】 定义含 10 个元素的数组 A，初始时元素值均为该数组类型能表示的最大数 MAX。 for M 中的每个元素 s if (s < A[9]) 丢弃 A[9]并将 s 按升序插入到 A 中； 当数据全部扫描完毕，数组 A[0]~A[9]保存的即是最小的 10 个数。 【答案 2】 定义含 10 个元素的大根堆 H，元素值均为该堆元素类型能表示的最大数 MAX。 for M 中的每个元素 s if （s < H 的堆顶元素） 删除堆顶元素并将 s 插入到 H 中； 当数据全部扫描完毕，堆 H 中保存的即是最小的 10 个数。 组成原理 43 某 CPU 中部分数据通路如图所示，其中，GPRs 为通用寄存器组；FR 为标志寄存器，用于存放 ALU 产生的标志信息；带箭头虚线表示控制信号，如控制信号 ReaD. Write 分别表示主存读、主存写，MDRin 表示内部总线上数据写入 MDR，MDRout 表示 MDR 的内容送内部总线。 MAR

第 43 题 组成原理cache概念

(15分)某CPU 中部分数据通路如图所示，其中，GPRs 为通用寄存器组；FR 为标志寄存器，用于 存放ALU产生的标志信息；带箭头虚线表示控制信号，如控制信号ReaD.Wr|te 分别表示主存读、主存 写 ，MDR|n 表示内部总线上数据写入MDR,MDRout 表示MDR的内容送内部总线。

(2)为什么要设置暂存器Y和Z?

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

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

(1)每个扇区包含数据及地址信息，地址信息分为3个字段，这3个字段的名称格式什么?对于该磁盘， 各字段至少占多少位?

(2)一个扇区的平均访问时间约为多少?

(3)若采用周期挪用DMA 方式进行磁盘与主机之间的数据传送，磁盘控制器中的数据缓冲区大小为64位， 则在一个扇区读写过程中，DMA 控制器向CPU 发送了多少次总线请求?若CPU 检测到DMA 控制器的 总线请求信号时也需要访问主存，则DMA 控制器是否可以获得总线使用权?为什么?

[tag_link]

[tag_link]

1）符号标志 SF 表示运算结果的正负性，因此 SF = F 15 对于加法运算 A + B → F ，若 A 、 B 为负，且 F 为正，则说明发生溢出：或者，若 A 、 B 为正， 且 F 为负，也说明发生溢出。因此，加运算时，溢出标志 OF = A 15 ⋅ B 15 ⋅ F 15 + A 15 ⋅ B 15 ⋅ F 15 。 对于减法运算 A − B → F ，若 A 为负、 B 为正，且 F 为正，则说明发生溢出：或者，若 A 为正、 B 为负，且 F 为负，也说明发生溢出。因此，减运算时，溢出标志 OF = A 15 ⋅ B 15 ⋅ F 15 + A 15 ⋅ B 15 ⋅ F 15 。 2）因为在单总线结构中，每一时刻总线上只有一个数据有效，而 ALU 有两个输入端和一个 输出端。因此，当 ALU 运算时，需要先用暂存器 Y 缓存其中一个输入端的数据，再通过 总线传送另一个输入端的数据。与此同时，ALU 的输出端产生运算结果，但由于总线正 被占用，因此需要暂存器 Z，以缓存 ALU 的输出端数据。 3）由图可知，rs 和 rd 都是 4bit，因此 GPRs 中最多有 2 4 = 16 个通用寄存器；rs 和 rd 来自指令寄 存器 IR；rd 表示寄存器编号，应连接地址译码器。 4）取指阶段需要根据程序计数器 PC 取出主存中的指令，并将指令写入指令寄存器 R 中。控制 信号序列如下： ①PCout,MARin // 将指令的地址写入 MAR ②Read // 读主存，并将读出的数据写入 MDR ③MDRout,Rin // 将 MDR 的内容写入指令寄存器 R 步骤①需要 1 个时钟周期，步骤②需要 5 个时钟周期，步骤③需要 1 个时钟周期，因此取指 令阶段至少需要 7 个时钟周期。 5）图中控制信号由控制部件（CU）产生。指令寄存器 IR 和标志寄存器 FR 的输出信号会连 到控制部件的输入端。 44 假设某磁盘驱动器中有 4 个双面盘片，每个盘面有 20000 个磁道，每个磁道有 500 个扇区，每个扇区可记录 512 字节的数据，盘片转速为 7200rpm（转/分），平均寻道时间为 5ms，请回答下列问题。

(1) 每个扇区包含数据及地址信息，地址信息分为 3 个字段，这 3 个字段的名称格式什么？对于该磁盘，各字段至少占多少位？

(2) 一个扇区的平均访问时间约为多少？

(3) 若采用周期挪用 DMA 方式进行磁盘与主机之间的数据传送，磁盘控制器中的数据缓冲区大小为 64 位，则在一个扇区读写过程中，DMA 控制器向 CPU 发送了多少次总线请求？若 CPU 检测到 DMA 控制器的总线请求信号时也需要访问主存，则 DMA 控制器是否可以获得总线使用权？为什么？ CHS地址 DMA 查看答案与解析 收藏

第 44 题 组成原理CHS地址

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

(1)每个扇区包含数据及地址信息，地址信息分为3个字段，这3个字段的名称格式什么?对于该磁盘， 各字段至少占多少位?

(2)一个扇区的平均访问时间约为多少?

(3)若采用周期挪用DMA 方式进行磁盘与主机之间的数据传送，磁盘控制器中的数据缓冲区大小为64位， 则在一个扇区读写过程中，DMA 控制器向CPU 发送了多少次总线请求?若CPU 检测到DMA 控制器的 总线请求信号时也需要访问主存，则DMA 控制器是否可以获得总线使用权?为什么?

[tag_link]

[tag_link]

1）符号标志 SF 表示运算结果的正负性，因此 SF = F 15 对于加法运算 A + B → F ，若 A 、 B 为负，且 F 为正，则说明发生溢出：或者，若 A 、 B 为正， 且 F 为负，也说明发生溢出。因此，加运算时，溢出标志 OF = A 15 ⋅ B 15 ⋅ F 15 + A 15 ⋅ B 15 ⋅ F 15 。 对于减法运算 A − B → F ，若 A 为负、 B 为正，且 F 为正，则说明发生溢出：或者，若 A 为正、 B 为负，且 F 为负，也说明发生溢出。因此，减运算时，溢出标志 OF = A 15 ⋅ B 15 ⋅ F 15 + A 15 ⋅ B 15 ⋅ F 15 。 2）因为在单总线结构中，每一时刻总线上只有一个数据有效，而 ALU 有两个输入端和一个 输出端。因此，当 ALU 运算时，需要先用暂存器 Y 缓存其中一个输入端的数据，再通过 总线传送另一个输入端的数据。与此同时，ALU 的输出端产生运算结果，但由于总线正 被占用，因此需要暂存器 Z，以缓存 ALU 的输出端数据。 3）由图可知，rs 和 rd 都是 4bit，因此 GPRs 中最多有 2 4 = 16 个通用寄存器；rs 和 rd 来自指令寄 存器 IR；rd 表示寄存器编号，应连接地址译码器。 4）取指阶段需要根据程序计数器 PC 取出主存中的指令，并将指令写入指令寄存器 R 中。控制 信号序列如下： ①PCout,MARin // 将指令的地址写入 MAR ②Read // 读主存，并将读出的数据写入 MDR ③MDRout,Rin // 将 MDR 的内容写入指令寄存器 R 步骤①需要 1 个时钟周期，步骤②需要 5 个时钟周期，步骤③需要 1 个时钟周期，因此取指 令阶段至少需要 7 个时钟周期。 5）图中控制信号由控制部件（CU）产生。指令寄存器 IR 和标志寄存器 FR 的输出信号会连 到控制部件的输入端。 44 假设某磁盘驱动器中有 4 个双面盘片，每个盘面有 20000 个磁道，每个磁道有 500 个扇区，每个扇区可记录 512 字节的数据，盘片转速为 7200rpm（转/分），平均寻道时间为 5ms，请回答下列问题。

(1) 每个扇区包含数据及地址信息，地址信息分为 3 个字段，这 3 个字段的名称格式什么？对于该磁盘，各字段至少占多少位？

(2) 一个扇区的平均访问时间约为多少？

(3) 若采用周期挪用 DMA 方式进行磁盘与主机之间的数据传送，磁盘控制器中的数据缓冲区大小为 64 位，则在一个扇区读写过程中，DMA 控制器向 CPU 发送了多少次总线请求？若 CPU 检测到 DMA 控制器的总线请求信号时也需要访问主存，则 DMA 控制器是否可以获得总线使用权？为什么？ CHS地址 DMA 查看答案与解析 收藏

第 45 题 操作系统inode

(7分)某文件系统的磁盘块大小为4KB, 目录项由文件名和索引节点号构成，每个索引节点占256 字节，其中包含直接地址项10个，一级、二级和三级间接地址项各1个，每个地址项占4字节。该文件 系统中子目录stu 的结构如题45(a)图所示，stu 包含子目录course 和文件doc,course 子目录包含文件 course1和 course2。各文件的文件名、索引节点号、占用磁盘块的块号如题45(b)图所示。

45- (a) 图 请回答下列问题。

[tag_link]

[tag_link]

1）在该文件系统中，目录项由文件名和索引结点号构成。由图 a 可知，stu 目录下有两个文 件，分别是 course 和 doc。由图 b 可知，这两个文件分别对应索引结点号 2 和 10。因此， 目录文件 stu 中两个目录项的内容是 2）由图 b 可知，文件 doc 和文件 course1 对应的索引结点号都是 10。说明 doc 和 course1 两 个目录项共享同一个索引结点，本质上对应同一个文件。而文件 course1 存储在 30 号磁盘 块，因此文件 doc 占用的磁盘块的块号 x 为 30。 3）需要读 2 个磁盘块。先读 course1 的索引结点所在的磁盘块，再读 course1 的内容所在的 磁盘块。目录文件 course 的内容已在内存中，即 coursel、course2 对应的目录项己在内存 中，根据 coursel 对应的目录项可以知道其索引结点号，即可读入 course1 的索引结点所 在的磁盘块：根据 course1 的索引结点可知该文件存储在 30 号磁盘块，因此可再读入 coursel 的内容所在的磁盘块。 4）存取 course2 需要使用索引结点的一级和二级间接地址项。6MB 大小的文件需要占用 6MB/4KB=1536 个磁盘块。直接地址项可以记录 10 个磁盘块号，一级间接地址块可以记 录 4KB/4B=1024 个磁盘块号，二级间接地址块可以记录 1024×1024 个磁盘块号，而 10 + 1024 < 1536 < 10 + 1024 + 1024 × 1024 。因此，6MB 大小的文件，需要使用一级间接地址 项和二级间接地址项（拓展：若文件的总大小超出 10 + 1024 + 1024 × 1024 块，则还需使 用三级间接地址项）。 46 某进程的两个线程 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 之间的同步关系，并说明所用信号量的作用及其初值。 A

第 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 完成后执行。请使用信号量的walt() 、slgnal( 操作描述T1 和T2 之间的同 步关系，并说明所用信号量的作用及其初值。

2018_Q7_3

[tag_link]

[tag_link]

进程 T1 要依次执行 A、E、F。进程 T2 要执行 B、C、D。由图可知，T2 执行 C 必须在 T1 执行完 A 之后；T1 执行 E 必须在 T2 执行完 C 之后。因此，有两对同步关系。信号量的定义 和同步关系的描述如下：

semaphore AC = 0 ; 
semaphore CE = 0 ; 
T1 () { 
    A ; 
    signal ( AC ); 
    wait ( CE ); 
    E ; 
    F ; 
} 
T2 () { 
    B ; 
    wait ( AC ); 
    C ; 
    signal ( CE ); 
    D ; 
}
第 47 题 计算机网络数据链路层

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

192.168.0.1/25

请回答下列问题。

[tag_link]

[tag_link]

1）设备 1 选择 100 BaseT 以太网交换机，设备 2 选择 100 BaseT 集线器。因为物理层设备既不 能隔离冲突域也不能隔离广播域，链路层设备可以隔离冲突域但不能隔离广播域。 2）假设 H2 与 H3 之间的最远距离是 D，根据 CSMA/CD 协议的 限制条件 ： 最短帧长 = 总线传播时延 × 数据传输速率 × 2 本题中由于使用 100 BaseT 局域网标准，所以数据传输速率为 100Mbps，总线传播时延由 两部分组成，一部分是信号传播时延，另一部分是信号通过设备 2 时产生的额外 1.51μs 时间延迟。代入公式为 64 B = (1.51 us + D / (2 × 10⁸ m/s)) × 100 Mbps × 2，注意单位换算，最终解得 D = 210m。 3）M 是 DHCP 发现报文（ Discover 报文）。路由器 E0 接口能收到封装 M 的以太网帧，由于 H4 发送的 DHCP 发现报文是广播的形式，所以同一个广播域内的所有设备和接口都可 以收到该以太网帧。由于是广播帧，所以目的 MAC 地址是全 1，S 向 DHCP 服务器转发 的封装 M 的以太网帧的目的 MAC 地址是 FF-FF-FF-FF-FF-FF。 4）在 H5 收到的帧中，地址 1、地址 2 和地址 3 分别是 00-11-11-11-11-E1、00-11-11-11-11-C1 和 0011-11-11-11-D1。该帧来自 AP，地址 1 代表接收端的地址，地址 2 代表 AP 的地址， 地址 3 是发送端的地址。

← 返回真题列表