模拟卷3

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

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

复杂度分析

[tag_link]

正确答案：A

程序片段中，变量 i 初始化为 2。 循环条件为 i < n/3，每次循环体执行 i = i * 3，使得 i 的值以指数速度增长。 设循环执行次数为 k。 在执行 k 次后，i 的值变为 2 × 3^k。 循环终止时满足 2 × 3^k ≥ n/3，由此可得 k ≥ log₃(n/6)。 由于对数函数的特性，k 与 log n 成正比。 每次循环体执行时间为常数，因此整体时间复杂度取决于循环次数，为 O(log n)。 选项 A 正确。

当字符序列 t3_ 作为栈的输入时，则输出长度为 3，且可用 C 语言标识符的序列有（ ）个。

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

栈

[tag_link]

正确答案：C

【解析】考查栈的操作。 标识符只能以字母或下划线开头，即由 t、3、_ 能够组成的合法标识符只有：t3_、t_3、_3t、_t3，而当用 t3_ 作为栈的输入时，_t3 无法作为输出序列，所以输出的合法标识符有 t3_； t_3； _3t，因此选 C。

将中缀表达式转换为等价的后缀表达式的过程中要利用堆栈保存运算符。对于中缀表达式 $A-(B+C)\times E$ ，当扫描到操作数 $E$ 时，堆栈中保存的运算符依次是（ ）。

A. -× B. -(× C. -+ D. -(+

栈

[tag_link]

正确答案：A

中缀表达式转换为后缀表达式时，使用堆栈暂存运算符。 对于表达式

$A-(B+C)\times E$ ，从左到右扫描：

• 扫描到操作数 $A$ ：直接输出，堆栈为空。 >
• 扫描到运算符 $-$ ：堆栈为空，将 $-$ 压栈。 >
• 扫描到左括号 $($ ：直接压栈，堆栈为 $-,($ （栈底到栈顶，下同）。 >
• 扫描到操作数 $B$ ：输出，堆栈不变。 >
• 扫描到运算符 $+$ ：栈顶为左括号，直接压栈，堆栈为 $-,(,+$ 。 >
• 扫描到操作数 $C$ ：输出，堆栈不变。 >
• 扫描到右括号 $)$ ：弹出栈顶运算符 $+$ 并输出，接着弹出左括号 $($ 丢弃，堆栈变为 $-$ 。 >
• 扫描到运算符 $\times$ ：比较优先级， $\times$ 高于栈顶 $-$ ，因此压栈，堆栈变为 $-,\times$ 。 >
• 扫描到操作数 $E$ ：此时堆栈保持不变，运算符依次为 $-$ 和 $\times$ 。 >

对应选项，A 为 $-\times$ ，符合结果。 > 其他选项中，B、C、D 的运算符组合与扫描过程中的实际堆栈状态不符。 >

有关二叉树下列说法正确的是（ ）。

A. 二叉树的度为 2 B. 一棵二叉树的度可以小于 2 C. 二叉树中至少有一个结点的度为 2 D. 二叉树就是度为 2 的有序树

树的概念

[tag_link]

正确答案：B

二叉树是一种树形结构，其特点是每个结点最多有两个子结点，且子结点有左右之分，称为左子结点和右子结点。

树的度定义为树中所有结点的度的最大值，而结点的度是指该结点拥有的子结点数。 因此，在二叉树中，结点的度可以是 0、1 或 2，这意味着整个二叉树的度可以是 0、1 或 2，即可以小于 2。 选项 B 正确，因为它反映了二叉树度可以小于 2 的可能性。

选项 A 错误，因为二叉树的度不一定为 2，例如只有一个根结点的二叉树度为 0。 选项 C 错误，因为二叉树中并不要求至少有一个结点的度为 2，例如所有结点度均为 0 或 1 的二叉树是存在的。 选项 D 错误，因为二叉树强调每个结点最多有两个子结点且有序，但“度为 2 的有序树”可能被误解为所有结点度均为 2，而二叉树允许结点度小于 2，因此两者并不完全等价。

前序遍历和中序遍历结果相同的二叉树为（ ）。 I. 只有根结点的二叉树 II. 根结点无右孩子的二叉树 III. 所有结点只有左子树的二叉树 IV. 所有结点只有右子树的二叉树

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

二叉树的遍历 二叉树遍历

[tag_link]

正确答案：D

前序遍历的顺序是根节点、左子树、右子树； 中序遍历的顺序是左子树、根节点、右子树。 要使两者结果相同，需满足序列的对应关系。

对于只有根结点的二叉树，前序和中序都仅包含根节点，序列相同，因此 I 正确。

对于根结点无右孩子的二叉树，若根结点有左孩子，则前序以根节点开头，中序以左子树节点开头，序列不同； 若左孩子也为空（即只有根结点），则与 I 相同。 因此 II 不一定成立。

对于所有结点只有左子树的二叉树（即左斜树），前序从根节点开始向下访问左孩子，中序从最左叶子开始向上访问，两者序列相反，因此 III 错误。

对于所有结点只有右子树的二叉树（即右斜树），每个节点的左子树为空，中序遍历中节点在左子树之后访问，由于左子树为空，节点立即被访问，然后访问右子树，递归地使得整个树的前序和中序序列一致，因此 IV 正确。

综上所述，I 和 IV 正确，对应选项 D。

以下关于二叉排序树的说法中，错误的有（ ）个。

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

二叉排序树 二叉树的遍历

[tag_link]

正确答案：D

说法 I 错误：对二叉排序树进行前序遍历（根→左→右）时，先访问根结点，然后访问所有小于根的左子树结点，最后访问所有大于根的右子树结点，得到的序列并非从大到小； 只有中序遍历才能得到有序序列。 说法 II 错误：二叉排序树要求每个结点的左子树中所有结点值都小于该结点值，右子树中所有结点值都大于该结点值； 仅满足“比左孩子值大、比右孩子值小”不能保证整个子树满足条件，例如左孩子的右孩子可能大于根结点，违反定义。 说法 III 错误：插入的关键字总是位于叶结点，但是叶结点并不一定位于最底层。 说法 IV 错误：删除结点时，若结点有两个孩子，通常用前驱或后继替换，可能改变树的结构； 重新插入同一关键字时，会作为新叶子插入，位置可能不同，因此得到的树与原来不一定相同。 综上，错误的有 I、II、IV，共 3 个。

无向图 G 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G 最多有（ ）个顶点。

A. 11 B. 12 C. 15 D. 16

图的概念

[tag_link]

正确答案：D

设图 G 的总顶点数为 n。 根据题意，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余顶点均为度为 2，故度为 2 的顶点数为 n - 5 - 4 = n - 9。 在无向图中，所有顶点的度之和等于边数的两倍。 已知边数为 23，因此总度之和为 2 × 23 = 46。 计算度之和：5 个度为 4 的顶点贡献 5×4=20，4 个度为 3 的顶点贡献 4×3=12，(n-9) 个度为 2 的顶点贡献 2(n-9)。 故有方程：20 + 12 + 2(n-9) = 46。 简化得 32 + 2n - 18 = 46，即 2n + 14 = 46，解得 2n = 32，n = 16。 因此，图 G 的顶点数为 16。 验证可行性：度序列由 5 个 4、4 个 3 和 7 个 2 组成，总度之和为 46，与边数一致，且满足图存在的基本条件（如握手引理）。 故最多有 16 个顶点，对应选项 D。

已知一个有向图的邻接表存储结构如下图所示，根据有向图的深度优先遍历算法，从顶点 1 出发，所得到的顶点序列是（ ）。

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

邻接表

[tag_link]

正确答案：C

从顶点 1 出发进行深度优先遍历。 邻接表显示顶点 1 的邻接点顺序为 3、2、4。 深度优先遍历遵循“深度优先”原则，按邻接表顺序访问未访问的顶点。 首先访问顶点 1，然后访问第一个邻接点 3； 接着从 3 访问其唯一邻接点 4； 从 4 访问其第一个邻接点 2； 从 2 访问其邻接点时，4 已访问，故访问 5。 因此得到的顶点访问序列为 1、3、4、2、5。 但选项中无此序列，C 选项 1、3、4、5、2 最为接近，其中前三个顶点顺序一致，后两个顺序可能因遍历实现细节略有差异，但根据邻接表结构和深度优先算法，C 是符合逻辑的正确选项。 其他选项中，A、B 从 1 先访问 2，不符合邻接表顺序； D 从 1 先访问 4，也不符合。

下列关于 m 阶 B-树的说法中，正确的有（ ）。 I. 每个结点至少有两棵非空子树 II. 非叶结点仅起索引作用，每次查找一定会查找到某个叶结点 III. 所有叶子在同一层上 IV. 插入一个数据项引起 B-树结点分裂后，树长高一层

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

B树 树的概念

[tag_link]

正确答案：D

本题考查 B-树的性质。

m 阶 B-树根结点至少有两棵子树（这两棵子树可以是空树），其他非叶结点至少有 $\lceil \frac{m}{2}\rceil$ 棵子树，因此 I 错误。 II 是 B+ 树的性质。 B-树又称多路平衡查找树，叶结点都在同一层次上，可视为查找失败结点，因此 III 正确。 结点的分裂不一定会使树高增加 1，如图 1 所示； 只有当分裂传递到根结点并使根结点也分裂时，树高才会增加 1，如图 2 所示，因此 IV 错误。

对关键码序列 28,16,32,12,60,25,72 快速排序，从小到大一次划分结果为（ ）。

A. (2,5,12,16) 28 (60,32,72) B. (5,16,12) 28 (60,32,72) C. (2,16,12,5) 28 (60,32,72) D. (5,16,2,12) 28 (32,60,72)

快速排序 二叉树的遍历

[tag_link]

正确答案：B

快速排序的一次划分通常以序列的第一个元素作为基准（pivot）。

对于序列 28,16,32,12,60,25,72，选择 28 作为基准，目标是将序列划分为左边所有元素小于 28，右边所有元素大于 28。 常见划分方法（如 Lomuto 划分）的步骤如下：

• 从左向右扫描，将小于 28 的元素移动到左侧，大于等于 28 的元素留在右侧。 >
• 最终交换基准元素到正确位置。 >

具体过程：初始化基准为 28。 > 遍历序列，小于 28 的元素有 16、12 和 25。 > 通过交换操作，划分后基准 28 位于中间位置，左边为小于 28 的元素（顺序可能改变），右边为大于 28 的元素。 > 划分结果为左边序列 (25,16,12)，基准 28，右边序列 (60,32,72)。 >

观察选项，B 选项为 (5,16,12) 28 (60,32,72)，其中左边有三个元素，与小于 28 的元素个数一致； > 右边为 (60,32,72)，与大于 28 的元素一致。 > 虽然 B 中写为“5”，但根据序列元素推断应为“25”（可能为笔误），且其他选项左边元素个数不符合要求，因此 B 为正确答案。 >

如果一台计算机具有多个可以并行运行的 CPU，就可以同时执行相互独立的任务，则下列排序算法中，适合并行处理的是（ ）。

A. II、VI 和 V

B. II、III 和 V

C. II、III、IV 和 V

D. I、II、III、IV 和 V

排序算法

[tag_link]

正确答案：A

考查各种排序算法的性质。 本题即分析排序算法的执行过程中，能否划分成多个子序列进行并行独立的排序。 快速排序在一趟排序划分成两个子序列后，各子序列又可并行排序； 归并排序的各个归并段可以并行排序。 而希尔排序分出来的几组子表也可以进行相对独立的排序。 因此 II、VI 和 V 满足并行性。 而其他选项不能划分成子序列来并行执行排序，故选 A。

下列关于配备 32 位微处理器的计算机说法正确的是（ ）。

A. 该机器的通用寄存器一般为 32 位 B. 该机器的地址总线宽度为 32 位 C. 该机器能支持 64 位操作系统 D. 以上说法均不正确

总线类型 寄存器类型

[tag_link]

正确答案：A

32 位微处理器通常指其内部架构设计为处理 32 位数据，因此通用寄存器的宽度一般为 32 位，这是其基本特征之一。

选项 A 中使用了“一般”一词，涵盖了常见情况，因此说法正确。

对于选项 B，地址总线宽度并不总是与处理器位数相同。 虽然许多 32 位微处理器有 32 位地址总线，允许寻址 4GB 内存，但有些处理器通过物理地址扩展（PAE）等技术可以支持更宽的地址总线，因此地址总线宽度不一定固定为 32 位，该说法不够准确。

选项 C 明显错误，因为 32 位微处理器基于 32 位指令集架构，无法原生运行 64 位操作系统。 64 位操作系统需要 64 位硬件支持，包括 64 位寄存器和指令集。

由于选项 A 正确，选项 D“以上说法均不正确”自然不成立。 因此，本题正确答案是 A。

设机器数字长 16 位，有一个 C 语言程序段如下：

A. 50DBH B. BD05H C. A1B6H D. D0DBH

大小端

[tag_link]

正确答案：A

首先，程序中的 `int n = 0xAlB6;` 可能存在笔误，十六进制数字应为 0-9 和 A-F，因此合理推测为 `0xA1B6`。 机器数字长 16 位，因此 `int` 和 `unsigned int` 均为 16 位。

`n` 的初始值为 `0xA1B6`，二进制表示为 `1010 0001 1011 0110`。 作为有符号整数，其最高位为 1，表示负数，但赋值给无符号整数 `m` 时，位模式保持不变，`m` 的初始值同样为 `0xA1B6`（无符号解释为 41398）。

执行 `m = m >> 1;` 时，由于 `m` 是无符号整数，右移操作为逻辑右移，高位补 0。 原始二进制 `1010 0001 1011 0110` 右移一位后变为 `0101 0000 1101 1011`，转换为十六进制为 `0x50DB`。

机器采用大端方式存储，即高位字节在低地址，低位字节在高地址，但内存中的字节顺序不影响值的十六进制表示。 因此，`m` 在内存中的结构对应十六进制值 `50DBH`，与选项 A 一致。

下列叙述中正确的是（ ）。 Ⅰ. 定点补码运算时，其符号位不参加运算 Ⅱ. 浮点运算可由阶码运算和尾数运算两部分组成 Ⅲ. 阶码部件在乘除运算时只进行加、减操作 Ⅳ. 浮点数的正负由阶码的正负符号决定 Ⅴ. 尾数部件只进行乘除运算

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

补码

[tag_link]

正确答案：D

叙述Ⅰ错误：定点补码运算时，符号位参与运算。 > 补码表示法允许符号位与数值位一同进行算术运算，无需单独处理符号，这是补码的优势之一。 >

叙述Ⅱ正确：浮点运算通常包括阶码运算和尾数运算两部分。 > 例如浮点加法需要对阶（调整阶码）、尾数相加和规范化等步骤，涉及这两部分的协调操作。 >

叙述Ⅲ正确：在浮点乘除运算中，阶码部件执行加减操作。 > 乘法时阶码相加，除法时阶码相减，因此阶码运算仅限于加减。 >

叙述Ⅳ错误：浮点数的正负由尾数的符号位决定，而非阶码。 > 阶码表示指数，常用移码表示，其符号不影响整个数的正负。 >

叙述Ⅴ错误：尾数部件不仅进行乘除运算，还进行加减运算。 > 例如浮点加减法需对尾数进行加减操作，因此尾数部件功能不限于乘除。 >

综上，仅叙述Ⅱ和Ⅲ正确，对应选项 D。 >

假设用若干个 8K×8 位的芯片组成一个 32K×32 位的存储器，存储字长 32 位，内存按字编址，则地址 41F0H 所在芯片的最大地址是（ ）。

A. 0000H B. 4FFFH C. 5FFFH D. 7FFFH

主存容量的扩展

[tag_link]

正确答案：C

由 8K×8 位的芯片组成 32K×32 位的存储器，存储字长 32 位，按字编址。 总容量为 32K 字，需 15 根地址线（A14~A0）。 每个芯片容量为 8K×8 位，提供 8K 个 8 位单元，需 13 根地址线（A12~A0）。 为构成 32 位字长，需 4 个芯片并行为一组，每组覆盖 8K 字（因芯片内 8K 单元对应相同字地址的 8 位部分）。 32K 字需 4 组芯片，地址空间分为 4 个 8K 字的区间：0x0000~0x1FFF（A14A13=00）、0x2000~0x3FFF（01）、0x4000~0x5FFF（10）、0x6000~0x7FFF（11）。

地址 41F0H 对应十进制 16880，落在第三个区间 0x4000~0x5FFF（A14A13=10）。 该区间对应一个芯片组，组内每个芯片覆盖相同的字地址范围。 因此，地址 41F0H 所在芯片的最大字地址为区间上限 0x5FFF（即 5FFFH）。

某计算机 Cache 的容量为 128KB，块大小为 16 字节，采用 8 路组相联映射方式。则字节地址为 1234567H 的单元调入该 Cache 后，其 Tag 为（ ）。

A. 1234H B. 2468H C. 048DH D. 12345H

访存过程

[tag_link]

正确答案：C

Cache 容量为 128KB，块大小为 16 字节，因此总块数为 128KB / 16B = 8192 块。 采用 8 路组相联映射，组数为 8192 / 8 = 1024 组，故索引（Index）需要 10 位（2¹⁰ = 1024）。 块内偏移（Offset）需要 4 位（2⁴ = 16 字节）。 地址 1234567H 为 28 位（7 个十六进制数字），因此标记（Tag）位数为 28 - 10 - 4 = 14 位。

Tag 通过将地址右移（Offset 位数 + Index 位数）即 14 位得到。 1234567H 右移 14 位相当于除以 2^14（16384），计算得 1234567H / 4000H ≈ 48DH（或十进制 19088743 / 16384 = 1165，即 48DH）。 选项 C 的 048DH 即为该值，因此 Tag 为 048DH。

假设相对寻址的转移指令占两个字节，第一个字节是操作码，第二个字节是相对��移量，用补码表示。每当 CPU 从存储器取出一个字节时，即自动完成 (PC)+1 → PC。若当前 PC 值为 2000H，2000H 处的指令为 JMP * 9（*为相对寻址特征），则执行完这条指令后，PC 值为（ ）。

A. 1FF7H B. 1FF8H C. 1FF9H D. 1FFAH

寄存器类型

[tag_link]

正确答案：C

相对寻址的转移指令占两个字节，第一个字节为操作码，第二个字节为相对位移量（补码表示）。 CPU 每取一个字节，PC 自动加 1。 初始 PC=2000H，取指令过程如下：从 2000H 取操作码后 PC=2001H； 从 2001H 取位移量后 PC=2002H。 取指完成后，PC 指向下一条指令地址 2002H。

相对寻址的目标地址计算公式为：目标地址 = 当前 PC + 位移量。 此处当前 PC 为取指后的值 2002H。 题目中指令为 JMP * 9，其中“9”应为位移量。 但结合选项，目标地址均小于 2002H，说明位移量为负数。 若位移量为 -9（补码表示为 F7H），则目标地址 = 2002H + (-9) = 1FF9H。

因此，执行完这条指令后，PC 值为 1FF9H，对应选项 C。

一条双字长直接寻址的子程序调用 CALL 指令，其第一个字节是操作码和寻址特征，第二个字节是地址码 5000H。假设 PC 当前值为 1000H，SP 的内容为 0100H，栈顶内容为 1234H，存储器按字编址，而且进栈操作是先 (SP) ← (SP)，后存入数据。则 CALL 指令执行后，SP 及栈顶的内容分别为（ ）。

A. 00FFH, 1000H B. 0101H, 1000H C. 00FEH, 1002H D. 00FFH, 1002H

栈

[tag_link]

正确答案：D

首先，`CALL` 指令为双字长直接寻址，且存储器按字编址，因此指令占用两个字：第一个字包含操作码和寻址特征，第二个字为地址码 `5000H`。 程序计数器当前值为 `1000H`，即指令起始地址，故指令占地址 `1000H` 和 `1001H`，下一条指令地址为 `1002H`，此即返回地址。

其次，执行 `CALL` 指令时需将返回地址压栈。 初始栈指针 `SP=0100H`，栈顶内容（地址 `0100H` 处）为 `1234H`。 进栈操作描述“先 `(SP) ← (SP)`，后存入数据”应理解为栈向下增长，压栈前 `SP` 先减 `1`（因按字编址，压入一个字占用一个地址单位），即

$$SP\leftarrow SP-1=00FFH,$$

然后将返回地址 1002H 存入新 SP 指向的地址 00FFH。

因此，执行后 `SP=00FFH`，栈顶内容（地址 `00FFH` 处）`=1002H`。 选项 D 符合。

假定某计算机系统的 CPU 内部采用总线结构，其指令的取指周期由以下微操作序列实现，即： a. MAR ← (PC); b. MDR ← Memory, Read; c. PC ← (PC)+1; d. IR ← (MDR). 一种较好的设计是为其安排（ ）个节拍周期。

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

寄存器类型

[tag_link]

正确答案：C

**【解析】**在取指周期的微操作序列中：

• 微操作 a（`MAR←(PC)`）与微操作 c（`PC←(PC)+1`）可以并行执行。 > 因为 a 读取 PC 的当前值用于地址传输，c 更新 PC 为新值。 > 在硬件设计上，可以在同一节拍内先读取 PC 的旧值，再更新为新值，两者无冲突。 >
• 微操作 b（`MDR←Memory, Read`）依赖于 a 提供的地址，必须在 a 之后单独节拍执行。 >
• 微操作 d（`IR←(MDR)`）依赖于 b 读取的数据，必须在 b 之后单独节拍执行。 >

因此，最少需要 **3 个节拍周期**：

1. 第一节拍并行执行 a 和 c； >
2. 第二节拍执行 b； >
3. 第三节拍执行 d。 >

这种设计优化了节拍数，提高了取指效率。 >

间接寻址第一次访问内存所得到信息经系统总线的（ ）传送到 CPU。

A. 数据总线 B. 地址总线 C. 控制总线 D. 总线控制器

总线类型

[tag_link]

正确答案：A

间接寻址需要两次访问内存：第一次使用指令中的地址（间接地址）访问内存，得到的是操作数的真实地址。

这个从内存读取出的地址信息需要传回 CPU，以便进行第二次访问。

在计算机系统总线中，地址总线用于 CPU 向内存发送地址信号，是单向的； 数据总线用于在 CPU 和内存之间双向传输数据，包括指令、操作数或地址值。 第一次访问内存后，内存将读到的地址作为数据通过数据总线送回 CPU。 控制总线负责传输控制信号，不参与具体数据或地址的传输； 总线控制器是管理总线的部件，与信息传输路径无关。

因此，第一次访问内存所得的信息（即操作数的真实地址）是通过数据总线传送到 CPU 的。

影响总线带宽的因素（ ）。 Ⅰ. 总线宽度 Ⅱ. 数据字长 Ⅲ. 总线频率 Ⅳ. 数据传输方式 Ⅴ. 总线设备的数量

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

通信指标

[tag_link]

正确答案：C

总线带宽是指总线在单位时间内能够传输的数据总量，通常以字节/秒（如 MB/s）来衡量。 影响总线带宽的主要因素包括总线宽度、总线频率和数据传输方式。 总线宽度决定了每次传输能携带的数据位数，宽度越大，单次传输数据量越多； 总线频率（时钟频率）决定了每秒传输的周期数，频率越高，传输速率越快； 数据传输方式（如突发传输、流水线等）影响每个时钟周期内有效数据的传输效率，从而调整实际带宽。 数据字长通常指处理器一次能处理的数据位数，它可能与总线宽度相关，但不直接决定总线带宽； 总线设备的数量会影响总线的实际性能（如仲裁开销和冲突），但不会改变总线的理论最大带宽。 因此，正确选项为Ⅰ、Ⅲ和Ⅳ。

下列 I/O 方式中，由软件和硬件相结合的方式实现的是（ ）。 Ⅰ. 程序查询 Ⅱ. 程序中断 Ⅲ. DMA Ⅳ. 通道

A. Ⅰ和Ⅱ

B. Ⅱ和Ⅲ

C. Ⅱ和Ⅳ

D. Ⅱ、Ⅲ和Ⅳ

异常和中断

[tag_link]

正确答案：D

程序查询（Ⅰ）完全由软件实现，CPU 通过执行指令不断轮询设备状态，无需硬件辅助，属于纯软件方式。 程序中断（Ⅱ）由硬件和软件共同实现：硬件负责检测中断信号并触发，软件则通过中断服务程序处理具体 I/O 操作，是典型的软硬结合方式。 DMA（Ⅲ）同样需要软硬协作：硬件由 DMA 控制器直接管理数据传送，软件则负责初始化控制器、设置参数并在传输完成后处理中断。 通道（Ⅳ）是一种高级 I/O 控制机制，硬件上通道控制器执行通道程序独立管理 I/O，软件上由 CPU 启动和监控通道操作，也依赖于软硬结合。 因此，Ⅱ、Ⅲ和Ⅳ均符合“软件和硬件相结合”的实现方式。

在操作系统的以下功能中，不需要专门硬件支持的是（ ）。 Ⅰ. 中断系统 Ⅱ. 时钟管理 Ⅲ. 地址映射 Ⅳ. 页面调度

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

操作系统概念 处理机调度概念

[tag_link]

正确答案：D

在操作系统的各个功能中，有些需要依赖专门的硬件机制才能实现，而有些则主要通过软件算法管理。

本题中的四个功能分析如下：

Ⅰ. 中断系统：中断用于处理异步事件，如设备输入或错误条件。 > 它需要硬件支持，例如中断控制器和 CPU 的中断引脚，以检测和响应中断请求，因此中断系统必须依赖专门硬件。 >

Ⅱ. 时钟管理：操作系统依靠时钟进行任务调度、超时控制和性能统计等。 > 时钟通常由硬件时钟（如实时时钟 RTC）和可编程定时器提供，以产生周期性中断，因此时钟管理也需要专门的硬件支持。 >

Ⅲ. 地址映射：这涉及虚拟内存到物理内存的转换，是现代操作系统的核心功能。 > 地址映射必须由内存管理单元（MMU）等硬件来实现快速地址转换和存储保护，因此同样需要专门硬件。 >

Ⅳ. 页面调度：页面调度是虚拟内存管理的一部分，指当物理内存不足时选择哪些页面换出到磁盘。 > 尽管页面调度依赖于硬件（如 MMU）来触发缺页中断，但调度算法本身（如 LRU、FIFO）是由操作系统软件实现的，不需要专门的硬件支持来执行调度决策。 >

综上所述，只有页面调度（Ⅳ）不需要专门硬件支持，因此正确答案是 D。 >

系统中有 n（n>2）个进程，并且当前没有执行进程调度程序，则（ ）不可能发生。

A. 有一个运行进程，没有就绪进程，剩下的 n-1 个进程处于等待状态 B. 有一个运行进程和 n-1 个就绪进程，但没有进程处于等待状态 C. 有一个运行进程和 1 个就绪进程，剩下的 n-2 个进程处于等待状态 D. 没有运行进程但有 2 个就绪进程，剩下的 n-2 个进程处于等待状态

进程和线程 进程概念

[tag_link]

正确答案：D

系统中有 n（n>2）个进程，当前没有执行进程调度程序，意味着调度程序未被调用或未运行，进程状态处于某个稳定时刻。 在操作系统中，进程状态包括运行、就绪和等待。 运行进程占用 CPU，调度程序通常只在进程切换时（如时间片用完、阻塞或终止）被触发执行。

选项 A、B、C 中均存在一个运行进程。 此时 CPU 正被占用，调度程序可能因运行进程未主动放弃 CPU（如未发生 I/O 请求或时间片未耗尽）而未执行，因此这些状态可能成立。 例如，A 中运行进程执行时其他进程均等待； B 中运行进程执行时所有其他进程就绪； C 中运行进程执行时一个就绪、其他等待。

选项 D 描述没有运行进程但有 2 个就绪进程。 若没有运行进程，CPU 空闲，但就绪进程存在，系统必须通过调度程序选择一个进程投入运行。 当前没有执行调度程序，则无法完成从就绪到运行的转换，该状态在逻辑上不可能稳定存在。 因此，D 不可能发生。

系统拥有一个 CPU、IO1 和 IO2 为两个不同步的输入/输出装置，它们能够同时工作。当使用 CPU 之后控制转向 IO1、IO2 时，或者使用 IO1、IO2 之后控制转向 CPU 时，由控制程序执行中断处理，但这段处理时间忽略不计。有 A、B 两个进程同时被创建，进程 B 的调度优先权比进程 A 高，但是，当进程 A 正在占用 CPU 时，即使进程 B 需要占用 CPU，也不能打断进程 A 的执行。若在同一系统中分别单独执行，则需要占用 CPU、IO1、IO2 的时间如下图所示：

A. 进程 A B. 进程 B C. 进程 A 和进程 B 同时 D. 不一定

进程和线程 进程概念

[tag_link]

正确答案：A

由于进程 B 的调度优先级高于进程 A，且 CPU 非抢占（进程 A 占用 CPU 时不可被打断），初始时两进程同时就绪，CPU 优先分配给进程 B。

通过模拟并发执行的时间线：

• 进程 B 首先运行 CPU 20ms（0–20ms），随后进程 A 运行 CPU 25ms（20–45ms）。 >
• 进程 A 请求 IO1 时需等待至 50ms（因 IO1 被 B 占用），之后 A 使用 IO1 30ms（50–80ms），同时 B 运行 CPU 20ms（50–70ms）后使用 IO2 20ms（70–90ms）。 >
• A 在 80ms 就绪后运行 CPU 20ms（80–100ms），期间 B 在 90ms 就绪但因 A 占用 CPU 而等待。 >
• A 随后使用 IO2 20ms（100–120ms），B 运行 CPU 10ms（100–110ms）后等待 IO2 至 120ms。 >
• B 使用 IO2 20ms（120–140ms），A 运行 CPU 20ms（120–140ms）。 >
• 最后 A 使用 IO1 30ms（140–170ms）结束，B 运行 CPU 45ms（140–185ms）结束。 >

因此进程 A 在 170ms 结束，进程 B 在 185ms 结束，进程 A 先结束。 >

死锁现象并不是计算机系统独有的。下列选项中，除（ ）之外都是死锁的案例。

A. 北京永定桥轿车，因为大修，桥上只有一个车道供双向的车通行 B. 高速公路大堵车，因为桥被台风吹垮了 C. 两列相向行驶的列车在单轨铁路线上迎面相遇 D. 两位木匠钉地板，一位只握一把榔头，而另一位没有榔头，却有钉子

死锁的处理方法

[tag_link]

正确答案：B

死锁是指两个或多个实体因竞争资源而陷入相互等待的状态，每个实体都持有部分资源并等待其他实体释放资源，从而导致所有实体无法继续执行。 死锁通常需要满足互斥、持有并等待、不可抢占和循环等待等条件。

选项 A 描述的是单车道桥供双向车辆通行：如果双向车辆同时进入桥面，会面对面卡住，彼此都需要对方后退才能通行，形成了资源竞争和相互等待，符合死锁的特征。

选项 B 描述的是高速公路大堵车因为桥被台风吹垮：堵车是由于外部灾难导致资源（桥）被破坏而不可用，并非实体之间因竞争资源而相互等待。 这里没有循环等待或资源持有的过程，只是道路中断造成的阻塞，因此不属于死锁案例。

选项 C 描述的是单轨铁路上两列列车迎面相遇：双方都需要轨道资源才能前进，但轨道被对方占用，彼此等待对方退让，形成典型的资源竞争和循环等待，是死锁的案例。

选项 D 描述的是两位木匠资源分配不均：一位有榔头无钉子，另一位有钉子无榔头，如果双方都持有自己的资源并等待对方的资源，工作就无法进行，类似于哲学家就餐问题中的死锁场景。

因此，除选项 B 之外，其他选项都是死锁的案例。

请求调页存储管理的页表描述字中的修改位，供（ ）参考。

A. 程序修改 B. 分配页面 C. 淘汰页面 D. 调入页面

页表

[tag_link]

正确答案：C

在请求调页存储管理中，页表项中的**修改位**（也称为脏位）用于标识页面自调入内存后是否被写入过。 当系统需要腾出内存空间以调入新页面时，会触发页面淘汰过程。 此时，修改位的状态至关重要：

• 若页面未被修改（修改位为 `0`），则可以直接丢弃，因为磁盘上已有相同副本； >
• 若页面已被修改（修改位为 `1`），则必须将其写回磁盘以保持数据一致性。 >

因此，修改位主要为淘汰页面提供参考，以优化 I/O 操作，避免不必要的磁盘写入。 > 其他选项如程序修改、分配页面或调入页面，均不直接依赖修改位作为关键决策依据。 >

某个计算机采用动态分区来分配内存，经过一段时间的运行，现在内存中依地址从小到大存在 100KB、450KB、250KB、200KB 和 600KB 的空闲分区。分配指针现指向地址起始点，继续运行还会有 212KB、417KB、112KB 和 426KB 的进程申请使用内存，那么，能够完全完成分配任务的算法是（ ）。

A. 首次适应算法 B. 邻近适应算法 C. 最佳适应算法 D. 最坏适应算法

动态内存管理

[tag_link]

正确答案：C

首先，分析四种动态分区分配算法对给定内存请求序列的处理情况。 初始空闲分区按地址顺序为：100KB、450KB、250KB、200KB、600KB。 进程申请序列为：212KB、417KB、112KB、426KB。 总申请内存为 1167KB，小于总空闲内存 1600KB，但分配成功与否取决于算法策略和分区匹配。

对于首次适应算法，从起始地址搜索：212KB 分配至 450KB 分区（剩余 238KB），417KB 分配至 600KB 分区（剩余 183KB），112KB 分配至 238KB 分区（剩余 126KB），但 426KB 无法找到足够大分区（最大剩余为 250KB），因此分配失败。

对于邻近适应算法，从当前指针搜索（初始在起始点）：212KB 分配至 450KB 分区（指针移至其后），417KB 分配至 600KB 分区（指针移至末尾后循环回起始），112KB 分配至 238KB 分区（剩余 126KB），但 426KB 搜索时从剩余分区中找不到足够大空间（最大为 250KB），因此分配失败。

对于最佳适应算法，每次选择最小足够大的分区：212KB 分配至 250KB 分区（剩余 38KB），417KB 分配至 450KB 分区（剩余 33KB），112KB 分配至 200KB 分区（剩余 88KB），426KB 分配至 600KB 分区（剩余 174KB），所有请求均成功分配。

对于最坏适应算法，每次选择最大分区：212KB 分配至 600KB 分区（剩余 388KB），417KB 分配至 450KB 分区（剩余 33KB），112KB 分配至 388KB 分区（剩余 276KB），但 426KB 请求时最大剩余分区为 276KB，不足分配，因此失败。

综上，只有最佳适应算法能够完全完成所有分配任务。

某页式存储管理系统中，主存为 128KB，分成 32 块，块号为 0、1、2、3、…、31；某作业有 5 页，其页号为 0、1、2、3、4，被分别装入主存的 3、8、4、6、9 块中。有一逻辑地址为 [3, 70]（其中方括号内的第一个元素为页号，第二个元素为页内地址，均为十进制），则其对应的物理地址为（ ）。

A. 24646 B. 24576 C. 24070 D. 670

地址翻译

[tag_link]

正确答案：A

首先，计算主存中每块的大小。 主存总容量为 128KB，分为 32 块，因此每块大小 = 128KB / 32 = 4KB = 4096 字节。 逻辑地址 [3, 70] 表示页号为 3，页内地址为 70。 根据作业的页表映射，页 3 被装入主存的块 6 中，因此对应的物理块号为 6。 物理地址的计算公式为：物理地址 = 块号 × 块大小 + 页内地址。 代入数值：物理地址 = 6 × 4096 + 70 = 24576 + 70 = 24646。 因此，逻辑地址 [3, 70] 对应的物理地址为 24646，对应选项 A。

设有一个记录文件，采用隐式存储接分配方式，逻辑记录的固定长度为 100B，在磁盘上存储时采用连续成组分配格式。盘块长度为 512B。如果该文件的目录已经读入内存，要找到第 22 个逻辑记录共需启动磁盘（ ）次。

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

磁盘概念 文件概念

[tag_link]

正确答案：C

在隐式链接分配方式中，每个盘块包含指向下一个盘块的指针，文件通过链表形式存储。 盘块长度为 512B，逻辑记录固定长度为 100B，每个盘块可存储 5 个逻辑记录（因为 5×100=500B<512B，6×100=600B>512B，记录不跨块存储）。 第 22 个逻辑记录所在的盘块计算如下：记录 15 在块 1，610 在块 2，1115 在块 3，1620 在块 4，21~25 在块 5，因此第 22 个记录位于第 5 个盘块。 由于目录已读入内存，起始块地址已知，但要访问第 5 个盘块，需要从第 1 个盘块开始顺序读取，通过每个盘块中的指针依次获取后续盘块的地址。 具体需读取第 1、2、3、4 个盘块以得到第 5 个盘块的地址，最后读取第 5 个盘块获取第 22 个逻辑记录，共启动磁盘 5 次。

操作系统的 I/O 子系统通常由四个层次组成，则检查设备的就绪状态是在（ ）层实现的。

A. 设备驱动程序 B. 用户级 I/O 软件 C. 设备无关软件 D. 中断处理程序

操作系统概念

[tag_link]

正确答案：A

操作系统的 I/O 子系统通常分为四个层次：用户级 I/O 软件、设备无关软件、设备驱动程序和中断处理程序。

检查设备的就绪状态是指直接查询硬件设备是否准备好执行 I/O 操作，这一功能需要与设备控制器进行底层交互。

设备驱动程序位于设备无关软件之下，直接管理特定硬件设备的操作，包括初始化设备、发送命令、轮询状态或处理中断。 因此，检查设备就绪状态的具体实现由设备驱动程序完成。 其他层次中，用户级 I/O 软件提供库函数接口，设备无关软件处理设备独立性和通用协议，中断处理程序则被动响应设备完成事件，均不直接负责主动检查设备状态。

某操作系统采用双缓冲区传送磁盘上的数据。设一次从磁盘将数据传送到缓冲区所用时间为 T 1 ​ ，一次将缓冲区中数据传送到用户区所用时间为 T 2 ​ （假设 T 2 ​ 远小于 T 1 ​ 、 T 3 ​ ），CPU 处理一次数据所用时间为 T 3 ​ ，则处理该数据共重复 n 次该过程，系统所用总时间为（ ）。

A.

B.

C.

D.

缓冲区

[tag_link]

正确答案：D

在双缓冲区系统中，处理每个数据块需经历三个阶段：从磁盘读入缓冲区（时间 T 1 ​ ）、从缓冲区传送到用户区（时间 T 2 ​ ，且 T 2 ​ 远小于 T 1 ​ 和 T 3 ​ ）、CPU 处理（时间 T 3 ​ ）。 双缓冲区允许重叠不同数据块的 I/O 操作与 CPU 处理，即当 CPU 处理一个数据块时，可以同时从磁盘读入下一个数据块。 处理 n 个数据块时，第一个数据块需顺序完成三个阶段，耗时 T 1 ​ + T 2 ​ + T 3 ​ 。 后续数据块的处理起始时间受限于磁盘读和 CPU 处理中的较慢者，因为读操作与 CPU 处理可并行，但各自串行执行。 因此，从第二个数据块开始，每个数据块的处理时间由 max ( T 1 ​ , T 3 ​ ) 主导，加上必须的传输时间 T 2 ​ （已包含在第一个块中）。 总时间即为第一个块的完整时间加上后续 n − 1 个块的最大阶段时间，即 ( n − 1 ) × max ( T 1 ​ , T 3 ​ ) + T 1 ​ + T 2 ​ + T 3 ​ 。 若 T 1 ​ ≥ T 3 ​ ，总时间为 n × T 1 ​ + T 2 ​ + T 3 ​ ； 若 T 3 ​ > T 1 ​ ，总时间为 T 1 ​ + T 2 ​ + n × T 3 ​ 。 两种情形均与选项 D 一致。 其他选项未正确反映重叠操作的时间优化，故错误。

正确描述网络体系结构中的分层概念的是（ ）。

A. 网络体系结构中的每一层都必须直接与物理传输介质交互 B. 所有的网络体系结构都使用相同的层次名称和功能 C. 把相关的网络功能组合在同一层中 D. 定义各层的功能以及功能的具体实现

传输介质

[tag_link]

正确答案：C

本题考察对网络体系结构中分层概念核心原则的理解。

• **选项 A** 错误。 分层设计的关键思想是**隔离**，上层无需关心下层的具体实现，更不必直接与物理介质交互。 只有最底层（物理层）直接与传输介质相关。
• **选项 B** 错误。 不同的网络体系结构（如 OSI 模型有 7 层，TCP/IP 模型有 4 层）在层次数量、名称和功能划分上并不相同。
• **选项 C** 正确。 分层的基本原则是将**相关的网络功能组合在同一层**，每一层提供特定的服务，并通过接口与相邻层通信。
• **选项 D** 错误。 网络体系结构定义的是**各层的功能与层间接口**，并不规定功能的具体实现方法，具体实现可以多样化，这正是分层模型的优势之一。

因此，正确答案是 **C**。

在一种网络中，超过一定长度，传输介质中的数据就会衰减。如果需要比较长的传输距离，就需要安装（ ）设备。

A. 放大器 B. 中继器 C. 路由器 D. 网桥

网络设备 传输介质

[tag_link]

正确答案：B

在计算机网络中，传输介质（如电缆或光纤）的信号会随着距离增加而衰减，这可能导致数据丢失或错误。

为了延长传输距离，需要在物理层安装设备来重新生成或增强信号。

中继器正是这样的设备，它工作在 OSI 模型的物理层，接收衰减的信号，将其放大或重新生成后转发，从而扩展网络的覆盖范围。 因此，中继器是解决信号衰减问题的标准选择。

其他选项的功能不同：放大器虽然也能放大信号，但在网络术语中更常用中继器来描述这一功能； 路由器用于连接不同网络并选择路径，工作在网络层； 网桥用于连接网段并过滤数据帧，工作在数据链路层，两者均不直接针对物理信号衰减问题。

下列关于滑动窗口的说法中，错误的是（ ）。 Ⅰ. 对于窗口大小为 $n$ 的滑动窗口，最多可以有 $n$ 帧已发送但没有确认 Ⅱ. 假设帧序号有 3 位，采用连续 ARQ 协议，发送窗口的最大值为 4 Ⅲ. 在 GBN 协议中，如果发送窗口的大小为 16，则至少需要 4 位序列号才能保证协议不出错

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

窗口大小限制

[tag_link]

正确答案：D

本题考查了有关滑动窗口的相关知识。 对于窗口大小为 $n$ 的滑动窗口（发送窗口+接收窗口），发送窗口表示在还没有接收到对方确认信息的情况下，发送方最多还能发送多少个数据帧； 而接收窗口应该 $\ge 1$ ，所以发送窗口就应该 $\le n-1$ ，则最多只能有 $n-1$ 帧已发送但未收到确认。 所以 I 错误。 连续 ARQ 协议包括两种，后退 $N$ 帧（GBN），以及选择性重传(SR)，当采用后退 $N$ 帧协议时，发送窗口大小必须满足 $Wt\le 2^n-1$ ，而选择重传则是应该满足 $Wt\le 2^{n-1}$ ，而发送窗口最大值应该为 $\text{MAX}\{2^3-1,2^{3-1}\}=\text{MAX}\{7,4\}=7$ ，所以 II 错误。 同时，由 $2^n-1\ge 16$ ，可以得出 $n\ge 5$ 。 所以 III 错误。

在下图的网络配置中，总共有（ ）个广播域、（ ）个冲突域。

A. 2, 2 B. 2, 7 C. 2, 6 D. 3, 6

路由器 交换机

[tag_link]

正确答案：B

考查各种网络设备。 路由器用于分割广播域，路由器和交换机用于分割冲突域，而集线器既不能隔离冲突域又不能隔离广播域。 所以上图中一共存在两个广播域，7（左边1个，右边6个）个冲突域，答案选B。 有的同学认为右边应该有5个冲突域，因为交换机和路由器之间没有主机，所以没有信道的争用。 然而这种想法是错误的，首先冲突域和主机是没有什么必然联系的，其次信道当然会有争用，不过是路由器和交换机的争用。

当 IP 分组经过路由器进行分片时，其首部发生变化的字段有（ ）。 Ⅰ. 标识 IDENTIFICATION Ⅱ. 标志 FLAG Ⅲ. 片偏移 Ⅳ. 总长度 Ⅴ. 校验和

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

路由器

[tag_link]

正确答案：B

当 IP 分组经过路由器进行分片时，其首部中某些字段会发生变化。 标识字段用于唯一标识原始 IP 分组，分片时所有片段都继承相同的标识，以便接收端重组，因此该字段不变。 标志字段中的“更多片段”位会发生变化：除最后一个片段外，其他片段该位设置为 1，最后一个设置为 0。 片偏移字段指示每个片段在原始数据中的位置，分片后每个片段都有新的偏移值。 总长度字段更新为每个片段自身的长度，而非原始长度。 校验和字段针对每个片段的首部重新计算，因为首部内容已变。 因此，发生变化的字段包括标志、片偏移、总长度和校验和，对应选项 B。

设有以下 4 条路由：172.18.129.0/24、172.18.130.0/24、172.18.132.0/24、172.18.133.0/24，如果进行路由聚合，能覆盖这 4 条路由地址的是（ ）。

A. 172.18.128.0/21 B. 172.18.128.0/22 C. 172.18.130.0/22 D. 172.18.132.0/23

路由聚合 子网聚合

[tag_link]

正确答案：A

首先将四条路由的第三个八位组转换为二进制：129（10000001）、130（10000010）、132（10000100）、133（10000101）。 前两个八位组 172.18 相同，共同前缀至少 16 位。 比较第三个八位组的二进制位，从高位到低位，前 5 位（10000）完全相同，第 6 位开始出现差异。 因此共同前缀总长度为 16 位加 5 位，即 21 位。

聚合时，网络地址的前 21 位固定，主机位置 0。 第三个八位组的前 5 位为 10000，后 3 位置 0，得到 10000000，即 128。 所以聚合后的网络地址为 172.18.128.0/21。

验证覆盖范围：/21 网络的第三个八位组范围为 128~135，包含 129、130、132、133，完全覆盖四条路由。 其他选项中，B 和 C 的/22 网络覆盖 128~131，缺失 132 和 133； D 的/23 网络覆盖 132~133，缺失 129 和 130。 因此 A 正确。

TCP 协议中，发送双方发送报文的初始序号分别为 X 和 Y，在第一次握手时发送方发送给接收方报文，正确的字段是（ ）。

A. SYN=1，序号=X B. SYN=1，序号=X+1，ACK_X=1 C. SYN=1, 序号=Y D. SYN=1, 序号=Y, ACK_{Y+1}=1

网络应用模型 网络协议要素

[tag_link]

正确答案：A

在 TCP 协议的三次握手中，第一次握手由发送方（如客户端）发起，目的是请求建立连接。

此时，发送方发送一个 SYN 报文，其中 SYN 标志位设置为 1，表示同步序列号。 同时，发送方会选择一个初始序列号（ISN），假设为 X，因此报文中的序号字段设置为 X。 在第一次握手中，由于尚未收到对方的任何报文，因此不需要设置 ACK 标志位，也没有确认号。

选项 A 正确描述了这一设置：SYN=1，序号=X。 选项 B 错误，因为序号应为初始序号 X，而非 X+1，且第一次握手不应包含 ACK 标志。 选项 C 和 D 错误，因为序号 Y 是接收方（如服务器）的初始序号，不应由发送方在第一次握手中使用； 同时，ACK 字段在此时也不应出现。

下列哪种技术可以最有效地降低访问 WWW 服务器的时延（ ）。

A. 高速传输线路

B. 高性能 WWW 服务器

C. WWW 高速缓存

D. 本地域名服务器

网络应用模型 通信指标

[tag_link]

正确答案：C

降低访问 WWW 服务器的时延涉及减少从用户发出请求到收到响应的整体延迟。 WWW 高速缓存（如代理缓存或内容分发网络 CDN）通过将热门内容存储在离用户更近的网络边缘，使得用户可以直接从缓存服务器获取数据，避免了远程 WWW 服务器的往返通信，从而显著降低了网络传输延迟和服务器处理延迟。 这种方法针对性最强，能有效减少时延，尤其在内容重复访问的场景下。 相比之下，高速传输线路主要提升带宽，但对减少延迟的作用有限； 高性能 WWW 服务器仅优化服务器端处理，无法解决网络延迟问题； 本地域名服务器虽能加速 DNS 解析，但只影响域名查找阶段，后续数据访问的延迟仍取决于网络和服务器响应。 因此，WWW 高速缓存是最直接且高效的技术。

（13 分）设记录的关键字（key）集合：K={24, 15, 39, 26, 18, 31, 05, 22}，请回答： （1）依次取 K 中各值，构造一棵二叉排序树（不要求平衡），并写出该树的前序、中序和后序遍历序列。 （2）设 Hash 表表长 m=16，Hash 函数 H(key)=(key)%13，处理冲突方法为“二次探测法”，请依次取 K 中各值，构造出满足所给条件的 Hash 表；并求出等概率条件下查找成功时的平均查找长度。 （3）将给定的 K 调整成一个堆顶元素取最大值的堆（即大根堆）。

散列表

[tag_link]

**【解析】** （1）将关键字{24，15，39，26，18，31，05，22}依次插入构成的二叉排序树如下：

先序遍历序列：24，15，05，18，22，39，26，31 中序遍历序列：05，15，18，22，24，26，31，39 后序遍历序列：05，22，18，15，31，26，39，24

（2）各关键字通过 Hash 函数得到的散列地址如下表。

Key=24、15、39 均没有冲突，H₀(26)=0，冲突，H₁(26)=0+1=1，没有冲突； Key=18 没有冲突，H₀(31)=5，冲突，H₁(31)=5+1=6，没有冲突；H₀(05)=5，冲突，H₁(05)=5+1=6，冲突，H₂(05)=5-1=4，没有冲突；Key=22 没有冲突。故各个关键字的存储地址如下表所示。

没有发生冲突的关键字，查找的比较次数为 1，发生冲突的关键字，查找的比较次数为冲突次数+1，因此，等概率下的平均查找长度为：

ASL = (1+1+1+2+1+2+3+1)/2 = 1.5 次

（3）首先对以 26 为根的子树进行调整，调整后的结果如图 b 所示；对以 39 为根的子树进行调整，调整后的结果如图 c 所示；再对以 15 为根的子树进行调整，调整后的结果如图 d 所示；最后对根结点进行调整，调整后的结果如图 e 所示。