答案A

解析
顺序表是用一段连续的存储单元依次存储线性表的元素，其操作的元素移动特性如下：
1. ①在表头插入一个元素：表头是顺序表的第一个位置，插入时需要将原有的所有元素（从第一个到最后一个）依次向后移动一个位置，才能腾出表头位置给新元素，会移动多个元素。
2. ②在表头删除一个元素：删除表头元素后，需要将后续的所有元素（从第二个到最后一个）依次向前移动一个位置，填补被删除的位置，会移动多个元素。
3. ③在表尾插入一个元素：表尾是顺序表的最后一个位置，直接在该位置的下一个连续存储单元放入新元素即可，无需移动任何元素（只要顺序表未满）。
4. ④在表尾删除一个元素：直接将顺序表的长度减1即可，无需移动任何元素。

综上，会移动多个元素的是①②，对应选项A。

答案D

解析

双向链表的结点包含前驱指针（p2/prev）和后继指针（p1/next），操作时需避免空指针访问（即访问`NULL`指针的成员，会导致程序崩溃），逐一分析选项：

1. 选项A：`while(cu!=NULL) {cu->p2 = cu->p1->p1; cu=cu->p1; }`
   当`cu`的后继指针`cu->p1`为`NULL`时，`cu->p1->p1`会访问空指针的成员，触发运行时错误，因此该代码无法正确执行。

2. 选项B：`while(cu!=NULL && cu->p2!=NULL){cu->p2 = cu->p1->p1; cu=cu->p1; }`
   条件仅判断了`cu->p2`（前驱）非空，未判断`cu->p1`（后继）非空。若`cu->p1`为`NULL`，`cu->p1->p1`仍会访问空指针，无法正确执行。

3. 选项C：`while(cu!=NULL) {if(cu->p1!= NULL){cu=cu->p1->p1; cu=cu->p1; }}`
   逻辑存在问题：当`cu->p1`非空时，先将`cu`赋值为`cu->p1->p1`（后继的后继），随后又将`cu`赋值为`cu->p1`（此时`cu`已是原后继的后继，其`p1`可能为`NULL`）；且若`cu->p1->p1`为`NULL`，后续`cu=cu->p1`也可能无意义。更关键的是，若`cu->p1`为空，循环内无任何操作，`cu`不会更新，会陷入死循环，无法正确执行。

4. 选项D：`while(cu!=NULL){if(cu->p1!= NULL) cu->p2 = cu->p1->p1; cu=cu->p1; }`
   - 先判断`cu`是否为`NULL`，避免空指针操作；
   - 仅当`cu->p1`非空时，才执行`cu->p2 = cu->p1->p1`，避免了访问空指针的情况；
   - 无论`cu->p1`是否为空，最后都会将`cu`更新为`cu->p1`，最终`cu`会逐步遍历到链表尾部（`NULL`），循环正常结束。
   因此该代码可以正确执行。

要解决这个问题，核心是利用层序遍历（从上到下、从左到右）的第一个元素是根节点，结合中序遍历（左-根-右）划分左右子树，逐步重建二叉树，最终得到后序遍历（左-右-根）。

步骤1：确定根节点（层序遍历的第一个元素）
层序遍历的本质是“逐层从左到右遍历”，因此层序序列的第一个元素是整个树的根节点。
题目中层序序列为a, b, g, c, d, e, f，第一个元素是a，故根节点为a。

步骤2：通过中序序列划分左/右子树
中序遍历的本质是“左子树 → 根 → 右子树”，因此在中序序列中找到根节点a，其左侧为左子树，右侧为右子树：
- 中序序列：b, e, d, f, c, a, g
- 左子树中序：[b, e, d, f, c]（根a左侧）
- 右子树中序：[g]（根a右侧）

步骤3：通过层序序列确定子树根节点
层序序列中，根节点a之后的元素按“左子树 → 右子树”的顺序排列：
- 层序序列（排除根a）：b, g, c, d, e, f
- 右子树仅含g（中序已确定），因此g是a的右孩子；
- 剩余元素b, c, d, e, f属于左子树，其中层序第一个元素b是左子树的根（a的左孩子）。

步骤4：递归重建左子树（根为b，中序[b, e, d, f, c]）
1. 中序中b是第一个元素 → b的左子树为空，右子树为[e, d, f, c]；
2. 层序中b之后的左子树元素是c → c是b的右孩子（右子树的根）；
3. 中序中c的左侧是[e, d, f]（c的左子树），右侧为空；
4. 层序中c之后的左子树元素是d → d是c的左孩子；
5. 中序中d的左侧是[e]（d的左子树），右侧是[f]（d的右子树）；
6. 层序中d之后的元素是e、f → e是d的左孩子，f是d的右孩子。

步骤5：最终二叉树结构（与中序、层序完全匹配）
        a
      /   \
     b     g
      \
       c
      /
     d
    / \
   e   f

步骤6：生成后序遍历（左-右-根）
按“左子树 → 右子树 → 根”的顺序遍历：
1. d的子树：e（左）→ f（右）→ d（根）；
2. c的子树：e,f,d（左）→ 空（右）→ c（根）；
3. b的子树：空（左）→ e,f,d,c（右）→ b（根）；
4. a的子树：e,f,d,c,b（左）→ g（右）→ a（根）。

最终后序遍历序列为：e, f, d, c, b, g, a，对应选项C。

详细解析
1. 核心知识点：森林与二叉树的转换规则（孩子兄弟表示法）
- 森林转换为二叉树的核心是“**树的孩子兄弟表示法**”：
  1. 每棵树的根节点视为兄弟关系，按森林中树的次序依次作为前一棵根节点的“右孩子”；
  2. 每棵树内部，节点的第一个孩子作为其“左孩子”，同一父节点的其他孩子依次作为前一个孩子的“右孩子”。
- 二叉树的高度定义：从根节点到最远叶子节点的路径长度（根节点深度为1，高度=最大深度）。

2. 求最小高度的关键：优化树的排列与内部结构
要使转换后的二叉树高度最小，需遵循两个原则：
1. **树的排列顺序**：将节点数多的树作为“左子树主体”，节点数少的树作为“右兄弟”（减少右子树的深度贡献）；
2. **树的内部结构**：每棵树自身应构建为“尽可能平衡的二叉树”（即完全二叉树，最小化单棵树转换后的高度）。

3. 分步计算
- 步骤1：计算每棵树单独转换为二叉树的最小高度（完全二叉树高度）
  - 节点数n=2：完全二叉树高度=2（根+1个孩子）；
  - n=3：完全二叉树高度=2（根+左孩子+左孩子的右兄弟）；
  - n=4：完全二叉树高度=3（根→左→左，根→左→右，根→右，共3层）；
  - n=5：完全二叉树高度=3（5个节点的完全二叉树：层1=1，层2=2，层3=2）；
  - n=7：完全二叉树高度=3（7个节点的满二叉树：层1=1，层2=2，层3=4）。

- 步骤2：优化森林中树的排列顺序
要最小化总高度，应将“高度最大的树作为主树（左子树核心）”，其余树作为主树的“右兄弟”（右子树），因为右兄弟的深度仅比主树根节点深1，贡献更小。
  - 选择节点数最多的树（n=7，转换后高度3）作为主树（根节点A）；
  - 剩余树按节点数从多到少排列（5、4、3、2），依次作为前一棵根的右孩子：
    - 主树根A的右孩子是n=5的树根B（深度2）；
    - B的右孩子是n=4的树根C（深度3）；
    - C的右孩子是n=3的树根D（深度4）；
    - D的右孩子是n=2的树根E（深度5）。

- 步骤3：计算总高度
主树（n=7）的转换后高度为3（最深节点在层3），而右兄弟链的最深节点是E（深度5），但主树内部的最深节点（层3）与右兄弟链的最深节点（层5）均不是最终的最大深度——需考虑“主树的左子树+右兄弟链”的组合深度：
  - 主树（n=7）的转换后二叉树结构：根A（层1）→左孩子（层2）→左/右孩子（层3）；
  - 右兄弟链：A（1）→B（2）→C（3）→D（4）→E（5），但E对应的树（n=2）转换后高度为2，其最深节点在层5+1=6（E的左孩子，层6）。
  - 最终最大深度为6，即二叉树高度为6。

考点分析
- 核心考点：森林与二叉树的转换规则、二叉树高度计算、完全二叉树的最小高度特性。
- 408考试频率：高频考点，常结合树的存储结构、森林与二叉树的互转考查。
- 易错点：忽略“树的内部结构优化（完全二叉树）”或“森林中树的排列顺序”对高度的影响，误将所有树的高度直接相加。

详细解析
1. 核心知识点：哈夫曼树的定义与构造
- 哈夫曼树（最优二叉树）：带权路径长度（WPL）最小的二叉树，其中WPL=Σ（每个节点的权值×该节点的深度）（根节点深度为1）。
- 哈夫曼树构造规则：
  1. 初始化：将所有节点视为独立的二叉树（森林），每个树的权值为节点权值；
  2. 合并：每次从森林中选择**权值最小的两棵树**，将它们作为左右子树合并为一棵新树，新树的权值=两棵子树权值之和；
  3. 重复：直到森林中只剩一棵二叉树，即为哈夫曼树。

2. 分步构造哈夫曼树（确保WPL最小）
已知权值集合：{1,2,4,5,8,10,12}（对应节点a~g），构造步骤如下：
- 第1次合并：选最小的1（a）和2（b），合并为新树T1（权值=3）；森林变为{3(T1),4(c),5(d),8(e),10(f),12(g)}；
- 第2次合并：选最小的3(T1)和4(c)，合并为新树T2（权值=7）；森林变为{5(d),7(T2),8(e),10(f),12(g)}；
- 第3次合并：选最小的5(d)和7(T2)，合并为新树T3（权值=12）；森林变为{8(e),10(f),12(g),12(T3)}；
- 第4次合并：选最小的8(e)和10(f)，合并为新树T4（权值=18）；森林变为{12(g),12(T3),18(T4)}；
- 第5次合并：选最小的12(g)和12(T3)，合并为新树T5（权值=24）；森林变为{18(T4),24(T5)}；
- 第6次合并：合并18(T4)和24(T5)，得到哈夫曼树（根节点权值=42）。

3. 确定各节点的深度
根据构造过程，绘制哈夫曼树结构（深度从根节点1开始）：
- 根节点（权值42）：深度1；
  - 左子树T4（权值18）：深度2；
    - 左子树e（权值8）：深度3；
    - 右子树f（权值10）：深度3；
  - 右子树T5（权值24）：深度2；
    - 左子树g（权值12）：深度3；
    - 右子树T3（权值12）：深度3；
      - 左子树d（权值5）：深度4；
      - 右子树T2（权值7）：深度4；
        - 左子树T1（权值3）：深度5；
          - 左子树a（权值1）：深度6；
          - 右子树b（权值2）：深度6；
        - 右子树c（权值4）：深度5。

- 关键结论：e（权值8）的深度为3，同深度的节点为f（权值10）和g（权值12）。

考点分析
- 核心考点：哈夫曼树的构造方法、WPL计算、节点深度判断。
- 408考试频率：高频考点，常以选择题或应用题形式考查哈夫曼树的构造与WPL计算。
- 易错点：合并时未严格选择“权值最小的两棵树”，导致树结构错误；混淆“深度”（根为1）与“层数”的定义。

答案D

详细解析
1. 核心知识点：有向图的邻接表存储结构
- 邻接表存储规则：
  1. 为每个顶点v∈V创建一个“出边链表”，链表中存储v的所有出边（即从v出发指向其他顶点的边）；
  2. 每个顶点的出边链表由节点组成，每个节点包含“邻接顶点编号”和“下一条出边指针”。
- 入度定义：某顶点v的入度=以v为终点的边的数量（即所有指向v的边的条数）。

2. 入度计算的过程与时间复杂度分析
要计算某顶点v的入度，需统计所有边中“终点为v”的边的数量。但邻接表的存储特性是“只记录每个顶点的出边”，不直接存储入边信息，因此必须遍历**所有边**才能找到指向v的边：
- 遍历方式：依次访问每个顶点的出边链表，检查每条边的终点是否为v，若为则计数+1；
- 时间复杂度分析：
  - 遍历所有顶点的出边链表，总遍历次数=所有边的数量|E|（每条边仅存储一次）；
  - 极端情况1：|E|=0（空图），此时需遍历所有|V|个顶点的空链表，时间复杂度为O(|V|)；
  - 极端情况2：|E|很大（如完全有向图，|E|=|V|×(|V|-1)），此时时间复杂度为O(|E|)；
  - 综上，最坏情况下的时间复杂度为O(max(|V|,|E|))——取|V|和|E|中的较大值。

3. 选项排除
- A. O(|V|)：仅适用于|E|≤|V|的情况，不全面；
- B. O(min(|V|,|E|))：与实际遍历逻辑矛盾，最小化无意义；
- C. O(|E|)：仅适用于|E|≥|V|的情况，忽略空图或稀疏图的O(|V|)场景；
- D. O(max(|V|,|E|))：覆盖所有极端情况，正确。

考点分析
- 核心考点：有向图的邻接表存储结构、入度的定义与计算方法、时间复杂度分析。
- 408考试频率：高频考点，常结合图的存储结构（邻接表、邻接矩阵）考查遍历、度数计算等操作的时间复杂度。
- 易错点：混淆“入度”与“出度”的计算逻辑（出度可直接通过顶点的出边链表长度获得，时间复杂度O(1)），误选O(|V|)或O(|E|)。

解析
关键前提
- 有向无环图（DAG）的最长路径长度（边数）≤ \( n-1 \)（因路径中顶点不重复，最多含 \( n \) 个顶点，对应 \( n-1 \) 条边）；
- 有环有向图存在可重复经过的环结构，可通过循环遍历环生成任意长度的字符串。

选项分析
- 选项A：若 \( G \) 无环，最长路径的边数为 \( n-1 \)，因此 \( S \) 中字符串的最大长度为 \( n-1 \)（空字符串长度为0）。由于每个长度对应的字符串数量有限（每条边的字符固定），故 \( S \) 是有穷集。A正确。
- 选项B：若 \( G \) 无环，最长路径的边数仅为 \( n-1 \)，对应的字符串长度为 \( n-1 \)，不可能存在长度为 \( n \) 的字符串（长度为 \( n \) 需 \( n \) 条边，对应 \( n+1 \) 个顶点，与 \( |V|=n \) 矛盾）。B错误。
- 选项C：若 \( G \) 有环，设环的长度为 \( k \)（\( k \geq 1 \)），可通过循环遍历环 \( t \) 次生成长度为 \( \text{初始路径长度} + t \times k \) 的字符串。当 \( t \) 足够大时，字符串长度必然大于 \( n \)。C正确。
- 选项D：若 \( G \) 有环，取环上任意一条路径（含环本身），环的长度 \( k \leq n \)（环中顶点数不超过 \( n \)），因此存在长度为 \( k \) 的字符串（\( k \leq n < 2n \)），或通过一次环遍历生成长度为 \( k \) 的字符串，显然 \( k < 2n \)。D正确。

考点分析
- 核心考点：有向图的环结构性质、路径长度与顶点数的关系；
- 延伸考点：字符串集的有穷性判定（依赖图的无环性）；
- 408关联知识点：图的基本概念（环、路径）、DAG的最长路径特性。

平衡二叉树（AVL树）的高度为4，根节点左右子树的高度组合可能为（3,3）或（3,2）或（2,3）。要最大化左右子树的节点数之差，应使一棵子树节点数尽可能多，另一棵尽可能少，同时满足高度约束。

- 高度为3的AVL树，最大节点数为满二叉树的节点数，即 \(2^3 - 1 = 7\)；最小节点数为 \(N_{\text{min}}(3) = 4\)。
- 高度为2的AVL树，最大节点数为3（满二叉树），最小节点数为2。

当左右子树高度分别为3和2时，节点数之差可达最大：左子树取最大节点数7，右子树取最小节点数2，差值为 \(7 - 2 = 5\)。此时根节点左右子树高度差为1，满足平衡条件，且整棵树高度为4。

其他组合的差值均小于5。因此，根节点的左右子树的节点数之差最多为5。

答案为 D. 5。

B

根据直接插入排序法依次计算每个选项的比较次数就行，B选项最少，共8次。

答案A

解析
1. 题目核心分析
本题本质是多关键字排序问题：主关键字为C1成绩，次关键字为总分（C1+C2），排序优先级为“主关键字优先，次关键字补充”。解题关键是判断哪种排序算法对多关键字场景的适配性最优。

2. 各选项逐一分析
（1）选项A：基数排序（正确答案）
基数排序是多关键字排序的经典算法，其核心思想是按关键字的优先级（本题中C1为第一优先级，总分为第二优先级），通过“分配-收集”过程依次处理每个关键字，无需自定义复杂的比较逻辑。
适配性分析：处理本题需求时，可先按C1成绩（主关键字）进行基数排序，再按总分（次关键字）进行基数排序（或通过一次多关键字基数排序直接完成）。基数排序无需元素间的直接比较，仅通过关键字的“桶分配”实现排序，在多关键字场景下效率高于基于比较的排序算法，是最适合的选择。

（2）选项B：快速排序（错误）
快速排序是基于比较的排序算法，处理多关键字时需自定义比较函数（先比较C1，C1相等再比较总分），虽然技术上可行，但存在明显缺陷：
快速排序的优势在于单关键字无序序列的高效排序（平均时间复杂度O(nlogn)），但多关键字场景下需额外处理比较逻辑，未体现其算法优势；
快速排序是不稳定排序，若C1相同的元素在排序过程中相对位置可能被打乱，需额外处理稳定性问题（本题虽未明确要求稳定性，但多关键字排序中稳定性通常是重要考量）。

（3）选项C：希尔排序（错误）
希尔排序是插入排序的改进版，核心是通过“增量序列”减少插入排序的移动次数，仅适用于单关键字排序。
适配性分析：处理多关键字时需手动嵌入双关键字比较逻辑，且希尔排序的增量序列设计未针对多关键字优化，排序效率较低（时间复杂度依赖增量序列，最坏为O(n²)），完全不适配本题需求。

（4）选项D：选择排序（错误）
选择排序是基于“每次选择最小元素”的比较排序，时间复杂度固定为O(n²)，效率极低。
适配性分析：处理多关键字时需按“C1优先，总分补充”的规则比较元素，但选择排序的核心优势在于空间复杂度O(1)（原地排序），而非多关键字处理能力，且O(n²)的时间复杂度无法满足大规模数据的排序需求，不符合“最适合”的要求。

3. 考点分析
本题考查排序算法的适用场景与核心特性，属于408数据结构“排序”章节的重点考点，具体要求：
掌握多关键字排序的定义与处理逻辑；
区分基数排序（非比较排序）与快速排序、希尔排序、选择排序（比较排序）的本质差异；
理解各类排序算法的适用场景（如基数排序适配多关键字，快速排序适配单关键字无序序列，希尔排序适配单关键字部分有序序列等）。

4. 延伸提示
408考试中，排序算法的考查常结合“算法特性+场景适配”，需重点记忆：
非比较排序（基数排序、计数排序、桶排序）的核心优势是处理多关键字或范围有限的关键字；
比较排序（快速、归并、堆排等）需自定义比较逻辑处理多关键字，且稳定性、时间复杂度需结合场景判断。

答案：C

详细解析
核心知识点回顾
外部排序的k路归并核心逻辑：
1. 首先通过内部排序将外存数据分割为若干个有序的初始归并段（记初始归并段数为m）；
2. 利用k路归并算法（需内存提供k个输入缓冲区+1个输出缓冲区），将m个初始归并段逐步合并为1个有序文件，合并的轮次即为归并趟数d。

归并趟数的计算公式（向上取整）：
d = ⌈log_k m⌉

逐项分析
Ⅰ. k越大，d越小
根据归并趟数公式 d = ⌈log_k m⌉，当初始归并段数m固定时，k（归并路数）与d（归并趟数）呈反相关：
例：m=8（8个初始归并段）
k=2时，d=⌈log_2 8⌉=3趟；
k=4时，d=⌈log_4 8⌉=2趟；
k=8时，d=⌈log_8 8⌉=1趟。
k增大时，log_k m减小，归并趟数d随之减小，因此Ⅰ正确。

Ⅱ. 初始归并段数不影响d
由公式 d = ⌈log_k m⌉ 可知，d由k（归并路数）和m（初始归并段数）共同决定：
例：k=2（固定）
m=4时，d=⌈log_2 4⌉=2趟；
m=8时，d=⌈log_2 8⌉=3趟。
初始归并段数m变化会直接导致d变化，因此Ⅱ错误。

Ⅲ. 内存大小限制初始归并段的最大长度
初始归并段通过内部排序生成：内存可分配的排序缓冲区空间越大，一次能加载并排序的数据量越多，生成的初始归并段长度就越长；反之，内存空间不足时，只能分割为更多、更短的初始归并段。
例：若内存最多容纳1000条数据，则单次内部排序最多生成长度为1000的初始归并段，无法生成更长的归并段。
因此内存大小直接限制初始归并段的最大长度，Ⅲ正确。

结论
正确的说法为Ⅰ、Ⅲ，对应选项C。

考点定位
1. 外部排序的核心流程（初始归并段生成+k路归并）；
2. 归并趟数的计算逻辑；
3. 归并路数、初始归并段数、内存大小三者的相互影响。

该考点属于数据结构“排序”章节的重点内容，常以选择题形式考查，需熟练掌握公式推导及各因素间的关联关系。

在计算机系统层次结构中，最上层是应用软件层，A正确；ISA（指令集体系结构）是软件与硬件之间的接口，不可或缺，B正确；计算机组成（微架构）是ISA的逻辑实现，而非直接的物理实现层（物理实现涉及电路、布局等更低层设计），因此C错误；操作系统基于ISA管理硬件资源，并向上层软件提供抽象服务，D正确。故本题错误叙述为C。

A

B

A

D

要解决这道题，需分析各类指令对“程序下一条指令地址（由PC寄存器决定）”的影响：

指令分析：
1. Ⅰ 条件转移：
   条件转移仅在“条件满足”时跳转（修改PC为目标地址）；若“条件不满足”，程序按顺序执行，PC保持“PC+指令长度”（与顺序执行的地址一致）。因此，条件转移可能不改变下一条指令地址。

2. Ⅱ Call（调用指令）：
   执行Call时，会将“当前PC的下一条地址”压栈，同时将PC设为“子程序入口地址”，强制跳转到子程序。因此，Call必然改变下一条指令地址。

3. Ⅲ 陷入指令：
   陷入指令会触发异常/中断，PC会跳转到“异常处理程序的入口地址”。因此，陷入指令必然改变下一条指令地址。

4. Ⅳ ret（返回指令）：
   执行ret时，会从栈中弹出“之前Call保存的返回地址”（即Call之后的下一条指令地址，也是主程序原本的顺序执行地址），并赋值给PC。因此，ret会恢复主程序的顺序地址，不改变下一条指令地址。

结论：
Ⅰ和Ⅳ可能不改变下一条指令地址，答案为 B。

要解决这个问题，核心是掌握组相联映射的组号计算逻辑，步骤如下：

第一步：明确关键参数
题目给出条件：
按字节编址（1地址=1字节）
Cache总行数=1024行，4路组相联（1组=4行）
主存块大小=32B
访问主存地址=1028（十进制，字节地址）

第二步：计算核心中间量
1. 计算Cache组数
组相联映射中，组数=Cache总行数÷路数（1组包含“路数”行）：
组数 = 1024 ÷ 4 = 256 组

2. 计算主存块号
主存块号 = 主存地址 ÷ 主存块大小（整数除法，忽略块内偏移）：
主存地址1028对应的主存块号 = 1028 ÷ 32 = 32（因为32×32=1024，1028属于第32个主存块，块内偏移为4）

3. 计算组号
组相联映射的核心规则：主存块号 mod Cache组数 = 组号（确保主存块映射到唯一组）：
组号 = 32 mod 256 = 32

最终答案
该数据所在主存块对应的组号为32，选C。

答案：A

答案：D（I、II、III均正确）

核心逻辑分析（基于“不考虑异常中断和访存额外开销”的理想条件）：
1. 关于I：单周期数据通路的CPI=1  
单周期数据通路的核心设计是：**所有指令都在同一个时钟周期内完成执行**（时钟周期长度由最长指令的执行时间决定）。无论指令类型（如加法、加载），每条指令仅占用1个时钟周期，因此 **CPI（每条指令平均时钟周期数）=1**，I正确。

2. 关于II：多周期数据通路的CPI>1  
多周期数据通路的设计是：**将单条指令的执行分解为多个独立阶段**（如取指、译码、执行、写回，通常k≥2个阶段），每个阶段占用1个时钟周期。因此，单条指令的CPI=k（k≥2），平均CPI必然大于1，II正确。

3. 关于III：流水线数据通路的CPI=1  
流水线数据通路的核心是“重叠执行指令”：将指令执行拆分为多个并行阶段（与多周期一致），但不同指令的不同阶段可在同一时钟周期内并行处理。在理想条件下（无流水线阻塞、无冒险），**每个时钟周期可启动一条新指令、完成一条指令**，最终每条指令的平均时钟周期数=1，即CPI=1，III正确。

综上，I、II、III均正确，答案为 **D**。

在I/O子系统中，特权指令是指只能在核心态（内核模式）下执行的指令，用于保护系统资源。分析各个选项：

- A. I/O指令：直接操作外设，通常不允许用户程序随意访问，属于特权指令。
- B. 关中断指令：用于禁止中断，防止用户程序干扰系统调度，属于特权指令。
- C. 中断返回指令：用于从中断处理程序返回，会改变处理器状态和模式，属于特权指令。
- D. 系统调用指令：是用户程序主动进入内核态的接口，本身在用户态下执行，通过陷入机制触发内核服务，不属于特权指令。

因此，不是特权指令的是D. 系统调用指令。

答案：C

C

答案：D

答案：D

答案：A

答案：C

根据 Bernstein 条件，两个进程并发执行不会发生错误（即保持数据一致性）的充要条件是：  
1. 进程 P 的读集与进程 Q 的写集不相交：\( R(P) \cap W(Q) = \emptyset \)（对应条件Ⅳ）。  
2. 进程 P 的写集与进程 Q 的读集不相交：\( W(P) \cap R(Q) = \emptyset \)（对应条件Ⅰ）。  
3. 进程 P 的写集与进程 Q 的写集不相交：\( W(P) \cap W(Q) = \emptyset \)（对应条件Ⅲ）。  
读-读冲突（条件Ⅱ）不会导致错误，因此不是必要条件。  
综上，充要条件为Ⅰ、Ⅲ、Ⅳ，对应选项 C。

C

答案：C

B

答案：D

答案：D

B

D

D

答案:B

答案：B

A

答案：C

D

答案部分
（1）因为二叉搜索树的中序遍历序列是递增序列，所以使用中序递归遍历二叉树，绝对值与 min 比较后如果比 min 小则继续找；如果大于等于 min，则可以停止查找（使用 flag 标记是否要停止递归），输出。

（2）代码实现：

int min=INT_MAX;
int flag=0;
BiTNode* preNode=NULL;
void seatchK(BiTree root,int k){
    if(root==NULL) return;
    if(flag==1) return;
    seatchK(root->left,k);
    int my_abs=(root->data-k>0)?(root->data-k):(k-root->data);
    if(my_abs>=min){
        if(my_abs>min){printf("差值:%d,结点值:%d",my_abs,root->data);}
        else{printf("差值:%d,结点值:%d,%d",my_abs,root->data,preNode->data);}
        flag=1;
        return;
    }
    min=my_abs;
    preNode=root;
    seatchK(root->right,k);
}

答案内容：
（1）不能，6先出栈后5、4的顺序必须逆序；能得到。
（2）\( P_i>P_k>P_j \)
（3）5个。分别是2143、2134、2341、2314、2431
（4）以1开头的出栈序列有M个，以2开头的出栈序列有M个，全部出栈序列有\(\frac{C_{2k}^k}{k+1}\)个。

答案:（1）分析可知，计算机C按字节编址，所以主存单元的宽度为8位。通用寄存器的宽度与机器字长通常一致，该机的字长为16位，所以是16位。
（2）Op1和op2可以相同，op2和op3不可以相同。
（3）分析可知，该指令为R型指令，且实现的是加法运算，即r2+r9->R2，所以r2的内容为ABCDH+ F001H=9BCEH，R9内容不变，即为F001H。
（4）①是1110；②是0000 0100；③是1111 1011；④是0000 0000 0010

答案：（1）多路选择器
（2）Extop 至少需要 1 位。因为通过 1 位即可实现符号拓展和零拓展。
（3）MARsrc=0，ALUAsrc=0，ALUBsrc=1，RegWr=0
（4）ALUBsrc=2，RegWsrc=1，RegDst=1，RegWr=1，不可以相同，因为左移指令的 shamt需零扩展，而 M 型 offset 需符号扩展，扩展方式不同。

答案：
（1）10ms的时候，产生第1次时间中断，P1和P2都在就绪队列中，此时P2的优先级最高，所以调度P2；
20ms的时候，发生第2次时间中断，P4的优先级最高，所以调度P4；
90ms：发生第9次时间中断，P4运行结束，调度P1；
140ms：发生14次时间中断，P1优先级值减1，变为2，回到就绪队列；此时P3先进入就绪队列，所以调度P3；
所以发生22次时间中断，7次调度；

（2）减少，增大；

答案：
（1）盘块大小4KB，索引节点号128B，所以一个盘块中可以存放4K/128B=32个索引节点；
1000/32≈31.25，且从100盘块号开始存放，所以file索引节点号存放的盘块号是131；
直接地址项所表示的文件大小是5×4K=20480B，21460存放在一级间接地址中，所以最多
需要读2个盘块。
（4096×4K）/128B=2¹⁷个文件
（2）由于dir1非空，所以删除dir1时，需要先删除目录文件file，所以①释放file的索引
节点和占用的盘块，并且把其对应的磁盘位图和索引位图中的信息改为0；②删除dir目录
中dir1的目录项内容，并且更新其对应的位图中信息变为0；

答案：
（1）三次握手。确认序号是 1001
（2）C的拥塞窗口增加到 3MSS=1500B；C的发送窗口设置为 min{1500B,1000B}=1000B
（3）四次挥手；FIN=1，seq=2001，ack_seq=3002
（4）4RTT=20ms