模拟卷 2

选择题

一、单项选择题：第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。

1

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

y = 0;
while (n >= (y+1) * (y+1))
    y++;

正确答案：D
【解析】
程序片段中，变量 y 从 0 开始，每次循环迭代 y 增加 1。循环条件为

n \geq (y + 1)^{2}

，即

(y + 1)^{2} \leq n

时循环继续。因此，循环执行的次数取决于满足该条件的最大整数 y。
设循环迭代了 k 次，则 k 满足

k^{2} \leq n

且

(k + 1)^{2} > n

，这意味着 k 是

⌊ n ⌋

。循环迭代次数与

n

成正比，故时间复杂度为

O (n)

。
其他选项中，

O (lo g n)

、

O (n)

和

O (n lo g n)

均与迭代次数不符。

2

循环队列用数组 A[0...m-1] 存放其元素值，头尾指针分别为 front 和 rear，front 指向队头元素，rear 指向队尾元素的下一个元素，其移动按数组下标增大的方向进行（rear != m-1 时），则当前队列中的元素个数是（　）。

正确答案：A

【解析】在循环队列中，front 指针指向队头元素，rear 指针指向队尾元素的下一个位置。队列中的元素从 front 开始，到 rear 的前一个位置结束。由于数组是循环的：

当 rear ≥ front 时，元素个数为 rear − front；
当 rear < front 时，表示 rear 已从数组末尾绕回到开头，此时元素个数为 (rear + m) − front，即 rear − front + m。

综合这两种情况，元素个数可统一表示为
(rear − front + m) % m，
该公式通过取模运算确保结果始终为非负整数且正确反映队列长度。

其他选项中：

B 项 (rear − front + 1) % m 在队列为空（front == rear）时会得到 1，而非 0；
C 项 rear − front − 1 在空队列时得到 −1，且不适用于循环情况；
D 项 rear − front 在 rear < front 时会产生负数，未考虑循环特性。

因此，只有 A 项适用于所有情况。

3

将 5 个字母 “ooops” 按此顺序进栈，则有（　）种不同的出栈顺序可以仍然得到 “ooops”。

正确答案：C

【解析】 将5个字母“ooops”按顺序进栈，即进栈序列为o、o、o、p、s。要求出栈序列仍然为“ooops”，即出栈顺序为o、o、o、p、s。由于三个o相同，不同的出栈顺序指的是三个o的个体出栈顺序不同，但最终输出的字符串相同。

设三个o分别为A、B、C（按进栈顺序），p为D，s为E。出栈序列必须满足前三个为A、B、C的某种排列，第四个为D，第五个为E。三个o的排列共有6种：ABC、ACB、BAC、BCA、CAB、CBA。需要检查每种排列是否满足栈的合法性（即能否通过合理的进栈和出栈操作实现）。

ABCDE：合法，可每进栈一个元素后立即出栈。
ACBDE：合法，A进栈后出栈，B进栈后不出，C进栈后出栈C，再出栈B。
BACDE：合法，A进栈后不出，B进栈后出栈B，再出栈A，然后C、D、E依次进栈出栈。
BCADE：合法，A进栈后不出，B进栈后出栈B，C进栈后出栈C，再出栈A。
CABDE：不合法，因为C首先出栈后，栈中剩余A和B（B为栈顶），下一个需要出栈A，但A不在栈顶，无法直接出栈。
CBADE：合法，A进栈后不出，B进栈后不出，C进栈后出栈C，再出栈B，最后出栈A。

因此，只有5种合法的出栈顺序，对应选项C。

4

设高度为 100 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数最少为（　）。

正确答案：C

【解析】 首先，由题意可知，二叉树中只有度为0和度为2的结点，根据二叉树性质，有 $n_{0} = n_{2} + 1$ （其中 $n_{0}$ 为叶子结点数， $n_{2}$ 为度为2的结点数），因此总结点数 $n = n_{0} + n_{2} = 2 n_{2} + 1$ ，即 $n$ 必为奇数，排除选项A和D。

其次，考虑最小结点数的情况。高度为100通常指树的层数为100（根结点在第1层）。为了使结点数最少，树应形成一种“偏斜”形状：每个内部结点（度为2）有一个子结点为内部结点延续高度，另一个子结点为叶子结点。这样，从根到最深叶子路径上的结点均为内部结点（除最深叶子外），且每个内部结点附带一个不在该路径上的叶子结点。

具体计算：设高度为 $h$ （层数），则路径上有 $h$ 个结点，其中前 $h - 1$ 层为内部结点，第 $h$ 层为叶子结点。内部结点数为 $h - 1$ ，每个内部结点附带一个叶子结点，故附加叶子结点数为 $h - 1$ ，加上路径上的叶子结点1个，总叶子结点数为 $h$ 。因此总结点数 $n = (h - 1) + h = 2 h - 1$ 。代入 $h = 100$ ，得 $n = 2 \times 100 - 1 = 199$ 。

若高度定义为边数，则最小结点数为 $2 h + 1 = 201$ ，但结合常见教材定义（高度指层数）及选项奇偶性，本题应取层数定义，故最小结点数为199。

5

由某种序列可以唯一地确定一棵二叉树，不能唯一地确定一棵二叉树是（　）。

正确答案：D

【解析】 在二叉树的遍历序列中，不同的序列组合对二叉树结构的确定能力不同。已知先序序列和中序序列可以唯一确定一棵二叉树，因为先序序列提供根节点信息，中序序列区分左右子树；同样，后序序列和中序序列也可以唯一确定二叉树，原理类似。

中序序列和层序序列也能唯一确定二叉树，因为层序序列给出层次顺序，结合中序序列的左右子树信息，可以通过递归方式重建二叉树。

然而，先序序列和层序序列不能唯一确定二叉树。例如，考虑只有两个节点A和B的二叉树：若B是A的左子节点，先序序列为A、B，层序序列为A、B；若B是A的右子节点，先序序列同样为A、B，层序序列也为A、B。这两个不同的二叉树产生了相同的先序和层序序列，因此无法唯一确定结构。

因此，不能唯一确定二叉树的选项是D。

6

在含有 15 个结点的平衡二叉树上，查找关键字为 28（存在该结点）的结点，则依次比较的关键字有可能是（　）。

正确答案：C

【解析】 在平衡二叉树（如AVL树）中查找结点时，比较序列必须遵循二叉搜索树的性质：若目标值小于当前结点值，则进入左子树；若大于，则进入右子树。同时，树有15个结点且平衡，高度约为 log₂15≈4，因此查找路径上的结点数通常不超过4个（对应高度为3）。

选项A：比较30后，28<30应进入左子树，但下一个比较36>30，不可能进入左子树，违反二叉搜索树性质。
选项B：比较38后，28<38应进入左子树，但下一个比较48>38，不可能进入左子树，同样违反性质。
选项C：序列48,18,38,28符合二叉搜索树性质：28<48进入左子树；28>18进入右子树；28<38进入左子树；找到28。路径长度为4，对应树高度为3，对于15个结点的平衡二叉树是可能的，可以通过调整其他结点保持平衡。
选项D：序列60,20,50,40,38,28虽符合二叉搜索树性质，但路径长度为6，对应树高度至少为5。对于15个结点的平衡二叉树，高度为5至少需要20个结点（如AVL树的最小结点数要求），因此不可能在保持平衡的前提下存在这样的查找路径。

综上，只有选项C可能。

7

对于一组权值都相等的 16 个字母，构造相应的哈夫曼树，这棵哈夫曼树是一棵（　）。

正确答案：C

【解析】 哈夫曼树的构造过程中，每次合并都是将两个权值最小的节点合并为一个新的内部节点，因此每个内部节点都恰好有两个子节点，而叶子节点则没有子节点。根据二叉树的定义，如果一棵二叉树中的每个节点要么是叶子节点（无子节点），要么是有两个子节点的内部节点，那么这棵树称为满二叉树（或称严格二叉树）。因此，无论权值是否相等，哈夫曼树总是满足这一条件，它必然是一棵满二叉树。

对于本题中权值相等的16个字母，构造出的哈夫曼树同样符合这一性质：每个内部节点都有两个子节点，所以它是一棵满二叉树。虽然权值相等时，通过特定的合并顺序可能使树的结构更加平衡（例如形成完全二叉树），但满二叉树这一性质是始终成立的。其他选项如完全二叉树或一般二叉树不一定必然满足，而满二叉树则是哈夫曼树的固有特征，故选项C正确。

8

下列关于 B-树和 B+树的叙述中，不正确的是（　）。

正确答案：A

【解析】 在B-树和B+树的比较中，B+树由于所有数据存储在叶子节点且叶子节点通过指针链接成有序链表，可以高效地进行顺序查找（即范围查询或全表扫描）。而B-树的数据分布在整个树的节点中，叶子节点之间没有直接链接，进行顺序查找时需要从根节点开始反复进行树搜索，效率较低。因此，B-树不能像B+树那样有效地支持顺序查找，选项A的叙述不正确。

选项B正确，因为B-树和B+树都是平衡的多路搜索树，所有叶子节点处于同一层，保持了树的平衡性。选项C正确，两者都支持基于键值的随机查找，查找时间复杂度与树高相关，效率较高。选项D正确，B-树和B+树在数据库和文件系统中被广泛用作索引结构，以优化数据存取性能。

9

对一组数据（25,84,21,47,15,27,68,35,20）进行排序，前三趟的排序结果如下：

第一趟：20,15,21,25,47,27,68,35,84
第二趟：15,20,21,25,35,27,47,68,84
第三趟：15,20,21,25,27,35,47,68,84

则所采用的排序方法是（　）。

正确答案：D
【解析】 观察初始序列（25,84,21,47,15,27,68,35,20）和前三趟结果：第一趟后25位于序列中间，其左侧元素（20,15,21）均小于25，右侧元素（47,27,68,35,84）均大于25，这表明25在第一趟后已到达其最终排序位置，符合快速排序“选取基准并分区”的特点。第二趟和第三趟继续对左右子序列进行类似分区操作，逐步使整个序列有序。选择排序每趟应将最小元素置于前端，但第一趟结果中最小元素15不在首位，故排除；希尔排序基于增量分组排序，结果通常不每趟使基准元素就位；归并排序通过合并有序子序列实现，早期阶段元素不会快速定位到最终位置。因此，所给过程与快速排序一致。

10

对一组数据（84,47,15,21,25）排序，数据在排序的过程中的变化如下：

(1) 84 47 15 21 25
(2) 25 47 15 21 84
(3) 21 25 15 47 84

则所采用的排序方法是（　）。

正确答案：C

【解析】 观察排序过程中的变化：初始序列为 (84,47,15,21,25)。第一步变为 (25,47,15,21,84)，这类似于快速排序中选择第一个元素 84 作为枢轴进行分区的结果：将小于 84 的元素移至左边，大于的移至右边，最终 84 被放置到正确位置（末尾）。第二步变为 (21,25,15,47,84)，这对应于对左子序列 (25,47,15,21) 进行快速排序的分区操作，选择 25 作为枢轴，经过交换和调整后得到此序列。这些步骤符合快速排序的分区递归特性。

其他排序方法不符：冒泡排序每趟通过相邻交换将最大元素移至末尾，第一趟后应为 (47,15,21,25,84)，与第二步不同；插入排序逐步构建有序序列，不会直接将 84 移至末尾；堆排序需先建堆再交换调整，但第二步到第三步的变化不似堆调整过程。因此，所选方法为快速排序。

11

下列排序方法中，时间性能与待排序记录的初始状态无关的是（　）。

正确答案：C

【解析】 排序算法的时间性能是否与初始状态相关，取决于其时间复杂度在不同输入情况下的变化。
插入排序在最好情况下（已排序）时间复杂度为 $O (n)$ ，最坏和平均为 $O (n^{2})$ ，因此与初始状态有关；快速排序的平均时间复杂度为 $O (n lo g n)$ ，但最坏情况下（如已排序数组且枢轴选择不当时）会退化到 $O (n^{2})$ ，也与初始状态有关。

归并排序采用分治策略，无论输入数据是否有序，其时间复杂度稳定为 $O (n lo g n)$ ，与初始状态无关；选择排序始终通过遍历未排序部分寻找最小（或最大）元素，其最好、最坏和平均时间复杂度均为 $O (n^{2})$ ，因此也与初始状态无关。

选项 C 中的选择排序和归并排序均满足时间性能与初始状态无关的条件，而其他选项至少包含一种与初始状态相关的算法，故 C 为正确答案。

12

对汇编语言程序员来说，以下部件中不透明的是（　）。

I. 指令缓冲器
II. 移位器
III. 通用寄存器
IV. 中断寄存器
V. 乘法器
VI. 先行进位链

正确答案：C

【解析】 在计算机体系结构中，对汇编语言程序员“不透明”的部件是指程序员需要直接了解或操作的部件，而“透明”的部件则由硬件自动管理，程序员无需关心其具体实现。

对于各个部件的分析如下：

I. 指令缓冲器：用于缓存指令，由硬件自动管理，程序员不直接控制，因此是透明的。
II. 移位器：执行移位操作，程序员通过移位指令（如SHL、SHR）使用，但移位器内部实现不可见，因此是透明的。
III. 通用寄存器：程序员在指令中直接指定寄存器来存储数据和进行计算，是汇编编程的基础，因此是不透明的。
IV. 中断寄存器：用于处理中断，程序员需要配置中断处理程序、设置中断向量等，在系统编程中直接操作，因此是不透明的。
V. 乘法器：执行乘法运算，程序员通过乘法指令（如MUL）使用，但乘法器本身是硬件单元，内部实现不可见，因此是透明的。
VI. 先行进位链：用于加速加法器，完全是硬件细节，程序员无需关心，因此是透明的。

综上所述，不透明的部件是III（通用寄存器）和IV（中断寄存器），对应选项C。

13

一个 8 位的二进制整数，若采用补码表示，且由 3 个“1”和 5 个“0”组成，则最小值为（　）。

正确答案：C

【解析】 在 8 位补码表示中，最高位是符号位：0 表示正数，1 表示负数。由于要求最小值，该数必为负数，因此符号位必须为 1。已知该数由 3 个“1”和 5 个“0”组成，因此符号位占用一个“1”，剩余 7 位由 2 个“1”和 5 个“0”组成。

补码表示中，负数的值计算公式为：

- 128 + (剩余 7 位的无符号值)

要使得数值最小，需要剩余 7 位的无符号值尽可能小。

剩余 7 位中，无符号值最小的情况是将两个“1”放在最低位（即第 0 位和第 1 位），此时剩余 7 位二进制为 0000011，对应的无符号值为 3。因此整个 8 位二进制数为 10000011。

计算数值：

- 128 + 3 = - 125

即选项 C。

验证其他选项：

-127 的补码为 10000001，只有 2 个“1”，不符合条件；
-32 的补码为 11100000，虽符合 3 个“1”和 5 个“0”，但值为 -32，大于 -125；
-3 的补码为 11111101，有 7 个“1”，不符合条件。

因此，最小值为 -125。

14

单精度 IEEE754 标准规格化的 float 类型所能表示的最接近 0 的负数是（　）。

正确答案：A

【解析】 单精度 IEEE754 浮点数采用 32 位表示，包含 1 位符号位、8 位指数位和 23 位尾数位。
规格化数的指数位不全为 0 也不全为 1，实际指数 $E = e - 127$ （其中 $e$ 为指数位的无符号值），范围在 $- 126$ 到 $127$ 之间；尾数部分隐含最高位 1，即实际尾数 $M = 1 + f$ （ $f$ 为尾数位表示的小数）。规格化负数的值为：

- (1 + f) \times 2^{E}

最接近 0 的负数需绝对值最小，因此应取最小指数 $E = - 126$ （对应 $e = 1$ ）和最小尾数 $M = 1$ （对应 $f = 0$ ）。代入公式得：

- 1 \times 2^{- 126} = - 2^{- 126}

即选项 A。

选项 B 和 C 涉及因子 $2^{- 23}$ ，对应于非规格化数（指数 $e = 0$ 时尾数无隐含 1），不符合本题要求的规格化数条件；选项 D 的指数 $- 127$ 低于规格化指数最小值 $- 126$ ，不符合规格化规则。因此，只有 A 正确。

15

下列关于 DRAM 和 SRAM 的说法中，错误的是（　）。

I. SRAM 不是易失性存储器，而 DRAM 是易失性存储器
II. DRAM 比 SRAM 集成度更高，因此读写速度也更快
III. 主存一般由 DRAM 构成，而高速缓存一般由 SRAM 构成
IV. 与 SRAM 相比，DRAM 由于需要刷新，所以功耗较高

正确答案：D

【解析】本题考查 SRAM 和 DRAM 的区别。SRAM 和 DRAM 的差别在于 DRAM 时常需要刷新，但是 SRAM 和 DRAM 都属于易失性存储器，掉电就会丢失，I 错误。SRAM 的集成度虽然更低，但速度更快，因此通常用于高速缓存 Cache，而 DRAM 则是读写速度偏慢，集成度更高，因此通常用于计算机内存，II 错误。主存可以用 SRAM 实现，只是成本高且容量相对小，III 错误。和 SRAM 相比，DRAM 成本低、功耗低、但需要刷新，IV 错误。

注意：SRAM 和 DRAM 的特点见下表。

RAM 类型	特点
SRAM	非破坏性读出，不需要刷新。断电信息即丢失，属易失性存储器。存取速度快，但集成度低，功耗较大，常用于 Cache。
DRAM	破坏性读出，需要定期刷新。断电信息即丢失，属易失性存储器。集成性高、位价低、容量大和功耗低。存取速度比 SRAM 慢，常用于大容量的主存系统。

16

某计算机的存储系统由 Cache-主存系统构成，Cache 的存取周期为 10ns，主存的存取周期为 50ns。在 CPU 执行一段程序时，Cache 完成存取的次数为 4800 次，主存完成的存取次数为 200 次，该 Cache-主存系统的效率是（　）。（设 Cache 和主存不能同时访问）

正确答案：A

首先，计算总存取次数：高速缓存完成 4800 次，主存完成 200 次，总次数为

4800 + 200 = 5000

命中率

H = 高速缓存存取次数 / 总次数 = \frac{4800}{5000} = 0.96

由于高速缓存和主存不能同时访问，当高速缓存命中时，访问时间仅为高速缓存的存取周期 10 ns；当高速缓存未命中时，需要先访问高速缓存（耗时 10 ns），发现未命中后再访问主存（耗时 50 ns），总时间为

10 ns + 50 ns = 60 ns

平均访问时间

T_{avg} = H \times T_{cache} + (1 - H) \times (T_{cache} + T_{mem})

代入数值

T_{avg} = 0.96 \times 10 ns + 0.04 \times (10 ns + 50 ns) = 9.6 ns + 0.04 \times 60 ns = 9.6 ns + 2.4 ns = 12 ns

也可使用简化公式

T_{avg} = T_{cache} + (1 - H) \times T_{mem} = 10 ns + 0.04 \times 50 ns = 10 ns + 2 ns = 12 ns

两种公式结果一致，因为

H \times T_{cache} + (1 - H) \times (T_{cache} + T_{mem}) = T_{cache} + (1 - H) \times T_{mem}

效率 $e$ 定义为高速缓存存取周期与平均访问时间的比值，即

e = \frac{T _{cache}}{T _{avg}} = \frac{10 ns}{12 ns} \approx 0.8333

对应选项 A。

17

在运算类的零地址指令中，它的操作数来自（　）。

正确答案：D

【解析】 零地址指令在指令格式中没有显式的地址字段，操作数的来源是隐含的。对于运算类的零地址指令，通常用于堆栈型计算机架构。在这种架构中，操作数存储在堆栈的顶部，执行运算时，指令会从堆栈中弹出所需操作数。例如，加法指令会弹出栈顶和次栈顶的两个操作数进行相加，然后将结果压回堆栈。因此，运算类零地址指令的操作数直接来自栈顶和次栈顶。

选项A、B、C均不符合零地址指令的特点：A中的暂存器和总线常见于其他寻址方式；B中的寄存器通常对应一地址或二地址指令；C中的ALU是运算单元，而非操作数来源。只有D正确描述了零地址指令在堆栈架构下的操作数来源。

18

在微程序控制器中，以下说法正确的是（　）。

I. 采用微程序控制方式的处理器称为微处理器
II. 每一条机器指令由一个微程序来解释执行
III. 在微指令的编码中，执行效率最低的是直接编码方式
IV. 水平型微指令能充分利用数据通路的并行结构

正确答案：B

【解析】
首先分析每个说法的正确性：

说法 I 错误。采用微程序控制方式的处理器不一定称为微处理器，微处理器通常指中央处理单元的集成芯片，其控制方式可以是微程序控制或硬连线控制，因此该说法不准确。

说法 II 正确。在微程序控制器中，每一条机器指令确实对应一个微程序，由该微程序中的微指令序列来解释和执行指令，这是微程序控制的基本原理。

说法 III 错误。微指令的编码方式中，直接编码（直接控制）方式每个控制位直接对应一个控制信号，无需解码，并行性高、执行速度快，因此执行效率较高，而不是最低。效率较低的方式通常是字段编码等需要解码的垂直型微指令。

说法 IV 正确。水平型微指令具有较长的微指令字，每个位或字段可直接控制数据通路的多个操作，允许在同一周期内发出多个控制信号，从而充分利用数据通路的并行结构。

综上，正确的说法是 II 和 IV，对应选项 B。

19

当微指令采用分段编码时，我们将互斥性微命令（　）。

正确答案：A

【解析】 在微指令的分段编码（也称为字段编码）设计中，微指令通常被划分为多个字段，每个字段控制一组相关的操作。互斥性微命令指的是那些不能在同一微周期内同时执行的微命令，例如对同一功能部件的不同操作。

为了确保这些互斥命令不会同时被激活，最有效的方法是将它们放置在同一个字段中。因为同一字段内的微命令通过编码方式表示，一次只能选择一个值，从而自然实现了互斥性。而不同字段的微命令可以并行执行，因为它们控制的是系统中不同的、独立的部件。

选项B中的多级译码通常用于字段间接编码，以扩展编码空间，但并非处理互斥命令的直接方法。选项C和D则不符合分段编码的设计原则，可能导致控制冲突或资源浪费。因此，正确答案是A，即将互斥性微命令放在同一段中。

20

在下列各种情况下，最应采用异步传输方式的是（　）。

正确答案：A

【解析】 异步传输方式适用于设备之间速度差异较大或无需共享时钟信号的场景，它通过握手信号（如就绪和确认）来协调数据传输，能有效处理不同速度设备间的通信。

选项A中，I/O接口与打印机交换信息时，打印机作为典型的慢速外部设备，其工作速度远低于计算机内部总线，采用异步传输可以灵活适应速度不匹配，避免数据丢失或冲突。

其他选项则更适合同步传输：CPU与主存交换信息需要高速、稳定的时钟同步以保证效率；CPU和PCI总线交换信息通常基于同步时钟设计；选项D直接提及统一时序信号控制，属于典型的同步方式。因此，最应采用异步传输的是A。

21

CPU 响应中断时，保护两个关键的硬件状态是（　）。

正确答案：A

【解析】 CPU响应中断时，必须保存当前程序的执行现场，以便在中断处理结束后能准确恢复原程序的运行。两个最关键的硬件状态是程序计数器（PC）和程序状态字（PSW）。PC存储了下一条要执行的指令地址，保护PC能确保中断返回后继续执行原程序；PSW包含了处理器的状态标志（如条件码、中断使能位等），保护PSW能维持处理器的状态一致性。

其他选项中，IR（指令寄存器）存放当前指令，但中断响应时通常不保护它，因为中断处理更关注未来执行的地址和整体状态；AR（地址寄存器）用于内存寻址，也不是必须保护的核心状态。因此，选项A正确。

22

1K×8 位 ROM 芯片和 1K×8 位 RAM 芯片的引脚（含地址与数据）的总数分别是（　）。

正确答案：C
【解析】
对于 1K×8 位的 ROM 和 RAM 芯片，存储容量均为 1K 个字，每个字 8 位。
1K 等于 1024，因此地址线需要 10 根（因为

2^{10} = 1024

），数据线需要 8 根。
地址与数据引脚的总数为

10 + 8 = 18

。
问题中“引脚（含地址与数据）的总数”通常指的是地址和数据引脚的总和，不包括控制引脚等其他引脚。
因此，无论是 ROM 还是 RAM，地址和数据引脚的总数都是 18，与选项 C 相符。

23

在操作系统中，以下只能在核心态下处理执行的指令是（　）。

正确答案：C

【解析】 在操作系统中，核心态（也称为内核态或特权态）与用户态是处理器的两种运行模式。核心态下可以执行所有指令，包括特权指令，而用户态下只能执行非特权指令，以防止用户程序直接访问系统资源或影响系统安全。

选项分析如下：

A. 读时钟：读取时钟值通常不是特权指令，用户程序可以通过非特权指令或系统调用来获取时间信息，因此可以在用户态下执行。

B. 寄存器清零：清零通用寄存器（如数据寄存器）是常见的非特权指令，用户程序可以自由操作自己的寄存器，无需切换到核心态。

C. 系统调用：系统调用是用户程序主动请求操作系统服务的机制。当执行系统调用指令（如陷阱指令）时，会触发处理器从用户态切换到核心态，由操作系统内核在核心态下处理该请求。因此，系统调用的处理过程只能在核心态下执行。

D. 取数：取数指令（如从内存加载数据）通常是非特权指令，用户程序在用户态下可以访问自己的内存空间。只有访问受保护的系统内存或执行特权操作时才需核心态。

综上，只有系统调用的处理必须在核心态下完成，故正确答案为C。

24

下列各种调度算法中，属于基于时间片的调度算法的是（　）。

I. 时间片轮转法
II. 多级反馈队列调度算法
III. 抢占式调度算法
IV. FCFS（先来先服务）调度算法
V. 高响应比优先调度算法

正确答案：A

【解析】 基于时间片的调度算法是指在调度过程中使用固定或可变的时间片来分配CPU时间，进程在时间片用完时会被抢占。下面对每个算法进行分析：

时间片轮转法是典型的基于时间片的调度算法，它为每个进程分配一个固定的时间片，时间片结束后进程被抢占并放回就绪队列末尾。多级反馈队列调度算法也属于基于时间片的算法，它使用多个队列，每个队列可能具有不同的时间片大小，进程在队列间移动时依据时间片进行调度。

抢占式调度算法是一个广义类别，指允许在进程运行期间将其中断的调度方式，但抢占不一定基于时间片，可能基于优先级或其他条件，因此它不特指基于时间片的算法。FCFS（先来先服务）调度算法是非抢占式的，进程一旦开始运行直到完成或阻塞，不使用时间片。高响应比优先调度算法同样是非抢占式的，基于计算响应比来选择进程，不涉及时间片。

因此，属于基于时间片的调度算法的只有Ⅰ和Ⅱ，对应选项A。

25

在某个十字路口，每个车道只允许一辆汽车通过，且允许直行、左拐和右拐，如图 1 所示。如果把各个方向的车看成进程，则需要对这些进程进行同步，那么这里临界资源个数至少应该有（　）个。

正确答案：C

【解析】

不妨如上图所示，把十字路口车道的公共区域分为 4 块，分别为图上的 1、2、3、4，直行的车辆需要获得该方向上的两个邻近的临界资源，如北方开来的车辆需要获得 1、2 两个临界资源。南方开来的车需要获得 3、4 两个临界资源。而往右转的车辆则只需要获得一个临界资源，比如北方来车右转的情况需要获得 1 这个临界资源。左转的情况需要获得 3 个临界资源，比如北方来车左转组需要 1、2、3 号临界资源。综上所述，4 个临界资源便可以很好地保证车子不相撞（即互斥的效果）。当然只用 4 个信号量还是很容易造成死锁的，不过这并不是本题要考虑的问题，题目中问到的是至少用几个信号量。

也可以用排除法来做该题，该路口可以有南北方向车同时直行，所以临界资源个数大于或等于 2，排除 A。该路口可以 4 个方向车都左转，所以临界资源个数大于或等于 4，排除 B。D 选项通常不会选，所以选 C。

26

对于两个并发进程，设互斥信号量为 mutex，若 mutex=0，则表示（　）。

正确答案：B
【解析】 互斥信号量 mutex 用于控制进程对临界区的访问，其初始值通常为 1，表示没有进程进入临界区。当 mutex=0 时，表示有一个进程已经成功执行了 P(mutex) 操作（即 wait 操作），将 mutex 减 1 后变为 0，这意味着该进程进入了临界区，且当前没有其他进程在等待进入临界区（因为等待时 mutex 会变为负值）。因此，选项 B 正确。选项 A 错误，因为 mutex=0 表示有进程在临界区内；选项 C 和 D 错误，因为 mutex=0 时没有进程等待，等待发生时 mutex 值会小于 0。

27

有两个优先级相同的并发程序 P1 和 P2，它们的执行过程如下所示，假设当前信号量 s1=0，s2=0。当前的 z=2，进程运行结束后，x、y 和 z 的值分别是（　）。

进程 P1

...
y = 1;
y = y + 2;
z = y + 1;
V(s1);
P(s2);
y = z + y;
...

进程 P2

...
x = 1;
x = x + 1;
P(s1);
x = x + y;
z = x + z;
V(s2);
...

正确答案：C

【解析】 首先分析进程同步关系。信号量 s1 和 s2 初始值为 0，因此 P2 中的 P(s1) 必须等待 P1 执行 V(s1) 后才能继续，而 P1 中的 P(s2) 必须等待 P2 执行 V(s2) 后才能继续。这强制了执行顺序：P1 必须先执行到 V(s1)，P2 才能执行 P(s1) 之后的代码；P2 必须执行到 V(s2)，P1 才能执行 P(s2) 之后的代码。

具体执行顺序如下：

P1 执行：
$y = 1$ → $y = 1 + 2 = 3$ → $z = y + 1 = 3 + 1 = 4$ （覆盖初始 $z = 2$ ）→ V(s1) 使 $s 1 = 1$ 。
P1 执行 P(s2)，但 $s 2 = 0$ ，因此阻塞。
P2 执行：
$x = 1$ → $x = 1 + 1 = 2$ → P(s1) 因 $s 1 = 1$ 而继续， $s 1 = 0$ → $x = x + y = 2 + 3 = 5$ （此时 $y = 3$ 来自 P1）→ $z = x + z = 5 + 4 = 9$ （此时 $z = 4$ 来自 P1）→ V(s2) 使 $s 2 = 1$ 。
P1 因 $s 2 = 1$ 而唤醒，执行 $y = z + y = 9 + 3 = 12$ （此时 $z = 9$ 来自 P2， $y = 3$ 来自之前）。

最终， $x = 5$ ， $y = 12$ ， $z = 9$ ，对应选项 C。其他选项的数值与上述计算不符，因此 C 正确。

28

对外存对换区的管理应以（　）为主要目标。

正确答案：D

【解析】 对外存对换区（swap area）的管理是操作系统虚拟内存机制的关键部分，主要用于在物理内存不足时，将暂时不用的内存页换出到外存，并在需要时换入。这一过程直接影响系统的性能和用户体验。

管理对换区的主要目标应聚焦于优化交换操作的效率，因为换入换出速度直接决定了内存交换的延迟。如果换入换出速度慢，会导致进程频繁等待数据加载，增加响应时间，降低系统整体吞吐量。因此，提高换入、换出速度是对换区管理的核心目标，它通过减少交换延迟来提升系统性能。

相比之下，其他选项虽有一定关联，但并非主要目标。提高系统吞吐量（A）是最终效果之一，但更依赖于换入换出速度的优化；提高存储空间的利用率（B）重要，但对换区作为专用区域，其空间管理通常以支持快速交换为前提；降低存储费用（C）涉及硬件成本，而对换区管理更关注性能而非经济因素。因此，正确答案是D。

29

下列叙述中错误的是（　）。

I. 在请求分页存储管理中，若把页面的大小增加一倍，则缺页中断次数会减少一半
II. 分页存储管理方案在逻辑上扩充了主存容量
III. 在分页存储管理中，减少页面大小，可以减少内存的浪费，所以页面越小越好
IV. 一个虚拟存储器，其地址空间的大小等于辅存的容量加上主存的容量

正确答案：A
【解析】
I 错误：在请求分页存储管理中，缺页中断次数受程序访问局部性、工作集大小等多因素影响，增加页面大小可能减少缺页次数，但并非精确减半，叙述过于绝对。
II 正确：分页存储管理通过将进程地址空间划分为页面，并利用外存交换，使得进程可以使用比物理内存更大的逻辑地址空间，从而在逻辑上扩充了主存容量。
III 错误：减少页面大小虽可降低内部碎片，但会导致页表增大、管理开销上升，并可能增加缺页中断次数，因此页面并非越小越好。
IV 错误：虚拟存储器的地址空间大小由地址位数（如 CPU 寻址能力）决定，是逻辑概念，不等于主存与辅存容量之和；实际物理资源（主存和辅存）用于支持虚拟地址空间的映射和交换。
综上，错误叙述为 I、III 和 IV，对应选项 A。

30

在一个 64 位的计算机系统中，地址线宽为 64 位，实际使用的虚拟地址空间的大小是 $2^{48}$ 。若采用虚拟页式存储管理，每页的大小为 $2^{13}$ ，即 8KB，页表项长为 8 字节，采用多级页表进行管理，那么多级页表的级数最小是（　）。

正确答案：B

【解析】 虚拟地址空间大小为 $2^{48}$ 字节，页大小为 $2^{13}$ 字节，因此虚拟地址的页内偏移占 13 位，剩余 $48 - 13 = 35$ 位用于页表索引。每个页表项为 8 字节，页大小 $2^{13}$ 字节，故一页可容纳 $2^{13} /8 = 2^{10}$ 个页表项，即每个页表最多有 $2^{10}$ 个条目，对应每级页表索引最多占 10 位（满足 $2^{10} \times 8 \leq 2^{13}$ ）。

设多级页表级数为 $k$ ，每级索引位数分别为 $a_{1}, a_{2}, \dots, a_{k}$ ，需满足 $a_{1} + a_{2} + \dots + a_{k} = 35$ 且每个 $a_{i} \leq 10$ 。为最小化 $k$ ，应使每级索引位数尽可能大，即取 $a_{i} = 10$ 。当 $k = 3$ 时，最大索引位数为 $3 \times 10 = 30 < 35$ ，无法覆盖全部 35 位；当 $k = 4$ 时，可分配为 $10, 10, 10, 5$ （总和 35），每个 $\leq 10$ ，满足要求。因此最小级数为 4。

31

某文件系统物理结构采用三级索引分配方法，如果每个磁盘块的大小为 1024B，每个盘块索引号占用 4 字节，请问在该文件系统中，最大的文件长度约为（　）。

正确答案：A

【解析】
每个磁盘块大小为 1024 字节，每个盘块索引号占用 4 字节，因此一个索引块可以存储的索引号数量为

1024 \div 4 = 256

个。

在三级索引分配方法中，文件通过三级间接索引访问数据块：

顶级索引块（三级间接块）存储 256 个指针，每个指向一个二级索引块；
每个二级索引块存储 256 个指针，每个指向一个一级索引块；
每个一级索引块存储 256 个指针，每个指向一个数据块。

因此，总数据块数为

256 \times 256 \times 256 = 25 6^{3} = 2^{24}

块。

每个数据块大小为 1024 字节（即 $2^{10}$ 字节），所以最大文件长度为

2^{24} \times 2^{10} = 2^{34}

字节。

由于

1 GB = 2^{30} 字节

因此文件长度为

2^{34} \div 2^{30} = 2^{4} = 16 GB

故最大文件长度约为 16 GB，选项 A 正确。

32

设一个磁道访问请求序列为 55,58,39,18,90,160,150,38,184，磁头的起始位置为 100。若采用 SSTF（最近寻道时间优先）算法，则磁头移动（　）个磁道。

正确答案：D

【解析】
采用 SSTF 算法，磁头从起始位置 100 开始，每次选择距离当前磁头位置最近的请求进行服务。具体过程如下：

初始位置 100，距离最近的请求是 90（距离 10），磁头移动到 90，移动 10 磁道。
位置 90，最近请求是 58（距离 32），移动到 58，累计移动 42 磁道。
位置 58，最近请求是 55（距离 3），移动到 55，累计 45 磁道。
位置 55，最近请求是 39（距离 16），移动到 39，累计 61 磁道。
位置 39，最近请求是 38（距离 1），移动到 38，累计 62 磁道。
位置 38，最近请求是 18（距离 20），移动到 18，累计 82 磁道。
位置 18，剩余请求中最近的是 150（距离 132），移动到 150，累计 214 磁道。
位置 150，最近请求是 160（距离 10），移动到 160，累计 224 磁道。
位置 160，最后请求 184（距离 24），移动到 184，累计 248 磁道。

因此，磁头总移动磁道数为 248，对应选项 D。

33

在 OSI 参考模型中，为上一层提供可靠、无错误的数据信息的协议层是（　）。

正确答案：D
【解析】 在OSI参考模型中，传输层（第4层）负责实现端到端的可靠数据传输。它通过错误检测、重传机制、流量控制和序列号等手段，确保二进制信息块（如数据段）在系统间正确传输，并为上一层（会话层）提供无错误的数据服务。物理层仅负责原始比特流的传输，不涉及可靠性；数据链路层虽在相邻节点间提供帧的可靠传输，但局限于单条链路；网络层主要处理路由和寻址，不保证端到端的可靠性。因此，符合题目描述的协议层是传输层。

34

设信道带宽为 4KHz，信噪比为 30dB，按照香农定理，信道的最大数据速率约等于（　）。

正确答案：D

【解析】 根据香农定理，信道的最大数据速率由公式

C = B lo g_{2} (1 + S / N)

决定，其中 $C$ 为最大数据速率（单位 b/s）， $B$ 为信道带宽（单位 Hz）， $S / N$ 为信噪比线性值。

题目给出带宽 $B = 4 kHz = 4000 Hz$ ，信噪比为 $30 dB$ 。首先需要将分贝形式的信噪比转换为线性值，转换公式为

SNR(dB) = 10 lo g_{10} (S / N)

代入 $30 dB$ 得

30 = 10 lo g_{10} (S / N)

计算得

lo g_{10} (S / N) = 3

因此

S / N = 1 0^{3} = 1000

接下来代入香农公式：

C = 4000 \times lo g_{2} (1 + 1000) = 4000 \times lo g_{2} (1001)

由于 $1001$ 接近 $1000$ ，可近似为 $lo g_{2} (1000)$ 。使用换底公式计算

lo g_{2} (1000) = \frac{lo g _{10} ( 1000 )}{lo g _{10} ( 2 )} = \frac{3}{0.3010} \approx 9.966

因此

C \approx 4000 \times 9.966 = 39864 b/s

约合 $39.86 kb/s$ 。四舍五入后最接近 $40 kb/s$ ，故选项 D 正确。

35

以太网中，当数据传输率提高时，帧的发送时间就会相应的缩短，这样可能会影响对冲突的检测。为了能有效地检测到冲突，可以使用的解决方案有（　）。

正确答案：B

【解析】 在以太网的CSMA/CD协议中，冲突检测的有效性依赖于帧的发送时间不小于信号在电缆中的往返传播延迟。当数据传输率提高时，帧的发送时间会相应缩短（发送时间=帧长/数据率），这可能导致在帧发送完毕前无法检测到冲突，从而影响网络可靠性。

为了确保冲突检测，需要维持“帧发送时间≥往返传播延迟”的条件。解决方案可以从两方面入手：一是减少电缆长度，从而降低信号传播延迟，使得往返时间缩短，这样即使发送时间较短也能覆盖冲突检测窗口；二是增加最短帧长，直接延长帧的发送时间，保证有足够时间检测冲突。因此，选项B中的减少电缆介质长度或增加最短帧长是正确的做法。

其他选项分析：A和C中的减少最短帧长会进一步缩短发送时间，加剧冲突检测困难；C中的增加电缆长度会增大传播延迟，要求更长的帧发送时间，与数据率提高的效应叠加后问题更严重；D中的“提高存取、换出速度”并非CSMA/CD标准中解决此问题的有效方法，且表述模糊。

36

若子网掩码是 255.255.192.0，那么下列主机必须通过路由器才能与主机 129.23.144.16 通信的是（　）。

正确答案：B

【解析】 首先，子网掩码为 255.255.192.0，转换为二进制是 11111111.11111111.11000000.00000000，即前缀长度为 /18。网络部分占前 18 位，主机部分占后 14 位。

主机 129.23.144.16 的 IP 地址二进制为 10000001.00010111.10010000.00010000。与子网掩码按位与后得到子网地址：第一、二字节不变（129.23），第三字节仅保留前两位（10），后六位置零得 10000000（即 128），第四字节全零。因此子网地址为 129.23.128.0/18。

该子网的范围由第三字节决定：由于子网掩码第三字节为 192（二进制 11000000），子网划分以 64 为增量。子网地址第三字节为 128（128 = 2 × 64），所以该子网覆盖第三字节从 128 到 191 的 IP 地址，即 129.23.128.1 至 129.23.191.254。

现在检查各选项是否在同一子网：

A. 129.23.191.21：第三字节 191，在 128~191 范围内，子网地址为 129.23.128.0，在同一子网。
B. 129.23.127.222：第三字节 127，小于 128，计算得其子网地址为 129.23.64.0（127 ÷ 64 整数部分为 1，1 × 64 = 64），不在同一子网。
C. 129.23.130.33：第三字节 130，在 128~191 范围内，子网地址为 129.23.128.0，在同一子网。
D. 129.23.148.127：第三字节 148，在 128~191 范围内，子网地址为 129.23.128.0，在同一子网。

因此，只有主机 129.23.127.222 与主机 129.23.144.16 不在同一子网，必须通过路由器才能通信。

37

在基于 TCP/IP 模型的分组交换网络中，每个分组都可能走不同的路径，所以在分组到达目的主机后应该重新排序；又由于不同类型物理网络的 MTU 不同，所以一个分组在传输的过程中也可能需要分段，这些分段在到达目的主机后也必须重组。对于分组的排序和分段的重组，下列说法正确的是（　）。

正确答案：D

【解析】 在TCP/IP模型中，网络层（或称互联网层）主要使用IP协议，负责将数据包从源主机路由到目的主机。由于不同物理网络的MTU（最大传输单元）可能不同，当IP数据报的大小超过某段网络的MTU时，网络层会在传输过程中对其进行分片。这些分片作为独立的IP数据报传输，并在到达目的主机后，由网络层根据分片头部的信息（如标识符、偏移量等）进行重组，恢复原始数据报。因此，分段的重组工作由网络层完成。

另一方面，传输层（如TCP协议）负责端到端的可靠通信。在分组交换网络中，各个分组可能通过不同路径传输，导致到达顺序混乱。TCP协议通过为每个数据段分配序列号，在接收端对到达的数据段进行排序，确保数据以正确的顺序交付给应用层。因此，排序工作由传输层完成。

综合来看，排序是传输层的功能，而重组是网络层的功能，选项D正确描述了这一点。其他选项混淆了这两项职责在TCP/IP模型中的归属。

38

ARP 的作用是由 IP 地址求 MAC 地址，某节点响应其他节点的 ARP 请求是通过（　）发送的。

正确答案：A

【解析】 ARP（地址解析协议）的主要作用是在局域网中根据已知的IP地址来查询对应的MAC地址，以实现数据链路层的通信。当一台设备需要解析某个IP地址的MAC地址时，它会发送一个ARP请求报文，这个请求以广播形式发送到整个本地网络，因为发送者尚未知道目标设备的MAC地址，无法直接寻址。

收到ARP请求的节点会检查请求中的目标IP地址是否与自己的IP地址匹配。如果匹配，该节点就会准备一个ARP响应报文。由于在ARP请求报文中包含了发送者的IP地址和MAC地址，响应节点可以直接使用这些信息，将ARP响应通过单播方式发送回请求节点，而无需再次广播。单播发送提高了网络效率，避免了不必要的网络流量。

因此，ARP响应是通过单播发送的，对应选项A。其他选项中，组播和广播通常用于一对多通信，而点播并非标准网络术语，常与单播同义，但在此上下文中单播是最准确的描述。

39

下列关于 TCP 协议的叙述中，错误的是（　）。

I. TCP 是一个点到点的通信协议
II. TCP 提供了无连接的可靠数据传输
III. TCP 将来自上层的字节流组织成 IP 数据报，然后交给 IP 协议
IV. TCP 将收到的报文段组成字节流交给上层

正确答案：D

【解析】 本题考查对 TCP 协议的理解。TCP 是在不可靠的 IP 层之上实现可靠的数据传输协议，它主要解决传输的可靠、有序、无丢失和不重复的问题，其主要特点是：①TCP 是面向连接的传输层协议。②每一条 TCP 连接只能有两个端点，每一条 TCP 连接只能是端对端的（进程—进程）。③TCP 提供可靠的交付服务，保证传送的数据无差错、不丢失、不重复且有序。④TCP 提供全双工通信，允许通信双方的应用进程在任何时候都能发送数据，为此 TCP 连接的两端都设有发送缓存和接收缓存。⑤TCP 是面向字节流的，虽然应用程序和 TCP 的交互是一次一个数据块（大小不等），但 TCP 把应用程序交下来的数据看成仅仅是一连串的无结构的字节流。

Ⅰ：IP 协议才是点到点的通信协议（也说是主机—主机），而 TCP 是端到端的协议，故Ⅰ错误；
Ⅱ：TCP 提供面向连接的可靠数据传输服务，故Ⅱ错误；
Ⅲ：IP 数据报不是由传输层来组织的，而应该由网络层加上 IP 数据报的首部来形成 IP 数据报，故Ⅲ错误；
Ⅳ：前面已经分析，正确。

综上，Ⅰ、Ⅱ和Ⅲ都是错误的。

40

A 和 B 建立 TCP 连接，MSS 为 1KB。某时，慢开始门限值为 2KB，A 的拥塞窗口为 4KB，在接下来的一个 RTT 内，A 向 B 发送了 4KB 的数据（TCP 的数据部分），并且得到了 B 的确认，确认报文中的窗口字段的值为 2KB，那么，请问在下一个 RTT 中，A 最多能向 B 发送的数据（　）。

正确答案：A

【解析】
首先，TCP 发送方的实际发送窗口大小由拥塞窗口（cwnd）和接收方通告窗口（rwnd）共同决定，取两者最小值。初始时，cwnd = 4 KB，ssthresh = 2 KB，由于 cwnd > ssthresh，因此 A 处于拥塞避免阶段。在拥塞避免阶段，当发送的数据在一个 RTT 内被全部确认后，cwnd 会线性增加一个 MSS（1 KB），因此更新后的 cwnd = 4 KB + 1 KB = 5 KB。

然而，确认报文中携带的窗口字段值为 2 KB，即接收方通告窗口 rwnd = 2 KB。因此，下一个 RTT 中 A 的发送窗口大小为

min (cwnd, rwnd) = min (5 KB, 2 KB) = 2 KB

所以，A 最多能向 B 发送 2 KB 数据。

解答题

第 41～47 题，共 70 分。

41

（11 分）如下图所示：

（1）写出该图的邻接矩阵。

（2）写出全部拓扑序列。

（3）以 V1 为源点，以 V8 为终点，给出所有事件（和活动）允许发生的最早时间和最晚时间，并给出关键路径。

（4）求 V1 结点到各点的最短路径和距离。

事件	V1	V2	V3	V4	V5	V6	V7	V8
最早发生时间	0	2	3	7	13	11	16	17
最晚发生时间	0	2	3	7	13	11	16	17

活动	V2-V4	V3-V4	V3-V5	V4-V6	V6-V5	V5-V7	V6-V8	V7-V8
最早开始时间	2	3	3	7	11	13	11	16
最晚开始时间	2	4	3	7	11	13	11	16
时间余量	0	1	0	0	0	0	0	0

42

（13 分）将一个数组最开始的若干个元素搬到数组的末尾，称之为数组的旋转。输入一个已排好序数组的一个旋转，求该旋转数组的最小元素。如，数组 {3, 4, 5, 1, 2} 为有序数组 {1, 2, 3, 4, 5} 的一个旋转数组，该数组的最小值为 1。

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

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

（3）说明你所设计算法的时间复杂度和空间复杂度。

【答案】

（1）基本设计思想：
采用改进的二分查找。由于旋转数组由两个有序子数组构成，且最小元素是第二个子数组的首元素。设置两个指针 low 和 high 分别指向数组首尾，计算中间位置 mid。比较 nums[mid] 与 nums[high]：

若 nums[mid] > nums[high]，说明最小值在右半部分，令 low = mid + 1；
若 nums[mid] < nums[high]，说明最小值在左半部分（包含 mid），令 high = mid；
若相等，无法判断，但可通过 high– 缩小范围（不会丢失最小值）。
重复直到 low == high，此时指向最小元素。

（2）算法描述（C++）：

int findMin(vector<int>& nums) {
    int low = 0, high = nums.size() - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;  // 防止溢出
        if (nums[mid] > nums[high]) {
            low = mid + 1;  // 最小值在右半部分
        } else if (nums[mid] < nums[high]) {
            high = mid;  // 最小值在左半部分（可能为 mid）
        } else {
            high--;  // 相等时无法判断，缩小右边界
        }
    }
    return nums[low];  // low == high，指向最小值
}

（3）时间复杂度：平均 O(log n)，最坏情况（全部相等） O(n)。
空间复杂度：O(1)，仅用了常数个变量。

【解析】
本题是旋转数组找最小值的经典问题。原数组有序，旋转后形成两个有序子数组，且最小值位于第二个子数组开头。直接遍历需要 O(n) 时间，而利用二分思想可提升效率。
比较 nums[mid] 与 nums[high] 是关键：若 nums[mid] > nums[high]，说明 mid 属于第一个子数组，最小值必在 mid 右侧；若 nums[mid] < nums[high]，说明 mid 属于第二个子数组，最小值在 mid 左侧（含 mid）；若相等，则无法二分（如数组有重复元素），但通过 high– 可逐步缩小范围，确保不遗漏最小值。
算法在大部分情况下达到对数复杂度，仅当大量重复元素时退化为线性，这是处理重复情况下的最优方式之一。

43

（11 分）某计算机的主存地址数为 16 位，按字节编址。假定数据 Cache 中最多存放 32 个主存块，采用 2-路组相联方式，块大小为 16B，每块设置了 1 位有效位。采用一次性写回策略，为此每块设置了 1 位“脏”位。请问：

（1）主存地址中标记（Tag）、组号（Index）和块内地址（Offset）三部分的位置和位数分别是多少？该数据 Cache 的总位数是多少？

（2）设字长为 4B，Cache 起始为空，CPU 从主存单元 0，1，…，99，依次读出 100 个字（主存一次读出一个字），并重复按此次序读 6 次，问命中率是多少？

（3）如果块表中组号为 10、行号为 1 的 Cache 块的标记为 36H，有效位为 1，则在 CPU 送来主存的字地址为 36A8H 时是否命中？若命中，此时 Cache 的字地址为多少？

44

已知带返转指令的含义如下图所示：

（1）机器周期长度固定，写出机器在执行带返转指令时，硬布线控制取指令段和执行阶段所需的全部微操作命令及节拍安排。

（2）若采用微程序控制，还需增加哪些微操作？

（3）假设该机指令系统采用 6 位定长操作码格式，共对应多少个微程序？

（4）在原理、执行速度和灵活性三个方面分析硬布线控制和微程序控制的区别。

45

（7 分）系统有 5 个进程，其就绪时刻（指在该时刻已进入就绪队列）、服务时间如下表所示。分别计算采用先来先服务、短作业优先、高响应比优先的平均周转时间和带权周转时间。

进程	就绪时刻	服务时间
P₁	0	3
P₂	2	6
P₃	4	4
P₄	6	5
P₅	8	2

作业号	就绪时刻	服务时间	等待时间	开始时刻	结束时刻	周期时间	带权周转时间
P₁	0	3	0	0	3	3	3/3=1.0
P₂	2	6	1	3	9	7	7/6=1.17
P₃	4	4	5	9	13	9	9/4=2.25
P₄	6	5	7	13	18	12	12/5=2.4
P₅	8	2	10	18	20	12	12/2=6.0
平均						8.6	2.56

作业号	就绪时刻	服务时间	等待时间	开始时刻	结束时刻	周期时间	带权周转时间
P₁	0	3	0	0	3	3	3/3=1.0
P₂	2	6	1	3	9	7	7/6=1.17
P₅	8	2	1	9	11	3	3/2=1.5
P₃	4	4	7	11	15	11	11/4=2.75
P₄	6	5	9	15	20	14	14/5=2.8
平均						7.6	1.84

作业号	就绪时刻	服务时间	等待时间	开始时刻	结束时刻	周期时间	带权周转时间
P₁	0	3	0	0	3	3	3/3=1.0
P₂	2	6	1	3	9	7	7/6=1.17
P₃	4	4	5	9	13	9	9/4=2.25
P₅	8	2	5	13	15	7	7/2=3.5
P₄	6	5	9	15	20	14	14/5=2.8
平均						8.0	2.14

46

在一个分页存储管理系统中，地址空间分页（每页 1K），物理空间分块，设主存总量为 256KB，描述主存分配情况的位示意图如下右图所示（0 表示未分配，1 表示已分配），此时作业调度程序选中一个长为 5.2KB 的作业投入内存。试问：

（1）为该作业分配内存后（分配内存时，首先分配低地址的内存空间），请填写该作业的页表内容。

（2）页式存储管理有无内存碎片存在？若有，会存在哪种内存碎片？为该作业分配内存后，会产生内存碎片吗？如果产生，大小为多少？

（3）假设一个 64MB 内存容量的计算机，采用页式存储管理（页面大小为 4K），内存分配采用位示图方式管理，请问位示图将占用多大的内存？

页号	块号
0	21
1	27
2	28
3	29
4	34
5	35

47

（9 分）本地主机 A 的一个应用程序使用 TCP 协议与同一局域网内的另一台主机 B 通信。用 Sniffer 工具捕获本机 A 以太网发送和接收的所有通信流量，目前已得到 8 个 IP 数据报。表 1 以 16 进制格式逐字节列出了这些 IP 数据报的全部内容，其中，编号 2、3、6 为主机 A 收到的 IP 数据报，其余为主机 A 发出的 IP 数据报。假定所有数据报的 IP 和 TCP 校验和均是正确的。

表 1 Sniffer 捕获到的 IP 数据报

编号 12345678 IP 包的全部内容 45000030 c 0 a 800 c 0 7002 ff ff 82 f c 4000 066431 ba ec e 20000 8006 f 5 a 5 2268 b 990 020405 b 4 c 0 a 80015 0000000001010402 4500002 f d a 207 b 57 375 c 0400 00074000 0800695 a 08090 a 0 b 40012442 366 f 0007 0 c 0 d 0 e 0 f c 0 a 80065 73485 b 49 101112 45000030 c 0 a 80015 70122000 00004000 31 ba 0664 83450000 4006 b 8 a 2 5 b 9 f f 71 c 020405 b 4 c 0 a 800 c 0 2268 b 991 01010402 45000028 c 0 a 800 c 0 5010 ff ff 82 fd 4000 066431 ba c 6 d 90000 8006 f 5 a c 2268 b 991 c 0 a 80015 5 b 9 f f 71 d 45000038 c 0 a 800 c 0 5018 ff ff 24346 a 13 82 f e 4000 066431 ba b c b 70000 55 b 76559 8006 f 59 b 2268 b 991 f 89 f e 3 e 3 c 0 a 80015 5 b 9 f f 71 d 2 c 12 c 289 45000028 c 0 a 80015 50102000 3 f 284000 31 ba 0664 a f f 90000 40067982 5 b 9 f f 71 d c 0 a 800 c 0 2268 b 9 a 1 45000038 c 0 a 800 c 0 5018 ff ff 24346 a 13 830 b 4000 066431 ba b c a 70000 55 b 76559 8006 f 58 e 2268 b 9 a 1 f 89 f e 3 e 3 c 0 a 80015 5 b 9 f f 71 d 2 c 12 c 289 45000048 c 0 a 800 c 0 5018 ff ff 24346 a 13 751 b 4 f 75 833 e 0000 066431 ba b 28 d 0000 55 b 76559 62 df 0319 8006354 c 2268 b 9 a 1 f 89 f e 3 e 3 dd 472 c 3 a c 0 a 80015 5 b 9 f f 71 d 2 c 12 c 289 b 10 c 9 a f 1

IP 分组头结构和 TCP 段头结构分别如图1、图2所示：

协议域为1、6、17、89分别对应ICMP、TCP、UDP、OSPF协议。

本题中窗口域描述窗口时使用的计量单位为1字节。
请回答下列问题：

(1) 表 1 的 IP 分组中，哪几个完成了 TCP 连接建立过程中的三次握手？根据三次握手报文提供的信息，连接建立后，如果 B 发数据给 A，那么首字节的编号是多少？

(2) 根据表 1 中的 IP 分组，A 上的应用程序已经请求 TCP 发送的应用层数据的总字节是多少？

(3) 如果 8 号 IP 分组之后，B 正确收到了 A 已发出的所有 IP 分组，B 发给 A 的 TCP 报文段中 ack 号应当是多少（十六进制）？在 8 号 IP 分组之后，A 上的应用程序请求 TCP 发送新的 65495 字节的应用层数据，那么，按 TCP 协议，在 A 未能得到 B 的任何确认报文之前，TCP 可以发送到网络中的应用层数据最多是多少字节？