模拟卷1

已知一个栈的进栈序列是 1、2、3、…、n，其输出序列为 p₁、p₂、p₃、…、pₙ，若 p₁=3，则 p₂ 为（ ）。

A. 2 或 4、5、…、n 都有可能 B. 可能是 1 C. 一定是 2 D. 只可能是 2 或 4

栈 入栈出栈序列

[tag_link]

正确答案：A

已知进栈序列为1,2,3,…,n，且第一个出栈元素p₁=3。 根据栈的后进先出特性，为了使得3第一个出栈，操作序列必须是：先将1和2依次进栈，然后将3进栈并立即出栈。 此时栈中剩余元素为1和2（2在栈顶），且后续元素4,5,…,n尚未进栈。

对于第二个出栈元素p₂，存在两种可能：一是直接出栈当前栈顶元素2，则p₂=2； 二是暂不出栈2，而是将后续元素4,5,…,n依次进栈，并在进栈过程中或进栈后出栈某个元素，此时p₂可以是4,5,…,n中的任意一个。 需要注意的是，p₂不可能是1，因为1位于栈底，必须等待其上方所有元素出栈后才能出栈，而p₂是第二个出栈元素，若不出栈2则无法触及1。 因此，p₂可能是2或4,5,…,n中的任意值，与选项A相符。

利用栈求表达式的值时，设立运算数栈 OPEN。假设 OPEN 只有两个存储单元，则在下列表达式中，不会发生溢出的是（ ）。

A. A-B*(C-D) B. (A-B)C-D C. (A-BC)-D D. (A-B)*(C-D)

栈

[tag_link]

正确答案：B

在利用栈求表达式值时，运算数栈 OPEN 用于存储运算数和中间计算结果。 > 由于 OPEN 只有两个存储单元，栈最多能同时容纳两个运算数，若在求值过程中尝试压入第三个运算数，就会发生溢出。 > 因此，需要分析每个表达式在求值过程中运算数栈的最大深度是否超过2。 >

通过将中缀表达式转换为后缀表达式并模拟求值过程，可以计算栈的最大深度：

• 表达式 A: A-B*(C-D)，后缀为 A B C D - * -。 > 求值时，压入 A、B、C 后栈深度达到3，发生溢出。 >
• 表达式 B: (A-B)*C-D，后缀为 A B - C * D -。 > 求值时，栈中最多同时存在两个运算数（如中间结果和 C 或最终结果和 D），最大深度为2，不会溢出。 >
• 表达式 C: (A-B*C)-D，后缀为 A B C * - D -。 > 求值时，压入 A、B、C 后栈深度达到3，发生溢出。 >
• 表达式 D: (A-B)*(C-D)，后缀为 A B - C D - *。 > 求值时，压入中间结果、C、D 后栈深度达到3，发生溢出。 >

因此，只有表达式 B 在求值过程中运算数栈的最大深度不超过2，不会发生溢出。 >

已知 A[1..N] 是一棵顺序存储的完全二叉树，9 号结点和 11 号结点共同的祖先是（ ）。

A. 4 B. 6 C. 2 D. 8

完全二叉树

[tag_link]

正确答案：C

在顺序存储的完全二叉树中，节点编号对应数组索引，且任意节点 i 的父节点索引为 floor(i/2)。 对于节点 9，其祖先链依次为：9 → 4 → 2 → 1； 对于节点 11，其祖先链依次为：11 → 5 → 2 → 1。 比较两条祖先链，第一个共同的节点是 2，因此 9 号结点和 11 号结点共同的祖先是 2。 选项 A、B、D 均不在两者的共同祖先链中，故正确答案为 C。

在常用的描述二叉排序树的存储结构中，关键字值最大的结点是（ ）。

A. 左指针一定为空 B. 右指针一定为空 C. 左、右指针均为空 D. 左、右指针均不为空

二叉排序树

[tag_link]

正确答案：B

在二叉排序树中，关键字值最大的结点位于树的最右侧，这是由二叉排序树的性质决定的：对于任意结点，其左子树中的所有结点关键字值均小于该结点，右子树中的所有结点关键字值均大于该结点。 因此，从根结点开始一直向右遍历，直到没有右子结点时，所到达的结点即为最大值结点。 由于该结点没有右子结点，其右指针一定为空。

左指针的情况则不确定：最大值结点可能有左子树（此时左指针不为空），也可能没有左子树（此时左指针为空），但这并不影响其作为最大值结点的特性。 选项A、C、D均不能准确描述最大值结点的指针状态，故选项B正确。

分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。

A. （100,80,90,60,120,110,130） B. （100,120,110,130,80,60,90） C. （100,60,80,90,120,110,130） D. （100,80,60,90,120,130,110）

二叉排序树

[tag_link]

正确答案：C

在构造二叉排序树时，序列A、B、D生成的树结构相同，而序列C生成的左子树结构不同，具体如下：

• A、B、D的树结构为：

`        100
       /   \
      80    120
     / \    / \
    60  90 110 130
`

• C的树结构为：

`        100
       /   \
      60    120
        \    / \
         80 110 130
          \
           90
`

因此，与其他三个序列所构造的结果不同的是C。 >

设无向图 G=(V,E) 和 G’=(V’,E’)，如果 G’ 是 G 的生成树，则下面说法错误的是（ ）。

A. G’ 是 G 的子图 B. G’ 是 G 的连通分量 C. G’ 是 G 的极小连通子图且 V’=V D. G’ 是 G 的一个无环子图

最小生成树 图的概念

[tag_link]

正确答案：B

生成树是无向连通图的一个子图，它包含原图的所有顶点，并且是树结构，因此是无环的连通图。 选项A正确，因为生成树的顶点集和边集都是原图的子集，所以它是原图的子图。 选项B错误，因为连通分量是极大连通子图，即不能再添加任何顶点或边而保持连通。 生成树是极小连通子图，不是极大连通子图。 对于连通图，其唯一的连通分量是图本身，而生成树是它的一个真子图（除非原图本身就是树），因此生成树不是连通分量。 选项C正确，生成树是极小连通子图，意味着去掉任意一条边都会破坏其连通性，并且顶点集与原图相同（V’=V）。 选项D正确，生成树作为树结构，不包含任何环，因此是无环子图。

若 G 是一个具有 36 条边的非连通无向简单图，则图 G 的结点数至少是（ ）。

A. 11 B. 10 C. 9 D. 8

图的概念

[tag_link]

正确答案：B

首先，由于 G 是非连通无向简单图，它至少包含两个连通分支。 设结点总数为 n，边数为 36。 为了最小化 n，应使一个连通分支尽可能大（边数多），而其他分支尽可能小（如孤立点，不贡献边数）。 因此，考虑图由一个具有 m 个结点的连通分支和若干孤立点组成，其中所有边均来自该连通分支，即该分支有 36 条边。

对于 m 个结点的简单连通图，边数最多为 m(m-1)/2，因此需满足 m(m-1)/2 ≥ 36。 计算得 m(m-1) ≥ 72。 当 m=9 时，9×8=72，即完全图 K9 恰有 36 条边。 此时若图仅含 K9，则为连通图，但要求非连通，故需至少增加一个孤立点，使结点数 n ≥ m+1=10。 因此 n=10 是可能的构造：一个 9 结点的完全图（36 条边）和一个孤立点，图是非连通的，总边数 36。

验证更小的 n：若 n=9，则非连通图的最大边数出现在两个分支分别为 8 和 1 个结点时，最大边数为 8×7/2+0=28<36，无法达到 36 条边。 n=8 时更不可能。 因此，满足条件的结点数至少为 10。

在有向图 G 的拓扑序列中，若顶点 Vᵢ 在顶点 Vⱼ 之前，则下列情形不可能出现的是（ ）。

A. G 中有弧<Vᵢ, Vⱼ> B. G 中有一条从 Vᵢ 到 Vⱼ 的路径 C. G 中没有弧<Vᵢ, Vⱼ> D. G 中有一条从 Vⱼ 到 Vᵢ 的路径

拓扑排序

[tag_link]

正确答案：D

拓扑序列是针对有向无环图（DAG）的一种顶点排序，要求对于图中的任意有向边，起点在终点之前。

因此，若顶点Vᵢ在拓扑序列中位于Vⱼ之前，则图中不能存在从Vⱼ到Vᵢ的路径，否则会形成环路，违反拓扑序列的定义。

分析选项：

• A：存在弧（即从Vᵢ到Vⱼ的有向边）是可能的，因为该边方向与序列顺序一致，符合拓扑序列要求。 >
• B：存在从Vᵢ到Vⱼ的路径也是可能的，路径意味着Vᵢ是Vⱼ的前驱，在拓扑序列中自然位于其前。 >
• C：没有弧同样可能，因为Vᵢ和Vⱼ之间可能通过其他顶点间接连通，或没有直接关联但序列顺序由其他边决定。 >
• D：存在从Vⱼ到Vᵢ的路径是不可能的，因为如果有这样的路径，根据拓扑序列性质，Vⱼ必须位于Vᵢ之前，这与已知的Vᵢ在Vⱼ之前矛盾。 >

因此，不可能出现的情形是D。 >

具有 12 个关键字的有序表中，对每个关键字的查找概率相同，折半查找查找成功和查找失败的平均查找长度依次为（ ）。

A. 37/12,49/13 B. 35/12,39/13 C. 37/13,49/13 D. 37/12,49/12

平均查找长度

[tag_link]

正确答案：A

对于有序表折半查找，平均查找长度（ASL）需通过二叉判定树计算。 成功查找的 ASL 是找到每个关键字所需比较次数的平均值，失败查找的 ASL 是查找失败时比较次数的平均值。

首先构建 12 个关键字的判定树。 根节点为关键字 6（深度 1），左子树包含关键字 1~5，右子树包含关键字 7~12。 递归划分得到各关键字深度（即比较次数）：关键字 1、4、7、11 深度 3； 关键字 2、5、8、10、12 深度 4； 关键字 3、9 深度 2； 关键字 6 深度 1。 比较次数总和为 37，成功 ASL = 37/12。

失败查找对应判定树的外部节点，共 13 个。 外部节点的比较次数等于其父节点的深度：深度为 3 的父节点（关键字 1、4、7）对应 3 个外部节点，各比较 3 次； 深度为 4 的父节点（关键字 2、5、8、10、12）对应 10 个外部节点，各比较 4 次。 比较次数总和为 3×3 + 4×10 = 49，失败 ASL = 49/13。

因此，成功和失败的平均查找长度依次为 37/12 和 49/13，对应选项 A。

设线性表中每个元素有两个数据项 k1 和 k2，现对线性表按以下规则进行排序：先看数据项 k1，k1 值小的元素在前，大的在后；在 k1 值相同的情况下，再看 k2，k2 值小的在前，大的在后。满足这种要求的排序方法是（ ）。

A. 先按 k1 进行直接插入排序，再按 k2 进行简单选择排序 B. 先按 k2 进行直接插入排序，再按 k1 进行简单选择排序 C. 先按 k1 进行简单选择排序，再按 k2 进行直接插入排序 D. 先按 k2 进行直接选择排序，再按 k1 进行直接插入排序

插入排序

[tag_link]

正确答案：D

该排序要求为先按k1排序，k1相同时再按k2排序，属于多关键字排序。

为实现此类排序，通常需先按次要关键字（k2）排序，再按主要关键字（k1）进行稳定排序，从而在k1相同的情况下保持k2的顺序。

分析各选项：A先按k1进行直接插入排序（稳定），再按k2进行简单选择排序（不稳定），第二次不稳定排序可能破坏已排好的k1顺序，不满足要求； B先按k2进行直接插入排序（稳定），再按k1进行简单选择排序（不稳定），第二次不稳定排序可能打乱k1相同时的k2顺序，不符合要求； C先按k1进行简单选择排序（不稳定），再按k2进行直接插入排序（稳定），第一次不稳定排序导致k1顺序混乱，第二次稳定排序按k2进行，最终序列主要按k2排序，而非先k1后k2，同样不满足； D先按k2进行直接选择排序（不稳定），再按k1进行直接插入排序（稳定），第一次按k2排序后序列整体k2有序，第二次稳定排序按k1进行，能保证k1有序的同时，对k1相同的元素保持第一次排序后的k2顺序，从而实现先k1后k2的排序要求，故D正确。

18 个初始归并段进行 5 路平衡归并，需要增加（ ）个虚拟归并段。

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

外部排序 操作系统概念

[tag_link]

正确答案：C

在5路平衡归并中，每次归并操作都需要恰好5个归并段作为输入，以确保归并过程平衡。

初始归并段数为18个，但归并过程中，每次归并会减少归并段的数量。 具体来说，每归并一次，5个归并段合并为1个新段，因此段数减少4个（即k-1，其中k=5）。

设归并次数为m，最终剩下1个归并段，则有关系式：18 - 4m = 1。 计算得m = (18-1)/4 = 17/4 = 4.25，不是整数。 这意味着如果不添加虚拟归并段，无法通过整数次归并完成，且最后一次归并可能不足5路，破坏平衡性。

为了使得归并次数为整数且每次归并都是5路，需要添加d个虚拟归并段，使总段数S’ = 18 + d，并满足(S’ - 1)能被4整除（即归并次数为整数）。 计算(18 + d - 1) = 17 + d，需使17 + d是4的倍数。 17除以4余1，因此d最小为3（因1+3=4可被4整除）。 此时S’ = 21，归并次数m = (21-1)/4 = 5，均为整数。

验证归并过程：添加3个虚拟段后，总段数21，进行5次归并，每次归并5个段（虚拟段视为空段，不影响结果），最终得到1个有序文件，符合5路平衡归并要求。 因此，需要增加3个虚拟归并段。

某工作站采用时钟频率 f 为 15MHz、处理速率为 10MIPS 的处理机来执行一个已知混合程序。假定该混合型程序平均每条指令需要 1 次访存，且每次存取存储器存取为 1 周期延迟，试问此计算机的有效 CPI 是（ ）。

A. 2.5 B. 2 C. 1.5 D. 1

计算机性能指标

[tag_link]

正确答案：C

有效 CPI（每条指令的时钟周期数）可以根据处理速率（MIPS）和时钟频率（f）的关系计算。 公式为：MIPS = f（MHz）/ CPI。 给定 f = 15 MHz，处理速率为 10 MIPS，代入公式得 CPI = 15 / 10 = 1.5。

问题中提到的访存信息（平均每条指令 1 次访存，每次访存 1 周期延迟）是背景条件，但处理速率 10 MIPS 是实际测量值，已经包含了所有延迟效果，因此直接使用公式计算出的 CPI 即为有效 CPI，无需额外调整。 计算结果显示 CPI 为 1.5，对应选项 C。

如果某单精度浮点数、某原码、某补码、某移码的 32 位机器数均为 0xF0000000，这些数从大到小的顺序是（ ）。

A. 浮点数>原码>补码>移码 B. 浮点数>移码>补码>原码 C. 移码>原码>补码>浮点数 D. 移码>补码>原码>浮点数

补码

[tag_link]

正确答案：D

首先，将32位机器数0xF0000000转换为二进制：1111 0000 0000 0000 0000 0000 0000 0000。 然后分别计算四种表示法对应的真值。

对于单精度浮点数（IEEE 754格式），符号位s=1，指数e=11100000（二进制，即224），尾数f全为0。 实际指数E=e-127=97，故浮点数值为(-1)^1×1.0×2^97 = -2^97，这是一个非常大的负数。

对于原码表示，符号位为1表示负数，数值位为后31位（111000…000），其绝对值为2^30+2^29+2^28=7×2^28，故原码值为-7×2^28。

对于补码表示，最高位为1表示负数，其值计算公式为-2^31+(其他位数值)。 其他位数值同样为7×2^28，故补码值为-2^31+7×2^28 = -2^28。

对于移码表示，通常偏移量为2^31，机器数作为无符号整数时值为2^31+2^30+2^29+2^28=15×2^28，真值为无符号值减2^31，即15×2^28-2^31=7×2^28，这是一个正数。

比较四个值：移码值7×2^28为正数最大； 补码值-2^28为负数但大于原码值-7×2^28（因为-2^28 > -7×2^28）； 浮点数值-2^97是绝对值最大的负数，故最小。 因此从大到小顺序为移码>补码>原码>浮点数，对应选项D。

在 C 语言中，short 型的长度为 16 位，若编译器将一个 short 型变量 x 分配到一个 32 位寄存器 R 中，且 X=0x8FA0，则 R 的内容为（ ）。

A. 0x00008FA0 B. 0xFFFF8FA0 C. 0xFFFFFFA0 D. 0x80008FA0

寄存器类型

[tag_link]

正确答案：B

在 C 语言中，short 类型默认为有符号整数，长度为 16 位。 当将其值存入 32 位寄存器时，需要进行符号扩展以保持数值不变。 给定 x = 0x8FA0，其二进制表示为 1000 1111 1010 0000，最高位为 1，表示负数。 符号扩展时，高 16 位需用符号位（1）填充，因此扩展后的 32 位值为 0xFFFF8FA0。

下列关于 ROM 和 RAM 的说法中，错误的是（ ）。 Ⅰ. CD-ROM 是 ROM 的一种，因此只能写入一次 Ⅱ. Flash 快闪存储器属于随机存取存储器，具有随机存取的功能 Ⅲ. RAM 的读出方式是破坏性读出，因此读后需要再生 Ⅳ. SRAM 读后不需要刷新，而 DRAM 读后需要刷新

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

主存容量的扩展

[tag_link]

正确答案：D

首先分析每个陈述的正确性：

陈述Ⅰ：CD-ROM是只读存储器（ROM）的一种，其内容在生产时写入，用户无法修改或写入，因此“只能写入一次”的说法不准确。 > ROM的本质是只读，而非可写入（即使一次），所以该陈述错误。 >

陈述Ⅱ：Flash快闪存储器属于非易失性存储器，具有随机存取功能，但通常归类为ROM的衍生类型（如EEPROM），而非随机存取存储器（RAM）。 > RAM特指易失性存储器（如DRAM和SRAM），用于主存，因此Flash不属于RAM，该陈述错误。 >

陈述Ⅲ：RAM的读出方式并非都是破坏性读出。 > DRAM（动态RAM）的读出是破坏性的，需要刷新； > 但SRAM（静态RAM）的读出是非破坏性的，无需刷新。 > 该陈述笼统地认为所有RAM都是破坏性读出，因此错误。 >

陈述Ⅳ：SRAM基于触发器存储数据，读后无需刷新； > DRAM基于电容存储电荷，读后需要刷新以维持数据，该陈述正确。 >

综上所述，陈述Ⅰ、Ⅱ、Ⅲ均错误，对应选项D。 >

下列因素中，与 Cache 的命中率无关的是（ ）。

A. Cache 块的大小 B. Cache 的容量 C. Cache 的存取速度 D. Cache 的组织方式

访存过程

[tag_link]

正确答案：C

Cache命中率是指CPU访问数据时在Cache中找到所需数据的概率，它主要受Cache设计参数和结构的影响。

下面分析每个选项：

• **A. Cache块的大小**：块大小影响空间局部性的利用。 > 较大的块可以预取更多相邻数据，可能提高命中率； > 但块过大可能导致Cache中块数减少，增加冲突缺失。 > 因此，块大小与命中率相关。 >

• **B. Cache的容量**：容量越大，能存储的数据越多，减少容量缺失，从而提高命中率。 > 因此，容量与命中率直接相关。 >

• **C. Cache的存取速度**：存取速度指访问Cache的读写时间，它影响CPU访问延迟和系统性能，但不决定数据是否存在于Cache中。 > 命中率关注数据的存在性，而非访问快慢，因此存取速度与命中率无关。 >

• **D. Cache的组织方式**：如直接映射、组相联等方式，影响地址映射和冲突处理，不同的组织方式可能导致不同程度的冲突缺失，从而影响命中率。 > 因此，组织方式与命中率相关。 >

综上，与Cache命中率无关的是Cache的存取速度。 >

下列关于各种寻址方式获取操作数快慢的说法中，正确的是（ ）。 Ⅰ. 立即寻址快于堆栈寻址 Ⅱ. 堆栈寻址快于寄存器寻址 Ⅲ. 寄存器一次间接寻址快于变址寻址 Ⅳ. 变址寻址快于一次间接寻址

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

指令寻址方式 寄存器类型

[tag_link]

正确答案：C

Ⅰ. 立即寻址中操作数直接包含在指令中，无需访问内存或寄存器，因此获取速度最快； 堆栈寻址通常需要通过堆栈指针访问内存，涉及内存访问，速度较慢。 故立即寻址快于堆栈寻址，Ⅰ正确。 Ⅱ. 堆栈寻址需要访问内存，而寄存器寻址直接访问CPU内部寄存器，寄存器寻址速度更快。 因此堆栈寻址快于寄存器寻址的说法错误，Ⅱ不正确。 Ⅲ. 寄存器一次间接寻址先从寄存器获取地址，再访问内存一次； 变址寻址需计算地址（基址加偏移量）后再访问内存一次。 由于变址寻址多了地址计算步骤，寄存器一次间接寻址通常更快，Ⅲ正确。 Ⅳ. 变址寻址经过一次地址计算和一次内存访问； 一次间接寻址（通常指内存间接）需两次内存访问（先取地址再取操作数）。 因此变址寻址快于一次间接寻址，Ⅳ正确。 综上，Ⅰ、Ⅲ和Ⅳ正确，对应选项C。

指令（ ）从主存中读出：

A. 总是根据程序计数器 PC B. 有时根据 PC，有时根据转移指令 C. 根据地址寄存器 D. 有时根据 PC，有时根据地址寄存器

寄存器类型

[tag_link]

正确答案：A

在计算机系统中，程序计数器（PC）专门用于存储下一条要执行指令的地址。 指令的取指阶段总是基于PC的当前值从主存中读取指令，这是冯·诺依曼架构的基本工作原理。 即使遇到转移指令（如跳转或分支），也是先将计算出的目标地址加载到PC中，然后继续根据更新后的PC读取指令，因此指令读取始终依赖于PC。

其他选项中，B提到“有时根据转移指令”不正确，因为转移指令仅修改PC的值，不直接作为读取地址的来源； C和D涉及地址寄存器，但地址寄存器通常用于数据访问或特定寻址模式，并非指令读取的常规依据。 因此，A是唯一准确的描述。

在微程序控制器中，微程序的入口地址是由（ ）形成的。

A. 机器指令的地址码字段 B. 微指令的微地址字段 C. 机器指令的操作码字段 D. 微指令的操作码字段

指令格式 指令操作码

[tag_link]

正确答案：C

在微程序控制器中，微程序用于产生控制信号以执行机器指令。 当控制器开始执行一条新的机器指令时，需要确定该指令对应的微程序序列的起始地址，即入口地址。 这个入口地址的形成通常基于机器指令的操作码字段。

机器指令的操作码字段指明了指令的类型（如加法、跳转等），控制器通过操作码查询一个映射表（如微地址生成器或控制存储器地址转换逻辑），从而得到对应的微程序入口地址。 这个过程是微程序控制器中指令解码的关键步骤。

选项A不正确，因为机器指令的地址码字段主要用于指定操作数地址（如内存地址或寄存器编号），与微程序入口地址无关。 选项B不正确，微指令的微地址字段用于在微程序内部指定下一条微指令的地址（例如实现微程序分支），而不是形成整个微程序的初始入口。 选项D也不正确，微指令的操作码字段用于控制具体的微操作，不参与生成微程序入口地址。 因此，正确答案是C。

下列关于总线仲裁方式的说法中，正确的有（ ）。 Ⅰ. 独立请求方式响应时间最快，是以增加控制线路数为代价的 Ⅱ. 计数器定时查询方式下，有一根总线请求（BR）和一根设备地址线，若每次计数都从 0 开始，则设备号小的优先级高 Ⅲ. 链式查询方式对电路故障最敏感 Ⅳ. 分布式仲裁控制逻辑分散在总线各部件中，不需要中央仲裁器

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

主存容量的扩展

[tag_link]

正确答案：B

关于总线仲裁方式，以下对各项说法的分析可以确定正确与否：

说法Ⅰ正确。 > 独立请求仲裁方式为每个设备配备独立的总线请求线和授权线，仲裁器可直接响应请求，因此响应时间最快，但代价是控制线路数量增加，硬件成本较高。 >

说法Ⅱ错误。 > 计数器定时查询方式中，所有设备共享一根总线请求（BR）线，但设备地址线并非一根，而是一组地址线（数量由设备总数决定，通常为多位）。 > 仲裁器通过地址线发送计数值，设备根据地址比较自身优先级。 > 虽然计数从0开始时设备号小的优先级高，但“一根设备地址线”的描述不准确，因此该说法存在错误。 >

说法Ⅲ正确。 > 链式查询方式依靠一根总线授权（BG）信号在设备间串行传递，若链中某个设备出现电路故障，授权信号可能无法向后传递，导致后续设备无法获得总线使用权，因此对电路故障最为敏感。 >

说法Ⅳ正确。 > 分布式仲裁方式没有中央仲裁器，每个设备内置仲裁逻辑，通过竞争机制决定总线使用权，控制逻辑分散在各部件中，符合描述。 >

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

传输一幅分辨率为 640 像素×480 像素，6.5 万色的照片（图像），假设采用数据传输速率为 56k/s，大约需要的时间是（ ）。

A. 34.82s B. 42.86s C. 85.71s D. 87.7s

磁盘性能指标

[tag_link]

正确答案：D

首先计算图像的总像素数：640像素 × 480像素 = 307,200像素。 图像为6.5万色（即65,000种颜色），颜色深度需要满足2^b ≥ 65,000，由于2^16 = 65,536，因此每个像素需要16位来表示颜色。

图像总数据量为307,200像素 × 16位/像素 = 4,915,200位。 数据传输速率为56k/s，在通信领域中通常表示56千比特每秒，即56,000比特/秒（其中k=1000）。

传输时间 = 总数据量 / 数据传输速率 = 4,915,200位 / 56,000位/秒 ≈ 87.77秒，四舍五入后约为87.7秒，与选项D相符。 注意，若将k按1024计算，会得到约85.71秒（对应选项C），但根据常规的数据传输速率定义，应采用k=1000，因此正确答案为D。

下列说法中，错误的是（ ）。 Ⅰ. 在中断响应周期，置 “0” 允许中断触发器是由关中断指令完成的。 Ⅱ. 中断服务程序的最后一条指令是转移指令 Ⅲ. CPU 通过中断来实现对通道的控制 Ⅳ. 程序中断和通道方式都是由软件和硬件结合实现的 I/O 方式

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

异常和中断

[tag_link]

正确答案：C

Ⅰ错误：在中断响应周期，允许中断触发器被置“0”（即关中断）是由硬件自动完成的，目的是保护中断现场，防止嵌套中断； 关中断指令是软件中使用的，并非在响应周期由指令完成。 Ⅱ错误：中断服务程序的最后一条指令通常是专门的中断返回指令（如IRET），用于恢复现场并返回到被中断的程序； 转移指令（如JMP）用于跳转，不是中断服务程序的规范结尾。 Ⅲ错误：CPU对通道的控制是通过发送通道命令字或启动I/O指令来实现的，而中断是通道向CPU报告状态或完成情况的机制，并非CPU控制通道的手段。 Ⅳ正确：程序中断方式通过硬件中断机制和软件服务程序结合实现I/O； 通道方式通过硬件通道处理器执行通道程序与CPU协作，同样软硬结合。 因此，错误的说法是Ⅰ、Ⅱ和Ⅲ，对应选项C。

在操作系统中，有些指令只能在系统的内核态下运行，而不允许普通用户程序使用。下列操作中，可以运行在用户态下的是（ ）。

A. 设置定时器的初值 B. 触发 Trap 指令 C. 内存单元复位 D. 关闭中断允许位

用户态和内核态

[tag_link]

正确答案：B

在操作系统中，用户态和内核态是两种不同的运行模式。

用户态下程序权限较低，只能执行非特权指令； 内核态下操作系统内核可以执行所有指令，包括特权指令，以管理硬件和系统资源。

选项A“设置定时器的初值”通常涉及硬件定时器的直接配置，这属于特权操作，必须在内核态下执行，用户程序只能通过系统调用间接请求内核完成。

选项B“触发Trap指令”是用户程序主动从用户态切换到内核态的一种机制，例如执行系统调用或处理异常。 Trap指令本身可以在用户态下触发，从而引发陷入内核的处理过程。

选项C“内存单元复位”可能指对物理内存单元的清除或重置操作，这需要直接访问系统内存资源，用户态程序无权执行，必须由内核态代码处理。

选项D“关闭中断允许位”涉及修改CPU的中断标志，这是关键的系统控制操作，允许中断是保证系统响应性和多任务的基础，因此关闭中断必须是内核态特权指令。

综上，只有触发Trap指令可以在用户态下运行，其他选项都需要内核态权限。

以下描述中，哪个不是多线程系统的特长，（ ）。

A. 利用线程并行地执行矩阵乘法运算 B. Web 服务器利用线程请求 HTTP 服务 C. 键盘驱动程序为每一个正在运行的应用配备一个线程，用来响应相应的键盘输入 D. 基于 GUI 的 debugger 用不同线程处理用户的输入、计算、跟踪等操作。

进程和线程

[tag_link]

正确答案：C

多线程系统的特长主要包括提高并发性、有效利用多核处理器、改善程序响应时间以及优化资源共享等，适用于并行计算、高并发服务和任务分离等场景。

A选项描述利用线程并行执行矩阵乘法运算，这属于计算密集型任务的并行化，能够充分利用多核CPU加速运算，是多线程在提升性能方面的典型应用。

B选项描述Web服务器利用线程处理HTTP请求，这是多线程在I/O密集型服务中的常见用法，通过为每个请求分配线程来提高并发处理能力，增强服务器效率。

C选项描述键盘驱动程序为每个正在运行的应用配备一个线程来响应键盘输入，这种做法并不符合多线程系统的特长。 键盘输入通常由操作系统统一管理（如通过中断或事件驱动机制），驱动层应集中处理输入事件再分发给相关应用。 为每个应用单独配备线程会导致线程数量过多，增加上下文切换开销和系统复杂度，反而降低效率，因此这不是多线程的优势所在。

D选项描述基于GUI的debugger使用不同线程处理用户输入、计算和跟踪等操作，这体现了多线程在改善响应性方面的特长。 通过将耗时任务与用户界面分离，可以避免界面冻结，提升用户体验，是多线程在交互式应用中的合理运用。

综上所述，C选项中的方法并非多线程系统的特长，因为它可能引入不必要的资源消耗和设计低效。

对计型信号量 S 执行 V 操作后，下列选项中错误的是（ ）。 Ⅰ. 当 S.value≤0 时，唤醒一个阻塞队列进程 Ⅱ. 只有当 S.value<0 时，唤醒一个阻塞队列进程 Ⅲ. 当 S.value<=0 时，唤醒一个就绪队列进程；当 S.value>0 时，系统不做额外操作

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

进程和线程 进程概念

[tag_link]

正确答案：D

在计型信号量的V操作中，首先将S.value加1，然后判断S.value的值。

若S.value小于等于0，说明之前有进程因资源不足而阻塞，此时应从阻塞队列中唤醒一个进程，并将其移至就绪队列； 若S.value大于0，则无需进行唤醒操作。

对于选项Ⅰ：当S.value≤0时，确实需要唤醒一个阻塞队列进程，因此该选项正确。 对于选项Ⅱ：它强调“只有”当S.value<0时才唤醒，但标准V操作在S.value=0时同样会唤醒进程（因为加1前S.value为-1，表示有进程阻塞），因此该选项错误。 对于选项Ⅲ：V操作唤醒的是阻塞队列中的进程，而非就绪队列中的进程。 就绪队列中的进程已处于就绪状态，无需唤醒，因此该选项错误。

综上，错误的选项是Ⅱ和Ⅲ，对应答案D。

死锁与安全状态的关系是（ ）。

A. 死锁状态有可能是安全状态 B. 安全状态有可能成为死锁状态 C. 不安全状态就是死锁状态 D. 死锁状态一定是不安全状态

银行家算法 死锁的处理方法

[tag_link]

正确答案：D

死锁状态是指系统中多个进程因竞争资源而相互等待，导致所有进程都无法继续执行的状态。

安全状态则是指系统存在至少一个安全序列，能够按照该序列为所有进程分配资源并确保它们顺利完成，从而避免死锁。

分析选项：A项错误，因为死锁状态意味着系统已无法找到安全序列，与安全状态的定义相悖，不可能是安全状态。 B项表述不准确，安全状态本身并不直接等同于死锁状态； 虽然系统从安全状态出发，若资源分配不当可能进入不安全状态并最终导致死锁，但安全状态不会直接“成为”死锁状态。 C项错误，不安全状态仅表示系统可能无法避免死锁，但并非一定已陷入死锁； 例如，系统可能处于不安全状态但仍可通过合适的资源分配避免死锁。 D项正确，因为死锁发生时，系统必定不存在任何安全序列，因此死锁状态一定是不安全状态，这是死锁与安全状态之间的基本关系。

利用死锁定理简化下列进程资源图，则处于死锁状态的是（ ）。

A. I B. II C. I 和 II D. 都不处于死锁状态

进程和线程 进程概念

[tag_link]

正确答案：B

【解析】根据死锁定理，首先需要找出既不阻塞又不是孤点的进程。 对于Ⅰ图，由于 R2 资源已经分配了 2 个，还剩余一个空闲 R2，可以满足进程 P2 的需求，所以 P2 是这样的进程。 P2 运行结束后，释放一个 R1 资源和两个 R2 资源，可以满足 P1 进程的需求，从而系统的资源分配图可以完全简化，不是处于死锁状态。 而对于Ⅱ图，P1 需要 R1 资源，但是唯一的一个 R1 资源已经分配给 P2； 同样，P2 需要 R4 资源，而 R4 资源也只有一个且已经分配给了 P3； 而 P3 还需要一个 R2 资源，但是两个 R2 资源都已经分配完毕了，所以 P1，P2，P3 都处于阻塞状态，系统中不存在既不阻塞又不是孤点的进程，所以系统Ⅱ处于死锁状态。

注意：在进程资源图中，P->R 表示进程正在请求资源，若 R->P，表示资源已被分配给进程（资源只能是被动的）

在虚拟分页存储管理系统中，若进程访问的页面不在主存，且主存中没有可用的空闲帧时，系统正确的处理顺序为（ ）。

A. 决定淘汰页→页面调出→缺页中断→页面调入 B. 决定淘汰页→页面调入→缺页中断→页面调出 C. 缺页中断→决定淘汰页→页面调出→页面调入 D. 缺页中断→决定淘汰页→页面调入→页面调出

缺页异常

[tag_link]

正确答案：C

在虚拟分页存储管理系统中，当进程访问的页面不在主存时，会首先触发缺页中断，这是处理流程的起点。 由于主存中没有可用的空闲帧，系统无法直接调入新页面，必须通过页面置换来腾出空间。 因此，在缺页中断发生后，系统需要决定淘汰哪个页面（即选择置换页），然后将淘汰的页面调出到磁盘（若被修改则需写回），最后才能将所需的页面从磁盘调入主存中腾出的帧。 选项C的顺序“缺页中断→决定淘汰页→页面调出→页面调入”符合这一逻辑，而其他选项或颠倒了中断触发时机，或在无空闲帧时错误地先执行页面调入，因此不正确。

在文件系统中，“Open” 系统调用的主要功能是（ ）。

A. 把文件的内容从外存读入内存 B. 把文件控制信息从外存读入内存 C. 把文件的 FAT 表从外存读入内存 D. 把磁盘的超级块从外存读到内存

文件概念

[tag_link]

正确答案：B

“Open”系统调用的主要功能是建立进程与文件之间的连接，为后续读写操作做准备。

它并不直接读取文件内容，而是通过解析文件路径、检查权限等步骤，将文件的控制信息（如inode或文件控制块）从外存读入内存，以便操作系统快速管理文件状态和访问权限。

选项A描述的是“read”调用的功能； 选项C中FAT表是文件系统整体结构的一部分，通常在挂载时缓存，而非每次打开文件时单独读取； 选项D的超级块包含文件系统全局信息，也是在挂载时加载。 因此，只有B准确反映了“Open”的核心作用。

下列关于文件系统的说法中，正确的是（ ）。

A. 文件系统负责文件存储空间的管理但不能实现文件名到物理地址的转换 B. 在多级目录结构中对文件的访问是通过路径名和用户目录名进行的 C. 文件可以被划分成大小相等的若干物理块且物理块大小也可任意指定 D. 逻辑记录是对文件进行存取操作的基本单位

文件概念

[tag_link]

正确答案：D

本题考查文件系统的多个知识点。 文件系统使用文件名进行管理，也实现了文件名到物理地址的转换，A 错误。 在多级目录结构中，从根目录到任何数据文件都只有一条唯一的路径，该路径从树根开始，把全部目录文件名和文件名依次用“/”连接起来，即构成该数据文件的路径名。 B 的说法不准确，对文件的访问只需通过路径名即可。 文件被划分的物理块的大小是固定的，通常和内存管理中的页面大小一致，C 错误。 逻辑记录是文件中按信息在逻辑上的独立含义来划分的信息单位，它是对文件进行存取操作的基本单位，D 正确。

一个交叉存放信息的磁盘，信息存放方式如图所示，磁盘旋转方向为逆时针方向。每个磁道有 8 个扇区，每个扇区 512 字节，旋转速度为 3000 转/分。假定磁头已在读取信息的磁道上，0 扇区转到磁头下需要 1/2 转，且设备对应的控制器不能同时进行输入/输出，在数据从控制器传送至内存的这段时间内，从磁头下通过的扇区数为 2，问依次读取一个磁道上所有的扇区所需时间和该磁盘的数据传输速度依次是（ ）。

A. 0.07s，58.5KB/s B. 0.07s，57.1KB/s C. 0.08s，57.1KB/s D. 0.08s，58.5KB/s

磁盘概念 机械硬盘

[tag_link]

正确答案：A

本题考查磁盘读取的速度。

首先注意磁盘旋转方向为逆时针方向，对于磁头和磁盘的运动实际上是磁头不动，磁盘转的，而磁盘逆时针方向旋转按扇区来看即 0、3、6……这个顺序。 而每个号码连续的扇区正好相隔 2 个扇区，即是数据从控制器传送到内存的时间，所以相当于磁头连续工作。

由题中条件知，旋转速度为 3000 转/分 = 50 转/秒，即 20ms/转。 读一个扇区需要时间为 20/8 = 2.5ms。 读一个扇区并将扇区数据送入内存需要时间为 2.5 × 3 = 7.5ms。 读出一个磁道上的所有扇区需要时间为 20/2 + 8 × 7.5 = 70ms = 0.07s。 每磁道数据量为 8 × 512 = 4KB。 数据传输速度为 4 × 1024 / (1000 × 0.07 s) = 58.5KB/s。 故依次读出一个磁道上的所有扇区需要 0.07s，其数据传输速度为 58.5KB/s。

注意：硬盘传送速率中的 K 是按 1000 来计算的，并不是 1024。

CPU 输出数据的速度远高于打印机的打印速度，为解决这一矛盾，可采用的技术是（ ）。

A. 并行技术 B. 通道技术 C. 缓冲技术 D. 堆存技术

缓冲区

[tag_link]

正确答案：C

CPU输出数据的速度远高于打印机的打印速度，这种速度不匹配会导致CPU经常处于等待状态，降低系统整体效率。 为了解决这一矛盾，缓冲技术被广泛应用。 缓冲技术通过在内存中设置一个缓冲区，CPU将数据快速输出到缓冲区中暂存，然后打印机可以按照自己的较慢速度从缓冲区中读取数据。 这样，CPU在输出数据后无需直接等待打印机完成，可以继续执行其他任务，从而平滑了速度差异，提高了资源利用率和系统吞吐量。 其他选项中，并行技术主要用于同时执行多个任务或使用多个设备，但在此场景下，单个CPU与单个打印机的速度矛盾并未直接通过并行解决； 通道技术是一种I/O管理方式，通过专用处理器处理I/O操作以减少CPU干预，但它更侧重于优化I/O流程，而非专门针对速度不匹配； 堆存技术并非标准计算机术语，可能指堆内存管理或其他存储方式，与解决速度矛盾无关。 因此，缓冲技术是最直接且有效的选择。

在不同网络结点的对等层之间通信需要的是（ ）。

A. 模块接口 B. 对等层协议 C. 服务原语 D. 电信号

网络应用模型

[tag_link]

正确答案：B

在不同网络结点的对等层之间通信需要使用对等层协议。 对等层协议定义了同一层在不同节点上的实体之间通信的规则、格式和语义，例如OSI模型或TCP/IP模型中各层的协议（如传输层的TCP、网络层的IP），确保对等层实体能够正确交换信息并实现网络功能。

其他选项中，模块接口通常指软件内部组件之间的调用接口，不直接涉及网络对等层通信； 服务原语是同一节点内相邻层之间交互的接口，用于上层调用下层提供的服务，属于层间通信而非对等层通信； 电信号是物理层传输的介质信号（如电压、光信号），属于通信的物理实现基础，但不是对等层通信所需的逻辑机制。

下列叙述中，正确的是（ ）。

A. 电路交换是真正的物理线路交换，而虚电路交换是逻辑上的连接，且一条物理线路只可以进行一条逻辑连接 B. 虚电路的连接是临时性连接，当会话结束时就释放这种连接 C. 数据报服务不提供可靠传输，但可以保证分组的有序到达 D. 数据报服务中，每个分组在传输过程中都必须携带源地址和目的地址

数据报和虚电路

[tag_link]

正确答案：D

选项A错误，因为电路交换确实是物理线路交换，但虚电路交换是逻辑连接，且一条物理线路可以支持多条虚电路（即多个逻辑连接），而非仅一条。 选项B不准确，虚电路分为永久虚电路（PVC）和交换虚电路（SVC），其中SVC是临时连接，会话结束释放，但PVC是永久性的，不随会话结束释放。 选项C错误，数据报服务不提供可靠传输，也不保证分组有序到达，分组可能丢失、重复或乱序。 选项D正确，在数据报服务中，每个分组独立路由，必须携带源地址和目的地址，以便网络设备进行转发。

以太网中，在第 5 次碰撞之后，一个节点选择的 r 值为 4 的概率是（ ）。

A. 1/8 B. 1/16 C. 1/32 D. 1/64

以太网

[tag_link]

正确答案：C

【解析】在以太网中，采用截断二进制指数退避算法处理碰撞。 当节点第

$n$ 次发生碰撞时，它会从区间 $[0,2^k-1]$ 中随机选择一个整数 $r$ ，其中 $k=\min (n,10)$ 。

这意味着 $k$ 随碰撞次数增加而增大，但最大为 $10$ 。

对于第

$5$ 次碰撞， $k=\min (5,10)=5$ ，因此 $r$ 的取值范围是 $0$ 到 $2^5-1=0$ 到 $31$ ，共有 $32$ 个可能的整数值。

由于选择是均匀随机的，每个值被选中的概率相等。

因此，选择

$r=4$ 的概率是 $\frac{1}{32}$ 。

对应选项 C。

以太网中如果发生介质访问冲突，按照二进制指数后退算法决定下一次重发的时间，使用二进制后退算法的好处是（ ）。

A. 这种算法简单 B. 这种算法执行速度快 C. 这种算法考虑了网络负载对冲突的影响 D. 这种算法与网络的规模大小无关

散列表

[tag_link]

正确答案：C

二进制指数后退算法在以太网中用于处理介质访问冲突。

当冲突发生时，发送方会根据冲突次数 k，从 0 到 2^k - 1 个时间槽中随机选择一个值作为退避时间。 随着冲突次数增加，退避时间区间呈指数增长，这意味着在网络负载较高、冲突频繁时，发送方会等待更长时间再重发，从而降低再次冲突的概率。

这种设计使算法能够动态适应网络负载：负载越重，冲突越多，退避时间越长，有效缓解拥塞。 因此，算法的主要好处是考虑了网络负载对冲突的影响。 选项 A 和 B 并非算法的核心优势； 选项 D 不准确，因为算法参数（如时间槽）与网络规模（如传播延迟）相关，但算法重点在于负载自适应。

在某个子网中给四台主机分配 IP 地址（子网掩码均为 255.255.255.224），其中一台因 IP 地址分配不当而存在通信故障。这一台主机的 IP 地址是（ ）。

A. 200.10.1.60 B. 200.10.1.65 C. 200.10.1.70 D. 200.10.1.75

子网划分

[tag_link]

正确答案：A

子网掩码 255.255.255.224 对应 CIDR /27，块大小为 32。 通过计算每个 IP 地址的网络地址：

• 200.10.1.60 与子网掩码 AND 运算后得到网络地址 200.10.1.32； >
• 200.10.1.65、200.10.1.70 和 200.10.1.75 的网络地址均为 200.10.1.64。 >

四台主机应属于同一子网才能直接通信，但 200.10.1.60 的网络地址与其他三台不同，因此该主机因 IP 地址分配不当而存在通信故障。 >

在 IP 分组传输的过程中（不包括 NAT 情况），以下 IP 分组头中的域保持不变的是（ ）。

A. 总长度 B. 首部校验和 C. 生存时间 D. 源 IP 地址

路由器

[tag_link]

正确答案：D

在 IP 分组传输过程中（不考虑 NAT），IP 头部的某些字段会因网络操作而变化。

具体分析如下：

• **总长度（A）**：该字段表示整个 IP 数据报的长度，如果分组在传输中遇到较小 MTU 的网络而被分片，每个分片的总长度将重新计算，因此该字段可能改变。 >
• **首部校验和（B）**：该字段用于验证头部完整性。 > 当分组经过路由器时，生存时间（TTL）字段减少，导致头部内容变化，路由器必须重新计算校验和，因此该字段会更新。 >
• **生存时间（C）**：该字段每经过一个路由器就减 1，以防止分组无限循环，因此它在传输中不断变化。 >
• **源 IP 地址（D）**：该字段标识发送方的 IP 地址，在端到端传输中，除非经过 NAT 等地址转换设备，否则不会改变。 > 题目明确排除 NAT 情况，因此源 IP 地址保持不变。 > 综上，只有源 IP 地址在传输过程中保持不变。 >

信道带宽为 1Gbps，端到端时延为 10ms，TCP 的发送窗口为 65535B，则可能达到的最大吞吐量是（ ）。

A. 1Mbps B. 3.3Mbps C. 26.2Mbps D. 52.4Mbps

通信指标

[tag_link]

正确答案：C

首先，计算 TCP 发送窗口对应的比特数。 窗口大小为 65535 字节，每字节 8 比特，因此窗口比特数为 65535 × 8 = 524280 比特。

其次，确定往返时间（RTT）。 题目中给出的“端到端时延”通常指的是单向传播时延，在计算 TCP 吞吐量时需使用往返时间，故 RTT = 2 × 端到端时延 = 2 × 10ms = 20ms = 0.02 秒。

然后，计算在窗口限制下的最大吞吐量。 吞吐量公式为窗口大小除以 RTT，即 524280 比特 / 0.02 秒 = 26.214 × 10⁶ bps = 26.214 Mbps，约等于 26.2 Mbps。

最后，比较带宽限制。 信道带宽为 1 Gbps（即 1000 Mbps），远高于窗口限制的 26.2 Mbps，因此实际最大吞吐量受限于发送窗口，结果为 26.2 Mbps，对应选项 C。

域名系统 DNS 的组成包括（ ）。 Ⅰ. 域名空间 Ⅱ. 分布式数据库 Ⅲ. 域名服务器 Ⅳ. 从内部 IP 地址到外部 IP 地址的翻译程序

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

网络应用模型

[tag_link]

正确答案：B

DNS（域名系统）的核心功能是将域名解析为IP地址，其组成包括域名空间、分布式数据库和域名服务器。 域名空间（Ⅰ）定义了域名的层次结构； 分布式数据库（Ⅱ）存储了全球的域名与IP地址映射关系，并以分布式方式部署； 域名服务器（Ⅲ）是运行DNS服务的实体，负责处理查询请求。 选项Ⅳ描述的是“从内部IP地址到外部IP地址的翻译程序”，这实际指的是NAT（网络地址转换）技术，用于在私有网络和公共网络之间转换IP地址，属于网络层功能，与DNS的域名解析无关，因此不属于DNS的组成部分。 故正确答案为B，即Ⅰ、Ⅱ和Ⅲ。

（10 分）下面有一种称为“破圈法”的求解最小生成树的方法：所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。 试判断这种方法是否正确。如果正确，请说明理由；如果不正确，举出反例（注：圈就是回路）。

最小生成树

[tag_link]

**【答案】** 正确

**【解析】** 连通图的生成树包括图中的全部 n 个顶点和足以使图连通的 n-1 条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩 n-1 条边为止。

破圈法的正确性基于最小生成树的一个关键性质：在连通无向图的任意一个圈中，权值最大的边一定不属于任何最小生成树（如果边权互异，则该边绝对不在最小生成树中；如果边权有重复，则存在至少一个最小生成树不包含该边）。执行破圈法时，每次任选一个圈并去掉其中权最大的边，相当于移除了一条不在最小生成树中的边，且由于圈是连通的，去掉一条边不会破坏图的连通性。反复执行这一操作，直到图中没有圈为止，此时得到的图是连通且无环的，即为一棵生成树。由于去除的边都不在最小生成树中，而剩下的边数恰好为顶点数减一，因此这棵生成树就是最小生成树。综上，破圈法是求解最小生成树的一种正确方法。

（12 分）假设二叉树采用二叉链存储结构存储，设计一个算法，求出根结点到给定某结点之间的路径，要求：

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

（2）写出二叉树采用的存储结构代码。

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

复杂度分析 图的遍历

[tag_link]

【答案】

（1）算法的基本设计思想：采用递归的深度优先搜索（DFS）方法。从根结点开始，先序遍历二叉树，在遍历过程中使用一个动态数组（如向量）记录当前访问路径。当访问到目标结点时，当前数组中的结点序列即为根结点到目标结点的路径；如果当前结点不是目标结点，则递归遍历其左子树和右子树。若左右子树均未找到目标结点，则进行回溯，从路径中移除当前结点，并返回上一层继续搜索。这种方法利用回溯确保路径的正确性。

（2）二叉树采用的存储结构代码（C 语言描述）：

typedef struct BiTNode {
    char data;                        // 结点数据，假设为字符型
    struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;

（3）算法描述（C++ 语言，基于上述存储结构）：

#include <vector>
using namespace std;

// 函数功能：查找从根结点到目标结点的路径
// 参数：root 为当前子树根结点，target 为目标结点，path 用于存储路径
// 返回值：bool 类型，找到路径返回 true，否则返回 false
bool findPath(BiTree root, BiTree target, vector<BiTree> &path) {
    if (root == nullptr) return false;            // 空树，直接返回 false
    path.push_back(root);                         // 当前结点加入路径
    if (root == target) return true;              // 找到目标结点，返回 true
    if (findPath(root->lchild, target, path)) return true;  // 递归搜索左子树
    if (findPath(root->rchild, target, path)) return true;  // 递归搜索右子树
    path.pop_back();                              // 左右子树均未找到，回溯，移除当前结点
    return false;
}
// 调用示例：假设 root 为根结点指针，target 为目标结点指针，path 为空的 vector<BiTree> 类型，
// 调用 findPath(root, target, path) 后，若返回 true，则 path 中存储从根到目标的路径结点序列。

【解析】算法的核心思想是递归深度优先搜索，结合回溯记录路径。从根结点开始，先访问当前结点并加入路径，然后判断是否为给定结点：若是则成功；否则递归搜索左子树和右子树。递归调用前将当前结点加入路径，调用后若子树中找到目标，则当前结点保留在路径中（因为它是路径的一部分），否则通过 pop_back() 移除当前结点，实现回溯。这保证了路径从根结点到目标结点的顺序性。存储结构采用二叉链，每个结点包含数据域和左右孩子指针，便于递归遍历。算法的时间复杂度为 O(n)，其中 n 为二叉树结点数，最坏情况下需要遍历所有结点；空间复杂度为 O(h)，h 为二叉树高度，主要由递归栈和路径向量占用，路径向量最多存储 h 个结点。该算法简洁有效，适用于二叉链存储的二叉树路径查找问题。

（12 分）以下是计算两个向量点积的程序段：

请回答下列问题： （1）请分析访问数组 x 和 y 时的时间局部性和空间局部性？ （2）假设数据 Cache 采用直接映射方式，Cache 容量为 32 字节，每个主存块大小为 16 字节；编译器将变量 sum 和 i 分配在寄存器中，内存按字节编址，数组 x 存放在 0000 0040H 开始的 32 字节的连续存储区中，数组 y 则紧跟在 x 后进行存放。该程序数据访问的命中率是多少？要求说明每次访问时 Cache 的命中情况。 （3）将上述（2）中的数据 Cache 改用 2-路组相联映射方式，块大小改为 8 字节，其他条件不变，则该程序数据访问的命中率是多少？ （4）在上述（2）中条件不变的情况下，将数组 x 定义为 float[12]，则数据访问的命中率是多少？

访存过程

[tag_link]

**【答案】** （1）时间局部性差，空间局部性好。 （2）命中率为0%。 （3）命中率为50%。 （4）命中率为75%。

**【解析】** （1）时间局部性指同一数据在短期内被重复访问的可能性，数组 `x` 和 `y` 的每个元素在循环中仅被访问一次，因此时间局部性较差；空间局部性指访问附近数据的可能性较高，数组元素按顺序访问且内存连续，因此空间局部性较好。

(2) Cache 共有 32B / 16B = 2 行；4 个数组元素占一个主存块（现在的计算机中 float 型一般为 32 位，占 4B）；数组 x 的 8 个元素（共 32B）分别存放在主存 40H 开始的 32 个单元中，共占有 2 个主存块，其中 x[0]～x[3] 在第 4 块（00H-0FH 为第 0 块，10H-1FH 为第 1 块，以此类推，40H-4FH 为第 4 块，下同），x[4]～x[7] 在第 5 块中，数组 y 的 8 个元素分别在主存第 6 块和第 7 块中。所以，x[0]～x[3] 和 y[0]～y[3] 都映射到 Cache 第 0 行；x[4]～x[7] 和 y[4]～y[7] 都映射到 Cache 第 1 行，如下图所示。因为 x[i] 和 y[i]（0≤i≤7）总是映射到同一个 Cache 行，相互淘汰对方，故每次都不命中，命中率为 0。

**(3)** 若 Cache 改用 2-路组相联，块大小改为 8B，则 Cache 共有 4 行，每组 2 行，共 2 组。两个数组元素占一个主存块。数组 x 占 4 个主存块，数组元素 x[0]～x[1]，x[2]～x[3]，x[4]～x[5]，x[6]～x[7] 分别在第 8～11 块中（与上题同理，这里 00H～07H 为第 0 块，08H～0FH 为第 1 块，以此类推）；数组 y 占 4 个主存块，数组元素 y[0]～y[1]，y[2]～y[3]，y[4]～y[5]，y[6]～y[7] 分别在第 12～15 块中，映射关系如下图所示：因为每组有两行，所以 x[i] 和 y[i]（0≤i≤7）虽然映射到同一个 Cache 组，但可以存放到同一组的不同 Cache 行内，因此，不会发生冲突。每调入一个主存块，装入的 2 个数组元素中，第 2 个数组元素总是命中，故命中率为 50%。

**(4)** 将数组 x 定义为 12 个元素后，则 x 共有 48B，使得 y 从主存第 7 块开始存放，即 x[0]～x[3] 在第 4 块，x[4]～x[7] 在第 5 块，x[8]～x[11] 在第 6 块中；y[0]～y[3] 在第 7 块，y[4]～y[7] 在第 8 块。因此，x[i] 和 y[i]（0≤i≤7）就不会映射到同一个 Cache 行中，映射关系如下图所示。每调入一个主存块，装入 4 个数组元素，第一个元素不命中，后面 3 个总命中，故命中率为 75%。

（12 分）假定硬盘传输数据以 32 位的字为单位，传输速率为 1MB/s。CPU 的时钟频率为 50MHz。

（1）采用程序查询的输入输出方式，假定不能使数据丢失，求传输程序运行周期占用 CPU 的时间比率。

（2）采用中断方法进行控制，每次传输的开销（包括中断处理）为 100 个时钟周期。求 CPU 为传输硬盘数据花费的时间比率。

（3）采用 DMA 控制器进行输入输出操作，假定 DMA 的启动操作需要 1000 个时钟周期，DMA 完成时处理中断需要 500 个时钟周期。如果平均传输的数据长度为 4KB（此处，1MB=1000KB），问在硬盘工作的一次传输中，处理器将用多少时间比重进行输入输出操作，忽略 DMA 申请使用总线的影响。

异常和中断 计算机性能指标

[tag_link]

【答案】 (1) 100% (2) 50% (3) 0.75% 【解析】 首先，计算基本参数。硬盘传输速率为 1 MB/s，根据给定 1 MB = 1000 KB，假定 1 KB = 1000 字节，则 1 MB/s = 1 , 000 , 000 字节 / 秒 . 数据传输以 32 位字为单位，每字 4 字节，因此每秒传输字数为 1 , 000 , 000/4 = 250 , 000 字 / 秒 . 每字传输时间间隔为 1/250 , 000 秒 = 4 × 1 0 − 6 秒 = 4 微秒 . CPU 时钟频率为 50 MHz，即 50 × 1 0 6 周期 / 秒 , 时钟周期为 1/ ( 50 × 1 0 6 ) = 2 × 1 0 − 8 秒 = 0.02 微秒 . 每字传输时间间隔对应的时钟周期数为 4 微秒 /0.02 微秒 = 200 周期 .

（1）程序查询方式：为确保数据不丢失，CPU 必须在每字传输时间内完成对该字的查询与传输。假定传输程序处理每字需 200 周期，则每秒 CPU 用于传输的时间为 250 , 000 字 / 秒 × 200 周期 / 字 = 50 × 1 0 6 周期 / 秒 , 与 CPU 总周期数相等，故占用比率为 1，即 100%。

（2）中断方式：每次传输开销（包括中断处理）为 100 时钟周期。每秒中断次数为 250{,}000 次，故每秒 CPU 用于传输的时间为 250 , 000 × 100 = 25 × 1 0 6 周期 . CPU 总周期为 50 × 1 0 6 周期 / 秒 , 因此时间比率为 25 × 1 0 6 /50 × 1 0 6 = 0.5 , 即 50%。

（3）DMA 方式：平均传输数据长度为 4 KB。根据 1 MB = 1000 KB， 4 KB = 4000 字节 . 传输 4 KB 所需时间为 4000 字节 /1 , 000 , 000 字节 / 秒 = 0.004 秒 = 4 毫秒 . 对应的时钟周期数为 4 × 1 0 − 3 秒 / ( 2 × 1 0 − 8 秒 / 周期 ) = 200 , 000 周期 . CPU 每次 DMA 传输参与时间：启动 DMA 需 1000 周期，完成中断处理需 500 周期，共 1500 周期。在硬盘一次传输中，处理器进行输入输出操作的时间比重为 1500 周期 /200 , 000 周期 = 0.0075 , 即 0.75%。

（7 分）一个磁盘机有 19,456 个柱面，16 个读写磁头，并且每个磁道有 63 个扇区。磁盘以 5400rpm 的速度旋转。试问：

（1）如果磁盘的平均寻道时间是 10ms，那么读一个扇区的平均时间是多少？

（2）在一个请求分页系统中，若将该磁盘用作交换设备，而且页面大小和扇区的大小相同。读入一个换出页的平均时间和上面计算的相同。假设如果一个页必须被换出，则寻找换入页的平均寻道时间将只有 1ms，那么传输这两个页的平均时间是多少？

（3）如果在该系统中打开的文件数目远远多于驱动器的数目时，对磁盘机有什么影响？

磁盘概念 磁盘性能指标

[tag_link]

**【答案】** (1) 读一个扇区的平均时间约为15.73 ms。 (2) 传输两个页（换入页和换出页）的平均时间约为22.46 ms。 (3) 可能导致饥饿或者抖动。

**【解析】** （1）读取一个扇区的平均时间由三部分组成：平均寻道时间、平均旋转延迟和数据传输时间。平均寻道时间给定为 $10\text{ms}$ 。磁盘转速为 $5400\text{rpm}$ ，旋转一圈的时间为

$$\frac{60}{5400}=\frac{1}{90}\text{s}\approx 11.111\text{ms},$$

平均旋转延迟为半圈时间，即 $5.556\text{ms}$ 。每个磁道有 $63$ 个扇区，一个扇区的数据传输时间为

$$\frac{11.111}{63}\approx 0.176\text{ms}.$$

因此，总平均时间为

$$10\text{ms}+5.556\text{ms}+0.176\text{ms}\approx 15.73\text{ms}.$$

（2）在请求分页系统中，页面大小与扇区相同。读入一个换出页的平均时间与（1）相同，为 $15.73\text{ms}$ 。但当必须换出页时，寻找换入页的平均寻道时间减少为 $1\text{ms}$ ，因此换入页的传输时间变为

$$1\text{ms}+5.556\text{ms}+0.176\text{ms}\approx 6.73\text{ms}.$$

对于换出页，其传输时间仍假设为正常写操作时间，即平均寻道时间 $10\text{ms}$ 、旋转延迟 $5.556\text{ms}$ 和数据传输 $0.176\text{ms}$ ，合计约 $15.73\text{ms}$ 。传输两个页（换入和换出）的总平均时间为

$$6.73\text{ms}+15.73\text{ms}\approx 22.46\text{ms}.$$

（3）可能会产生两个后果： 第一个后果是饥饿，这是由于请求磁盘 I/O 操作的应用程序得不到满足而长时间在阻塞队列等待，从而导致饥饿； 第二个后果是抖动，由于每次磁盘 I/O 操作完成后都要进行磁盘的换入换出，从而导致抖动。

（9 分）一个进程分配给 4 个页帧（下面的所有数字均为十进制数，每一项都是从 0 开始计数的）。最后一次把一页装入到一个页帧的时间、最后一次访问页帧中的页的时间、每个页帧中的虚页号以及每个页帧的访问位（R）和修改位（M）如下表所示（时间均为从进程开始到该事件之前的时钟值，而不是从事件发生到当前的时钟值）。

当虚页 4 发生缺页时，使用下列存储器管理策略，哪一个页帧将用于置换？解释每种情况的原因。

（1）FIFO（先进先出）算法。

（2）LRU（最近最少使用）算法。

（3）改进的 Clock 算法。

（4）在缺页之前给定上述的存储器状态，考虑下面的虚页访问串：

4, 0, 0, 0, 2, 4, 2, 1, 0, 3, 2

如果使用 LRU 页面置换算法，分给 4 个页帧，会发生多少缺页？

协议数据单元

[tag_link]

**【答案】** （1）页帧3 （2）页帧1 （3）页帧1 （4）3次缺页

**【解析】** （1）FIFO算法基于页面加载时间，选择加载时间最早的页面置换。表中加载时间分别为：页帧0（60）、页帧1（130）、页帧2（26）、页帧3（20）。页帧3的加载时间最早（20），因此用于置换。

（2）LRU算法基于最近访问时间，选择访问时间最早的页面置换。表中访问时间分别为：页帧0（161）、页帧1（160）、页帧2（162）、页帧3（163）。页帧1的访问时间最早（160），因此用于置换。

（3）改进的Clock算法优先选择R=0且M=0的页面。表中页帧状态：页帧0（R=0, M=1）、页帧1（R=0, M=0）、页帧2（R=1, M=0）、页帧3（R=1, M=1）。页帧1满足R=0且M=0，因此用于置换。算法扫描时（假设从页帧0开始），遇到页帧1即选中，无需进一步扫描。

（4）使用LRU算法模拟虚页访问串。初始内存中有虚页0、1、2、3，最后访问时间如表所示（虚页1最早，虚页3最晚）。模拟过程：

• 访问虚页4：缺页，置换LRU页面虚页1（页帧1），装入虚页4。
• 访问虚页0：命中，更新访问时间。
• 访问虚页0：命中，更新访问时间。
• 访问虚页0：命中，更新访问时间。
• 访问虚页2：命中，更新访问时间。
• 访问虚页4：命中，更新访问时间。
• 访问虚页2：命中，更新访问时间。
• 访问虚页1：缺页，置换LRU页面虚页3（页帧3），装入虚页1。
• 访问虚页0：命中，更新访问时间。
• 访问虚页3：缺页，置换LRU页面虚页4（页帧1），装入虚页3。
• 访问虚页2：命中，更新访问时间。 缺页发生在访问4、1、3时，共3次缺页。

（9 分）TCP 的拥塞窗口 cwnd 大小与传输轮次 n 的关系如下所示：

（1）画出 TCP 的拥塞窗口与传输轮次的关系曲线。

（2）分别指明 TCP 工作在慢开始阶段和拥塞避免阶段的时间间隔。

（3）在第 16 轮次和第 22 轮次之后发送方是通过收到三个重复的确认还是通过超时检测到丢失了报文段？

（4）在第 1 轮次、第 18 轮次和第 24 轮次发送时，门限 ssthresh 分别被设置为多大？

（5）在第几轮次发送出第 70 个报文段？

（6）假定在第 26 轮次之后收到了三个重复的确认，因而检测出了报文段的丢失，那么拥塞窗口 cwnd 和门限 ssthresh 应设置为多大？

协议数据单元

[tag_link]

**【解析】** 本题考查TCP的拥塞控制算法。在画出拥塞窗口与传输轮次的曲线后，根据四种拥塞控制算法的特点，以图像的拐点进行分段分析。初始时，拥塞窗口置为 1，即 `cwnd=1`，慢开始门限置为 32，即 `ssthresh=32`。慢开始阶段，`cwnd` 初值为 1，以后发送方每收到一个确认 ACK，`cwnd` 值加 1，也即经过每个传输轮次（RTT），`cwnd` 呈指数规律增长。当拥塞窗口 `cwnd` 增长到慢开始门限 `ssthresh` 时（即当 `cwnd=32` 时），就改用拥塞避免算法，`cwnd` 按线性规律加性增长。当 `cwnd=42` 时，收到三个重复的确认，启用快恢复算法，更新 `ssthresh` 值为 21（即变为超时时 `cwnd` 值 42 的一半）。`cwnd` 重置为 `ssthresh` 减半后的值，并执行拥塞避免算法。当 `cwnd=26` 时，网络出现拥塞，改用慢开始算法，`ssthresh` 置为拥塞时窗口值的一半，即 13，`cwnd` 置为 1。

(1) 拥塞窗口与传输轮次的关系曲线如下图所示：

(2) 慢开始的时间间隔：[1, 6] 和 [23, 26]。拥塞避免的时间间隔：[6, 16] 和 [17, 22]。

(3) 在第 16 轮次之后发送方通过收到三个重复的确认检测到丢失的报文段。在第 22 轮次之后发送方是通过超时检测到丢失的报文段。

(4) 在第 1 轮次发送时，门限 `ssthresh` 被设置为 32。 在第 18 轮次发送时，门限 `ssthresh` 被设置为发生拥塞时的一半，即 21。 在第 24 轮次发送时，门限 `ssthresh` 是第 22 轮次发生拥塞时的一半，即 13。

(5) 第 70 报文段在第 7 轮次发送出。

(6) 拥塞窗口 `cwnd` 和门限 `ssthresh` 应设置为 8 的一半，即 4。