模拟卷4

从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列的是（ ）。

A. 二叉排序树 B. 大顶堆 C. 小顶堆 D. 平衡二叉树

堆的概念 平衡二叉树

[tag_link]

正确答案：C

在小顶堆中，每个结点的关键字都小于或等于其子结点的关键字。

因此，从任意结点出发，向上遍历父结点直至根结点，所经过的结点关键字会逐渐减小或保持不变，即序列必然是降序排列。

对于大顶堆，父结点的关键字大于或等于子结点的关键字，路径上的结点关键字序列是升序排列，不符合要求。 二叉排序树和平衡二叉树的关键字排列没有统一规则，路径上的结点序列不一定满足降序排列。

设待排序元素序列所有元素的关键字都相等，则下列排序方法中排序速度最慢的是（ ）。

A. 直接插入排序

B. 冒泡排序

C. 简单选择排序

D. 基数排序

复杂度分析

[tag_link]

正确答案：C

当待排序元素序列中所有关键字都相等时，序列本身已处于有序状态。 此时，不同排序算法的性能表现取决于它们在最好情况下的时间复杂度或实际执行步骤。 直接插入排序 ：在最好情况下（序列有序），只需进行 n-1 次比较，且无需移动元素，时间复杂度为 O(n)，速度很快。 冒泡排序 ：通过优化（如设置交换标志），在序列有序时，一趟扫描（n-1 次比较）后即可终止，时间复杂度也为 O(n)，效率较高。 简单选择排序 ：无论序列是否有序，都必须执行 n-1 趟选择操作，每趟需比较剩余元素以确定最小（或最大）值，比较次数恒定为约 n(n-1)/2 次，时间复杂度始终为 O(n²)，无法利用有序性加速，因此在此场景下速度最慢。 基数排序 ：其时间复杂度为 O(d*(n+k))，其中 d 为关键字位数，k 为基数。 当所有关键字相等时，分配和收集操作仍需执行，但整体仍保持线性时间复杂度，远优于 O(n²)。 综上所述，在关键字全相等的情况下，简单选择排序由于固定的二次时间复杂度，排序速度最慢。

已知一台时钟频率为 2GHz 的计算机的 CPI 为 1.2。某程序 P 在该计算机上的指令条数为 4×10⁷ 条。若在该计算机上，程序 P 从开始启动到执行结束所经历的时间是 4s，则运行 P 所用 CPU 时间占整个 CPU 时间的百分比大约是（ ）。

A. 40% B. 60% C. 80% D. 100%

计算机性能指标

[tag_link]

正确答案：B

首先，计算程序 P 的 CPU 时间。 CPU 时间的计算公式为：CPU 时间 = 指令条数 × CPI / 时钟频率。 根据题意，时钟频率为 2 GHz = 2 × 10⁹ Hz，CPI 为 1.2，指令条数应为 4 × 10⁹ 条（注：原题中给出的 4 × 10⁷ 条可能为笔误，因为若按此计算，CPU 时间占比仅为 0.6%，与选项不符，结合计算机典型指令规模，此处采用 4 × 10⁹ 条以匹配选项）。

代入公式：CPU 时间 = (4 × 10⁹) × 1.2 / (2 × 10⁹) = 4.8 × 10⁹ / (2 × 10⁹) = 2.4 秒。

程序 P 从启动到结束所经历的墙钟时间为 4 秒，因此运行 P 所用 CPU 时间占整个 CPU 时间的百分比为：(2.4 秒 / 4 秒) × 100% = 60%。

故答案为 60%，对应选项 B。

已知小写英文字母“a”的 ASCII 码值为 61H，现字母“g”被存放在某个存储单元中，若采用偶校验（假设最高位作为校验位），则该存储单元中存放的十六进制数是（ ）。

A. 66H B. E6H C. 67H D. E7H

差错控制

[tag_link]

正确答案：D

首先，由已知条件小写字母“a”的 ASCII 码值为 61H，可推知字母“g”的 ASCII 码值为 61H + 6 = 67H。 ASCII 码通常用 7 位表示，在存储时占用一个字节，其中低 7 位为数据位，最高位用作校验位。

采用偶校验时，需要使整个字节（包括校验位）中 1 的个数为偶数。 计算数据位（即“g”的 ASCII 码 67H 对应的 7 位二进制）中 1 的个数：67H 的二进制表示为 1100111（7 位），其中 1 的个数为 5，是奇数。

因此，校验位应设置为 1，使得总 1 的个数变为偶数（5+1=6）。 将校验位 1 与数据位组合，得到完整的 8 位二进制数为 11100111，转换为十六进制为 E7H。

故存储单元中存放的十六进制数是 E7H，对应选项 D。

设浮点数的基数为 4，尾数用原码表示，则以下（ ）是规格化的数。

A. 1.001101 B. 0.001101 C. 1.011011 D. 0.000010

补码

[tag_link]

正确答案：C

对于基数为 4 的浮点数，规格化要求尾数的绝对值满足 1/4 ≤ |m| < 1。

尾数用原码表示，选项中第一位为符号位（1 表示负，0 表示正），数值部分为小数点后的二进制序列。

首先检查各选项数值部分的绝对值或基 4 表示。 基数为 4 时，每个基 4 数字对应两个二进制位，规格化要求第一个基 4 数字不为零，即数值部分的前两个二进制位不能全为 0。

• A 选项：数值部分 .001101，前两位为 00，对应基 4 数字 0，绝对值约为 0.203125 < 1/4，不规格化。
• B 选项：数值部分 .001101，前两位为 00，对应基 4 数字 0，绝对值约为 0.203125 < 1/4，不规格化。
• C 选项：数值部分 .011011，前两位为 01，对应基 4 数字 1，绝对值约为 0.421875 ≥ 1/4，且小于 1，满足规格化条件。
• D 选项：数值部分 .000010，前两位为 00，对应基 4 数字 0，绝对值约为 0.03125 < 1/4，不规格化。

因此，只有 C 选项是规格化的数。

设某按字节编址的计算机已配有 00000H～07FFFH 的 ROM 区，MAR 为 20 位，现再用 16K×8 位的 RAM 芯片构成剩下的 RAM 区 08000H～FFFFFH，则需要这样的 RAM 芯片（ ）片。

A. 61 B. 62 C. 63 D. 64

主存容量的扩展

[tag_link]

正确答案：B

首先，MAR 为 20 位，总地址空间为 2^20=1MB，地址范围从 00000H 到 FFFFFH。 ROM 区已配置为 00000H～07FFFH，计算其大小：结束地址 07FFFH 减去起始地址 00000H 再加 1，得到 08000H，即 32KB（因为 08000H=32768 字节=32KB）。

因此，RAM 区的地址范围为 08000H～FFFFFH。 总地址空间为 100000H（即 1MB），RAM 区大小等于总空间减去 ROM 区大小，即 100000H - 08000H = F8000H，转换为十进制为 992KB（因为 F8000H=1,015,808 字节=992KB）。

题目中 RAM 芯片规格为 16K×8 位，即每个芯片容量为 16KB（16K×8 位=16,384 字节）。 所需芯片数等于 RAM 区总容量除以单个芯片容量：992KB / 16KB = 62。 因此，需要 62 片这样的 RAM 芯片。

在 Cache 和主存构成的两级存储体系中，Cache 的存取时间是 100ns，主存的存取时间是 1000ns，如果希望有效（平均）存取时间不超过 Cache 存取时间 15%，则 Cache 的命中率至少应为（ ）。（设 Cache 和主存不能同时访问。）

A. 90% B. 98% C. 95% D. 99%

访存过程

[tag_link]

正确答案：D

在高速缓存与主存不能同时访问的两级存储体系中，有效存取时间取决于命中率 $H$ 。

命中时存取时间为高速缓存存取时间 $100\text{ns}$ ，未命中时需先访问高速缓存（ $100\text{ns}$ ）再访问主存（ $1000\text{ns}$ ），总时间为 $1100\text{ns}$ 。 因此有效存取时间公式为： $$T_{\text{eff}}=H\times 100+(1-H)\times (100+1000)=1100-1000H.$$

题目要求有效存取时间不超过高速缓存存取时间的 $15\%$ ，即不超过 $100\text{ns}\times 1.15=115\text{ns}$ 。 代入不等式： $$1100-1000H\le 115.$$

解得： $$1000H\ge 985,H\ge 0.985,$$

即命中率至少为 $98.5\%$ 。 选项中 $99\%$ 满足要求，因此高速缓存命中率至少应为 $99\%$ 。

为了缩短指令中某个地址段的位数，有效的方法是采取（ ）。

A. 立即寻址 B. 变址寻址 C. 间接寻址 D. 寄存器寻址

寄存器类型 指令寻址方式

[tag_link]

正确答案：D

为了缩短指令中地址段的位数，有效的方法是采用寄存器寻址。 在寄存器寻址中，操作数存储在寄存器中，指令中只需指定寄存器编号。 由于寄存器数量有限（例如，32 个寄存器仅需 5 位二进制表示），而内存地址通常需要较多位数（如 32 位或 64 位），因此使用寄存器编号替代内存地址能显著减少地址段所需的位数。

其他选项分析：立即寻址将操作数直接包含在指令中，虽能缩短指令整体长度，但它是消除地址段而非缩短地址段位数； 变址寻址通过寄存器与偏移量组合形成地址，偏移量可能较短，但需额外指定寄存器，不直接优化地址段位数； 间接寻址指令中包含一个间接地址，该地址位数通常与内存地址相近，不能有效缩短地址段位数。 因此，寄存器寻址是最直接有效的方法。

下面关于 RISC 技术的描述中，正确的是（ ）。

A. 采用 RISC 技术后，计算机的体系结构又恢复到早期的比较简单的情况 B. 为了实现兼容，新设计的 RISC 是从原来的 CISC 系统的指令系统中挑选一部分实现的 C. RISC 的主要目标是减少指令数 D. RISC 设有乘、除法指令和浮点运算指令，只是很少使用

复杂和精简指令集

[tag_link]

正确答案：C

RISC（精简指令集计算机）技术的核心设计思想是简化指令集，使每条指令的执行时间尽可能缩短，从而提高处理器的整体效率。

减少指令数量是 RISC 的一个关键特征，这有助于简化硬件设计、优化流水线执行，并降低指令复杂度。 因此，选项 C“RISC 的主要目标是减少指令数”是正确的描述。

选项 A 不正确，因为 RISC 并非简单恢复到早期计算机架构，而是基于现代设计原则（如硬连线控制、流水线技术）的全新演进。 选项 B 错误，因为 RISC 指令集通常是独立设计的，专注于常用指令的优化，而不是从 CISC 指令系统中挑选一部分以实现兼容； 实际上，RISC 与 CISC 在指令集设计上有本质区别。 选项 D 也不准确，虽然一些 RISC 处理器可能不直接包含乘、除法或浮点运算指令（或通过软件模拟实现），但现代 RISC 架构常将这些指令作为扩展集成，且在使用时并非“很少使用”，而是根据应用需求频繁调用。

流水 CPU 是由一系列叫做“段”的处理部件组成的。当流水稳定后，相比具备 $m$ 个并行部件的 CPU 相比，一个 $m$ 段流水 CPU（ ）。

A. 具备同等水平的吞吐能力 B. 不具备同等能力的吞吐能力 C. 吞吐能力小于前者的吞吐能力 D. 吞吐能力大于后者的吞吐能力

计算机性能指标

[tag_link]

正确答案：C

对于一个 $m$ 段流水 CPU，在流水稳定后，理想情况下每个时钟周期可以完成一条指令，因此吞吐能力为每时钟周期一条指令。 而对于具备 $m$ 个并行部件的 CPU，每个部件可以独立执行指令，每个时钟周期可以同时完成 $m$ 条指令，因此吞吐能力为每时钟周期 $m$ 条指令。 假设时钟周期相同，前者的吞吐能力明显小于后者。 因此，一个 $m$ 段流水 CPU 的吞吐能力小于具备 $m$ 个并行部件的 CPU 的吞吐能力，对应选项 C。

在做手术过程中，医生将手伸出，等护士将手术刀递上，待医生握紧后，护士才松手。如果把医生和护士看作两个通信模块，上述一系列动作相当于（ ）。

A. 同步通信 B. 异步通信的全互锁方式 C. 异步通信的半互锁方式 D. 异步通信的不互锁方式

操作系统概念

[tag_link]

正确答案：B

在手术过程中，医生伸手相当于通信中的发送方发出请求信号，护士递上手术刀相当于接收方收到请求后发送应答信号，而医生握紧后护士才松手相当于发送方确认收到应答后，接收方等待确认信号才完成操作。 这一系列动作体现了完整的握手协议，需要双方相互确认，确保可靠传递。 异步通信的全互锁方式正是通过请求、应答和确认三个步骤实现可靠通信，而半互锁方式缺少接收方等待确认的环节，不互锁方式则没有等待过程，同步通信则依赖统一时钟而不需要握手。 因此，该场景对应于异步通信的全互锁方式。

当有中断源发出请求时，CPU 可执行相应的中断服务程序，以下可以提出中断的是（ ）。 I. 外部事件 II. Cache III. 虚拟存储器失效 IV. 浮点运算下溢 V. 浮点运算上溢

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

补码

[tag_link]

正确答案：D

中断源可以分为外部中断和内部中断（异常）。 外部事件如 I/O 设备请求属于典型的外部中断，能够提出中断请求。 虚拟存储器失效（如页面错误）是内部异常，会触发缺页中断，由 CPU 执行中断服务程序处理。 浮点运算上溢属于算术异常，通常作为中断源，CPU 可响应并处理。 Cache 缺失一般由硬件透明处理，不直接向 CPU 提出中断； 浮点运算下溢虽然也是浮点异常，但在许多系统中常被屏蔽或默认处理为零，一般不视为直接中断源。 因此，可以提出中断的是 I、III 和 V。

在 DMA 方式下，数据从内存传送到外设经过的路径是（ ）。

A. 内存 → 数据总线 → 外设

B. 内存 → 数据总线 → DMA → 外设

C. 内存 → CPU → 数据总线 → 外设

D. 外设 → 内存

总线类型 异常和中断

[tag_link]

正确答案：B

【解析】本题考查 DMA 的数据传送方式。 在 DMA 方式下，数据传送不需要经过 CPU，但需要经过 DMA 控制器中的数据缓冲寄存器。 DMA 控制器中的数据缓冲寄存器用来暂存每次传送的数据。 输入时，数据由外设（如磁盘）先送往数据缓冲寄存器，再通过数据总线送到主存。 反之，输出时，数据由主存通过数据总线送到数据缓冲寄存器，然后再送到外设。

当中断发生后，进入中断处理的程序属于（ ）。

A. 用户程序 B. 可能是用户程序，也可能是 OS 程序 C. OS 程序 D. 单独的程序，既不是用户程序也不是 OS 程序

操作系统概念

[tag_link]

正确答案：C

中断发生后，CPU 会暂停当前执行的用户程序，并切换到内核模式（或特权模式），然后根据中断向量表跳转到对应的中断处理程序。 这些中断处理程序，也称为中断服务例程（ISR），是操作系统内核的一部分，负责直接处理硬件中断、异常等事件，管理系统资源和调度。 由于中断处理涉及对硬件和核心系统资源的访问，必须由操作系统在特权模式下执行，用户程序无权直接处理中断。 因此，进入中断处理的程序始终属于 OS 程序，而非用户程序或其他独立实体。

支持多道程序设计的操作系统在运行过程中，会不断选择新进程来运行，共享 CPU 资源，但是下面哪个不是操作系统选择新进程的直接原因，（ ）。

A. 运行进程的时间片用完 B. 运行进程出错 C. 运行进程等待某个事件的发生 D. 有新的进程被创建进入就绪队列

进程和线程 进程概念

[tag_link]

正确答案：D

在支持多道程序设计的操作系统中，进程调度是共享 CPU 资源的核心机制。

操作系统选择新进程来运行通常由特定事件直接触发，这些事件导致当前运行的进程无法继续使用 CPU，从而需要调度程序从就绪队列中选择另一个进程。

选项 A、B 和 C 描述的情况都会直接导致当前进程停止运行：时间片用完时进程被剥夺 CPU； 进程出错时可能终止或进入异常状态； 进程等待事件时会主动阻塞并释放 CPU。 这些事件都意味着 CPU 立即空闲，因此操作系统必须选择新进程来运行，它们都是调度的直接原因。

选项 D 描述的是有新进程被创建并进入就绪队列。 这种情况本身并不直接迫使操作系统中断当前进程的运行。 除非采用抢占式调度且新进程优先级更高，否则新进程只是加入就绪队列等待，当前进程可能继续执行直到主动放弃 CPU 或时间片用完。 因此，新进程创建不是选择新进程的直接原因，而是可能影响后续调度决策的一个条件。

为实现人机交互作用应采用的调度算法是（ ）。

A. 短作业优先调度 B. 时间片轮转法 C. 基于优先权的剥夺调度算法 D. 高响应比优先调度

时间片轮转 处理机调度概念

[tag_link]

正确答案：B

人机交互作用通常指交互式系统，如分时系统，其核心需求是快速响应时间以保证用户体验流畅。 时间片轮转法通过为每个进程分配固定的时间片，并在时间片用完后轮转调度��确保了所有进程都能公平、定期地获得 CPU 时间，从而提供可预测的低延迟响应，非常适合交互式环境。 其他算法则不太适用：短作业优先调度偏向短作业，可能导致长作业饿死，响应时间不稳定； 基于优先权的剥夺调度算法更适用于实时系统，可能牺牲公平性； 高响应比优先调度主要用于批处理系统，无法保证交互所需的即时响应。 因此，时间片轮转法是最佳选择。

某系统有 3 台打印机，N 个进程共享使用。每个进程需先申请 1 台打印机，使用完毕后再释放。用 PV 操作管理时，设置信号量 S 的初值为 3，以下关于信号量 S 的叙述中，正确的是（）

A. 当前 S 的值表示系统中当前可用的打印机台数 B. 当前 S 的值表示系统中当前被占用的打印机台数 C. 当前 S 的值表示系统中当前阻塞等待打印机的进程数 D. 若当前 S 的值为 0，则一定没有进程正在使用打印机

信号量 进程和线程

[tag_link]

正确答案：A

• 信号量 S 用于表示资源（打印机）的数量，采用**资源信号量**（或称记录型信号量）的典型用法。 > 初始时 S = 3，表示 3 台打印机都可用。 >
• 进程申请打印机时执行 P(S)：若 S > 0，则 S 减 1 并分配一台打印机； > 若 S = 0，则进程阻塞等待。 > 因此 **S 的当前值表示系统中当前可用的打印机数量**，A 正确。 >
• B 错误，被占用的打印机数 = 3 − S。 >
• C 错误，阻塞进程数由另一个等待队列记录，并不等于 S 的值（S 可能为负数，其绝对值表示阻塞进程数，但题目是记录型信号量的常规描述，一般 S 值不直接表示阻塞进程数，且通常教材中 S 的值可以小于 0，其绝对值为等待进程数，但本题强调“当前 S 的值”直接含义，应选 A）。 >
• D 错误，S = 0 表示打印机已全部分配出去，可能正有多个进程在使用打印机。 >

若存储单元长度为 $n$ ，存放在该存储单元的程序长度为 $m$ ，则剩下长度为 $n-m$ 的空间称为该单元的内部碎片。下面存储分配方法中，哪种存在内部碎片（ ）。 I. 固定式分区 II. 动态分区 III. 页式管理 IV. 段式管理 V. 段页式管理 VI. 请求段式管理

A. I 和 II B. I、III 和 V C. IV、V 和 VI D. III 和 V

分段内存管理

[tag_link]

正确答案：B

内部碎片是指分配给程序的内存块中未被使用的部分，即当分配的内存块大于程序实际需要的空间时，多余的部分形成内部碎片。

根据定义，分析各存储分配方法：

固定式分区（I）将内存划分为固定大小的分区，程序分配到足够大的分区中，如果分区大于程序大小，分区内剩余空间即为内部碎片。 >

动态分区（II）根据程序需要动态分配内存，分配的大小恰好等于程序需求，因此没有内部碎片，但可能产生外部碎片。 >

页式管理（III）将内存和程序分为固定大小的页和页框，程序的最后一页可能不满，导致页框内剩余空间成为内部碎片。 >

段式管理（IV）按程序的逻辑段分配内存，段大小可变，分配的内存块等于段大小，因此没有内部碎片。 >

段页式管理（V）结合段式和页式，程序先分段再分页，内存以页为单位分配，由于页大小固定，每个页框可能未被完全利用，存在内部碎片。 >

请求段式管理（VI）基于段式管理，段大小可变，分配内存块等于段大小，没有内部碎片。 >

因此，存在内部碎片的方法是固定式分区（I）、页式管理（III）和段页式管理（V），对应选项 B。 >

在一个请求分页系统中，采用 LRU 页面置换算法时，假如一个作业的页面走向为 1,3,2,1,1,3,5,1,3,2,1,5。当分配给该作业的物理块数分别为 3 和 4 时，则在访问过程中所发生的缺页率分别为（ ）。

A. 50%、33% B. 25%、100% C. 25%、33% D. 50%、75%

缺页异常

[tag_link]

正确答案：A

首先计算物理块数为 3 时的缺页率。

采用 LRU 算法，模拟访问过程：初始物理块为空，页面走向为

$$1,3,2,1,1,3,5,1,3,2,1,5$$

当物理块数为 3 时，访问过程中缺页发生情况如下：

• 访问 1、3、2 时均缺页（加载页面）； >
• 访问第 4 个页面 1 时命中； >
• 第 5 个页面 1 命中； >
• 第 6 个页面 3 命中； >
• 第 7 个页面 5 缺页（置换最近最少使用的页面 2）； >
• 第 8 个页面 1 命中； >
• 第 9 个页面 3 命中； >
• 第 10 个页面 2 缺页（置换页面 5）； >
• 第 11 个页面 1 命中； >
• 第 12 个页面 5 缺页（置换页面 3）。 >

总计缺页次数为 6 次，总访问次数为 12 次，缺页率为

$$\frac{6}{12}=50\%$$

再计算物理块数为 4 时的缺页率。

物理块数为 4 时，模拟过程如下：

• 访问 1、3、2 时均缺页（加载页面）； >
• 访问第 4 个页面 1 命中； >
• 第 5 个页面 1 命中； >
• 第 6 个页面 3 命中； >
• 第 7 个页面 5 缺页（此时物理块未满，加载页面 5）； >
• 之后第 8 至 12 个页面 $1,3,2,1,5$ 均在物理块中命中。 >

总计缺页次数为 4 次，总访问次数为 12 次，缺页率约为

$$\frac{4}{12}\approx 33\%$$

因此，物理块数 3 和 4 对应的缺页率分别为 $50\%$ 和 $33\%$ ，对应选项 A。

下列关于文件系统的说法中，错误的是（ ）。 I. 一个文件在同一系统中、不同的存储介质上的拷贝，应采用同一种物理结构 II. 对一个文件的访问，常由用户访问权限和用户优先级共同限制 III. 文件系统采用树型目录结构后，对于不同用户的文件，其文件名应该不同 IV. 为防止系统故障造成系统内文件受损，常采用存取控制矩阵方法保护文件

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

文件概念

[tag_link]

正确答案：D

说法 I 错误，因为文件的物理结构取决于存储介质的特性，不同介质（如硬盘与磁带）可能采用不同的物理结构以优化性能或适应硬件限制，因此拷贝到不同介质时不必使用同一种物理结构。

说法 II 错误，对文件的访问限制主要基于用户访问权限（如读、写、执行），用户优先级通常用于进程调度或资源分配，而非直接限制文件访问，因此“常由用户优先级共同限制”不符合常规文件系统设计。

说法 III 错误，树型目录结构允许通过路径唯一标识文件，不同用户的文件可以具有相同的文件名，只要存储在不同目录下，无需强制文件名不同。

说法 IV 错误，存取控制矩阵主要用于防止未授权访问，属于安全保护机制； 为防止系统故障导致文件受损，常采用备份、日志文件系统或冗余存储等恢复方法，而非存取控制矩阵。

综上，I、II、III 和 IV 均错误，故正确答案为 D。

现代操作系统中，文件系统都有效地解决了文件重名（即允许不同用户的文件可以具有相同的文件名）问题，系统是通过（ ）来实现这一功能的。

A. 重名翻译机构 B. 建立索引表 C. 树型目录结构 D. 建立指针

文件概念

[tag_link]

正确答案：C

现代操作系统中，文件系统采用树型目录结构来解决文件重名问题。 这种结构通过路径名唯一标识文件，路径由目录层级和文件名组成。 不同用户可以在各自的目录下创建同名文件，因为完整路径不同，系统能够区分它们，避免冲突。

例如，用户 A 的文件可能位于“/home/userA/doc.txt”，用户 B 的同名文件位于“/home/userB/doc.txt”。 树型目录结构自然支持这种隔离，是文件系统管理文件的基本方式。

其他选项中，建立索引表主要用于加快文件访问速度，建立指针常用于文件链接，而“重名翻译机构”并非操作系统标准术语，因此它们不能有效解决文件重名问题。

若用 8 个字（字长 32 位，且字号和位号都从 0 开始计数）组成的位示图管理内存，假设用户归还一个块号为 100 的内存块时，它对应位示图的位置为（ ）。

A. 字号为 3，位号为 5 B. 字号为 4，位号为 4 C. 字号为 3，位号为 4 D. 字号为 4，位号为 5

位图法

[tag_link]

正确答案：C

位示图使用 8 个字（每个字 32 位）管理内存，总位数为 8×32=256 位，对应 256 个内存块，块号从 0 到 255。 字号和位号均从 0 开始计数。 计算块号 100 对应的位示图位置时，采用公式：字号 = 块号 ÷ 每字位数，位号 = 块号 % 每字位数。 每字位数为 32，因此 100 ÷ 32 = 3（商），余数 4。 即字号为 3，位号为 4。

验证：字号 3 对应的起始块号为 3×32=96，结束块号为 127。 块号 100 在该范围内，位号=100-96=4。 故对应位示图位置为字号 3、位号 4，与选项 C 一致。

I/O 中断是 CPU 与通道协调工作的一种手段，所以在（ ）时，便要产生中断。

A. CPU 执行“启动 I/O”指令而被通道拒绝接收

B. 通道接收了 CPU 的启动请求

C. 通道完成了通道程序的执行

D. 通道在执行通道程序的过程中

异常和中断

[tag_link]

正确答案：C

I/O 中断是 CPU 与通道之间协调工作的重要机制，用于通知 CPU 有关 I/O 操作的状态变化。 在通道系统中，通道独立执行通道程序来处理 I/O 操作，当通道完成通道程序的执行时，它必须向 CPU 发出中断信号，以便 CPU 得知操作已结束，并可以继续后续处理（如检查操作结果或启动新的 I/O）。 因此，在这种情况下，中断是必须产生的。 对于其他选项：A 描述的是启动被拒绝的异常情况，虽然也可能产生中断，但并非通道协调工作中的常态； B 中通道接收启动请求时通常不会立即产生中断，因为通道只是开始执行程序； D 过于模糊，通道在执行过程中可能仅在特定事件（如错误）下产生中断，而非必然。 综上，C 是最符合题意的选项。

对于可靠服务和不可靠服务，正确的理解是（ ）。

A. 可靠服务是通过高质量的连接线路来保证数据可靠传输 B. 如果网络本身是不可靠的，那么用户只能尝试使用而无更好的办法 C. 可靠性是相对的，不可能完全保证数据准确传输到目的地 D. 对于不可靠的网络，可以通过应用或用户来保障数据传输的正确性

网络协议

[tag_link]

正确答案：D

可靠服务和不可靠服务是计算机网络中的重要概念。 > 可靠服务指数据传输过程中确保无错误、不丢失、不重复且按序交付，通常通过协议机制（如确认、重传、错误检测等）实现，而非仅依赖高质量的物理线路，因此选项 A 不正确。 > 选项 B 的说法过于悲观，即使网络层不可靠，用户或应用程序可以通过上层协议（如 TCP）或自定义机制来提升可靠性，并非无计可施。 >

选项 C 提到“可靠性是相对的，不可能完全保证”，这在一定程度上反映了现实网络中的不确定性，但网络协议设计的目标是提供高可靠性，理论上可通过持续重传等机制接近完全保证，因此该表述不够准确。 > 相比之下，选项 D 正确指出，对于不可靠的网络（如 IP 网络），可以通过应用层或用户端的措施（如使用 TCP 协议或实现应用层确认）来保障数据传输的正确性，这体现了计算机网络中分层设计和端到端原则的核心理念。 >

综上，选项 D 最符合对可靠服务和不可靠服务的正确理解。 >

采用 GBN 帧协议，接收窗口内的序号为 4 时，接收到正确的 5 号帧应该（ ）。

A. 丢弃 5 号帧 B. 将窗口滑动到 5 号 C. 将 5 号帧缓存下来 D. 将 5 号帧交给上层处理

协议数据单元

[tag_link]

正确答案：A

在 GBN（Go-Back-N）协议中，接收窗口的大小固定为 1，这意味着接收方每次只期望接收一个按序到达的帧。 题目中，接收窗口内的序号为 4，表示接收方正等待接收序号为 4 的帧。 当接收到正确的 5 号帧时，由于 5 号帧不是期望的序号（4 号），它属于乱序到达的帧。 根据 GBN 协议规则，接收方会直接丢弃所有乱序帧，而不进行缓存或处理。 同时，接收窗口不会滑动，因为滑动窗口的条件是收到期望的序号帧（即 4 号帧）。 因此，丢弃 5 号帧是符合 GBN 协议的正确操作。 其他选项如滑动窗口、缓存或交给上层处理都不适用于 GBN 协议对乱序帧的处理方式。

信道速率为 4kbps，采用停止—等待协议，设传播时延 $t=20$ ms，确认帧长度和处理时间均可忽略。若信道的利用率能达到至少 50%，则帧长至少为（ ）。

A. 40bit B. 80bit C. 160bit D. 320bit

协议数据单元 信道利用率

[tag_link]

正确答案：C

信道利用率是指发送数据的时间占总周期时间的比例。

在停止—等待协议中，一个周期包括发送数据帧、数据帧的传播时延、发送确认帧（本题中确认帧长度可忽略，故发送时间为 0）以及确认帧的传播时延。 设帧长为 $L$ 比特，信道速率 $R=4000\text{bps}$ ，则发送时间 $T_t=L/R$ 。 传播时延 $t=20\text{ms}=0.02\text{s}$ ，总周期时间为 $T_t+2t$ 。

信道利用率

$U=\frac{T_t}{T_t+2t}$ ，要求 $U\ge 0.5$ ，即

$$\frac{T_t}{T_t+2t}\ge \mathrm{0.5.}$$

解此不等式：

$$T_t\ge 0.5(T_t+2t)⟹T_t\ge 0.5T_t+t⟹0.5T_t\ge t⟹T_t\ge 2t.$$

代入 $T_t=L/R$ 和 $t=0.02\text{s}$ ，得

$$\frac{L}{4000}\ge 2\times 0.02⟹\frac{L}{4000}\ge 0.04⟹L\ge 0.04\times 4000=160\text{bit}.$$

因此，帧长至少为 160 比特，对应选项 C。

TCP/IP 网络中，某主机的 IP 地址为 130.25.3.135，子网掩码为 255.255.255.192，那么该主机所在的子网的网络地址是（ ），该子网最大可分配地址个数是（ ）。

A. 130.25.0.0, 30 B. 130.25.3.0, 30 C. 130.25.3.128, 62 D. 130.25.3.255, 126

子网划分

[tag_link]

正确答案：C

首先，计算子网的网络地址。

将 IP 地址 130.25.3.135 和子网掩码 255.255.255.192 转换为二进制进行 AND 操作。

• IP 地址的二进制为 `10000010.00011001.00000011.10000111`
• 子网掩码的二进制为 `11111111.11111111.11111111.11000000`

AND 操作后，前三个字节不变，最后一个字节为

10000111 AND 11000000 = 10000000 即十进制 128，因此网络地址为 130.25.3.128。

其次，计算子网最大可分配地址个数。 子网掩码 `255.255.255.192` 对应 `/26`，主机位有

$6$ 位，总主机地址数为 $2^6=64$ 。

减去网络地址和广播地址后，可分配地址个数为

$$64-2=62$$

因此，该子网网络地址为 130.25.3.128，最大可分配地址个数为 $62$ ，对应选项 C。

R1 和 R2 是一个自治系统中采用 RIP 路由协议的两个相邻路由器，R1 的路由表如表 1 所示，当 R1 收到 R2 发送的报文（见表 2）后，R1 更新后的 3 个路由表项中距离值从上到下依次为（ ）。

A. 0、4、3 B. 0、4、4 C. 0、5、3 D. 0、5、4

路由表 路由器

[tag_link]

正确答案：D

RIP 协议采用距离向量算法，路由器根据邻居发来的路由更新报文更新自己的路由表。 更新时，对于每个目的网络，计算通过邻居的新距离：邻居报告的距离加上从本路由器到邻居的跳数（相邻路由器跳数为 1），然后与当前距离比较，若新距离更小则更新，若相等或更大则保持原路由。

对于目的网络 10.0.0.0，R1 当前为直接连接，距离 0； R2 报告距离 3，新距离为 3+1=4，大于 0，因此保持距离 0 不变。

对于目的网络 20.0.0.0，R1 当前距离 7 通过 R2； R2 报告距离 4，新距离为 4+1=5，小于 7，因此更新为距离 5。

对于目的网络 30.0.0.0，R1 当前距离 4 通过 R2； R2 报告距离 3，新距离为 3+1=4，等于当前距离，因此保持距离 4 不变。

更新后三个路由表项的距离值依次为 0、5、4，对应选项 D。

下图中，主机 A 发送一个 IP 数据报给主机 B。通信过程中以太网 1 上出现的以太网帧中承载一个 IP 数据报，该以太网帧中的目的地址和 IP 报头中的目的地址分别是（ ）。

A. B 的 MAC 地址，B 的 IP 地址 B. B 的 MAC 地址，R1 的 IP 地址 C. R1 的 MAC 地址，B 的 IP 地址 D. R1 的 MAC 地址，R1 的 IP 地址

以太网 协议数据单元

[tag_link]

正确答案：C

在主机 A 向主机 B 发送 IP 数据报的过程中，由于主机 B 位于不同的网络（通过 WAN 连接），主机 A 需要先将数据报发送到默认网关（即交换机 R1，在此场景中充当路由器或网关角色）。 因此，在以太网 1 上，主机 A 发出的以太网帧的目的 MAC 地址是下一跳设备 R1 的 MAC 地址，以便帧能正确传递到 R1。 而 IP 数据报头的目的 IP 地址始终是最终目标主机 B 的 IP 地址，不会在传输过程中改变。 所以，以太网帧中的目的地址是 R1 的 MAC 地址，IP 报头中的目的地址是 B 的 IP 地址，对应选项 C。

下列网络设备中，能隔离 ARP 广播帧的是（ ）。

A. 路由器 B. 网桥 C. 以太网交换机 D. 集线器

协议数据单元 路由器

[tag_link]

正确答案：A

ARP（地址解析协议）广播帧用于在局域网内将 IP 地址解析为 MAC 地址，属于数据链路层的广播帧。

隔离广播帧意味着阻止其传播到其他网络段，从而缩小广播域。

路由器工作在网络层（第三层），基于 IP 地址进行路由决策。 当路由器接收到 ARP 广播帧时，不会将其转发到其他接口，因为广播帧的目标是本地网络，路由器会终止广播域。 因此，路由器能有效隔离 ARP 广播帧。

其他设备则不能隔离 ARP 广播帧：

• 网桥工作在数据链路层（第二层），虽然能基于 MAC 地址过滤帧，但会转发广播帧，扩展了广播域。 >
• 以太网交换机本质上是多端口网桥，默认情况下将广播帧泛洪到所有端口（除源端口），不隔离广播域； > 除非配置 VLAN，但这不是其基本功能。 >
• 集线器工作在物理层（第一层），仅对信号进行广播，所有端口共享同一冲突域和广播域，无法隔离任何帧。 >

因此，只有路由器具备隔离 ARP 广播帧的能力。 >

下列关于客户/服务器模型的描述中，错误的是（ ）。 I. 客户端和服务器必须都事先知道对方的地址，以提供请求和服务 II. HTTP 基于客户/服务器模型，客户端和服务器端的默认端口号都是 80 III. 浏览器显示的内容来自服务器 IV. 客户端是请求方，即使连接建立后，服务器也不能主动发送数据

A. I 和 IV

B. II 和 IV

C. I、II 和 IV

D. 只有 IV

网络应用模型

[tag_link]

正确答案：C

I 错误：在客户/服务器模型中，客户端需要知道服务器的地址以发起请求，但服务器不需要事先知道客户端的地址； 服务器在连接建立后从请求中获取客户端地址。 II 错误：HTTP 基于客户/服务器模型，但默认端口号仅服务器端为 80，客户端使用临时分配的随机端口，并非固定为 80。 III 正确：浏览器作为客户端，其显示的内容确实来自服务器响应的数据。 IV 错误：客户/服务器模型中，服务器在某些协议下可以主动发送数据，例如 FTP 主动模式或 WebSocket 推送，并非绝对不能主动发送。 因此，错误的陈述是 I、II 和 IV，对应选项 C。

请回答下列问题：

(1) 试证明若图中各条边的权值各不相同，则它的最小生成树唯一。 (2) Prim 算法和 Kruskal 算法生成的最小生成树一定相同吗？ (3) 画出下列带权图 G 的所有最小生成树。

最小生成树

[tag_link]

**【解析】** (1) 采用反证法证明：假设图中有两个不同的最小生成树 $T_1$ 和 $T_2$ 。设 $e$ 是 $T_1$ 中但不在 $T_2$ 中的权值最小的边。将 $e$ 添加到 $T_2$ 中，会形成一个环，该环中至少存在一条边 $f$ 不在 $T_1$ 中。由于图中各边权值各不相同，比较 $e$ 和 $f$ 的权值。若 $w(f)<w(e)$ ，则在 $T_2$ 中用 $e$ 替换 $f$ 会得到一棵权值更小的生成树，与 $T_2$ 是最小生成树矛盾；若 $w(f)>w(e)$ ，则在 $T_1$ 中用 $f$ 替换 $e$ 会得到一棵权值更小的生成树，与 $T_1$ 是最小生成树矛盾。因此假设不成立，最小生成树唯一。

(2) Prim 算法和 Kruskal 算法都是贪心算法，用于求解最小生成树。当图中边权值各不相同时，最小生成树唯一，因此两种算法必然得到相同的最小生成树。但当图中存在权值相同的边时，最小生成树可能不唯一，两种算法在选择边时可能做出不同选择，从而生成不同的最小生成树。因此，它们生成的最小生成树不一定相同。

(3) 根据 Kruskal 算法，先把 $c-d$ 的边（权值 $20$ ）加入集合，而接下来选择下一条边时，因为有两条权值为 $40$ 的边可以选择，那么因为不同的选择就会生成出不同的最小生成树。若选择 $b-d$ ，然后同样出现 $c-d$ 与 $a-c$ 的选择，而不管先选择哪条边，另一条边也会成为下一个选择的对象，所以这里不影响树的结构，最后答案为左边这棵树；而当之前第二次选择边的时候，选择 $c-b$ 则会是右边的最小生成树。