模拟卷 4

【解析】 循环队列中，队尾元素的位置由 rear 给出，队列当前元素个数为 length。设队首元素的位置为 front，由于队列元素从 front 连续存储到 rear（考虑循环），因此 rear 与 front 满足关系：

解出 front，得：

选项 C 的表达式为 (1 + rear - m - length) MOD m，可化简为：

在模 $m$ 运算下，减去 $m$ 不改变余数，因此该表达式等价于：

与推导结果一致。

通过实例验证：设 $m=10$ ， $\text{rear}=3$ ， $\text{length}=5$ ，则队首应为位置 9。
计算选项 C：

结果正确；而其他选项均不满足。因此，循环队列的队首元素实际位置为选项 C。

【解析】 栈以向量 V[1..n] 存储，初始栈顶指针 top 为 n+1，这表示栈为空且栈从数组末端向开头方向增长。因为向量有效索引是 1 到 n，top 初始值 n+1 是一个无效位置，意味着栈底在索引 n 附近，栈顶指针向索引 1 方向移动。

进栈操作需要将元素 x 存入向量的有效位置，并更新栈顶指针指向新栈顶。正确步骤应是先减小 top 指针，使其指向一个有效索引（如从 n+1 减到 n），然后将 x 存入该位置。这样，栈顶元素位于 V[top]，top 指向当前栈顶。

分析选项：

• A 和 B 中 top 增加会导致越界访问；
• D 先存入 x 但初始 top 为 n+1，直接访问 V[n+1] 越界；
• 只有 C 先执行 top = top - 1 使指针有效，再执行 V[top] = x，符合栈的操作逻辑。

因此，C 是正确操作。

【解析】 考查由遍历序列确定二叉树、森林与二叉树的转换。根据后序序列，A 是二叉树的根结点。根据中序遍历序列，则二叉树的形态一定如下图左所示。对于 A 的左子树，由后序序列可知，因为 B 比 D 后被访问，因此，B 必为 D 的父结点，又由中序序列可知，D 是 B 的右儿子。对于 A 的右子树，同理可确定结点 E、C、F 的关系。此二叉树的形态如下图右所示。

再根据二叉树与森林的对应关系。森林中树的棵数即为其对应二叉树（向右上旋转 45° 后）中根结点 A 及其“右兄弟”数。可知此森林中有 3 棵树，根结点分别为 A、C 和 F。

【解析】 首先分析选项 A：强连通有向图要求任意两个顶点之间存在双向路径，但并不要求直接有弧（即直接的边）。例如，一个包含三个顶点的有向环，顶点间通过路径相连而非都有直接弧，因此该表述错误。

接着看选项 B：图与树的区别在于树是无环连通图，且对于 n 个顶点的树，边数为 n-1。图的边数可以小于、等于或大于顶点数，例如孤立顶点图边数少于顶点数，因此该表述不准确。

选项 C 正确，因为无向图的连通分量定义为极大连通子图，即不能再添加其他顶点和边而保持连通的子图，这是图论中的标准概念。

最后检查选项 D：子图需要顶点集 V’⊆V 和边集 E’⊆E，且 E’中边的端点必须都在 V’中。选项仅说明 V’和 E’是子集，未强调边的端点限制，因此表述不完整，错误。

综上，正确选项为 C。

【解析】 考查初始堆的建立。首先对以第 $\lfloor n/2\rfloor$ 个结点为根的子树（也即最后一个结点的父结点为根的子树）筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，直到筛选到根结点。从 $\lfloor n/2\rfloor \sim 1$ 依次筛选堆的过程如下图所示：

【解析】
在小顶堆中，每个结点的关键字都小于或等于其子结点的关键字。因此，从任意结点出发，向上遍历父结点直至根结点，所经过的结点关键字会逐渐减小或保持不变，即序列必然是降序排列。

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

【解析】

当待排序元素序列中所有关键字都相等时，序列本身已处于有序状态。此时，不同排序算法的性能表现取决于它们在最好情况下的时间复杂度或实际执行步骤。

• 直接插入排序：在最好情况下（序列有序），只需进行 n-1 次比较，且无需移动元素，时间复杂度为 O(n)，速度很快。

• 冒泡排序：通过优化（如设置交换标志），在序列有序时，一趟扫描（n-1 次比较）后即可终止，时间复杂度也为 O(n)，效率较高。

• 简单选择排序：无论序列是否有序，都必须执行 n-1 趟选择操作，每趟需比较剩余元素以确定最小（或最大）值，比较次数恒定为约 n(n-1)/2 次，时间复杂度始终为 O(n²)，无法利用有序性加速，因此在此场景下速度最慢。

• 基数排序：其时间复杂度为 O(d*(n+k))，其中 d 为关键字位数，k 为基数。当所有关键字相等时，分配和收集操作仍需执行，但整体仍保持线性时间复杂度，远优于 O(n²)。

综上所述，在关键字全相等的情况下，简单选择排序由于固定的二次时间复杂度，排序速度最慢。

【解析】 首先，计算程序 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”的 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 的浮点数，规格化要求尾数的绝对值满足 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 选项是规格化的数。

【解析】 首先，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 芯片。

【解析】
在高速缓存与主存不能同时访问的两级存储体系中，有效存取时间取决于命中率 $H$ 。命中时存取时间为高速缓存存取时间 $100\text{ns}$ ，未命中时需先访问高速缓存（ $100\text{ns}$ ）再访问主存（ $1000\text{ns}$ ），总时间为 $1100\text{ns}$ 。因此有效存取时间公式为：

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

解得：

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

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

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

【解析】 RISC（精简指令集计算机）技术的核心设计思想是简化指令集，使每条指令的执行时间尽可能缩短，从而提高处理器的整体效率。减少指令数量是 RISC 的一个关键特征，这有助于简化硬件设计、优化流水线执行，并降低指令复杂度。因此，选项 C“RISC 的主要目标是减少指令数”是正确的描述。

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

【解析】
在支持多道程序设计的操作系统中，进程调度是共享 CPU 资源的核心机制。操作系统选择新进程来运行通常由特定事件直接触发，这些事件导致当前运行的进程无法继续使用 CPU，从而需要调度程序从就绪队列中选择另一个进程。

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

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

【解析】

• 信号量 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 表示打印机已全部分配出去，可能正有多个进程在使用打印机。

【解析】
内部碎片是指分配给程序的内存块中未被使用的部分，即当分配的内存块大于程序实际需要的空间时，多余的部分形成内部碎片。根据定义，分析各存储分配方法：

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

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

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

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

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

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

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

【解析】
首先计算物理块数为 3 时的缺页率。采用 LRU 算法，模拟访问过程：初始物理块为空，页面走向为

当物理块数为 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 次，缺页率为

再计算物理块数为 4 时的缺页率。物理块数为 4 时，模拟过程如下：

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

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

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

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

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

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

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

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

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

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

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

【解析】 位示图使用 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 与通道之间协调工作的重要机制，用于通知 CPU 有关 I/O 操作的状态变化。在通道系统中，通道独立执行通道程序来处理 I/O 操作，当通道完成通道程序的执行时，它必须向 CPU 发出中断信号，以便 CPU 得知操作已结束，并可以继续后续处理（如检查操作结果或启动新的 I/O）。因此，在这种情况下，中断是必须产生的。

对于其他选项：A 描述的是启动被拒绝的异常情况，虽然也可能产生中断，但并非通道协调工作中的常态；B 中通道接收启动请求时通常不会立即产生中断，因为通道只是开始执行程序；D 过于模糊，通道在执行过程中可能仅在特定事件（如错误）下产生中断，而非必然。综上，C 是最符合题意的选项。

【解析】

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

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

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

【解析】
信道利用率是指发送数据的时间占总周期时间的比例。在停止—等待协议中，一个周期包括发送数据帧、数据帧的传播时延、发送确认帧（本题中确认帧长度可忽略，故发送时间为 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$ ，即

解此不等式：

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

因此，帧长至少为 160 比特，对应选项 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$ 。减去网络地址和广播地址后，可分配地址个数为

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

【解析】 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。

【解析】
ARP（地址解析协议）广播帧用于在局域网内将 IP 地址解析为 MAC 地址，属于数据链路层的广播帧。隔离广播帧意味着阻止其传播到其他网络段，从而缩小广播域。

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

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

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

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