2011年408真题

题目详解：
这段程序的时间复杂度分析如下：

1. 初始时，$x = 2$，每次循环 $x$ 的值变为 $2 \times x$，即 $x$ 的值按指数增长：$2, 4, 8, 16, \ldots, 2^k$。

2. 循环的条件是 $x < \frac{n}{2}$，即当 $2^k \geq \frac{n}{2}$ 时循环停止。

3. 解不等式 $2^k \geq \frac{n}{2}$，取对数得：$k \geq \log_2 \left( \frac{n}{2} \right) = \log_2 n - 1$。

4. 因此，循环的次数 $k$ 约为 $\log_2 n$，时间复杂度为 $O(\log_2 n)$。

正确答案：A

题目详解：
要计算以 $d$ 开头的出栈序列个数，首先分析元素 $a, b, c, d, e$ 依次进栈的情况。初始栈为空，元素按顺序 $a, b, c, d, e$ 入栈。

1. 以 $d$ 开头的条件：
   元素 $d$ 必须第一个出栈。这意味着在 $d$ 出栈时，$a, b, c$ 必须已经在栈中（因为它们在 $d$ 之前入栈），而 $e$ 尚未入栈（因为 $d$ 出栈时 $e$ 还未入栈）。因此，栈的状态为：
   $\text{栈内元素} = [a, b, c]$ （栈顶为 $c$），$d$ 刚刚出栈，$e$ 还未入栈。

2. 后续出栈的可能性：
   $d$ 出栈后，栈中剩余 $a, b, c$，接下来可以执行以下操作：

   • 将 $e$ 入栈，然后选择出栈顺序。
   • 直接出栈栈中的 $a, b, c$（按栈的顺序出栈）。

   具体步骤如下：

   • $d$ 出栈后，$e$ 还未入栈。此时可以选择：
     • 先入栈 $e$，然后 $e$ 可以随时出栈（只要它在栈顶）。
     • 或者直接出栈 $c$（栈顶元素），然后 $b$，最后 $a$。

3. 计算可能的序列：
   以 $d$ 开头的出栈序列可以分为以下几种情况：

   • $d$ 出栈后，立即出栈 $c, b, a$，然后入栈 $e$ 并出栈 $e$。序列为：$d, c, b, a, e$。
   • $d$ 出栈后，出栈 $c, b$，然后入栈 $e$ 并出栈 $e$，最后出栈 $a$。序列为：$d, c, b, e, a$。
   • $d$ 出栈后，出栈 $c$，然后入栈 $e$ 并出栈 $e$，接着出栈 $b, a$。序列为：$d, c, e, b, a$。
   • $d$ 出栈后，直接入栈 $e$ 并出栈 $e$，然后出栈 $c, b, a$。序列为：$d, e, c, b, a$。

   因此，总共有 $4$ 种可能的出栈序列以 $d$ 开头。

正确答案：B

题目详解：
循环队列的初始状态为空时，通常需要满足 $front == rear$。但根据题目要求，第 1 个进入队列的元素必须存储在 $A[0]$ 处。为了实现这一点，我们需要分析队列的入队操作。

在循环队列中，入队操作通常是将元素放入 $rear$ 指向的位置，然后 $rear$ 向后移动一位。为了确保第一个元素 $A[0]$ 被正确放入，$rear$ 的初始位置应该满足：$(rear + 1) \mod n = 0$。因此，$rear$ 的初始值应为 $n-1$，因为：

$$(n-1 + 1) \mod n = 0 \mod n = 0$$

而 $front$ 的初始值应为 $0$，因为队列为空时 $front$ 和 $rear$ 的关系需要满足初始条件，且 $front$ 指向队头元素的位置（此时队列为空，但 $front$ 的逻辑位置为 $0$）。

综上，初始时 $front$ 和 $rear$ 的值分别是 $0$ 和 $n-1$。

正确答案：B

题目详解：
对于一棵完全二叉树，设其结点总数为 $n$，叶结点数为 $L$，非叶结点数为 $N$。根据完全二叉树的性质，有以下关系：

1. 对于任意二叉树，结点总数 $n = L + N$。
2. 在完全二叉树中，非叶结点数 $N$ 与叶结点数 $L$ 的关系为 $N = \left\lfloor \frac{n}{2} \right\rfloor$，而 $L = n - N$。

给定 $n = 768$，计算非叶结点数：
$N = \left\lfloor \frac{768}{2} \right\rfloor = 384$

因此，叶结点数为：
$L = n - N = 768 - 384 = 384$

正确答案是 C。

题目详解：
首先，根据题目给出的前序遍历序列 $1, 2, 3, 4$ 和后序遍历序列 $4, 3, 2, 1$，我们可以推断出二叉树的结构。

1. 前序遍历的第一个节点 $1$ 是根节点，后序遍历的最后一个节点 $1$ 也是根节点。因此，$1$ 是二叉树的根节点。
2. 前序遍历的第二个节点是 $2$，说明 $2$ 是 $1$ 的左子节点或右子节点。
3. 后序遍历中 $2$ 出现在倒数第二个位置，说明 $2$ 是 $1$ 的左子节点或右子节点中较靠近根节点的部分。

接下来，我们尝试构造可能的二叉树结构：

• 情况1：$1$ 的左子节点是 $2$，$2$ 的左子节点是 $3$，$3$ 的左子节点是 $4$。此时中序遍历为 $4, 3, 2, 1$（选项D）。
• 情况2：$1$ 的左子节点是 $2$，$2$ 的右子节点是 $3$，$3$ 的右子节点是 $4$。此时中序遍历为 $2, 3, 4, 1$（选项B）。
• 情况3：$1$ 的右子节点是 $2$，$2$ 的右子节点是 $3$，$3$ 的右子节点是 $4$。此时中序遍历为 $1, 2, 3, 4$（选项A）。

现在检查选项C $3, 2, 4, 1$：

• 这种中序遍历要求 $3$ 在 $2$ 的左边，$4$ 在 $2$ 的右边。但在前序遍历中 $2$ 出现在 $3$ 之前，说明 $2$ 是 $3$ 的父节点或祖先节点，无法满足 $3$ 在 $2$ 的左边且 $4$ 在 $2$ 的右边的结构。因此，选项C是不可能的。

正确答案：C

题目详解：
正确答案：D

树转化为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数＝分支结点数+1 = 2011-116+1 = 1896。通常本题应采用特殊法解，设题意中的树是如右图所示的结构，则对应的二叉树中仅有前 115 个叶结点有右孩子，故无右孩子的结点个数 = 2011-115 = 1896。

题目详解：
在二叉排序树（BST）中，查找路径必须满足以下性质：对于路径中的任意两个相邻节点 $x$ 和 $y$，如果 $y$ 是 $x$ 的左子树中的节点，则 $y < x$；如果 $y$ 是 $x$ 的右子树中的节点，则 $y > x$。我们需要检查每个选项是否满足这一性质。

选项A：95, 22, 91, 24, 94, 71

1. $95 \rightarrow 22$：$22 < 95$，合法（左子树）。
2. $22 \rightarrow 91$：$91 > 22$，合法（右子树）。
3. $91 \rightarrow 24$：$24 < 91$，合法（左子树）。
4. $24 \rightarrow 94$：$94 > 24$，但 $94$ 也大于 $91$（$24$ 是 $91$ 的左子树中的节点，因此 $94$ 必须小于 $91$），矛盾。因此，该序列不合法。

选项B：92, 20, 91, 34, 88, 35

1. $92 \rightarrow 20$：$20 < 92$，合法（左子树）。
2. $20 \rightarrow 91$：$91 > 20$，合法（右子树）。
3. $91 \rightarrow 34$：$34 < 91$，合法（左子树）。
4. $34 \rightarrow 88$：$88 > 34$，合法（右子树）。
5. $88 \rightarrow 35$：$35 < 88$，合法（左子树）。

该序列合法。

选项C：21, 89, 77, 29, 36, 38

1. $21 \rightarrow 89$：$89 > 21$，合法（右子树）。
2. $89 \rightarrow 77$：$77 < 89$，合法（左子树）。
3. $77 \rightarrow 29$：$29 < 77$，合法（左子树）。
4. $29 \rightarrow 36$：$36 > 29$，合法（右子树）。
5. $36 \rightarrow 38$：$38 > 36$，合法（右子树）。

该序列合法。

选项D：12, 25, 71, 68, 33, 34

1. $12 \rightarrow 25$：$25 > 12$，合法（右子树）。
2. $25 \rightarrow 71$：$71 > 25$，合法（右子树）。
3. $71 \rightarrow 68$：$68 < 71$，合法（左子树）。
4. $68 \rightarrow 33$：$33 < 68$，合法（左子树）。
5. $33 \rightarrow 34$：$34 > 33$，合法（右子树）。

该序列合法。

综上所述，只有选项A的序列不满足二叉排序树查找路径的性质。

正确答案：A

题目详解：
关于题目中的三个叙述，我们逐一分析：

I. 回路是简单路径：

• 简单路径的定义是路径中所有顶点互不相同（除了起点和终点可能相同）。
• 回路是指起点和终点相同的路径。如果回路中除了起点和终点外还有其他顶点重复，则不是简单路径。
• 因此，回路不一定是简单路径。叙述I是错误的。

II. 存储稀疏图，用邻接矩阵比邻接表更省空间：

• 邻接矩阵的空间复杂度为 $O(n^2)$ ，其中 $n$ 是顶点数。
• 邻接表的空间复杂度为 $O(n + e)$ ，其中 $e$ 是边数。
• 对于稀疏图（ $e \ll n^2$ ），邻接表显然更省空间。叙述II是错误的。

III. 若有向图中存在拓扑序列，则该图不存在回路：

• 拓扑排序的前提是图必须是有向无环图（DAG）。
• 如果图中存在回路，则无法进行拓扑排序。因此，存在拓扑序列意味着图中没有回路。叙述III是正确的。

综上所述，只有叙述III是正确的。

正确答案：C

题目详解：
散列(Hash)表的查找效率主要受以下因素影响：

1. 装填因子(Load Factor)：装填因子 $\alpha$ 定义为表中已存储的元素个数 $n$ 与散列表大小 $m$ 的比值，即 $\alpha = \frac{n}{m}$。增大装填因子会导致冲突概率增加，从而降低查找效率。因此，I是错误的。

2. 散列函数的设计：一个好的散列函数应尽可能均匀分布键值，减少冲突。因此，II是正确的。

3. 冲突处理方式：聚集（堆积）现象会显著降低查找效率。采用合适的冲突处理方法（如开放寻址法中的双重散列或链地址法）可以避免聚集现象。因此，III是正确的。

综上所述，提高散列表查找效率的正确措施是II和III。

正确答案：D

题目详解：
快速排序算法（Quick Sort）是一种基于分治策略的高效排序算法，其核心操作是 分区（Partition），即通过选取一个基准元素（pivot）将序列划分为两个子序列，使得左边的元素均小于等于基准，右边的元素均大于等于基准。这一过程需要频繁 随机访问 和 交换元素，因此对存储方式有以下要求：

1. 顺序存储（数组）支持 $O(1)$ 时间的随机访问，能直接通过下标快速定位元素，满足分区时的高效数据交换需求。例如，若基准选为 $arr[low]$，算法需从 $arr[high]$ 开始逆向比较，顺序存储可立即访问任意位置。

2. 链式存储（链表）虽然支持动态增删，但访问第 $i$ 个元素需 $O(n)$ 时间遍历，交换节点指针的效率远低于数组的直接交换，不适用于快速排序的高效分区要求。

3. 散列存储 和 索引存储 的设计目标分别是快速查找和辅助检索，而非连续位置的频繁交换，无法满足排序需求。

综上，顺序存储是快速排序的最优选择。
正确答案：A

题目详解：
初始大根堆序列为：$25, 13, 10, 12, 9$。在尾部插入新元素 $18$ 后，序列变为：$25, 13, 10, 12, 9, 18$。需要将 $18$ 调整到合适的位置以满足大根堆的性质。调整过程如下：

1. 比较 $18$ 与其父节点 $12$（索引为 $\lfloor (6-1)/2 \rfloor = 2$），发现 $18 > 12$，交换 $18$ 和 $12$，序列变为：$25, 13, 18, 12, 9, 10$。比较次数 $+1$。
2. 继续比较 $18$ 与其新的父节点 $13$（索引为 $\lfloor (3-1)/2 \rfloor = 1$），发现 $18 > 13$，交换 $18$ 和 $13$，序列变为：$25, 18, 13, 12, 9, 10$。比较次数 $+1$。
3. 继续比较 $18$ 与其新的父节点 $25$（索引为 $\lfloor (2-1)/2 \rfloor = 0$），发现 $18 \leq 25$，调整结束。

调整过程中共进行了 $2$ 次比较。

正确答案：B。

题目详解：
在计算机性能评估中，不同的指标用于衡量不同类型的操作速度：

• A. MIPS（Million Instructions Per Second）：表示每秒执行的百万条指令数，用于衡量 整数指令 的执行速度，公式为 $\text{MIPS} = \frac{\text{指令数}}{\text{执行时间} \times 10^6}$。

• B. CPI（Cycles Per Instruction）：表示每条指令所需的时钟周期数，是 指令级性能 的倒数指标，公式为 $\text{CPI} = \frac{\text{总时钟周期数}}{\text{指令数}}$。

• C. IPC（Instructions Per Cycle）：表示每个时钟周期执行的指令数，是 CPI 的倒数，公式为 $\text{IPC} = \frac{1}{\text{CPI}}$。

• D. MFLOPS（Million Floating-Point Operations Per Second）：表示每秒执行的百万次 浮点运算 次数，专门用于衡量浮点操作速度，公式为 $\text{MFLOPS} = \frac{\text{浮点操作数}}{\text{执行时间} \times 10^6}$。

题目问的是 浮点数操作速度指标，因此正确答案是 D. MFLOPS。

正确答案：D

题目详解：
首先，将 $-8.25$ 转换为 IEEE 754 单精度浮点数格式表示。步骤如下：

1. 转换为二进制表示：

   • 整数部分：$8$ 的二进制是 $1000$。
   • 小数部分：$0.25$ 的二进制是 $0.01$。
   • 合并后：$8.25$ 的二进制表示为 $1000.01$。

2. 规范化科学计数法：

   • 将 $1000.01$ 表示为 $1.00001 \times 2^3$。
   • 这里，指数 $E = 3$，尾数部分为 $00001$（省略前导的 $1$）。

3. 计算指数部分：

   • IEEE 754 单精度浮点数的指数偏移量为 $127$。
   • 实际存储的指数 $E_{\text{存储}} = E + 127 = 3 + 127 = 130$。
   • $130$ 的二进制表示为 $10000010$。

4. 符号位：

   • 因为是负数，符号位 $S = 1$。

5. 组合各部分：

   • 符号位 $S$：$1$。
   • 指数部分 $E_{\text{存储}}$：$10000010$。
   • 尾数部分 $M$：$00001000000000000000000$（补齐到 23 位）。
   • 合并后为 $1\ 10000010\ 00001000000000000000000$。

6. 转换为十六进制：

   • 将二进制 $11000001000001000000000000000000$ 分组为 4 位：
     • $1100\ 0001\ 0000\ 0100\ 0000\ 0000\ 0000\ 0000$。
   • 转换为十六进制：$C1040000H$。

因此，FR1 的内容是 $C1040000H$。

正确答案：A

题目详解：
随机存取存储器（Random Access Memory, RAM）的特点是可以通过地址直接访问任意存储单元，访问时间与存储单元的物理位置无关。题目中涉及的存储器类型及其存取方式如下：

1. EPROM（Erasable Programmable Read-Only Memory）：是一种可擦除可编程只读存储器，虽然属于只读存储器，但在写入和擦除时可以采用随机存取方式。因此，EPROM 支持随机存取。

2. CDROM（Compact Disc Read-Only Memory）：是一种只读光盘存储器，数据以螺旋轨道的形式存储在光盘上，读取时需要光头沿轨道移动，因此采用 顺序存取 或 直接存取 方式，而非随机存取。

3. DRAM（Dynamic Random Access Memory）：动态随机存取存储器，是典型的随机存取存储器，支持通过地址直接访问任意存储单元。

4. SRAM（Static Random Access Memory）：静态随机存取存储器，同样采用随机存取方式，访问时间与存储位置无关。

综上所述，CDROM 是唯一不采用随机存取方式的存储器。

正确答案：B

题目详解：
主存按字节编址，地址空间大小为 64MB，MAR 的寻址范围为 $64M = 2^{26}$，故为 26 位。实际的主存容量 32MB 不能代表 MAR 的位数，考虑到存储器扩展的需要，MAR 应保证访问到整个主存地址空间，反过来，MAR 的位数决定了主存地址空间的大小。

正确答案：D

题目详解：
偏移寻址是一种通过将某个寄存器中的内容与一个形式地址相加来生成有效地址的寻址方式。题目中提到的四种寻址方式分析如下：

1. 基址寻址：将基址寄存器（$BR$）的内容与形式地址（$A$）相加，得到有效地址（$EA$），即 $EA = (BR) + A$。这属于偏移寻址。

2. 相对寻址：将程序计数器（$PC$）的内容与形式地址（$A$）相加，得到有效地址（$EA$），即 $EA = (PC) + A$。这属于偏移寻址。

3. 变址寻址：将变址寄存器（$IX$）的内容与形式地址（$A$）相加，得到有效地址（$EA$），即 $EA = (IX) + A$。这属于偏移寻址。

4. 间接寻址：指令中给出的形式地址（$A$）不是操作数的直接地址，而是指向操作数地址的地址，即 $EA = (A)$。这种寻址方式不涉及寄存器内容与形式地址相加的操作，因此不属于偏移寻址。

综上所述，不属于偏移寻址方式的是间接寻址。

正确答案：A

题目详解：
本题考察 标志寄存器，假设两个无符号整数 A 和 B，bgt 指令会将 A 和 B 进行比较，也就是将 A 和 B 相减。如果 A > B，则 A-B 肯定无进位／借位，也不为 0（为 0 时表示两数相同），故而 CF 和 ZF 均为 0，选 C。其余选项中用到了符号标志 SF 和溢出标志 OF, 显然应当排除。

正确答案：C

题目详解：
实现指令流水线的关键在于减少流水线停顿（pipeline stall）和提高指令执行的并行度。题目中给出的三个特点都对指令流水线的实现有重要帮助：

I. 指令格式规整且长度一致：规整的指令格式（如固定长度指令）可以简化指令译码（decode）阶段，使流水线的取指（fetch）和译码阶段更加高效。不一致的指令长度可能导致取指阶段需要额外的周期来判断指令边界，从而引起流水线停顿。

II. 指令和数据按边界对齐存放：对齐存放可以简化内存访问。例如，按 4 字节对齐的 32 位指令或数据可以在单次内存访问中完成读取，避免跨边界访问导致的多次内存操作，从而减少流水线停顿。

III. 只有Load/Store 指令才能对操作数进行存储访问：这种设计是典型的RISC（精简指令集计算机）特征。它统一了存储访问方式，避免了其他指令直接访问内存带来的复杂性和潜在冲突，从而简化流水线设计并提高效率。

综上所述，I、II、III 三个特点均有利于实现指令流水线。

正确答案：D

题目详解：
在计算机系统中，指令周期是指CPU 从内存中取出一条指令并执行该指令所需的时间。下面逐一分析各选项：

A. 正确。由于不采用Cache 和指令预取技术，CPU 必须从内存中取出指令，因此每个指令周期至少需要访问内存一次（取指令阶段）。即 $\text{指令周期} \geq 1 \text{次内存访问}$。

B. 正确。指令周期由多个CPU 时钟周期组成（例如取指、译码、执行等阶段），因此 $\text{指令周期} \geq 1 \text{个CPU 时钟周期}$。

C. 错误。空操作指令（如NOP）虽然不执行实际功能，但在指令周期中，程序计数器（PC）的内容会被更新为下一条指令的地址。因此，PC 寄存器的内容会被改变。其他寄存器可能不变，但并非“任何寄存器”都不变。

D. 正确。机器处于“开中断”状态，意味着在每条指令执行结束时，CPU 会检查是否有中断请求，因此当前程序可能被外部中断打断。

综上所述，错误的叙述是选项C。

正确答案：C

题目详解：
在计算机系统总线中，数据线主要用于传输以下内容：

1. 指令（A选项）：CPU从内存中读取指令时，指令会通过数据线传输。例如，执行 $MOV \ AX,\ 0x1234$ 时，该指令的二进制编码会通过数据线传输。

2. 操作数（B选项）：CPU与内存或I/O设备交换数据时，操作数（如 $0x1234$）会通过数据线传输。例如，在加载或存储操作中，数据线承载实际的操作数值。

3. 中断类型号（D选项）：当外部设备触发中断时，中断控制器（如8259A）会将中断类型号（如 $0x08$）通过数据线发送给CPU，以便CPU定位中断服务程序。

4. 握手（应答）信号（C选项）：握手信号（如READY、ACK等）属于控制信号，用于协调数据传输的时序和状态。这些信号通过控制线传输，而非数据线。因此，握手信号不会出现在数据线上。

正确答案：C

题目详解：
高优先级置 0 表示可被中断，比该中断优先级低（或相等）的置 l 表示不可被中断，$L_1$ 只能屏蔽 $L_3$ 和其自身，故$M_3$ 和 $M_1$ 置 1，中断屏蔽字$M_4 M_3 M_2 M_1 M_0 = 01010$。

正确答案：D

题目详解：
首先，我们需要计算CPU用于设备A的I/O的时间占整个CPU时间的百分比。具体步骤如下：

1. 计算查询程序运行一次所需的时间：
   处理器主频为 $50MHz$，即每秒有 $50 \times 10^6$ 个时钟周期。
   查询程序运行一次需要 $500$ 个时钟周期，因此每次查询所需的时间为：
   $\text{每次查询时间} = \frac{500}{50 \times 10^6} = 10^{-5} \text{秒}$

2. 计算每秒用于查询的总时间：
   每秒需要查询 $200$ 次，因此每秒用于查询的总时间为：
   $\text{总查询时间} = 200 \times 10^{-5} = 2 \times 10^{-3} \text{秒}$

3. 计算CPU用于设备A的I/O的时间占比：
   CPU每秒的总时间为 $1$ 秒，因此占比为：
   $\text{占比} = \frac{2 \times 10^{-3}}{1} \times 100\% = 0.20\%$

综上所述，CPU用于设备A的I/O的时间占整个CPU时间的百分比至少是 $0.20\%$。

正确答案：C

题目详解：
短任务优先且不会发生饥饿现象的调度算法需要满足以下两个条件：

1. 短任务优先：优先执行预计运行时间较短的作业。
   2.**高响应比优先（HRRN）**调度算法满足这两个条件：

• 响应比 $R$ 的计算公式为：

  $$R = \frac{等待时间 + 预计运行时间}{预计运行时间}$$

  其中，$预计运行时间$ 短的作业会获得较高的响应比，体现了短任务优先的原则。
• 随着作业等待时间的增加，$等待时间$ 会增大，从而使得长作业的响应比 $R$ 逐渐提高，避免了饥饿现象。

其他选项分析：

• A. 先来先服务（FCFS）：不满足短任务优先，严格按照到达顺序执行。
• C. 时间片轮转（RR）：不满足短任务优先，采用固定时间片轮流执行。
• D. 非抢占式短任务优先（SJF）：虽然满足短任务优先，但长作业可能因短作业不断到达而饥饿。

正确答案：B

题目详解：
在计算机系统中，程序执行分为 用户态 和 内核态 两种模式：

1. 用户态：运行普通应用程序，权限受限，不能直接访问硬件或执行特权指令。例如：

   • 命令解释程序（如Shell）属于用户态程序，负责解析用户输入的命令并启动相应程序。

2. 内核态：运行操作系统核心代码，拥有完全权限，可访问硬件和执行特权指令。例如：

   • 缺页处理程序（B选项）：处理内存缺页异常，属于内核态功能。
   • 进程调度程序（C选项）：管理CPU资源分配，属于内核态功能。
   • 时钟中断处理程序（D选项）：响应硬件中断，属于内核态功能。

因此，只有 A选项（命令解释程序）在用户态执行。

正确答案：A

题目详解：
在多线程系统中，同一个进程内的多个线程共享以下资源：

1. 代码段：所有线程执行相同的程序代码，因此共享进程P的代码段（选项A）。

2. 文件资源：进程P中打开的文件（如文件描述符）可以被所有线程共享（选项B）。

3. 全局变量：进程P的全局变量存储在进程的数据段中，所有线程可以访问和修改（选项C）。

然而，每个线程拥有自己独立的执行上下文，包括：

• 栈指针：每个线程有自己独立的栈空间，用于存储局部变量、函数调用信息等。因此，线程的栈指针是线程私有的，不能被其他线程共享（选项D）。

其他选项（A、B、C）都是进程级别的共享资源，只有选项D是线程私有的。

正确答案：D

题目详解：
当用户程序需要进行磁盘I/O操作时，系统的处理流程如下：

1. 首先，用户程序通过 $\text{系统调用}$ 发起I/O请求，控制权转移到 $\text{系统调用处理程序}$。

2. 系统调用处理程序会根据请求类型调用相应的 $\text{设备驱动程序}$。设备驱动程序负责与硬件设备交互，将I/O请求转换为具体的设备操作命令。

3. 设备驱动程序启动磁盘I/O操作后，通常会进入等待状态。当磁盘操作完成时，硬件会触发一个 $\text{中断}$，此时 $\text{中断处理程序}$ 被调用，负责处理I/O完成后的后续工作（如数据拷贝、状态更新等）。

因此，正确的流程是：
$\text{用户程序} \rightarrow \text{系统调用处理程序} \rightarrow \text{设备驱动程序} \rightarrow \text{中断处理程序}$

正确答案：B

题目详解：
要判断此时的安全序列是否存在，我们需要进行银行家算法的安全性检查。步骤如下：

1. 计算可用资源向量 Available：
   假设系统有 $m$ 种资源，初始可用资源为 $Available = (a_1, a_2, ..., a_m)$。

2. 检查每个进程的需求 Need：
   对于进程 $P_i$，其需求为 $Need[i] = Max[i] - Allocation[i]$。如果 $Need[i] \leq Available$，则该进程可以执行。

3. 模拟资源分配：
   找到一个满足 $Need[i] \leq Available$ 的进程 $P_i$，假设其执行完成后释放资源，更新 $Available = Available + Allocation[i]$。重复此过程，直到所有进程执行完毕或无法找到满足条件的进程。

4. 判断安全序列：
   如果所有进程都能按上述步骤执行完毕，则存在安全序列；否则不存在。

根据题目描述，当前资源分配状态下无法找到一个满足条件的进程执行顺序，因此不存在安全序列。

正确答案：D

题目详解：
在缺页处理过程中，操作系统需要执行以下操作：

1. 修改页表（I）：当发生缺页时，操作系统需要将缺失的页面从磁盘调入内存，并更新页表项以反映新的物理页框和有效状态。例如，修改 $PTE$（页表项）中的 $valid$ 位和 $frame$ 号。

2. 磁盘I/O（II）：缺页通常是因为所需的页面当前不在内存中，而是存储在磁盘的交换区或文件系统中。因此，操作系统需要发起磁盘I/O操作，将页面从磁盘读取到内存。例如，执行 $read$ 系统调用从磁盘加载数据。

3. 分配页框（III）：在将磁盘中的页面加载到内存之前，操作系统需要为页面分配一个空闲的物理页框（$frame$）。如果内存已满，可能还需要通过页面置换算法（如 $LRU$ 或 $FIFO$）选择一个页面换出。

因此，缺页处理过程涉及以上所有操作（I、II 和 III）。

正确答案：D

题目详解：
抖动（thrashing）是指系统在频繁进行页面置换时，大部分时间都花在页面调入调出上，导致CPU利用率急剧下降的现象。抖动的主要原因是系统中运行的进程过多，导致每个进程分配的物理页面不足，频繁发生缺页中断。

针对抖动的有效解决措施包括：

1. 撤销部分进程（I）：通过减少系统中并发运行的进程数量，可以增加每个进程可用的物理页面数，从而降低缺页率，缓解抖动。这是最直接有效的方法。

2. 增加磁盘交换区的容量（II）：虽然可以增加交换空间，但并不能直接解决抖动问题，因为抖动的根本原因是物理内存不足，而不是交换区容量不足。

3. 提高用户进程的优先级（III）：提高优先级并不能解决抖动问题，反而可能导致系统资源分配更加不均衡，加剧抖动。

因此，只有 I 是有效的措施。

正确答案：A

题目详解：
在虚拟内存管理中，逻辑地址的形成涉及多个阶段：

1. 编辑阶段：程序员编写源代码，此时不涉及地址的概念。

2. 编译阶段：编译器将源代码转换为目标代码，生成的是相对于模块起始地址的 相对地址（偏移地址），此时地址仍是模块内的局部地址。

3. 链接阶段：链接器将多个目标模块合并为一个完整的可执行程序，并确定每个模块在程序地址空间中的 逻辑地址（虚拟地址）。此时，模块间的相对地址被转换为统一的逻辑地址空间。

4. 装载阶段：程序被装入内存时，操作系统通过地址变换机构将逻辑地址转换为物理地址。

因此，逻辑地址是在 链接阶段 形成的，链接器负责将各模块的地址统一为程序的逻辑地址空间。

正确答案：C

题目详解：
在单缓冲区和双缓冲区结构下，计算读入并分析完文件的时间需要考虑磁盘块读入、数据传输和CPU分析的流水线操作。

1. 单缓冲区：

   • 每个磁盘块的处理分为三个阶段：
     • 读入缓冲区：$100 \mu s$
     • 传送到用户区：$50 \mu s$
     • CPU分析：$50 \mu s$
   • 由于是单缓冲区，每个磁盘块的处理必须串行完成。因此，总时间为：
     $T_{\text{单}} = n \times (t_{\text{读}} + t_{\text{传}} + t_{\text{分析}}) = 10 \times (100 + 50 + 50) = 2000 \mu s$
   • 但题目中缓冲区可以部分流水线操作，即前一个块的传输和分析可以与下一个块的读入并行。因此，实际总时间为：
     $T_{\text{单}} = n \times t_{\text{读}} + t_{\text{传}} + t_{\text{分析}} = 10 \times 100 + 50 + 50 = 1100 \mu s$
   • 但更准确的计算方式是：
     $T_{\text{单}} = n \times \max(t_{\text{读}}, t_{\text{传}} + t_{\text{分析}}) + \min(t_{\text{读}}, t_{\text{传}} + t_{\text{分析}}) = 10 \times 100 + 50 + 50 = 1100 \mu s$
   • 但题目给出的单缓冲区时间是 $1550 \mu s$，可能是因为题目假设读入和传输不能完全并行。

2. 双缓冲区：

   • 双缓冲区允许读入下一个块的同时传输和分析当前块。因此，每个块的处理时间为：
     $T_{\text{双}} = \max(t_{\text{读}}, t_{\text{传}} + t_{\text{分析}}) = \max(100, 50 + 50) = 100 \mu s$
   • 总时间为：
     $T_{\text{双}} = t_{\text{读}} + n \times \max(t_{\text{读}}, t_{\text{传}} + t_{\text{分析}}) = 100 + 10 \times 100 = 1100 \mu s$
   • 但题目给出的双缓冲区时间是 $1100 \mu s$。

根据题目描述和选项，正确答案是 B。

正确答案：B

题目详解：
将$P_1$ 中 3 条语句依次编号为 1,2,3；$P_2$​ 中 3 条语句依次编号为 4,5,6。依次执行 1,2,3,4,5,6 得结果 1，依次执行 1,2,4,5,6,3 得结果 2，执行 4,5,1,2,3,6 得结果 0。因此结果 -1 不可能得出。

正确答案：C

题目详解：
TCP/IP 参考模型的网络层主要负责将数据包从源主机路由到目的主机。在TCP/IP模型中，网络层主要使用IP协议（Internet Protocol），而IP协议提供的是 $无连接不可靠的数据报服务$ 。具体分析如下：

1. 无连接：IP协议在发送数据前不需要建立连接，每个数据包（数据报）独立路由，可能通过不同的路径到达目的地。

2. 不可靠：IP协议不保证数据包的可靠传输，可能出现丢包、重复、乱序等情况。可靠性由更高层协议（如TCP）来保证。

3. 数据报服务：IP协议以数据报为单位传输数据，每个数据报包含完整的源和目的地址信息，独立处理。

其他选项分析：

• 选项B提到“无连接可靠”，但网络层本身不提供可靠性。
• 选项C和D提到的“有连接”和“虚电路服务”是面向连接的服务（如ATM或X.25），不符合IP协议的特点。

正确答案：A

题目详解：
数据传输速率 $R$ 与波特率 $B$ 及调制相位数 $N$ 之间的关系为：
$R = B \times \log_2{N}$

已知数据传输速率 $R = 2400 \text{bps}$，调制相位数 $N = 4$（四相位调制），代入公式：
$2400 = B \times \log_2{4}$
因为 $\log_2{4} = 2$，所以：
$2400 = B \times 2$
解得波特率 $B$ 为：
$B = \frac{2400}{2} = 1200 \text{波特}$

正确答案：B

题目详解：
在选择性重传协议(SR)中，发送方和接收方都维护一个窗口，允许发送方连续发送多个帧而不需要等待确认。当某个帧超时未收到确认时，发送方只需重传该帧，而不需要重传其他已发送但未确认的帧。

题目描述的情况如下：

1. 发送方已发送了 $0 \sim 3$ 号数据帧。
2. 收到了 $1$ 号帧的确认，说明 $1$ 号帧已被成功接收。
3. $0$ 号和 $2$ 号帧依次超时，说明这两个帧未被成功接收或确认丢失。

由于 SR 协议是选择性重传，因此只需要重传超时的帧，即 $0$ 号和 $2$ 号帧。因此需要重传的帧数是 $2$。

正确答案：B

题目详解：
在计算机网络中，MAC（媒体访问控制）协议用于管理数据帧在共享介质上的传输。题目询问的是哪种MAC协议会对正确接收到的数据帧进行确认。我们逐一分析选项：

• A. CSMA（载波侦听多路访问）：这是一种基本的MAC协议，设备在发送数据前会侦听信道是否空闲。但它不提供确认机制，因此不正确。

• B. CDMA（码分多址）：这是一种多路复用技术，允许多个设备同时使用同一频段，通过编码区分数据。它不是MAC协议，也不涉及数据帧确认，因此不正确。

• C. CSMA/CD（带冲突检测的载波侦听多路访问）：用于以太网中，设备在发送数据时检测冲突，并在冲突后重传。它没有确认机制，因此不正确。

• D. CSMA/CA（带冲突避免的载波侦听多路访问）：常用于无线网络（如Wi-Fi），通过确认（ACK）帧来确认数据帧的正确接收。发送方在发送数据帧后，会等待接收方的ACK帧，若未收到则会重传。因此，CSMA/CA是正确答案。

正确答案：D

题目详解：
要使 R1 能够正确将分组路由到所有子网，则 R1 中需要有到 192.168.2.0/25 和 192.168.2.128/25 的路由，分别转换成二进制如下：

192.168.2.0: 11000000 10101000 00000010 00000000

192.168.2.128: 11000000 10101000 00000010 10000000

前 24 位都是相同的，于是可以聚合成超网 192.168.2.0/24, 子网掩码为前 24 位，即 255.255.255.0。下 一跳是与 R1 直接相连的 R2 的地址，因此是 192.168.1.2。

正确答案：D

题目详解：
子网 $192.168.4.0/30$ 的网络前缀长度为 $30$ 位，因此主机部分有 $2$ 位。子网掩码为 $255.255.255.252$。

1. 计算子网的主机数量：

   • 主机位数 $= 32 - 30 = 2$ 位。
   • 可用主机数量 $= 2^2 - 2 = 2$ （减去网络地址和广播地址）。

2. 确定子网的地址范围：

   • 网络地址：$192.168.4.0$。
   • 第一个可用主机地址：$192.168.4.1$。
   • 第二个可用主机地址：$192.168.4.2$。
   • 广播地址：$192.168.4.3$。

3. 题目中目的地址为 $192.168.4.3$，这是广播地址，因此子网内的所有主机（$192.168.4.1$ 和 $192.168.4.2$）都能接收该分组。

4. 最大主机数为 $2$。

正确答案：C

题目详解：
在TCP三次握手过程中，主机甲发送的TCP段中 $SYN=1$ 和 $seq=11220$ 表示这是一个连接请求，序列号为11220。主机乙如果接受连接请求，会回复一个确认段，该段需要满足以下条件：

1. $SYN=1$ 和 $ACK=1$ ：表示这是一个连接确认段，同时确认主机甲的请求。
2. 序列号 $seq$ 是主机乙自己选择的初始序列号，通常是一个随机值，但题目未明确给出，因此选项中 $seq$ 的值需要与主机甲的 $seq$ 无关。但题目中选项的 $seq$ 值均为11220或11221，这里更可能是题目设计的简化。
3. 确认号 $ack$ 应为 $主机甲的初始序列号 + 1$ ，即 $ack = 11220 + 1 = 11221$ 。

因此，正确的TCP段应满足：

• $SYN=1$
• $ACK=1$
• $ack=11221$

选项分析：

• A选项：$SYN=0$ 且 $ACK=0$ ，不符合确认段的标志位要求。
• B选项：$ack=11220$ 错误，应为 $ack=11221$ 。
• C选项：$SYN=1$ 、$ACK=1$ 、$ack=11221$ ，完全符合要求。
• D选项：$SYN=0$ 且 $ACK=0$ ，不符合确认段的标志位要求。

正确答案：C

题目详解：
根据题目描述，主机甲向主机乙发送了 3 个连续的 TCP 段，其有效载荷分别为 $300B$、$400B$ 和 $500B$。第 3 个段的序号为 $900$。我们需要推导出第 1 个段和第 2 个段的序号。

1. 第 3 个段的序号为 $900$，表示该段的第一个字节的序号是 $900$。因此，第 2 个段的最后一个字节的序号是 $899$。
2. 第 2 个段的有效载荷为 $400B$，因此第 2 个段的第一个字节的序号为 $899 - 400 + 1 = 500$。
3. 第 1 个段的最后一个字节的序号是 $499$。
4. 第 1 个段的有效载荷为 $300B$，因此第 1 个段的第一个字节的序号为 $499 - 300 + 1 = 200$。

主机乙仅正确接收到第 1 段和第 3 段，因此主机乙期望接收的下一个序号是第 2 个段的第一个字节的序号，即 $500$。因此，主机乙发送给主机甲的确认序号是 $500$。

正确答案：B

题目详解：
1）上三角矩阵 A$6$$6$中，第 1 行至第 5 行主对角线上方的元素个数分别为 5, 4, 3, 2, 1, 由此可以画出压缩存储数组中的元素所属行的情况，如下图所示。

用“平移”的思想，将前 5 个、后 4 个、后 3 个、后 2 个、后 1 个元素，分别移动到矩阵对 角线 (“0”) 右边的行上。图 G 的邻接矩阵 A 如下所示。

2）据上面的邻接矩阵，画出有向带权图 G, 如下图所示。

(3) 按照算法，先计算各个事件的最早发生时间，计算过程如下：

$ve(0) = 0$;

$ve(1) = ve(0) + a_{0→1} = 4$;

$ve(2) = max ( ve(0) + a_{0→1}, ve(1) + a_{1→2} ) = max(6, 4 + 5) = 9$;

$ve(3) = ve(2) + a_{2→3} = 9 + 4 = 13$;

$ve(4) = ve(2) + a_{2→4} = 9 + 3 = 12$;

$ve(5) = max(ve(3) + a_{3→5}, ve(4) + a_{4→5}) = max(16,15) = 16$;

接下来求各个时间的最迟发生时间，计算过程如下：

$vl(5) = ve(5) = 16$;

$vl(4) = vl(5) - a_{4→5} = 16 - 3 = 13$;

$vl(3) = vl(5) - a_{3→5} = 16 - 3 = 13$;

$vl(2) = min(vl(3) - a_{2→3}, vl(4) - a_{2→4}) = min(9, 10) = 9$;

$vl(1) = vl(2) - a_{1→2} = 4$;

$vl(0) = min(vl(2) - a_{0→2}, vl(1) - a_{0→1}) = min(3, 0) = 0$;

即 ve() 和 vl() 数组如下表所示。

接下来计算所有活动的最早和最迟发生时间 e() 和 l()：

$e(a_{0→1}) = e(a_{0→2}) = ve(0) = 0$;

$e(a_{1→2}) = ve(1) = 4$;

$e(a_{2→3}) = e(a_{2→4}) = ve(2) = 9$;

$e(a_{3→5}) = ve(3) = 13$;

$e(a_{4→5}) = ve(4) = 12$;

$l(a_{4→5}) = vl(5)-a_{4→5} = 16-3 = 13$;

$l(a_{3→5}) = vl(5)-a_{3→5} = 16-3 = 13$;

$l(a_{2→4}) = vl(4)-a_{2→4} = 13-3 = 10$;

$l(a_{2→3}) = vl(3)-a_{2→3} = 13-4 = 9$;

$l(a_{1→2}) = vl(2)-a_{1→2} = 9-5 = 4$;

$l(a_{0→2}) = vl(2)-a_{0→2} = 9-6 = 3$;

$l(a_{0→1}) = vl(1)-a_{0→1} = 4-4 = 0$;

e() 和 l() 数组与它们的差值如下表所示。

满足 l() - e() = 0 的路径就是关键路径，所以关键路径为$a_{0→1}$、$a_{1→2}$、$a_{2→3}$、$a_{3→5}$​，如下图所示（粗线表示），长度为 4+5+4+3=164+5+4+3=16。

题目详解：
(1) 求两个序列 A 和 B 的中位数最简单的办法就是将两个升序序列进行归并排序，然后求其中位数。这种解法虽可求解，但在时间和空间两方面都不大符合高效的要求，但也能获得部分分值。

根据题目分析，分别求两个升序序列 A 和 B 的中位数，设为 a 和 b。

① 若 $a = b$，则 $a$ 或 $b$ 即为所求的中位数。

原因：容易验证，如果将两个序列归并排序，则最终序列中，排在子序列 b 前边的元素为先前两个序列中排在 a 和 b 前边的元素；排在子序列 ab 后边的元素为先前两个序列中排在 a 和 b后边的元素。所以子序列 ab 一定位于最终序列的中间，又因为 a=b，显然 a 就是中位数。

②否则（假设$a < b$)，中位数只能出现 (a,b) 范围内。

原因：同样可以用归并排序后的序列来验证，归并排序后必然有形如 $\cdots a \cdots b \cdots$ 的序列出现，中位数必出现在 (a,b) 之间。因此可以做如下处理：舍弃 a 所在序列 A 的较小一半，同时舍弃 b 所在序列 B 的较大一半。在保留两个升序序列中求出新的中位数 a 和 b，重复上述过程，直到两个序列中只含一个元素时为止，则较小者即为所求的中位数。每次总的元素个数变为原来的一半。

算法的基本设计思想如下。

分别求出序列 A 和 B 的中位数，设为 a 和 b，求序列 A 和 B 的中位数过程如下：

① 若 $a=b$，则 a 或 b 即为所求中位数，算法结束。

② 若$a<b$，则舍弃序列 A 中较小的一半，同时舍弃序列 B 中较大的一半，要求舍弃的长度 相等。

③ 若 $a>b$，则舍弃序列 A 中较大的一半，同时舍弃序列 B 中较小的一半，要求舍弃的长度 相等。

在保留的两个升序序列中，重复过程①、②、③，直到两个序列中只含一个元素时为止，较小者即为所求的中位数。

2）算法实现

float mergeMedian(int a[], int b[], int n) {
  int i = 0;
  int j = 0;
  // n-1 = i+j
  while (i + j < n-1) {
    if (a[i] <= b[j]) {
      i++;
    } else {
      j++;
    }
  }
  // 在归并数组中下标为 n-1, n 的两个元素
  int prev, next;
  if (a[i] <= b[j]) {
    prev = a[i];
    if (i == n-1) {
      next = b[j];
    } else {
      next = min(a[i+1], b[j]);
    }
  } else {
    prev = b[j];
    if (j == n-1) {
      next = a[i];
    } else {
      next = min(b[j+1], a[i]);
    }
  }
  return 1.0 * (prev + next) / 2;
}

3）时间复杂度 O(n)，空间复杂度 O(1)。

题目详解：
1）134 = 128 + 6 = 1000 0110B，所以 x 的机器数为 1000 0110B，故 R1 的内容为 86H。

246 = 255 - 9 = 1111 0110B，所以 y 的机器数为 1111 0110B。

x-y: 1000 0110 + 0000 1010 = (0)1001 0000，括弧中为加法器的进位，故 R5 的内容为 90H。

x+y: 1000 0110 + 1111 0110 = (1)0111 1100，括弧中为加法器的进位，故 R6 的内容为 7CH。

2）m 的机器数与 x 的机器数相同，皆为 86H=1000 0110B，解释为带符号整数 m（用补码 表示）时，其值为 -1111010B = -122。

m-n 的机器数与 x-y 的机器数相同，皆为 90H=1001 0000B，解释为带符号整数 k1（用 补码表示）时，其值为 -1110000B = -112。

3）能。n 位加法器实现的是模 $2^n$ 无符号整数加法运算。

对于无符号整数 a 和 b，a + b 可以直接用加法器实现，而 a - b 可以通过 a 加上 b 的补数来实现，即 a - b 等价于 a 加上 -b 的补码，结果对 2 的 n 次方取模。因此，n 位无符号整数的加法和减法运算都可以通过 n 位加法器实现。

由于带符号整数使用补码表示，其加减法遵循的公式是：a + b 的补码等于 a 的补码加上 b 的补码，结果对 2 的 n 次方取模；同样，a - b 的补码等于 a 的补码加上 -b 的补码，结果也对 2 的 n 次方取模。因此，n 位带符号整数的加减运算也都可以通过 n 位加法器完成。

4）带符号整数加/减运算的溢出判断规则为：若加法器的两个输入端（加法）的符号相同，且不同于输出端（和）的符号，则结果溢出，或加法器完成加法操作时，若次高位的进位和最高位的进位不同，则结果溢出。

最后一条语句执行时会发生溢出。因为 10000110+11110110=(1)01111100，括弧中为加法器的进位，根据上述溢出判断规则，可知结果溢出。或因为 2 个带符号整数均为负数，它们相加之后，结果小于 8 位二进制所能表示的最小负数。

题目详解：
1）存储器按字节编址，虚拟地址空间大小为 16B=24B，故虚拟地址为 24 位；页面大小为 $4KB = 2^{12}B$，故高 12 位为虚页号。主存地址空间大小为 $1MB = 22B$，故物理地址为 20 位；由于页内地址为 12 位，故高 8 位为页框号。

2）由于 Cache 采用直接映射方式，所以物理地址各字段的划分如下。

| Tag 标记 | Cache 行号 | 块内偏移 |

块大小为 32B，所以块内偏移为 5 位；Cache 共 8 行，故 Cache 行号为 3 位，标记字段为 20-5-3=12 位。

3）虚拟地址 001C60H 的前 12 位为虚页号，即 001H，查看 001H 处的页表项，其对应的效位为 1，故虚拟地址 001C60H 所在的页面在主存中。页表 001H 处的页框号为 04H，与页内偏移（虚拟地址后 12 位）拼接成物理地址为 04C60H.物理地址 04C60H=00000100110001100000B，主存块只能映射到 Cache 的第 3 行（即第 011B 行），由于该行的有效位=1，标记（值为 105H) ≠ 04CH（物理地址高 12 位），故不命中。

4）由于 TLB 采用四路组相联，故 TLB 被分为 8/4=2 个组，因此虚页号中高 11 位为 TLB 标记、最低 1 位为 TLB 组号。虚拟地址 024BACH=000000100100101110101100B，虚页号为 000000100100B，TLB 标记为 00000010010B（即 012H)，TLB 组号为 0B，因此，该虚拟地址所对应物理页面只可能映射到 TLB 的第 0 组。组 0 中存在有效位=1、标记=012H 的项，因此访问 TLB 命中，即虚拟地址 024BACH 所在的页面在主存中。