模拟卷7

设 $n$ 是描述问题规模的正整数，下列程序片段的时间复杂度是（ ）。

A. $O(\log n)$ B. $O(n)$ C. $O(\sqrt{n})$ D. $O(n^2)$

复杂度分析

[tag_link]

正确答案：A

程序首先将变量 $i$ 初始化为 $n$ 的平方，即 $i=n^2$ 。

然后进入 while 循环，循环条件为 $i\ne 1$ ，每次迭代将 $i$ 除以 $2$ 。 循环的迭代次数取决于 $i$ 从 $n^2$ 减少到 $1$ 所需除以 $2$ 的次数。

设迭代次数为

$k$ ，经过 $k$ 次迭代后， $i$ 的值变为 $n^2/2^k$ 。

当循环终止时， $i=1$ ，因此有 $n^2/2^k=1$ ，即 $n^2=2^k$ 。 取对数可得 $k={\log }_2(n^2)=2{\log }_{2}n$ 。

在时间复杂度分析中，常数因子可以忽略，因此迭代次数

$k$ 的数量级为 $O(\log n)$ 。

所以，该程序片段的时间复杂度是 $O(\log n)$ 。 对比选项，A 正确。

若已知一个栈的入栈序列是 1,2,3,4。其出栈序列为 p1,p2,p3,p4，则 p2,p4 不可能是（ ）。

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

入栈出栈序列 栈

[tag_link]

正确答案：C

栈的入栈序列为 1,2,3,4，出栈序列需符合栈的后进先出规则。 通过分析所有可能的出栈序列（共 14 种），并检查各选项中 p2（第二个出栈元素）和 p4（第四个出栈元素）的组合是否存在合法的序列对应。

• 选项 A（2、4）：存在合法序列如 1,2,3,4，其中 p2=2、p4=4，故可能。
• 选项 B（2、1）：存在合法序列如 3,2,4,1，其中 p2=2、p4=1，故可能。
• 选项 C（4、3）：不存在任何合法出栈序列同时满足 p2=4 且 p4=3。 例如，序列 1,4,2,3 看似满足，但实际上不合法，因为在出栈 4 后，栈中剩余 2 和 3 且 3 在栈顶，必须优先出栈 3，无法直接出栈 2，因此无法实现 p4=3。
• 选项 D（3、4）：存在合法序列如 1,3,2,4，其中 p2=3、p4=4，故可能。

综上，p2、p4 不可能是 4、3，对应选项 C。

执行完下列语句段后，i 值为（ ）。

A. 2 B. 4 C. 8 D. 无限递归

栈

[tag_link]

正确答案：B

首先，函数 f 是递归函数，其定义为：当参数 x 大于 0 时，返回 x 乘以 f(x-1)； 当 x 不大于 0（即 x ≤ 0）时，返回 2。 语句 `i = f(f(1));` 的执行过程分为两步：先计算内层 `f(1)`，再将结果作为参数计算外层 f。

计算 `f(1)`：由于 1 > 0，返回 `1 * f(0)`。 计算 `f(0)`：0 不大于 0，因此返回 2。 所以 `f(1) = 1 * 2 = 2`。

然后计算外层 `f(f(1))` 即 `f(2)`。 对于 `f(2)`：2 > 0，返回 `2 * f(1)`。 而 `f(1)` 已计算为 2，因此 `f(2) = 2 * 2 = 4`。 最终 i 的值为 4。

递归过程有限，因为对于正整数参数，递归总是递减到 0 后终止，不会无限递归。 因此正确答案为 B。

含有 4 个元素值均不相同的结点的二叉排序树有（ ）种。

A. 4 B. 6 C. 10 D. 14

二叉排序树 卡特兰数

[tag_link]

正确答案：D

二叉排序树（BST）的结构数量由卡特兰数决定。 对于 n 个值均不相同的节点，不同形态的二叉排序树数量等于第 n 个卡特兰数

$C_n$ ，计算公式为

$$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right),$$

其中 $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ 表示组合数。

当

$n=4$ 时，计算 $C_4$ ：

$$C_4=\frac{1}{5}\left(\genfrac{}{}{0ex}{}{8}{4}\right)=\frac{1}{5}\times 70=14.$$

因此，含有 4 个元素值均不相同的结点的二叉排序树共有 14 种。

由元素序列（27,16,75,38,51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为 2 的结点）是（ ）。

A. 27 B. 38 C. 51 D. 75

平衡二叉树

[tag_link]

正确答案：D

按序列（27,16,75,38,51）依次插入构造平衡二叉树：

• 插入 27 和 16 后，树平衡。 >
• 插入 75 后，树仍平衡。 >
• 插入 38 后，各节点平衡因子绝对值均不超过 1，树平衡。 >
• 插入 51 后，节点 38 的平衡因子变为 -1（平衡），但节点 75 的左子树高度为 1、右子树高度为 -1（空），平衡因子计算为 1 - (-1) = 2，绝对值首次达到 2，成为不平衡节点。 > 继续向上检查，节点 27 的平衡因子也变为 -2，但节点 75 是离插入点 51 最近的不平衡节点，因此最小不平衡子树的根是 75。 >

在下列二叉树中，（ ）的所有非叶结点的度均为 2。 Ⅰ. 完全二叉树 Ⅱ. 满二叉树 Ⅲ. 平衡二叉树 Ⅳ. 哈夫曼树 Ⅴ. 二叉排序树

A. Ⅱ和Ⅳ B. Ⅰ和Ⅲ C. Ⅱ、Ⅳ和Ⅴ D. Ⅱ、Ⅲ和Ⅳ

树的概念 哈夫曼树

[tag_link]

正确答案：A

首先，理解题意：所有非叶结点的度均为 2，意味着二叉树中每个内部节点都必须有两个子节点。

接下来逐一分析所列二叉树类型：

完全二叉树的定义是除最后一层外，其他层节点数达到最大值，且最后一层节点尽量靠左排列。 > 在这种情况下，非叶结点可能只有一个子节点（例如，当树节点数较少时），因此度可能为 1 或 2，不满足所有非叶结点度均为 2 的条件。 >

满二叉树则严格要求每个节点要么是叶子节点（度为 0），要么有两个子节点（度为 2）。 > 因此，满二叉树的所有非叶结点度均为 2，符合条件。 >

平衡二叉树（如 AVL 树）主要关注左右子树高度平衡，不限制节点的度数。 > 在平衡二叉树中，非叶结点可能只有左子节点或右子节点，即度可以为 1，所以不满足要求。 >

哈夫曼树在构建过程中，每次合并两个节点形成新的内部节点，因此每个内部节点都有两个子节点。 > 哈夫曼树的所有非叶结点度均为 2，符合条件。 >

二叉排序树中，节点度数取决于插入顺序和树的结构，非叶结点常常可能只有一个子节点（例如，在偏斜树中），因此度可能为 1 或 2，不满足所有非叶结点度均为 2 的条件。 >

综上，只有满二叉树和哈夫曼树满足所有非叶结点的度均为 2，对应选项中的Ⅱ和Ⅳ，故正确答案为 A。 >

一个含有 $n$ 个顶点和 $e$ 条边的简单无向图，其邻接矩阵存储中零元素的个数是（ ）。

A. $e$ B. $2e$ C. $n^2-e$ D. $n^2-2e$

邻接矩阵

[tag_link]

正确答案：D

邻接矩阵是一个 $n\times n$ 的矩阵，总共有 $n^2$ 个元素。 在简单无向图中，没有自环，因此对角线上的 $n$ 个元素均为零。 图的每条边对应两个对称的非对角线元素（例如，边 $(i,j)$ 对应 $A[i][j]$ 和 $A[j][i]$ ），所以非零元素的个数为 $2e$ 。 零元素的个数等于总元素数减去非零元素数，即 $n^2-2e$ 。

下列关于 AOE 网的叙述中，正确的是（ ）。

A. 关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短 B. 关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少 C. 关键路径上任一关键活动改变后，都必然会影响关键路径的改变 D. 若所有的关键路径一同延长或缩短，则不会引起关键路径的改变

关键路径

[tag_link]

正确答案：B

AOE 网中关键路径是从源点到汇点的最长路径，决定了整个工程的最短完成时间。 选项 A 错误，因为缩短关键路径上某个活动的时间后，如果该活动不再是关键路径的一部分（例如其他路径成为新的关键路径），整个工程时间可能不变甚至增加。 选项 B 错误，因为延长关键路径上活动的时间可能使关键路径发生改变，从而工程延长时间不一定等于活动延长时间。 选项 C 错误，因为改变关键路径上的活动（如时间调整）不一定导致关键路径改变，例如缩短活动后原路径仍为最长时，关键路径不变。 选项 D 正确，当所有关键路径同时延长或缩短相同量时，这些路径的相对长度保持不变，没有其他路径成为更长路径，因此关键路径集合不会改变。

下列关于散列表的说法中，不正确的是（ ）个。 Ⅰ. 散列表的平均查找长度与处理冲突方法无关 Ⅱ. 在散列表中，“比较”操作一般也是不可避免的 Ⅲ. 散列表在查找成功时的平均查找长度与表长有关 Ⅳ. 若在散列表中删除一个元素，只需简单地将该元素删除即可

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

散列表

[tag_link]

正确答案：C

Ⅰ错误。

散列表的平均查找长度（ASL）与处理冲突的方法密切相关。 例如，线性探测、二次探测和链地址法等不同方法会导致不同的查找性能，ASL 计算公式也各不相同，因此该说法不正确。

Ⅱ正确。 在散列表查找过程中，即使哈希函数直接映射到槽位，通常也需要比较关键字以确认是否找到目标元素，因为哈希冲突可能发生或需要验证匹配，因此“比较”操作一般是不可避免的。

Ⅲ错误。 散列表在查找成功时的平均查找长度主要取决于负载因子（元素个数与表长的比值），而不是表长本身。 例如，链地址法中成功查找的 ASL 约为 1 + α/2（α为负载因子），当负载因子固定时，ASL 与表长无关，因此该说法不正确。

Ⅳ错误。 在散列表中删除元素并不总是简单的，尤其是采用开放定址法时，直接删除元素可能会破坏查找链，导致后续查找失败，通常需要标记为“已删除”状态。 即使在链地址法中，删除也需调整指针，因此该说法不正确。

综上，不正确的说法有Ⅰ、Ⅲ、Ⅳ，共 3 个，故选 C。

数据序列（2,1,4,9,8,10,6,20）只能是（ ）排序的两趟排序后的结果。

A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序

排序算法 插入排序

[tag_link]

正确答案：A

首先分析序列（2,1,4,9,8,10,6,20）作为各排序算法两趟后的可能性。 冒泡排序两趟后，最大和第二大元素应位于末尾，但序列末尾为 6 和 20，第二大的 10 不在倒数第二，排除 B。 选择排序两趟后，最小和第二小元素应位于前两位，但序列前两位为 2 和 1，而非 1 和 2，排除 C。 插入排序两趟后，前两个元素应有序，但序列前两位为 2 和 1（无序），排除 D。

快速排序的可能在于：序列中元素 4 满足左边（2,1）均小于 4，右边（9,8,10,6,20）均大于 4，符合快速排序一趟分区后枢轴就位的特征。 考虑两趟操作：第一趟以最后一个元素 20 为枢轴进行分区，由于 20 最大，分区后序列不变； 第二趟对左子序列（2,1,4,9,8,10,6）以 4 为枢轴进行分区，使 4 就位，且左子序列保持为 2,1,4,9,8,10,6，从而得到当前序列。 尽管枢轴选择可能非标准（如选中间元素），但快速排序允许不同策略，而其他算法均不匹配，因此 A 正确。

假定我们从下图所示的堆中删除了值为 11 的结点，那么值为 70 的结点将出现在图中哪个指定位置（ ）。

A. A

B. B

C. C

D. D

堆的概念

[tag_link]

正确答案：C

本题考查堆的调整过程。 堆的调整流程如下图所示，可知 70 最后的位置为 C。

冯·诺伊曼机可以区分指令和数据的部件是（ ）。

A. 总线 B. 控制器 C. 控制存储器 D. 运算器

操作系统概念

[tag_link]

正确答案：B

冯·诺伊曼机采用存储程序结构，指令和数据共享同一个存储器。 为了正确执行程序，计算机必须能够区分指令和数据，这一功能主要由控制器实现。 控制器负责协调计算机的各部件工作，通过指令周期来管理操作：在取指阶段，控制器从存储器中读取指令，并更新程序计数器； 在执行阶段，控制器解码指令，并根据需要访问数据存储器或执行运算。 因此，控制器通过不同的时序和控制信号，确保指令被当作命令处理，而数据被当作操作数处理，从而有效区分两者。 其他部件如总线只负责传输信息，运算器专注于算术逻辑运算，控制存储器则用于存储微程序，它们均不直接承担区分指令和数据的核心角色。

已知 C 程序中，某类型为 int 的变量 x 的值为 -1088。程序执行时，x 先被存放在 16 位寄存器 R1 中，然后被进行算术右移 4 位的操作。则此时 R1 中的内容（以十六进制表示）是（ ）。

A. FBCOH B. FFBCH C. 0FBCH D. 87BCH

补码 寄存器类型

[tag_link]

正确答案：B

首先，变量 x 的值为 -1088，在 16 位寄存器中采用二进制补码表示。 1088 的十六进制表示为 0x0440，对其取反加一得到 -1088 的表示：0xFFFF - 0x0440 + 1 = 0xFBBF + 1 = 0xFBC0。 因此，寄存器 R1 初始内容为 0xFBC0。

执行算术右移 4 位时，由于符号位为 1，左移空出的高位补 4 个 1。 原始值 0xFBC0（二进制 1111 1011 1100 0000）右移 4 位后，低 4 位丢弃，高 4 位补 1，得到 1111 1111 1011 1100，即十六进制 0xFFBC。

另一种验证方式：算术右移 4 位等价于除以 16。 计算 -1088 / 16 = -68，而 -68 的 16 位二进制补码表示为 0xFFBC（68 为 0x0044，取反加一得 0xFFBC）。 因此，移位后 R1 的内容为 0xFFBC。

选项 A 为原始值，选项 C 和 D 均为正数表示，与结果不符，故正确答案为 B。

下列关于机器零的说法，正确的是（ ）。

A. 发生“下溢”时，浮点数被当做机器零，机器将暂停运行，转去处理“下溢” B. 只有以移码表示阶码时，才能用全 0 表示机器零的阶码 C. 机器零属于规格化的浮点数 D. 定点数中的零也是机器零

补码

[tag_link]

正确答案：B

【解析】本题考查机器零。 只有当数据发生“上溢”时，机器才会终止运算操作，转去进行溢出处理，A 错误。 规格后化可以判断运算结果是否上溢出（超过表示范围），但和机器零没有关联，规格化规定尾数的绝对值应大于或等于 1/R（R 为基数），并小于或等于 1，机器零显然不符合这个定义，C 错误。 定点数中所表示的 0，是实实在在的 0（坐标轴上的），而不是趋近 0 的机器零，D 错误。 在各种数码的表示法中，移码相当于真值在坐标轴上整体右移至正区间内，当移码表示的阶码全 0 时，为阶码表示的最小负数，此时直接认为浮点数是机器零，B 正确。

注意：当浮点运算结果在 0 到最小正数之间（正下溢）或最大负数到 0 之间（负下溢）时，浮点数值趋于 0，计算机将其当做机器零处理。

某存储系统中，主存容量是 Cache 容量的 4096 倍，Cache 被分为 64 块，当主存地址和 Cache 地址采用直接映射方式时，地址映射表的大小应为（ ）。（假设不考虑一致维护位）

A. $6\times 4097$ bit B. $64\times 12$ bit C. $6\times 4096$ bit D. $64\times 13$ bit

访存过程

[tag_link]

正确答案：B

本题考查 Cache 与主存的映射原理。 由于 Cache 被分为 64 块，那么 Cache 有 64 行，采用直接映射，一行相当于一组。 故而该标记阵列每行存储 1 个标记项，其中主存标记项为 12bit（

$2^{12}=4096$ ，是 Cache 容量的 4096 倍，那就是地址长度比 Cache 长 12 位），加上 1 位有效位，故而为 $64\times 13$ bit。

注意：主存—Cache 地址映射表（标记阵列）中内容：映射的 Cache 地址（直接映射不需要因为 Cache 地址唯一，组相联只需要组号）、主存标记（命中判断）、有效位。 如下图所示。

某虚拟存储系统采用页式存储管理，只有 a、b 和 c 三个页框，页面访问的顺序为： 0, 1, 2, 4, 2, 3, 0, 2, 1, 3, 2, 3, 0, 1, 4 若采用 FIFO 替换算法，则命中率为（ ）。

A. 20% B. 26.7% C. 15% D. 50%

访存过程 页面置换算法

[tag_link]

正确答案：B

本题考查 FIFO 算法。 FIFO 算法指淘汰**先进入**的，易知替换顺序为：

表中除了标注为命中的，其余均未命中，所以命中率为 $4/15=26.7\%$ 。 >

假设寄存器 R 中的数值为 200，主存地址为 200 和 300 的地址单元中存放的内容分别是 300 和 400，则（ ）访问到的操作数为 200。

A. Ⅰ和Ⅳ B. Ⅱ、Ⅲ C. Ⅲ、Ⅳ D. 只有Ⅰ

寄存器类型 指令寻址方式

[tag_link]

正确答案：D

本题考查各种数据寻址方式的原理。 直接寻址 200 中，200 就是有效地址，所访问的主存地址 200 对应的内容是 300，Ⅰ错误。 寄存器间接寻址（R）的访问结果与Ⅰ一样，Ⅱ错误。 存储器间接寻址（200）表示主存地址 200 中的内容为有效地址，所以有效地址为 300，访问的操作数是 400，Ⅲ错误。 寄存器寻址 R 表示寄存器 R 的内容即为操作数，所以只有Ⅳ正确。 此类题建议画出草图。

下列部件不属于控制器的是（ ）。

A. 指令寄存器 B. 程序计数器 C. 程序状态字寄存器 D. 时序电路

寄存器类型

[tag_link]

正确答案：C

控制器是 CPU 的核心部件，负责指令译码、产生控制信号以协调计算机各部件工作。 典型控制器包括指令寄存器、程序计数器、时序电路等。 指令寄存器（A）用于存储当前执行的指令，程序计数器（B）存放下一条指令地址，时序电路（D）产生定时信号控制指令执行步骤，三者均属于控制器。 程序状态字寄存器（C）主要存储处理器的状态信息（如进位、零标志等），这些信息反映运算器操作结果，虽可供控制器使用，但其本身属于处理器状态单元或运算器关联部分，不属于控制器。 因此，本题选项中不属于控制器的是程序状态字寄存器。

设指令由取指、分析、执行三个子部件完成，每个子部件的工作周期均为 t，采用常规标量流水线处理。若连续执行 10 条指令，则需要的时间为（ ）。

A. $8t$ B. $10t$ C. $12t$ D. $14t$

流水线概念

[tag_link]

正确答案：C

在常规标量流水线中，指令执行分为取指、分析、执行三个阶段，每个阶段耗时均为

$t$ 。

流水线处理允许连续指令重叠执行不同阶段，从而提升效率。 对于 $k$ 个阶段（本题 $k=3$ ）和 $n$ 条指令（本题 $n=10$ ），总时间计算公式为： $$\text{总时间}=(k+n-1)\cdot t$$

代入具体数值： $$\text{总时间}=(3+10-1)\cdot t=12t$$

这意味着第一条指令在 $3t$ 时完成，后续指令每隔 $t$ 时间完成一条，第 10 条指令在 $12t$ 时完成，因此连续执行 10 条指令需要 $12t$ 时间。

选项中，A.

$8t$ 、B. $10t$ 、D. $14t$ 均不符合计算结果，故正确答案为 C。

在 32 位总线系统中，若时钟频率为 500MHz，传送一个 32 位字需要 5 个时钟周期，则该总线系统的数据传输速率是（ ）。

A. $200MB/s$ B. $400MB/s$ C. $600MB/s$ D. $800MB/s$

计算机性能指标

[tag_link]

正确答案：B

首先，理解关键参数：总线宽度为 32 位，时钟频率为 500 MHz，传送一个 32 位字需要 5 个时钟周期。 数据传输速率指单位时间内传输的数据量，通常以字节每秒（B/s）为单位。

计算每秒传输的字数：时钟频率为 500 MHz，即每秒有

$500\times 10^6$ 个时钟周期。

由于每 5 个时钟周期传输一个字，因此每秒传输的字数为

$$500\times 10^6÷5=100\times 10^6\text{字/秒}$$

每个字的数据量：32 位等于 4 字节（因为 8 位为 1 字节）。

因此，每秒传输的数据量为

$$100\times 10^6\text{字/秒}\times 4\text{字节/字}=400\times 10^6\text{字节/秒}$$

在数据传输速率中，常以 MB/s 表示兆字节每秒，其中 1 MB = $10^6$ 字节。

因此， $400\times 10^6$ 字节/秒等于 400 MB/s，对应选项 B。

某计算机系统中的软盘驱动器以中断方式与处理机进行 I/O 通信，通信以 16bit 为传输单位，传输率为 50KB/s。每次传输的开销（包括中断）为 100 个节拍，处理器的主频为 50MHz，则磁盘使用时占用处理器时间的比例为（ ）。

A. 5% B. 10% C. 15% D. 20%

计算机性能指标

[tag_link]

正确答案：A

首先，传输单位为 16 比特，即 2 字节。 传输速率为 50 KB/s，这里按 1 KB = 1024 字节计算，每秒传输的字节数为

$$50\times 1024=51200\text{ 字节}$$

因此，每秒传输次数

$$N=\frac{51200\text{ 字节/秒}}{2\text{ 字节/次}}=25600\text{ 次}$$

处理器主频为 50 MHz，即

$$50\times 10^6\text{ Hz}$$

每个时钟周期（节拍）的时间为

$$\frac{1}{50\times 10^6}=2\times 10^{-8}\text{ 秒}$$

每次传输的开销为 100 个节拍，所以每次开销时间为

$$100\times 2\times 10^{-8}=2\times 10^{-6}\text{ 秒}$$

每秒总开销时间为

$$25600\text{ 次}\times 2\times 10^{-6}\text{ 秒/次}=0.0512\text{ 秒}$$

占用处理器时间的比例为

$$\frac{0.0512\text{ 秒}}{1\text{ 秒}}=0.0512=5.12\%\approx 5\%$$

若按 1 KB = 1000 字节计算，则

$$N=\frac{50\times 1000}{2}=25000\text{ 次/秒}$$

总开销时间为

$$25000\times 2\times 10^{-6}=0.05\text{ 秒}$$

比例仍为

$$\frac{0.05}{1}=5\%$$

因此，答案为 5%。

对于单 CPU 单通道工作过程，下列可以完全并行工作的是（ ）。

A. 程序和程序之间

B. 程序和通道之间

C. 程序和设备之间

D. 设备和设备之间

异常和中断

[tag_link]

正确答案：C

本题考查通道的工作原理。 做题的时候要注意完全并行的“完全”这两个字，对于单 CPU 系统来讲，程序和程��之间是并发的关系，而不是真正意义上的并行，要理解好并发和并行的区别。 通道方式是 DMA 方式的进一步发展，通道实际上也是实现 I/O 设备和主存之间直接交换数据的控制器。 通道的基本工作过程如下图所示。 CPU 通过执行 I/O 指令负责启停通道，以及处理来自通道的中断实现对通道的管理，因此通道和程序（即 CPU）并没有完全并行，因为通道仍然需要 CPU 来对它实行管理，B 错误。 而在设备工作时，它只与通道交互，此时程序与其并行工作，C 正确。 而 A、D 显然错误。

用户在编写程序时计划读取某个数据文件中的 20 个数据记录，他使用操作系统提供的接口是（ ）。

A. 系统调用 B. 图形用户接口 C. 原语 D. 命令行输入控制

系统调用 操作系统概念

[tag_link]

正确答案：A

在编写程序时，用户需要通过代码与操作系统交互来读取文件中的数据记录。 操作系统提供的系统调用（System Call）是专门为应用程序设计的编程接口，它允许程序请求操作系统的服务，如文件操作、进程管理等。 例如，在 C 语言中使用 read() 函数读取文件时，底层会调用操作系统的 read 系统调用，从而实现对文件的访问。

其他选项中，图形用户接口（GUI）是面向最终用户的视觉交互界面，通过点击、拖拽等方式操作，不适用于编程时的文件读取； 原语（Primitive）通常指操作系统内核中不可中断的基本操作，是系统调用的底层实现，但不直接暴露给应用程序员； 命令行输入控制是通过命令行界面输入指令来操作系统的交互方式，属于用户级交互，而非编程接口。 因此，用户在编写程序时读取数据文件应使用系统调用接口。

在多对一的线程模型中，当一个多线程进程中的某一个线程执行一个需阻塞的系统调用时，（ ）。

A. 该进程的其他线程仍将继续运行 B. 整个进程都将阻塞 C. 该阻塞线程将被撤销 D. 该进程将被撤销

进程和线程

[tag_link]

正确答案：B

在多对一的线程模型中，多个用户级线程映射到单个内核级线程。

这意味着所有用户级线程都由同一个内核线程管理，内核线程是操作系统进行调度和执行的基本单位。

当一个用户级线程执行了一个需阻塞的系统调用（例如等待 I/O 操作完成）时，控制权会转移到内核。 由于只有一个内核线程，该内核线程会因为系统调用而进入阻塞状态。 操作系统内核会将该内核线程（从而整个进程）置于阻塞队列，并切换到其他就绪进程执行。

因此，尽管进程内部有多个用户级线程，但由于它们共享同一个内核线程，一旦这个内核线程阻塞，整个进程就无法继续运行，所有用户级线程都会被阻塞。 其他选项不正确：A 错误，因为其他线程无法运行； C 和 D 错误，因为线程和进程通常不会被撤销，只是状态改变。

并发进程运行时，其推进的相对速度是（ ）。

A. 由进程的程序结构决定 B. 由进程自己的代码控制 C. 与进程调度策略有关 D. 在进程创建时确定的

进程和线程 进程概念

[tag_link]

正确答案：C

并发进程的推进相对速度主要与操作系统的进程调度策略有关。 在并发环境中，多个进程交替或并行执行，其执行顺序和获得 CPU 时间的频率由调度器根据策略（如时间片轮转、优先级调度等）动态决定。 进程的程序结构或代码虽可能影响其计算需求，但无法直接控制调度器的分配行为； 进程创建时可能设定初始属性，但推进速度在运行时会随系统负载和调度决策变化，并非固定不变。 因此，推进速度的关键因素是调度策略。

在使用信号量机制实现互斥和同步时，互斥信号量和同步信号量的初值分别为（ ）。

A. 0、1 B. 1、0 C. 1、1 D. 1、由用户确定

信号量

[tag_link]

正确答案：D

【解析】本题考查信号量机制。 互斥信号量的初值都设置为 1，P 操作成功则将其改成 0，V 操作成功将其改成 1。 实现同步时，信号量的初值应根据具体情况来确定，若期望的消息尚未产生，则对应的初值应设为 0； 若期望的消息已经存在，则信号量的初值应设为一个非 0 的正整数。

注意：互斥信号量和同步信号量的区别。 信号量机制是每年考题的重点，这就要求考生能在理解的基础上熟练应用和掌握信号量。

某操作系统采用可变分区分配存储管理方法，操作系统占用低地址部分的 126KB。用户区大小为 386KB，且用户区始址为 126KB，用空闲分区表管理空闲分区。若分配时采用分配空闲区高地址部分的方案，且初始时用户区的 386KB 空间空闲，对申请序列：作业 1 申请 80KB，作业 2 申请 56KB，作业 3 申请 120KB，作业 1 释放 80KB，作业 3 释放 120KB，作业 4 申请 156KB，作业 5 申请 81KB。如果采用首次适应算法处理上述序列，则最小空闲块的大小为（ ）。

A. $12KB$ B. $13KB$ C. $89KB$ D. $56KB$

操作系统概念 外存空间管理

[tag_link]

正确答案：B

我们按照序列逐步模拟存储分配与释放过程。 操作系统占用低地址 126KB，用户区始址 126KB，大小 386KB，即用户区范围为 126KB～512KB。 初始时，整个用户区空闲，空闲分区表仅有一个分区：起始地址 126KB，大小 386KB。 分配时采用首次适应算法，且从找到的空闲分区的高地址部分切割。

1. **作业 1 申请 80KB**：查找第一个大小≥80KB 的空闲分区（126KB, 386KB），从高地址部分切割 80KB，分配后空闲分区变为（126KB, 306KB）。 作业 1 占据 432KB～512KB。

2. **作业 2 申请 56KB**：查找第一个大小≥56KB 的空闲分区（126KB, 306KB），从高地址部分切割 56KB，分配后空闲分区变为（126KB, 250KB）。 作业 2 占据 376KB～432KB。

3. **作业 3 申请 120KB**：查找第一个大小≥120KB 的空闲分区（126KB, 250KB），从高地址部分切割 120KB，分配后空闲分区变为（126KB, 130KB）。 作业 3 占据 256KB～376KB。

4. **作业 1 释放 80KB**：释放区域为 432KB～512KB，与现有空闲分区（126KB, 130KB）不相邻，空闲分区表变为两个：（126KB, 130KB）和（432KB, 80KB）。

5. **作业 3 释放 120KB**：释放区域为 256KB～376KB，与第一个空闲分区（126KB, 130KB）相邻（结束于 256KB），合并为（126KB, 250KB）。 第二个空闲分区（432KB, 80KB）不变。 空闲分区表为（126KB, 250KB）和（432KB, 80KB）。

6. **作业 4 申请 156KB**：查找第一个大小≥156KB 的空闲分区（126KB, 250KB），从高地址部分切割 156KB，分配后该分区变为（126KB, 94KB）。 作业 4 占据 220KB～376KB。 空闲分区表为（126KB, 94KB）和（432KB, 80KB）。

7. **作业 5 申请 81KB**：查找第一个大小≥81KB 的空闲分区（126KB, 94KB），从高地址部分切割 81KB，分配后该分区变为（126KB, 13KB）。 作业 5 占据 139KB～220KB。 空闲分区表最终为（126KB, 13KB）和（432KB, 80KB）。

最终有两个空闲块，大小分别为 13KB 和 80KB，最小空闲块大小为 13KB，对应选项 B。

下列说法中，正确的是（ ）。 Ⅰ. 先进先出（FIFO）页面置换算法可能会产生 Belady 现象。 Ⅱ. 最近最少使用（LRU）页面置换算法可能会产生 Belady 现象。 Ⅲ. 在进程运行时，如果它的工作集页面都在虚拟存储器内，能够使该进程有效地运行，否则会出现频繁的页面调入/调出现象。 Ⅳ. 在进程运行时，如果它的工作集页面都在主存储器内，能够使该进程有效地运行，否则会出现频繁的页面调入/调出现象。

A. Ⅰ和Ⅲ B. Ⅰ和Ⅳ C. Ⅱ和Ⅲ D. Ⅱ和Ⅳ

页面置换算法 进程和线程

[tag_link]

正确答案：B

说法Ⅰ正确：先进先出（FIFO）页面置换算法在增加内存页面帧数时，可能导致缺页次数反而增加，这种现象称为 Belady 异常，因此 FIFO 确实可能产生 Belady 现象。

说法Ⅱ错误：最近最少使用（LRU）页面置换算法属于栈算法，对于任何页面访问序列，增加页面帧数不会增加缺页次数，因此 LRU 不会产生 Belady 现象。

说法Ⅲ错误：工作集是指进程在最近一段时间内访问的页面集合。 若工作集页面仅位于虚拟存储器（如磁盘交换区），进程访问时需频繁调入主存，会导致缺页中断和页面调入/调出，无法有效运行； 有效运行需要工作集页面位于主存储器中。

说法Ⅳ正确：当进程的工作集页面都在主存储器内时，进程可快速访问所需页面，减少缺页中断，从而有效运行； 否则，会因页面缺失而出现频繁的页面调入/调出现象。

综上，正确说法为Ⅰ和Ⅳ，对应选项 B。

在请求分页存储管理系统中，地址变换过程可能会因为（ ）而产生中断。 Ⅰ. 地址越界 Ⅱ. 缺页 Ⅲ. 访问权限错误 Ⅳ. 内存溢出

A. Ⅰ和Ⅱ B. Ⅰ、Ⅱ、Ⅲ和Ⅳ C. 仅Ⅱ D. Ⅰ、Ⅱ和Ⅲ

地址翻译 页表

[tag_link]

正确答案：D

在请求分页存储管理系统中，地址变换过程将逻辑地址转换为物理地址，该过程可能因多种异常情况而产生中断。

首先，地址越界（Ⅰ）可能触发中断。 当地址变换时，若逻辑地址的页号超出进程地址空间范围（如大于页表长度），硬件会检测到无效访问，产生越界中断。

其次，缺页（Ⅱ）是请求分页系统的核心中断来源。 当访问的页面不在内存中（页表项的有效位为 0），硬件会触发缺页中断，操作系统需调入页面。

第三，访问权限错误（Ⅲ）也可能导致中断。 页表项中包含保护位（如读、写权限），若进程试图以未授权方式访问页面（如写入只读页），会触发保护中断。

最后，内存溢出（Ⅳ）通常不是地址变换过程的直接中断原因。 内存溢出指系统内存不足，这可能在页面置换或内存分配时由操作系统处理，但地址变换本身不直接检测内存溢出； 缺页中断处理程序可能需处理内存不足，但变换过程不会因此产生中断。

因此，地址变换过程可能因Ⅰ、Ⅱ和Ⅲ产生中断，对应选项 D。

下面关于索引文件的叙述中，正确的是（ ）。

A. 索引文件中，索引表的每个表项中含有相应记录的关键字和存放该记录的物理地址 B. 文件进行检索时，首先从 FCB 中读出文件的第一个盘块号；而对索引文件进行检索时，应先从 FCB 中读出文件索引块的开始地址 C. 对于一个具有三级索引的文件，存取一个记录通常要访问三次磁盘 D. 在文件较大时，无论是进行顺序存取还是随机存取，通常都是以索引文件方式最快

文件概念

[tag_link]

正确答案：B

选项 A 不正确，因为索引文件的索引表项通常包含的是指向记录的指针（物理地址），但并不一定都包含关键字。

在操作系统的索引分配方式中，索引块存储的是文件块的物理地址，关键字索引更多用于数据库系统，而非一般文件系统的索引文件。

选项 B 正确，它描述了不同文件组织的检索起点。 对于非索引文件（如连续或链接分配），检索时常从文件控制块（FCB）中读取第一个盘块号； 而对于索引文件，由于文件数据块的地址存储在索引块中，因此需要先从 FCB 中读出索引块的起始地址，再访问索引块获取目标记录的物理地址。

选项 C 错误，因为三级索引文件存取一个记录通常需要四次磁盘访问：读取一级索引块、二级索引块、三级索引块各一次，最后读取数据块一次。 因此，访问次数是四次而非三次。

选项 D 错误，索引文件在随机存取时速度较快，但对于顺序存取，连续分配的文件组织方式可能更高效，因为可以直接顺序读取物理块，而索引文件需要额外访问索引结构，可能引入开销。 因此，并非在所有情况下索引文件都是最快的。

物理文件的组织方式是由（ ）确定的。

A. 应用程序 B. 存储介质 C. 外存容量 D. 存储介质和操作系统

文件概念 操作系统概念

[tag_link]

正确答案：D

物理文件的组织方式指的是文件在存储设备上的物理结构，例如顺序存储、链式存储或索引存储等。

这种组织方式不仅依赖于存储介质的物理特性（如磁盘的扇区大小、访问方式），还取决于操作系统如何管理这些介质。 操作系统通过文件系统（如 FAT、NTFS、ext4）将逻辑文件映射到物理存储空间，从而决定文件的布局和访问效率，因此存储介质和操作系统共同确定了物理文件的组织方式。

其他选项分析：A 项应用程序通常只处理文件的逻辑内容，不直接控制物理存储； B 项存储介质单独无法决定组织方式，因为它需要操作系统的管理来实现文件结构； C 项外存容量仅影响存储空间大小，而不影响具体的组织结构。 因此，D 项是最全面的正确答案。

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

A. CPU 在 I/O 设备进行数据准备时一直处于等待状态，直到 I/O 操作完成

B. 中断 I/O 方式下，每传输一个数据块都需要 CPU 进行多次干预

C. 中断处理过程中，CPU 在响应中断请求后立即保存当前进程的 PCB 信息

D. 采用中断驱动 I/O 方式时，CPU 与 I/O 设备之间无法实现并行工作

寄存器类型 进程控制块

[tag_link]

正确答案：B

A ❌ 描述的是 程序直接控制（轮询）方式 的特点，中断 I/O 方式中 CPU 在设备准备数据时可执行其他任务，无需忙等。 B ✅ 中断 I/O 方式下，每完成一个 字（或字节） 的传输，设备便向 CPU 发出中断请求，CPU 需介入进行数据存取与状态处理，因此传输一个数据块需多次中断及 CPU 干预。 C ❌ 响应中断后，CPU 首先保存的是 当前程序的现场（如 PC、寄存器等） ，而非整个 PCB； PCB 的保存通常在进程切换时发生，并非中断响应的立即操作。 D ❌ 中断 I/O 方式正是为了实现 CPU 与 I/O 设备的并行工作，设备准备数据时 CPU 可执行其他任务，通过中断机制进行协调。

在 OSI 参考模型中，下列哪一层的主要功能是提供端到端的可靠��据传输、流量控制和差错恢复？

A. 数据链路层（Data Link Layer） B. 网络层（Network Layer） C. 传输层（Transport Layer） D. 会话层（Session Layer）

差错控制 协议数据单元

[tag_link]

正确答案：C

• 传输层（Transport Layer）负责端到端的可靠数据传输，提供流量控制、差错恢复和连接管理等功能。 > 典型的协议如 TCP。 >
• 数据链路层 负责相邻节点间的可靠传输（帧同步、差错控制）。 >
• 网络层 负责路径选择、路由和寻址（如 IP 协议）。 >
• 会话层 负责建立、管理和终止会话。 >

若数据链路的发送窗口尺寸 WT=4，在发送 3 号帧，并接到 2 号帧的确认帧后，发送方还可以连续发送的帧数是（ ）。

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

协议数据单元

[tag_link]

正确答案：B

发送窗口尺寸 WT=4 表示发送方最多可以发送 4 个未被确认的帧。 假设帧编号从 0 开始，且确认是累积的（即确认帧号 n 表示所有帧号小于 n 的帧均已被确认）。

在发送 3 号帧之前，发送方可能已经发送了帧 0、1、2，此时有 3 个未确认帧。 发送 3 号帧后，未确认帧变为 4 个（帧 0、1、2、3），发送窗口已满，无法继续发送新帧。

接着，发送方接到 2 号帧的确认帧。 由于确认是累积的，这意味着帧 0、1、2 均已被确认。 因此，未确认帧只剩下帧 3，发送窗口基序号移动到 3，窗口允许发送帧 3、4、5、6。 由于帧 3 已经发送，当前未确认帧数为 1，而窗口大小为 4，所以发送方还可以连续发送 3 帧（即帧 4、5、6）。

因此，发送方还可以连续发送的帧数是 3 帧。

CSMA 协议可以利用多种监听算法来减小发送冲突的概率，下面关于各种监听算法的描述中，错误的是（ ）。

A. Ⅰ、Ⅱ和Ⅲ B. Ⅱ和Ⅲ C. Ⅰ、Ⅱ和Ⅳ D. Ⅱ和Ⅳ

散列表

[tag_link]

正确答案：A

首先，分析各监听算法的特性：非坚持型监听算法在信道忙时等待随机时间再监听，这减少了冲突，但可能导致信道空闲时无站点立即发送，从而增加网络空闲时间，因此陈述Ⅰ“有利于减少网络空闲时间”是错误的。

其次，1-坚持型监听算法在信道空闲时立即发送，虽然减少了空闲时间，但多个站点可能同时发送，导致冲突概率增加，因此陈述Ⅱ“有利于减少冲突的概率”是错误的。

再者，P 坚持型监听算法通过概率

$P$ 发送来平衡冲突和空闲时间，相比非坚持型能减少空闲时间，因此陈述Ⅲ“无法减少网络的空闲时间”是错误的。

最后，1-坚持型算法因持续监听并在信道空闲时立即发送，能及时抢占信道，陈述Ⅳ是正确的。

综上，错误的陈述是Ⅰ、Ⅱ和Ⅲ，对应选项 A。

在 CSMA/CD 协议中，下列指标与冲突时间没有关系的是（ ）。

A. 检测一次冲突所需要的最长时间 B. 最小帧长度 C. 最大帧长度 D. 最大帧碎片长度

散列表 协议数据单元

[tag_link]

正确答案：C

在 CSMA/CD 协议中，冲突时间（即冲突窗口或往返传播延迟）是一个关键参数，它决定了信号从发送端到最远站点再返回所需的最长时间。

这个时间直接影响到冲突检测和帧设计。

选项 A“检测一次冲突所需要的最长时间”本质上就是冲突时间本身，因此与冲突时间直接相关。 选项 B“最小帧长度”是为了确保在帧发送完毕前能够检测到冲突，其计算公式为最小帧长度 = 2 × 传播延迟 × 数据传输速率，这与冲突时间紧密相连。 选项 D“最大帧碎片长度”指的是冲突发生后可能产生的碎片的最大长度，由于碎片只能在冲突窗口内形成，其最大长度受限于冲突时间内传输的比特数，因此也与冲突时间有关。

相比之下，选项 C“最大帧长度”通常由协议规范、网络性能或缓冲区大小等因素决定，例如传统以太网中最大帧长度为 1518 字节，目的是限制帧的大小以避免信道过长时间被占用，但这一指标与冲突时间没有直接关系，冲突时间并不影响最大帧长度的设定。 因此，与冲突时间没有关系的是最大帧长度。

某端口的 IP 地址为 172.16.7.131.26，则该 IP 地址所在网络的广播地址（ ）。

A. 172.16.7.191 B. 172.16.7.129 C. 172.16.7.255 D. 172.16.7.252

子网划分

[tag_link]

正确答案：A

题目中给出的“172.16.7.131.26”可能为笔误，实际应表示 IP 地址 172.16.7.131，子网掩码为 26 位（即 172.16.7.131/26）。

子网掩码 26 位对应 255.255.255.192，其二进制形式为 11111111.11111111.11111111.11000000，表示前 26 位为网络部分，后 6 位为主机部分。

IP 地址 172.16.7.131 的第四个字节 131 转换为二进制是 10000011。 将其与子网掩码的第四个字节 192（二进制 11000000）进行 AND 运算，得到网络地址的第四个字节为 10000000（十进制 128），因此网络地址为 172.16.7.128。

广播地址是网络地址中主机部分全为 1 的地址。 由于主机部分有 6 位，将网络地址 172.16.7.128 的第四个字节后 6 位全置 1，得到二进制 10111111，转换为十进制为 191。 因此广播地址为 172.16.7.191。

其他选项中，B（172.16.7.129）是该子网内的一个主机地址； C（172.16.7.255）是未划分子网时的 C 类默认广播地址，但此处已子网划分； D（172.16.7.252）可能是其他子网的广播地址，均不正确。

在因特网中，IP 数据报的传输需要经由源主机和中途路由器到达目的主机，下面说法正确的是（ ）。

A. 源主机和中途路由器都知道 IP 数据报到达目的主机需要经过的完整路径 B. 源主机知道 IP 数据报到达目的主机需要经过的完整路径，而中途路由器不知道 C. 源主机不知道 IP 数据报到达目的主机需要经过的完整路径，而中途路由器知道 D. 源主机和中途路由器都不知道 IP 数据报到达目的主机需要经过的完整路径

路由器

[tag_link]

正确答案：D

在因特网中，IP 数据报的传输基于无连接的数据报交换机制。 源主机发送数据报时，仅根据本地路由表确定下一跳（如默认网关），而不知道到达目的主机的完整路径。 中途路由器在转发时，也仅根据自身路由表查询目的 IP 地址对应的下一跳，同样不了解完整路径。 整个传输过程依赖逐跳路由，每个节点独立决策，因此源主机和中途路由器都不知道完整路径，这体现了 IP 协议的分布式和自适应路由特性。 选项 A、B、C 的描述均不符合这一原理。

TCP 的通信双方，有一方发送了带有 FIN 标志的数据段后表示（ ）。

A. 将断开通信双方的 TCP 连接 B. 单方面释放连接，表示本方已经无数据发送，但是可以接受对方的数据 C. 中止数据连接，双方都不能发送数据 D. 连接被重新建立

进程内存空间

[tag_link]

正确答案：B

在 TCP 协议中，FIN（Finish）标志用于终止连接。

当通信一方发送带有 FIN 标志的数据段时，表示该方已经完成数据发送，并希望关闭从本方到对方的单向连接。 此时，连接进入“半关闭”状态：发送 FIN 的一方不再发送数据，但仍可以接收对方发送的数据，直到对方也发送 FIN 来关闭另一个方向的连接。

选项 A 错误，因为发送 FIN 并不会立即断开通信双方的 TCP 连接，对方可能仍需发送剩余数据； 选项 C 错误，因为发送 FIN 后，对方在确认前仍可发送数据； 选项 D 错误，因为 FIN 用于连接终止，而非重新建立连接。 因此，只有选项 B 准确描述了发送 FIN 后的状态。

UDP 协议和 TCP 协议报文首部的非共同字段有（ ）。

A. 源端口

B. 目的端口

C. 序列号

D. 校验和

协议数据单元

[tag_link]

正确答案：C

UDP 和 TCP 协议报文首部中，源端口和目的端口是两者都具备的字段，用于标识通信的端点。 校验和字段在 UDP 和 TCP 中也都存在，尽管 UDP 的校验和是可选的，但通常被视为首部的一部分。 序列号是 TCP 特有的字段，用于保证数据的有序传输和可靠性； UDP 作为无连接协议，没有序列号字段，因此序列号是两者的非共同字段。

（9 分）对于一个堆栈，若其入栈序列为 $1,2,3,\cdots ,n$ ，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为 $n$ 的二叉树的个数，且与不同形态的二叉树一一对应。请简要论述一种从堆栈输入（固定为 $1,2,3,\cdots ,n$ ）输出序列对应一种二叉树形态的方法，并以入栈序列 $1,2,3$ （即 $n=3$ ）为例加以说明。

入栈出栈序列

[tag_link]

**【答案】** 将固定入栈序列 $1,2,3,\cdots ,n$ 视为二叉树的前序遍历序列，而将出栈序列视为同一二叉树的中序遍历序列。由于二叉树的前序遍历和中序遍历可以唯一确定二叉树的结构，因此每个合法的出栈序列对应一种二叉树形态。

**【解析】** 对于入栈序列 $1,2,\cdots ,n$ ，其出栈序列的个数等于结点个数为 $n$ 的二叉树的个数，即第 $n$ 个卡特兰数。这一一对应可通过二叉树遍历序列建立：入栈序列固定为前序遍历序列，出栈序列作为中序遍历序列。具体地，前序遍历序列确定了根结点的访问顺序，中序遍历序列确定了左子树和右子树的划分，从而唯一重建二叉树。

以 $n=3$ 为例，入栈序列为 $1,2,3$ ，作为前序遍历序列。合法的出栈序列有 $5$ 种，分别作为中序遍历序列，重建二叉树如下：

• 出栈序列 $1,2,3$ ：前序 $1,2,3$ ，中序 $1,2,3$ ，重建得二叉树为根结点 $1$ 的右孩子为 $2$ ， $2$ 的右孩子为 $3$ 。
• 出栈序列 $1,3,2$ ：前序 $1,2,3$ ，中序 $1,3,2$ ，重建得根结点 $1$ 的右孩子为 $2$ ， $2$ 的左孩子为 $3$ 。
• 出栈序列 $2,1,3$ ：前序 $1,2,3$ ，中序 $2,1,3$ ，重建得根结点 $1$ 的左孩子为 $2$ ，右孩子为 $3$ 。
• 出栈序列 $2,3,1$ ：前序 $1,2,3$ ，中序 $2,3,1$ ，重建得根结点 $1$ 的左孩子为 $2$ ， $2$ 的右孩子为 $3$ 。
• 出栈序列 $3,2,1$ ：前序 $1,2,3$ ，中序 $3,2,1$ ，重建得根结点 $1$ 的左孩子为 $2$ ， $2$ 的左孩子为 $3$ 。

这五种二叉树形态恰好对应所有合法的出栈序列，验证了一一对应关系。

（13 分）已知一棵二叉树采用二叉链表存储，结点结构为：

root 指向根结点。请编写算法判断该二叉树是否是平衡二叉树，即二叉树中任意结点的左右子树的深度相差不超过 1。例如下图所示的二叉树就是一棵平衡二叉树。

要求：

（1）给出算法的基本设计思想。

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

复杂度分析 平衡二叉树

[tag_link]

【答案】

（1）基本设计思想：采用递归后序遍历二叉树，在计算每个结点高度的同时判断其左右子树是否平衡。递归函数返回当前子树的高度，若子树不平衡则返回 -1 作为标志。对于每个结点，先递归检查其左右子树，若任一子树返回 -1，则当前子树不平衡；否则计算左右子树高度差，若超过 1 则返回 -1，否则返回当前子树高度（即左右子树最大高度加 1）。最终，若根结点对应的递归返回值不为 -1，则二叉树是平衡的。

（2）算法描述（C 语言）： #include <stdlib.h> // 用于 abs 函数 #include <stdbool.h> // 用于 bool 类型 struct Node { struct Node * lchild ; int data ; struct Node * rchild ; }; // 辅助函数：检查以 root 为根的子树是否平衡，返回高度；若不平衡返回 -1 int checkBalance ( struct Node * root ) { if ( root == NULL ) { return 0 ; // 空树高度为 0，平衡 } // 递归检查左子树 int leftHeight = checkBalance ( root -> lchild ); if ( leftHeight == - 1 ) { return - 1 ; // 左子树不平衡，向上传递 } // 递归检查右子树 int rightHeight = checkBalance ( root -> rchild ); if ( rightHeight == - 1 ) { return - 1 ; // 右子树不平衡，向上传递 } // 检查当前结点左右子树高度差 if ( abs ( leftHeight - rightHeight ) > 1 ) { return - 1 ; // 当前结点不平衡 } // 返回当前子树高度 return ( leftHeight > rightHeight ? leftHeight : rightHeight ) + 1 ; } // 主函数：判断二叉树是否平衡 bool isBalanced ( struct Node * root ) { return checkBalance ( root ) != - 1 ; } 【解析】 该算法基于递归实现，核心思想是在计算结点高度时同步判断平衡性，避免重复遍历。checkBalance 函数采用后序遍历顺序：先递归处理左右子树，再处理当前结点。若子树不平衡（返回 -1），则立即向上返回，无需进一步计算；否则比较左右子树高度差，若超过 1 则返回 -1 表示不平衡，否则返回当前子树高度。isBalanced 函数通过调用 checkBalance 检查返回值是否为 -1 来判断整棵树的平衡性。算法中每个结点仅访问一次，时间复杂度为 O(n)，n 为结点数；递归栈空间复杂度为 O(h)，h 为树高。这种设计既高效又简洁，符合题目要求。

（10 分）设某计算机有变址寻址、间接寻址和相对寻址方式，一个指令长等于一个存储字。设当前指令的地址码部分为 001AH，正在执行的指令所在地址为 1F05H，变址寄存器中的内容为 23A0H。已知存储器的部分地址及相应内容如下表所示：

（1）当执行取数指令时，如为变址寻址方式，取出的数为多少？ （2）如为间接寻址，取出的数为多少？ （3）设计算机每取一个存储字 PC 自动加 1，转移指令采用相对寻址，当执行转移指令时，转移地址为多少？若希望转移到 23A0H，则指令的地址码部分应设为多少？

指令寻址方式

[tag_link]

**【解析】** 本题考查指令的寻址方式。前两小题涉及数据寻址，其最终目的是寻址操作数，第 3 小题涉及指令寻址，其目的是寻址下一条将要执行的指令地址。下表列出了基本的寻址方式，其中偏移寻址包括变址寻址、基址寻址和相对寻址三种方式。

特别注意相对寻址方式中的 PC 值更新的问题：根据历年统考真题，通常在取出当前指令后立即将 PC 的内容加 1（或加增量），使之变成下条指令的地址。

(1) 变址寻址时，操作数 $S=((Rx)+A)=(23A0H+001AH)=(23BAH)=1748H$ 。

(2) 间接寻址时，操作数 $S=((A))=((001AH))=(23A0H)=2600H$ 。

(3) 转移指令使用相对寻址，因为指令字长等于存储字长，PC 每取出一条指令后自动加 1，因此转移地址 = (PC) + 1 + A = 1F05H + 1 + 001AH = 1F20H。若希望转移到 23A0H，则指令的地址码部分应为 $23A0H-(PC)-1=23A0H-1F05H-1=049AH$ 。

（11 分）设有一个 CPU 的指令执行部件如下图所示，由 Cache 每隔 100ns 提供 1 条指令。（注：B1、B2 和 B3 是三个相同的并行部件）

（1）画出该指令流水线功能段的时空图。

（2）试计算流水线执行这 4 条指令的实际吞吐率和效率。

流水线概念

[tag_link]

【解析】 本题考查用时空图描述流水线的工作过程和流水线性能的计算方法。本题中的流水线使用重复设置瓶颈段的方法来消除瓶颈。B1、B2 和 B3 段是本题的关键，分为 3 条路径，每条都是 300ns，完全可以满足流水线的输入。

（1）在流水线的 B 段，可以同时并行执行 3 条指令。流水线的时空图如下所示。 [图片]

（2）完成 4 个任务的周期数为 T=(100+100+100+300+100+300)ns=1000ns；任务数为 N=4；则有吞吐率为： TP = T N ​ = 1000 4 ​ × 1 0 9 = 0.4 × 1 0 7 （条指令 / 秒） 流水线的效率为： 流水线的效率 = 总面积 任务所占面积 ​ = 7 × 10 ( 4 × 4 + 3 × 4 ) ​ = 40%

（7 分）兄弟俩共同使用一个账号，每次限存或取 10 元，存钱与取钱的进程分别如下所示：

由于兄弟俩可能同时存钱和取钱，因此这两个进程是并发的。若哥哥先存了两次钱，但在第三次存钱时，弟弟在取钱。请问：

（1）最后账号 amount 上面可能出现的值？ （2）如何用 P、V 操作实现两并发进程的互斥执行？

进程和线程 进程概念

[tag_link]

**【答案】** （1）最后账号 `amount` 可能出现的值为 10、20 或 30。 （2）使用 P、V 操作实现互斥：定义一个信号量 `mutex` 并初始化为 1。在存钱进程 `SAVE()` 和取钱进程 `TAKE()` 中，在访问共享变量 `amount` 的代码段前后分别执行 `P(mutex)` 和 `V(mutex)`，确保同一时刻只有一个进程进入临界区。

**【解析】** 假设存钱进程 `SAVE()` 和取钱进程 `TAKE()` 的正确逻辑为：

• `SAVE()`：读取 `amount` 到局部变量，加 10，再写回 `amount`。
• `TAKE()`：读取 `amount` 到局部变量，减 10，再写回 `amount`。 哥哥先存了两次钱，`amount` 从 0 增加到 20。第三次存钱时，弟弟同时取钱，两个进程并发执行，由于没有互斥保护，它们的操作可能交错执行，导致竞态条件。

考虑第三次存钱和取钱的交错情况：

• 若存钱先完整执行，再取钱执行：存钱后 `amount=30`，取钱后 `amount=20`，最终为 20。
• 若取钱先完整执行，再存钱执行：取钱后 `amount=10`，存钱后 `amount=20`，最终为 20。
• 若操作交错：例如存钱读取 20 后，取钱也读取 20，然后存钱写入 30，取钱写入 10，最终为 10；或类似交错导致存钱写入覆盖取钱结果，最终为 30。 因此，`amount` 可能为 10、20 或 30。

为实现互斥，引入信号量 `mutex` 并初始化为 1。在 `SAVE()` 和 `TAKE()` 中，将访问 `amount` 的代码段作为临界区，在进入前执行 `P(mutex)`（申请资源），退出后执行 `V(mutex)`（释放资源）。这样，任何时刻只有一个进程能执行临界区代码，避免数据不一致。修改后的代码示例如下：

semaphore mutex = 1;

SAVE() {
    P(mutex);
    int m1 = amount;
    m1 = m1 + 10;
    amount = m1;
    V(mutex);
}

TAKE() {
    P(mutex);
    int m2 = amount;
    m2 = m2 - 10;
    amount = m2;
    V(mutex);
}
`

通过 P、V 操作确保进程互斥执行，保证 `amount` 操作的原子性。

（7 分）设一个没有设置快表的虚拟页式存储系统，页面大小为 100 字节。一个仅有 460 个字节的程序有下述内存访问序列（下标从 0 开始）： 10、11、104、170、73、309、185、245、246、434、458、364。 为该程序分配有 2 个可用页帧（Page frame）。试问：

（1）试叙述缺页中断与一般中断的主要区别？ （2）若分别采用 FIFO 和 LRU 算法，试计算访问过程中发生多少次缺页中断？ （3）若一次访存的时间是 10ms，平均缺页中断处理时间为 25ms，为使该虚拟存储系统的平均有效访问时间不大于 22ms，则可接受的最大缺页中断率是多少？

缺页异常

[tag_link]

**【解析】** 本题考查缺页中断和页面置换算法。

（1）缺页中断是一种特殊的中断，它与一般中断的区别是： ① 在指令执行期间产生和处理中断信号。CPU 通常在一条指令执行完后检查是否有中断请求，而缺页中断是在指令执行时间，发现所要访问的指令或数据不在内存时产生和处理的； ② 一条指令在执行期间可能产生多次缺页中断。如一条读取数据的多字节指令，指令本身跨越两个页面，若指令后一部分所在页面和数据所在页面均不在内存，则该指令的执行至少产生两次缺页中断。

（2）每个页面大小为 100 字节，则页面的访问顺序如下：

采用 FIFO 算法的页面置换情况如下表，共产生缺页中断 6 次。

采用 LRU 算法的页面置换情况如下表，共产生缺页中断 7 次。

（3）设可接受的最大缺页中断率为 $p$ 。若要访问页面在内存中，一次访问的时间是 10ms（访问内存页表）+ 10ms（访问内存）= 20ms。如果不在内存，所花时间为 10ms（访问内存页表）+ 25ms（中断处理）+ 10ms（访问内存页表）+ 10ms（访问内存）= 55ms。

平均有效访问时间： $$20\text{ms}\times (1-p)+55\text{ms}\times p\le 22\text{ms}$$

解得可接受的最大缺页中断率 $p$ 为 5.7%。

（9 分）设有 4 台主机 A、B、C 和 D 都处在同一物理网络中，它们的 IP 地址分别为：

子网掩码都是 255.255.255.224。请回答：

（1）该网络的 4 台主机中哪些可以直接通信？哪些需要通过设置路由器才能通信？请画出网络连接示意图，并注明各个主机的子网地址和主机地址。 （2）如要加入第 5 台主机 E，使它能与主机 D 直接通信，其 IP 地址的范围是多少？ （3）若不改变主机 A 的物理位置，而将其 IP 改为 192.155.28.168，则它的直接广播地址和本地广播地址各是多少？若使用本地广播地址发送信息，请问哪些主机能够收到？ （4）若要使该网络中的 4 台主机都能够直接通信，可采取什么办法？

子网划分

[tag_link]

**【解析】** 本题考查 IPv4 的地址特点、子网划分方法及网络设备的应用。子网掩码为 255.255.255.224，仅和第四字节有关，转换为二进制 255.255.255.11100000。把主机的地址转换为二进制，并和子网掩码做“与”运算，就可求出其网络地址。具体如下所示：

（1）只有处于同一个网络的主机之间才能直接通信，因此，如上表所示，只有主机 A 和主机 B 在同一个子网（192.155.28.96）内，因此只有主机 A 和主机 B 之间才可以直接通信。主机 C 和主机 D，以及它们同 A 和 B 的通信必须经过路由器。

`A       主机地址  192.155.28.112     子网地址  192.155.28.96
B       主机地址  192.155.28.120     子网地址  192.155.28.96
C       主机地址  192.155.28.135     子网地址  192.155.28.128
D       主机地址  192.155.28.202     子网地址  192.155.28.192
`

（2）若要加入第 5 台主机 E，使它能与 D 直接通信，那么主机 E 必须位于和 D 相同的网络中，即 192.155.28.192，子网地址为 192.155.28.110|0 1010，即地址范围是去掉主机号为全 0 和全 1 的，以及 D 的主机号，就是 192.155.28.110|0 0001 到 192.155.28.110|1 1110（且不包括 192.155.28.202）这样地址范围是 192.155.28.193 到 192.155.28.222，注意要除掉 192.155.28.202。

（3）主机 A 地址改为 192.155.28.168，那么它所处的网络为 192.155.28.160。由定义，直接广播地址是主机号各位全为“1”，用于任何网络向该网络上所有的主机发送报文，每个子网的广播地址则是直接广播地址。本地广播地址，又称为有限广播地址，它的 32 位全为“1”，用于该网络不知道网络号时内部广播。因此，主机 A 的直接广播地址为 192.155.28.191，本地广播地址是 255.255.255.255，若使用本地广播地址发送信息，所有本地主机都能够收到，即主机 B，需要注意的是，路由器不会转发本地广播的包。

注意：关于本地广播和直接广播有很多同学弄不明白，这里说一下。 TCP/IP 规定，主机号全为“1”的网络地址用于广播之用，叫做广播地址。所谓广播，指同时向网上所有主机发送报文。广播地址包含一个有效的网络号和主机号，技术上称为直接广播地址。在网间网络的任何一点均可向其他任何网络进行直接广播，但直接广播有一个缺点，就是要知道信宿网络的网络号；另一个是采用直接广播地址的广播分组可能会被路由器转发，即外部网络的用户将会截取到这种广播分组，从而降低了网络的安全性。如果只需在本网络内部广播，但又不知道本网络网络号。TCP/IP 规定，32 比特全为“1”的网间网络地址用于本网广播，该地址叫做有限广播地址，即本地广播地址。

（4）若希望 4 台主机直接通信，可以修改子网掩码为 255.255.255.0，这样 4 台主机就处于一个网络中，可以直接通信。