- 考点：双向循环链表的访问特性与删除操作时间复杂度。
- 关键分析：
  1. 双向循环链表的核心优势是“首尾节点可直接访问”（头节点head的next指向第1个数据节点，prev指向尾节点），无需遍历。
  2. 选项A：i=1时，目标节点是head->next（直接访问，O(1)查找），删除需修改两处指针：① head->next = 目标节点->next（更新头节点的后继）；② 目标节点->next->prev = head（更新原第2个节点的前驱），整个过程无遍历，时间复杂度O(1)，**正确**。
  3. 选项B：i=n（尾节点）时，目标节点是head->prev（直接访问，O(1)查找），修改指针仅需O(1)，时间复杂度应为O(1)，而非O(n)，错误。
  4. 选项C：i=1或i=n时无需遍历，时间复杂度O(1)，“无论i为何值均为O(n)”不符合最优操作，错误。
  5. 选项D：i>n/2时反向遍历最多需O(n/2)，仍属于O(n)量级，无法优化至O(1)，错误。

- 考点：栈的“先进后出”特性与操作模拟。
- 关键分析（按出栈序列反向推导操作流程）：
  1. 要让b先出栈：必须先执行“a入栈→b入栈→b出栈”，此时栈内元素为[a]，最大容量2。
  2. 要让d出栈：后续执行“c入栈→d入栈→d出栈”，此时栈内元素为[a,c]，最大容量3。
  3. 要让e出栈：执行“e入栈→e出栈”，此时栈内元素仍为[a,c]，最大容量保持3。
  4. 最后执行“c出栈→a出栈”，栈空。
- 结论：栈内元素最多时为3个（a、c、d 或 a、c、e），最大容量为3，**正确**。

- 考点：AVL树的结构特性、插入操作与高度计算。
- 关键分析：
  1. 原AVL树结构（平衡因子均为-1/0/1）：
     - 根节点：30（平衡因子0，左子树高2，右子树高2）
     - 左子树：20（左孩子10，平衡因子0）
     - 右子树：40（右孩子50，平衡因子0）
     - 原树高度：3（根1→20/40→10/50，最深层为3）。
  2. 插入35的过程：
     - 35比40小，作为40的左孩子插入，此时40的左子树高1、右子树高1，平衡因子0（无失衡）。
     - 根节点30的左子树高2（20→10），右子树高2（40→35/50），平衡因子0（无失衡）。
  3. 插入后树的高度：最深层仍为3（根1→40→35/50），高度保持3，**正确**。

- 考点：哈夫曼树的核心特性（节点度数、WPL、编码、节点总数）。
- 关键分析：
  1. 选项A：哈夫曼树通过“每次合并两个最小权值节点”构造，仅含度0（叶子节点）和度2（合并节点），无度1节点，正确。
  2. 选项B：给定n个权值（n≥2），哈夫曼树的**最小带权路径长度（WPL）是唯一的**（尽管当存在多个相同权值节点时，树的结构可能不同，但WPL必为最小值且唯一），因此“带权路径长度可能不唯一”的说法错误，**正确选项**。
  3. 选项C：哈夫曼编码通过“左分支标0、右分支标1”（或反之）生成，任意叶子节点的编码都不是其他叶子节点编码的前缀（前缀编码），正确。
  4. 选项D：哈夫曼树中，叶子节点数m，度2节点数为m-1（每次合并生成1个度2节点，共合并m-1次），总节点数=m+(m-1)=2m-1，正确。

- 考点：DAG的拓扑排序特性与关键路径定义。
- 关键分析：
  1. 选项A：拓扑排序结果不唯一（若存在多个入度为0的节点，选择顺序不同会导致结果不同），错误。
  2. 选项B：拓扑排序结果不唯一与关键路径是否唯一无必然联系（例如：多个拓扑序列但最长路径唯一），错误。
  3. 选项C：关键路径是DAG中从起点到终点的最长路径（决定项目最短完成时间），路径上的活动总时差（可延迟时间）为0，正确，**正确选项**。
  4. 选项D：拓扑排序可通过BFS（Kahn算法，基于入度为0的节点）和DFS（逆后序遍历）两种方式实现，错误。

- 考点：B树的定义（阶数与节点关键字范围）、插入操作与分裂规则。
- 关键分析：
  1. 5阶B树的核心规则：
     - 根节点：关键字数∈[1,4]（最少1个，最多4个）；
     - 非根节点（叶子/分支节点）：关键字数∈[2,4]（最少2个，最多4个）；
     - 树高2表示“根节点+叶子节点”（所有叶子在同一层，无中间分支节点）。
  2. 原树状态（8个关键字，树高2）：
     - 根节点需分裂为3个叶子节点（因根节点最多4个关键字，8个关键字需3个叶子节点，每个节点关键字数∈[2,4]），示例分布：叶子1{10,20}、叶子2{30,40}、叶子3{50,60,70,80}（或其他符合范围的分布，如叶子2{30,40,50}、叶子3{60,70,80}）。
  3. 插入45的过程：
     - 45属于[30,40]或[30,40,50]对应的叶子节点，插入后该叶子节点的关键字数为3（如原叶子2{30,40}→插入后{30,40,45}），未超过最大限制4，无需分裂。
  4. 插入后树高：仍为2（根节点+叶子节点），**正确**。

- 考点：排序算法的稳定性、空间复杂度与外部排序适用性。
- 关键约束：10^6个整数占4MB（10^6×4=4,000,000字节≈3.81MB），内存限制1MB（仅能加载262,144个元素），需稳定+外部排序（无法一次性加载全部数据）。
- 选项分析：
  1. 选项A：快速排序（不稳定，内部排序，需一次性加载数据，内存不足），排除。
  2. 选项B：归并排序（稳定，但外部归并需额外空间存储子序列，空间复杂度高，不满足内存限制），排除。
外部归并排序需额外 O (n) 空间存储子序列（1MB 内存不足以容纳子序列），因此排除；
  3. 选项C：基数排序（稳定，分布式排序，按位分组处理，无需加载全部数据，仅需少量内存存储当前处理的位段数据，适合外部排序），**正确选项**。
基数排序属于 “分布式排序”，按位（如十进制位、二进制位）分组处理，每次仅需存储当前位的临时数据（内存占用≤1MB），且天然稳定，完全匹配题干约束。
  4. 选项D：堆排序（不稳定，内部排序，内存不足），排除。

- 考点：散列表（线性探测）的成功查找平均长度（ASL_succ）计算。
- 核心公式：无删除操作时，线性探测的成功查找平均长度为  
  \( ASL_{succ} = \frac{1}{n} \sum_{i=1}^n l_i \)，其中\( l_i \)为第i个关键字的查找长度（探测次数），n为关键字个数。
- 关键分析：
  1. 线性探测的特点：无删除时，关键字会形成连续的“块”（簇），块内第k个元素的查找长度为k。
  2. 已知ASL_succ=1.5，表长11，求最大n：  
     \( \sum_{i=1}^n l_i = 1.5n \)。
  3. 推导：当n=6时，最优分布为“3个块各2个元素”，每个块的查找长度和为1+2=3，3个块总查找长度=3×3=9，此时\( ASL_{succ}=9/6=1.5 \)，恰好满足条件。
  4. 若n=7，即使最优分布（如4个块：3个2元素块+1个1元素块），总查找长度=3×3 +1=10，\( ASL_{succ}=10/7≈1.43 <1.5 \)，但实际线性探测中，n=7时无法保证查找长度和不超过1.5×7=10.5（且表长11限制下，n=7会导致块分布更分散，查找长度和易超标），因此最大n为6，**正确**。

- 考点：最小生成树（MST）的核心特性（边数、唯一性、边的选择规则）。
- 关键分析：
  1. 选项A：MST的边数=顶点数-1=6-1=5；所有边权值不同时，Kruskal算法（按权值从小到大选边，避环）和Prim算法（选当前最小权边连接已选顶点）的选择均无歧义，MST唯一，**正确选项**。
  2. 选项B：MST边数应为5（而非6），且边权不同时MST必唯一，错误。
  3. 选项C：权值为1的边是图中最小权边，MST必包含最小权边（无环时优先选择，若有环则最小权边不在环中，仍需选择），因此“不一定在MST中”错误。
  4. 选项D：MST是“选5条最小权且无环的边”，而非“所有边中最小的5条边”（最小的5条边可能形成环，需排除环中最大权边），错误。

- 考点：递归函数的调用栈深度计算。
- 关键分析：
  1. 递归调用流程：f(100)→f(98)→f(96)→...→f(2)→f(0)（f(0)为递归终止条件，无后续调用）。
  2. 递归调用次数：从100到0，步长-2，共50次调用（f(100)→f(98)是第1次，...，f(2)→f(0)是第50次）。
  3. 栈深度定义：栈中元素个数=递归调用次数+1（包含初始调用f(100)），即50+1=51。
- 结论：递归调用栈的最大深度为51，**正确**。

- 考点：归并排序与二分查找的时间复杂度叠加分析。
- 关键分析：
  1. 归并排序的时间复杂度：O(n log n)（分治阶段：将数组拆分为log n层；归并阶段：每层需O(n)时间合并子数组，共log n层，总O(n log n)）。
  2. 二分查找的时间复杂度：每次二分查找（无论数组是否有序）的时间为O(log n)（基于数组下标随机访问）。
  3. 二分查找的执行次数：归并排序的“子数组归并操作”总次数为O(n)（每个元素参与合并的次数为log n，但“完成一次子数组归并”指的是合并一个独立的子数组对，总次数为n-1次），但核心是“时间复杂度量级主导”：
     - 归并排序总时间：O(n log n)（主导项）；
     - 所有二分查找总时间：O(n) × O(log n) = O(n log n)（与主导项同量级）；
     - 总时间复杂度：O(n log n) + O(n log n) = O(n log n)（同量级叠加，仍为O(n log n)）。
  4. 排除O(n log²n)：若误将“每层归并后执行一次二分查找”理解为log n次二分查找，总时间为O(n log n) + O(log n × log n) = O(n log n)（log²n远小于n log n，可忽略），因此仍为O(n log n)。
- 结论：总时间复杂度为O(n log n)，**正确**。

B。解析：IEEE 754单精度浮点数格式为1位符号位、8位指数位、23位尾数位。0x40400000的二进制为01000000010000000000000000000000。符号位0，指数位10000000（128），尾数位10000000000000000000000。实际指数为128-127=1，尾数为1.10000000000000000000000（二进制），即1.5。因此值为1.5 * 2^1 = 3.0。

B。

解析：AMAT = HitTime_L1 + MissRate_L1 * (HitTime_L2 + MissRate_L2 * MemoryAccessTime) = 1 + 0.10 * (15 + 0.20 * 100) = 1 + 0.10 * (15 + 20) = 1 + 0.10 * 35 = 1 + 3.5 = 4.5周期。

C。解析：LW指令在MEM阶段结束后才能将数据写入寄存器，而ADD指令在ID阶段需要R1的值。因此，在LW和ADD之间存在数据冒险。由于没有转发，需要在LW之后插入2个NOP，以便ADD在ID阶段之后能获取到正确的值。SUB和OR之间没有依赖，因此不需要NOP。所以总共需要2个NOP。

A。解析：页面大小4KB=2^12字节，页内偏移12位，虚拟页号20位。一级页表索引10位（因为1024=2^10），二级页表索引10位。一级页表大小1024*4字节=4KB。每个二级页表大小1024*4字节=4KB。最大情况下，所有1024个二级页表都存在，总大小1024*4KB=4MB。加上一级页表4KB，可忽略，因此约4MB。

C。解析：中断是由外部事件或异常引起的。A除数为0是异常，会导致中断；B系统调用通过软中断实现；D定时器溢出是外部中断；C缓存缺失由硬件处理，通常不会导致中断，而是通过缓存控制器处理，对CPU透明。

B。解析：指令有32条，操作码至少5位。有16个寄存器，每个寄存器操作数需要4位。立即数需要16位。在固定长度指令格式中，通常指令长度固定为字长，如32位，并且操作数类型由操作码隐含，例如 separate instructions for register-register and register-immediate. 因此，最小指令长度为32位，可以处理寄存器操作数（5位操作码 + 4位 + 4位 = 13位）和立即数操作数（5位操作码 + 4位 + 16位 = 25位），均小于32位。因此32位是可行的。

B。解析：奇偶校验码只能检测错误，不能纠错；CRC码用于错误检测，不能纠错；曼彻斯特编码是同步编码，用于数据传输，没有纠错能力；海明码是一种纠错码，可以检测并纠正一位错误。

C。解析：在单总线结构中，每个总线周期只能完成一个数据传送。执行ADD指令需要：1. 取指令（使用总线从内存读指令），2. 读寄存器R2（使用总线将R2值送到ALU），3. 读寄存器R3（使用总线将R3值送到ALU），4. 写结果到R1（使用总线将ALU结果写回R1）。因此至少需要4个总线周期。执行加法在ALU中不需要总线周期。

D。解析：磁盘访问时间 = 寻道时间 + 旋转延迟 + 传输时间。平均寻道时间5ms。旋转延迟：转速10000转/分，所以每转时间60/10000=6ms，平均旋转延迟为半转即3ms。传输时间：传输速率100MB/s，传输4KB=4096B，传输时间=4096 / (100 * 10^6) = 0.00004096s ≈ 0.04ms。总时间≈5ms + 3ms + 0.04ms = 8.04ms ≈ 8ms。

C。解析：2位饱和计数器有4种状态：00（强不跳转）、01（弱不跳转）、10（弱跳转）、11（强跳转）。状态转换：当跳转时状态增加（直到11），当不跳转时状态减少（直到00）。假设初始状态为00（强不跳转）。第一次不跳转：状态保持00。第二次跳转：状态增加至01（弱不跳转）。第三次跳转：状态增加至10（弱跳转）。第四次不跳转：状态减少至01（弱不跳转）。所以当前状态为弱不跳转。

D。解析：  
- A选项正确：RAID 0仅将数据条带化分布在多个磁盘，无冗余机制，任一磁盘损坏则数据丢失；  
- B选项正确：RAID 1通过“磁盘镜像”实现冗余，数据同时写入两个磁盘，一个损坏可从另一个恢复；  
- C选项正确：RAID 5是“条带化+分布式奇偶校验”，校验信息分散在所有磁盘（无单独校验盘），兼顾性能和冗余；  
- D选项错误：RAID 10（RAID 1+0）的逻辑是“先镜像，后条带化”（先将磁盘两两组成镜像组，再对镜像组做条带化）；RAID 01（RAID 0+1）的逻辑是“先条带化，后镜像”（先将磁盘组成条带组，再对条带组做镜像）。选项D颠倒了两者的顺序，因此描述错误。

正确答案是B。进程从运行状态转换为就绪状态通常是由于时间片用完，导致CPU被剥夺，进程重新进入就绪队列等待调度。A选项会导致进程从运行状态转换为阻塞状态；C选项会导致进程终止；D选项也会导致阻塞状态。

正确答案是D。使用银行家算法检查安全序列。Need矩阵计算为：P1: (2,2,2), P2: (2,1,2), P3: (2,2,2), P4: (0,1,1)。可用资源(1,1,2)。只有P4的Need (0,1,1) ≤ 可用(1,1,2)，因此必须从P4开始。序列D以P4开始：P4完成后释放资源，可用变为(2,2,2)；然后P3的Need (2,2,2) ≤ 可用(2,2,2)，满足，可用变为(2,3,4)；接着P2的Need (2,1,2) ≤ 可用(2,3,4)，满足，可用变为(4,4,5)；最后P1的Need (2,2,2) ≤ 可用(4,4,5)，满足。因此序列D是安全序列。其他序列不以P4开始，第一个进程的Need均大于可用，无法满足。

正确答案是A。逻辑地址32位，页面大小4KB=2^12字节，因此页内偏移占12位，页号占20位（32-12），所以有2^20个页面。每个页表项占4字节，因此页表大小 = 2^20 * 4字节 = 4 * 2^20字节 = 4MB。

正确答案是A。OPT算法选择将来最长时间不被访问的页面进行置换。页面引用序列：1,2,3,4,1,2,5,1,2,3,4,5。缺页过程如下：访问1（缺页，加载1）、访问2（缺页，加载2）、访问3（缺页，加载3）、访问4（缺页，置换3，因为3将来最远访问）、访问1（命中）、访问2（命中）、访问5（缺页，置换4，因为4将来最远）、访问1（命中）、访问2（命中）、访问3（缺页，置换1或2，假设置换1）、访问4（缺页，置换2）、访问5（命中）。缺页次数为7次（1,2,3,4,5,3,4）。

正确答案是A。直接指针指向10个数据块；一级间接指针指向一个间接块，包含1024个指针（4KB/4B），指向1024个数据块；二级间接指针指向1024×1024=2^20个数据块；三级间接指针指向1024×1024×1024=2^30个数据块。总数据块数 = 10 + 2^10 + 2^20 + 2^30。每个数据块大小4KB=2^12字节，因此最大文件大小 ≈ 2^30 × 2^12 = 2^42字节 = 4TB（忽略较小项）。

正确答案是D。由于并发执行，语句可能交错。可能序列包括：P1完全执行后P2执行（X=0→1→2→4→8）；P2完全执行后P1执行（X=0→0→0→1→2）；交错执行如P1第一次操作后P2两次操作再P1第二次操作（X=0→1→2→4→5）等。可能值包括2,3,4,5,6,8，但不包括16。

正确答案是A。SCAN算法从53向0移动，服务所有请求：先向0方向服务37、14，然后反向服务65、67、98、122、124、183。移动顺序：53→37（16道）、37→14（23道）、14→0（14道）、0→65（65道）、65→67（2道）、67→98（31道）、98→122（24道）、122→124（2道）、124→183（59道）。总道数=16+23+14+65+2+31+24+2+59=236。

正确答案是C。进程时间片用完会导致从运行状态转换为就绪状态，而不是阻塞状态。A、B、D都会导致进程等待事件（如资源、信号量、I/O）而进入阻塞状态。

正确答案是A。最佳适应算法选择最小的足够分区。空闲分区大小：10K-30K（20K）、40K-60K（20K）、70K-100K（30K）。所有分区都足够20K，但10K-30K和40K-60K都是最小大小20K。最佳适应通常选择第一个遇到的最小足够分区，因此分配10K-30K分区。

正确答案是D。微内核只包含最核心的功能（如进程间通信、基本调度），其他服务运行在用户态，通过IPC通信，易于扩展但可能性能较低。A错误，微内核通常不包含完整内存管理；B错误，宏内核性能不一定总是更优；C错误，微内核中文件系统服务运行在用户态。

正确答案是B。解析：原网络192.168.0.0/22的掩码为255.255.252.0，提供1022个可用主机地址。要划分为8个子网，需要借用3位子网位（2^3=8），新掩码长度为22+3=25，即255.255.255.128。主机位为7位，每个子网可用主机数为2^7-2=126，满足至少50台主机的需求。选项A（255.255.255.0）对应/24，只能划分4个子网，不满足8个；选项C（255.255.255.192）对应/26，主机位6位，每个子网62主机，但划分16个子网，浪费地址；选项D（255.255.255.224）对应/27，主机位5位，每个子网30主机<50，不满足。因此B最合适。

核心原理（TCP Reno算法标准逻辑）
快速恢复是TCP应对**轻度拥塞**的机制，触发条件为收到3个重复ACK（表明报文段未丢失但网络已出现拥塞迹象），核心操作步骤如下：
1. 首先将**慢启动阈值（ssthresh）** 调整为当前拥塞窗口（cwnd）的一半，通过降低阈值减少后续发送窗口的增长上限，降低拥塞风险。
2. 将**拥塞窗口（cwnd）** 设置为调整后的慢启动阈值（注：标准Reno算法中存在“cwnd = ssthresh + 3*MSS”的实现，但选项中无该表述，结合题目选项设计，C选项的核心逻辑与快速恢复的阶段切换、关键参数设置原则一致，为最优答案）。
3. 立即进入**拥塞避免阶段**，此后拥塞窗口按线性速度增长（每经过一个RTT增加1个MSS），避免窗口快速扩张再次引发拥塞。
- 选项A：错误。将cwnd设为1并重启慢启动，是“超时触发重度拥塞”时的处理逻辑，并非快速恢复的操作，二者触发场景和应对策略完全不同。
- 选项B：错误。“拥塞窗口减半”不符合快速恢复的标准流程，实际操作是先调整ssthresh为cwnd的一半，再将cwnd设为该ssthresh，而非直接对cwnd执行“减半”操作，表述存在逻辑偏差。
- 选项C：正确。准确匹配快速恢复的核心逻辑，既明确了cwnd与慢启动阈值的关联设置，也正确指出后续进入拥塞避免阶段，是选项中唯一符合TCP拥塞控制标准的描述。
- 选项D：错误。cwnd设为1是慢启动的初始状态，且“设为1后进入拥塞避免”无任何TCP拥塞控制场景支持，属于逻辑矛盾，不符合拥塞控制的阶段切换规则。

正确答案是D。解析：HTTP状态码304表示“Not Modified”，意味着资源未修改，客户端可以使用缓存的副本。服务器返回304时，通常不包含消息体（选项A正确），客户端可以直接使用缓存（选项B正确）。服务器可能在响应中包含Last-Modified头以确认修改时间（选项C正确）。选项D错误，因为客户端不需要重新发送请求；304响应指示客户端缓存有效，无需额外操作。

正确答案是C。解析：在OSPF中，Hello报文用于发现邻居、维护邻接关系，并在广播网络和非广播多路访问（NBMA）网络中选举指定路由器（DR）和备份指定路由器（BDR）。选项A错误，Hello报文也用于点对点和点对多点网络；选项B错误，Hello报文不包含LSDB信息，只包含路由器ID、Hello间隔等基本信息；选项D错误，Hello报文的发送间隔可以根据网络类型配置不同值，例如在广播网络中默认10秒，而在点对点网络中可能不同。

正确答案是D。解析：IPv6中，子网划分通常使用/64前缀用于单个子网，因为该前缀提供2^64个主机地址，远大于1000台主机的需求。选项A/48提供更大地址空间，但浪费；选项B/52和C/56也提供较多地址，但标准实践是使用/64用于主机分配，以确保无状态地址自动配置（SLAAC）正常工作。因此，尽管更短前缀也能满足，但/64是最小推荐值，且满足需求。

正确答案是D。解析：在TLS 1.2握手中，客户端和服务器最终协商出一个对称密钥，用于后续通信的加密。选项A错误，服务器证书在Certificate消息中发送，而不是ServerHello；选项B错误，预主密钥由客户端生成，并在ClientKeyExchange消息中加密发送；选项C错误，主密钥由双方基于预主密钥计算得出，不直接发送；选项D正确，握手完成后，通信使用对称加密。

正确答案是B。解析：ACL规则101的第一条拒绝来自主机192.168.1.100的TCP流量，目的端口为80（HTTP），第二条允许所有其他IP流量。因此，只有HTTP流量（端口80）从192.168.1.100发出时被阻止；其他流量如到192.168.1.100的流量不受影响。选项A错误，因为只阻止TCP端口80，不是所有TCP；选项C错误，因为ACL应用于入口接口，针对源地址192.168.1.100的出口流量；选项D错误，因为第二条规则允许其他IP流量。

正确答案是A。解析：DNS递归解析器在处理查询时，如果缓存中没有相应记录，会从根域名服务器开始迭代查询。根服务器提供顶级域名（TLD）服务器的地址，然后查询TLD服务器，获取权威服务器地址，最后查询权威服务器得到答案。选项B、C、D不正确：TLD服务器是第二步；权威服务器是最后一步；本地hosts文件在DNS查询之前检查，但解析器本身不查询hosts文件，那是客户端行为。

(1) 算法的基本设计思想:
由于需要对于每个元素 A[i] 计算与后续元素的最小绝对差，直接暴力枚举所有可能的 j (i < j ≤ n-1) 需要 O(n^2) 时间，效率较低。为了优化，可以从右向左扫描数组，并维护一个平衡二叉搜索树（如 C++ STL 中的 set），用于存储当前已扫描过的元素（即索引大于 i 的元素）。对于每个 A[i]，在集合中查找最接近 A[i] 的值，通过计算与集合中上下邻居的绝对差来得到最小值，并更新 res[i]。然后将 A[i] 插入集合中，以确保集合始终包含所有后续元素。这样每个插入和查询操作的时间为 O(log n)，总时间复杂度为 O(n log n)，空间复杂度为 O(n)。

(2) 算法描述（采用 C++ 语言）:
```cpp
#include <iostream>
#include <set>
#include <cmath>
#include <climits>
using namespace std;

void calMinDiff(int A[], int res[], int n) {
    if (n <= 0) return; // 处理空数组
    set<int> s; // 用于存储后续元素的平衡二叉搜索树
    res[n-1] = -1; // 最后一个元素没有后续元素，设为 -1
    if (n == 1) return; // 如果只有一个元素，直接返回

    s.insert(A[n-1]); // 修正：插入最后一个元素，以便处理 i=n-2 时有一个后续元素
    // 从右向左扫描数组，从倒数第二个元素开始
    for (int i = n-2; i >= 0; i--) {
        int minDiff = INT_MAX; // 初始化最小差为最大值
        auto it = s.lower_bound(A[i]); // 查找第一个大于等于 A[i] 的迭代器

        // 检查 upper neighbor（大于等于 A[i] 的最小值）
        if (it != s.end()) {
            minDiff = min(minDiff, abs(A[i] - *it));
        }
        // 检查 lower neighbor（小于 A[i] 的最大值）
        if (it != s.begin()) {
            it--; // 移动到前一个元素
            minDiff = min(minDiff, abs(A[i] - *it));
        }

        res[i] = minDiff; // 保存最小绝对差
        s.insert(A[i]); // 将当前元素插入集合，用于后续处理
    }
}
```
关键注释:
- `set<int> s`: 使用 set 作为平衡二叉搜索树，存储后续元素的值，保证元素有序且唯一。
- `s.lower_bound(A[i])`: 返回第一个大于等于 A[i] 的迭代器，用于找到 upper neighbor。
- 检查 `it != s.end()` 和 `it != s.begin()`: 确保迭代器有效，避免访问越界。
- `minDiff` 更新: 通过比较 upper neighbor 和 lower neighbor 与 A[i] 的绝对差，得到最小值。
- 从右向左扫描: 保证处理 A[i] 时，集合 s 中包含所有索引大于 i 的元素。

(3) 时间复杂度和空间复杂度:
- 时间复杂度: 算法中对于每个元素执行一次 set 的插入和查询操作，每个操作的时间复杂度为 O(log n)，因此总时间复杂度为 O(n log n)。
- 空间复杂度: 使用了一个 set 来存储最多 n-1 个元素，因此空间复杂度为 O(n)。
 

（1）构造散列表HT的过程如下：

关键字20：H(20)=20%11=9，地址9为空，插入。

关键字3：H(3)=3%11=3，地址3为空，插入。

关键字11：H(11)=11%11=0，地址0为空，插入。

关键字18：H(18)=18%11=7，地址7为空，插入。

关键字9：H(9)=9%11=9，冲突；H2(9)=(9%5)+1=4+1=5，i=1时H1=(9+1*5)%11=14%11=3，冲突；i=2时H2=(9+2*5)%11=19%11=8，地址8为空，插入。

关键字14：H(14)=14%11=3，冲突；H2(14)=(14%5)+1=4+1=5，i=1时H1=(3+1*5)%11=8%11=8，冲突；i=2时H2=(3+2*5)%11=13%11=2，地址2为空，插入。

关键字7：H(7)=7%11=7，冲突；H2(7)=(7%5)+1=2+1=3，i=1时H1=(7+1*3)%11=10%11=10，地址10为空，插入。
散列表HT如下：
地址0: 11
地址1: 空
地址2: 14
地址3: 3
地址4: 空
地址5: 空
地址6: 空
地址7: 18
地址8: 9
地址9: 20
地址10: 7
装填因子 = 表中已存储关键字数 / 表长度 = 7 / 11 ≈ 0.636。

（2）查找关键字14的比较序列：
H(14)=3，比较地址3（关键字3，不等于14）；
i=1时H1=(3+1*5)%11=8，比较地址8（关键字9，不等于14）；
i=2时H2=(3+2*5)%11=2，比较地址2（关键字14，等于14），找到。
因此，关键字比较序列为地址3、地址8、地址2。

（3）查找关键字8：
H(8)=8%11=8，比较地址8（关键字9，不等于8）；
i=1时H2(8)=(8%5)+1=3+1=4，H1=(8+1*4)%11=12%11=1，比较地址1（空），查找失败。
因此，查找失败时的散列地址是1。

（1）计算缓存参数：

缓存总大小128B，块大小16B，因此块数 = 128B / 16B = 8块。

2路组相联，因此组数 = 块数 / 路数 = 8 / 2 = 4组。

块内偏移位数：块大小16B，因此偏移位数 = log₂(16) = 4位。

组索引位数：组数4，因此索引位数 = log₂(4) = 2位。

标记位数：主存地址16位，因此标记位数 = 地址位数 - 偏移位数 - 索引位数 = 16 - 4 - 2 = 10位。

（2）访问序列在2路组相联下的命中情况：

初始缓存为空。

访问块0：组索引 = 0 mod 4 = 0，缺失，加载块0到组0。组0内容：块0（LRU状态：块0为MRU）。

访问块8：组索引 = 8 mod 4 = 0，缺失，加载块8到组0。组0内容：块0（LRU）、块8（MRU）。

访问块0：组索引 = 0 mod 4 = 0，命中，更新LRU，块0成为MRU。组0内容：块0（MRU）、块8（LRU）。

访问块8：组索引 = 8 mod 4 = 0，命中，更新LRU，块8成为MRU。组0内容：块0（LRU）、块8（MRU）。

访问块0：命中，更新LRU，块0成为MRU。

访问块8：命中，更新LRU，块8成为MRU。

访问块0：命中。

访问块8：命中。
因此，命中情况为：缺失、缺失、命中、命中、命中、命中、命中、命中。

（3）命中率计算：总访问8次，命中6次，命中率 = 6/8 = 75%。

（4）直接映射下的情况：

直接映射时，组数 = 块数 = 8组，索引位数 = log₂(8) = 3位，偏移位数4位，标记位数 = 16 - 4 - 3 = 9位。

访问序列命中情况：

访问块0：组索引 = 0 mod 8 = 0，缺失，加载块0到组0。

访问块8：组索引 = 8 mod 8 = 0，缺失，替换组0的块0，加载块8。

访问块0：组索引 = 0 mod 8 = 0，缺失，替换组0的块8，加载块0。

访问块8：缺失，替换组0的块0，加载块8。

访问块0：缺失，替换组0的块8，加载块0。

访问块8：缺失，替换组0的块0，加载块8。

访问块0：缺失，替换组0的块8，加载块0。

访问块8：缺失，替换组0的块0，加载块8。
因此，所有访问均缺失，命中率 = 0%。

（5）比较与解释：在2路组相联下命中率为75%，而直接映射下为0%。原因是直接映射中，块0和块8映射到同一组（组0），导致每次访问都发生冲突缺失；而2路组相联允许同一组存放两个块，因此块0和块8可以共存，后续访问命中率高。

（6）新序列在2路组相联下的命中率：

块0、8、16的组索引均为0 mod 4 = 0，都映射到组0。

访问序列：0,8,16,0,8,16,0,8,16

命中情况分析：

访问块0：缺失，加载块0。组0：块0（MRU）。

访问块8：缺失，加载块8。组0：块0（LRU）、块8（MRU）。

访问块16：缺失，替换LRU块0，加载块16。组0：块8（LRU）、块16（MRU）。

访问块0：缺失，替换LRU块8，加载块0。组0：块16（LRU）、块0（MRU）。

访问块8：缺失，替换LRU块16，加载块8。组0：块0（LRU）、块8（MRU）。

访问块16：缺失，替换LRU块0，加载块16。组0：块8（LRU）、块16（MRU）。

访问块0：缺失，替换LRU块8，加载块0。组0：块16（LRU）、块0（MRU）。

访问块8：缺失，替换LRU块16，加载块8。组0：块0（LRU）、块8（MRU）。

访问块16：缺失，替换LRU块0，加载块16。组0：块8（LRU）、块16（MRU）。
因此，所有访问均缺失，命中率 = 0%。
原因：由于三个块映射到同一组，而缓存只有2路，因此每次访问时，所需块都不在缓存中，导致总是缺失。

（1）缓存命中率计算：

缓存参数：总容量64KB，块大小64B，因此块数 = 64KB / 64B = 1024块。4路组相联，因此组数 = 1024 / 4 = 256组。

地址映射：地址32位，块大小64B，块偏移位为6位（地址位5-0）。组数256，索引位为8位（地址位13-6）。标签位为18位（地址位31-14）。

地址序列解析：

0x0000：块地址 = 0x0000 / 0x40 = 0，组索引 = 0 mod 256 = 0。

0x10000：块地址 = 0x10000 / 0x40 = 1024，组索引 = 1024 mod 256 = 0。
因此，所有地址映射到组0。

访问过程（4路组相联，LRU替换）：

访问1：0x0000（块0），组0，缺失，加载块0，组0状态：[块0]（LRU顺序：块0为最近使用）。

访问2：0x10000（块1024），组0，缺失，加载块1024，组0状态：[块0, 块1024]（块1024为最近使用）。

访问3：0x0000（块0），组0，命中，更新LRU，组0状态：[块1024, 块0]（块0为最近使用）。

访问4：0x10000（块1024），组0，命中，更新LRU，组0状态：[块0, 块1024]（块1024为最近使用）。

访问5：0x0000（块0），组0，命中，更新LRU，组0状态：[块1024, 块0]（块0为最近使用）。

访问6：0x10000（块1024），组0，命中，更新LRU，组0状态：[块0, 块1024]（块1024为最近使用）。

命中次数：4次（访问3、4、5、6），缺失次数：2次（访问1、2），总访问6次，命中率 = 4 / 6 ≈ 66.67%。

（2）平均内存访问时间（AMAT）计算：

命中时间 = 1时钟周期，缺失损失 = 100时钟周期。

缺失率 = 1 - 命中率 = 1 - 4/6 = 2/6 ≈ 33.33%。

AMAT = 命中时间 + 缺失率 × 缺失损失 = 1 + (2/6) × 100 ≈ 1 + 33.33 ≈ 34.33时钟周期。

（3）直接映射下命中率变化分析：

直接映射参数：组数 = 块数 = 1024组，每个组1块。索引位为10位（地址位15-6），标签位为16位（地址位31-16）。

地址映射：块0和块1024的组索引均为0（因为 0 mod 1024 = 0，1024 mod 1024 = 0），因此它们映射到组0。

访问过程（直接映射）：

访问1：0x0000（块0），组0，缺失，加载块0。

访问2：0x10000（块1024），组0，缺失，替换块0为块1024。

访问3：0x0000（块0），组0，缺失，替换块1024为块0。

访问4：0x10000（块1024），组0，缺失，替换块0为块1024。

访问5：0x0000（块0），组0，缺失，替换块1024为块0。

访问6：0x10000（块1024），组0，缺失，替换块0为块1024。

命中次数：0次，缺失次数：6次，命中率 = 0%。

变化分析：在直接映射下，命中率从66.67%降至0%。原因是直接映射每个组只有1块，而序列中块0和块1024映射到同一组，导致每次访问都发生冲突替换，无法命中；而4路组相联允许同一组存放多个块，因此块0和块1024可同时存在，后续访问能命中。

(1) 【得分点：计算正确得2分】
可用资源Available = 总资源 - 所有进程已分配资源之和。
总资源: A=10, B=5, C=7
已分配资源之和:

A: 0 (P0) + 2 (P1) + 3 (P2) + 2 (P3) + 0 (P4) = 7

B: 1 (P0) + 0 (P1) + 0 (P2) + 1 (P3) + 0 (P4) = 2

C: 0 (P0) + 0 (P1) + 2 (P2) + 1 (P3) + 2 (P4) = 5
因此，Available = (10-7, 5-2, 7-5) = (3,3,2)

(2) 【得分点：正确检查安全状态并给出安全序列得4分，其中序列正确得2分，步骤正确得2分】
使用银行家算法检查安全状态：

当前 Available = (3,3,2)

检查进程：

P1 Need=(1,2,2) ≤ Available=(3,3,2)，是。假设分配P1，P1完成释放Allocation=(2,0,0)，则Available=(3,3,2)+(2,0,0)=(5,3,2)

P3 Need=(0,1,1) ≤ (5,3,2)，是。分配P3，释放(2,1,1)，Available=(5,3,2)+(2,1,1)=(7,4,3)

P4 Need=(4,3,1) ≤ (7,4,3)，是。分配P4，释放(0,0,2)，Available=(7,4,3)+(0,0,2)=(7,4,5)

P0 Need=(7,4,3) ≤ (7,4,5)，是。分配P0，释放(0,1,0)，Available=(7,4,5)+(0,1,0)=(7,5,5)

P2 Need=(6,0,0) ≤ (7,5,5)，是。分配P2。
因此，存在安全序列，例如 P1, P3, P4, P0, P2。系统处于安全状态。

(3) 【得分点：正确判断并说明理由得2分，其中检查请求和安全性各1分】
P1请求Request=(1,0,2)：

检查Request ≤ Need? Request=(1,0,2) ≤ P1 Need=(1,2,2)，是。

检查Request ≤ Available? (1,0,2) ≤ Available=(3,3,2)，是。

假设分配：

P1 Allocation 变为 (2+1,0+0,0+2) = (3,0,2)

P1 Need 变为 (3,2,2) - (3,0,2) = (0,2,0)

Available 变为 (3,3,2) - (1,0,2) = (2,3,0)

检查系统安全性：

当前 Available=(2,3,0)

进程：

P1 Need=(0,2,0) ≤ (2,3,0)，是。分配P1，P1完成释放(3,0,2)，Available=(2,3,0)+(3,0,2)=(5,3,2)

P3 Need=(0,1,1) ≤ (5,3,2)，是。分配P3，释放(2,1,1)，Available=(5,3,2)+(2,1,1)=(7,4,3)

P4 Need=(4,3,1) ≤ (7,4,3)，是。分配P4，释放(0,0,2)，Available=(7,4,3)+(0,0,2)=(7,4,5)

P0 Need=(7,4,3) ≤ (7,4,5)，是。分配P0，释放(0,1,0)，Available=(7,4,5)+(0,1,0)=(7,5,5)

P2 Need=(6,0,0) ≤ (7,5,5)，是。分配P2。

存在安全序列，如 P1, P3, P4, P0, P2。因此系统安全，应该分配。

(1) 信号量定义和初始化：

semaphore mutex_r = 1; // 用于保护 readcount 的互斥访问

semaphore mutex_w = 1; // 用于保护 writecount 的互斥访问

semaphore read_try = 1; // 用于实现写者优先，控制读者进入

semaphore resource = 1; // 用于保证写者独占访问文件

int readcount = 0; // 当前读者数量

int writecount = 0; // 当前写者数量（包括等待和活跃的写者）

(2) 读者进程代码框架：

reader() {
    P(read_try);
    P(mutex_r);
    readcount++;
    if (readcount == 1) {
        P(resource);
    }
    V(mutex_r);
    V(read_try);
    
    // 读取文件操作（临界区）
    
    P(mutex_r);
    readcount--;
    if (readcount == 0) {
        V(resource);
    }
    V(mutex_r);
}

(3) 写者进程代码框架：

writer() {
    P(mutex_w);
    writecount++;
    if (writecount == 1) {
        P(read_try);
    }
    V(mutex_w);
    
    P(resource);
    // 写入文件操作（临界区）
    V(resource);
    
    P(mutex_w);
    writecount--;
    if (writecount == 0) {
        V(read_try);
    }
    V(mutex_w);
}

(4) 解释：

mutex_r 和 mutex_w 是二进制信号量，用于保护共享变量 readcount 和 writecount，防止多个进程同时修改而导致竞争条件。

read_try 信号量用于实现写者优先。当第一个写者到达时，通过 P(read_try) 阻止新读者进入；后续读者在 P(read_try) 时会被阻塞，直到所有写者完成（最后一个写者执行 V(read_try)）。这确保了有写者等待时，新读者无法开始读取。

resource 信号量用于保证写者独占访问文件。第一个读者会 P(resource) 以阻止写者，最后一个读者 V(resource) 以允许写者；写者在访问文件时持有 resource，确保互斥。

整体设计通过 read_try 和 writecount 协调，使写者优先于新读者，但允许现有读者完成，平衡了读写性能。

 (a) 快速重传触发时的cwnd大小
答案：8 MSS
解析：TCP Reno算法中，慢启动阶段每收到一个新ACK，cwnd按1 MSS递增。
- t=0：初始cwnd = 1 MSS（慢启动阶段，未达ssthresh=64 MSS）。
- t=0.1s：收到1个新ACK → cwnd = 1 + 1 = 2 MSS。
- t=0.2s：收到2个新ACK → cwnd = 2 + 2 = 4 MSS。
- t=0.3s：收到4个新ACK → cwnd = 4 + 4 = 8 MSS。
- t=0.4s：收到3个重复ACK触发快速重传，重复ACK不增加cwnd，因此cwnd保持8 MSS。

(b) 快速重传触发时的ssthresh和cwnd调整
答案：ssthresh = 4 MSS，调整后cwnd = 7 MSS
解析：根据Reno算法规则，快速重传触发时的调整逻辑如下：
1. 首先将ssthresh设置为当前cwnd的一半（向下取整），即 ssthresh = 8 MSS / 2 = 4 MSS。
2. 再将cwnd调整为“新计算的ssthresh + 3 MSS”，即 cwnd = 4 MSS + 3 MSS = 7 MSS。
3. 调整后进入快速恢复阶段，“+3 MSS”的依据是收到了3个重复ACK，表明网络仍能传输部分数据，无需过度缩减窗口。

 (c) 快速恢复结束后的阶段及cwnd变化
答案：进入拥塞避免阶段；cwnd按“每RTT增加1 MSS”的线性规律增长
解析：
1. t=0.5s收到重传段的ACK（新数据ACK），标志快速恢复阶段结束，TCP进入拥塞避免阶段。
2. 此时cwnd会重置为之前调整后的ssthresh值，即4 MSS。
3. 拥塞避免阶段采用“加法增加”策略，核心变化规律是每经过一个RTT，cwnd增加1 MSS（线性增长）。
4. 具体实现为：每收到一个新ACK，cwnd增加1/cwnd MSS，多个ACK的增量累积后，最终实现“每RTT增加1 MSS”的效果，避免窗口增长过快导致网络拥塞。