解析：本题考查线性表的基本概念及操作特性。
选项 A 错误，数组可以存储不同类型的数据（如结构体数组），只是在多数编程语言中数组元素类型需一致，但这并非数组作为线性表的本质属性。
选项 B 错误，存储密度是数据元素本身所占的存储量与整个节点结构所占的存储量之比。若链表节点的数据域较大，指针域占比低，其存储密度可能高于顺序表（如存储大字符串的链表）。
选项 C 正确，顺序表插入时，平均需移动 n/2 个元素，时间复杂度为 O (n)。
选项 D 错误，链表删除操作需先找到待删除节点的前驱，该过程在单链表中时间复杂度为 O (n)，因此整体删除操作时间复杂度为 O (n)。

解析：本题考查栈的 “后进先出” 特性。
选项 A：1 进栈，2 进栈，3 进栈，3 出栈，2 出栈，4 进栈，5 进栈，5 出栈，4 出栈，1 出栈，可行。
选项 B：1 进栈，2 进栈，2 出栈，1 出栈，3 进栈，4 进栈，5 进栈，5 出栈，4 出栈，3 出栈，可行。
选项 C：1-5 依次进栈后依次出栈，可行。
选项 D：1 出栈后，2,3,4,5 进栈，5 出栈后，栈顶为 4，无法先输出 2，故不可行。

解析：本题考查循环队列的元素计数。
在循环队列中，当 rear ≥ front 时，元素个数为 rear - front；当 rear < front 时，元素个数为 (rear + n) - front。综合两种情况，统一公式为 (rear - front + n) % n。选项 A 正确。

解析：本题考查二叉树的遍历推导。
后序遍历最后一个元素为根节点，故根节点为 E。
中序遍历中 E 左侧为左子树（ABC D），右侧为右子树（FG）。
左子树后序遍历为 BDCA，根为 A；右子树后序遍历为 FG，根为 G。
递归分析：A 的左子树中序为 BCD，后序为 BDC，根为 C；C 的左子树为 B，右子树为 D。G 的左子树为 F。
前序遍历顺序为：根 E → 左子树 A → A 的左子树 C → C 的左子树 B → C 的右子树 D → 右子树 G → G 的左子树 F，即 EACBDGF。选项 A 正确。

解析：本题考查完全二叉树的性质。
选项 A 正确，完全二叉树按层序编号，若节点无左孩子，则其右孩子必不存在（否则编号不连续），故为叶子节点。
选项 B 正确，完全二叉树深度公式为⌊log₂n⌋ + 1。
选项 C 正确，完全二叉树中右孩子存在则左孩子必存在（编号规则决定）。
选项 D 错误，完全二叉树的叶子节点只可能在最后一层或倒数第二层出现。例如，深度为 3 的完全二叉树，叶子节点可在第 2 层（如 7 个节点的完全二叉树，第 2 层有 2 个叶子节点）和第 3 层。

解析：本题考查无向图的深度优先遍历（DFS）。
DFS 的特点是 “尽可能深地搜索”，访问一个节点后立即访问其未访问的邻接节点。
选项 A：v1→v2（邻接 v1）→v3（邻接 v2）→v4（邻接 v3）→v5（邻接 v4），可行。
选项 B：v1→v3（邻接 v1）→v2（邻接 v3）→v5（邻接 v2）→v4（邻接 v5），可行。
选项 C：v1→v2→v5 后，v5 的未访问邻接节点为 v4，应优先访问 v4 而非回溯到 v3，故不可行。
选项 D：v1→v3→v4→v5→v2，可行。

解析：本题考查最短路径算法的特性。
选项 A 错误，Dijkstra 算法不能处理带负权边的图，会导致错误结果。
选项 B 正确，Floyd 算法通过三重循环实现，时间复杂度 O (n³)，需存储邻接矩阵，空间复杂度 O (n²)。
选项 C 错误，若负权回路不在某对节点的路径上，则这对节点的最短路径仍可能存在。
选项 D 错误，Bellman-Ford 算法最多迭代 n-1 次（n 为节点数），若第 n 次仍能松弛，则说明存在负权回路。

要解决这个问题，我们需要明确折半查找（二分查找）的基本原理：每次通过比较中间元素，将查找范围缩小一半，直到找到目标元素或确定其不存在。
已知有序表为：(12,18,24,35,47,50,62,83,90,115,134)，共 11 个元素，目标元素为 115。以下是具体查找过程：
第一次比较：
初始范围为整个列表（索引 0-10），中间元素索引为(0+10)/2=5，对应值为 50。
因 115＞50，查找范围缩小到右半部分（索引 6-10）。
第二次比较：
新范围为索引 6-10，中间元素索引为(6+10)/2=8，对应值为 90。
因 115＞90，查找范围缩小到右半部分（索引 9-10）。
第三次比较：
新范围为索引 9-10，中间元素索引为(9+10)/2=9（向下取整），对应值为 115。
目标元素与中间元素相等，查找成功。
综上，查找 115 的比较次数为 3 次。
答案：A

要解决这个问题，需结合哈希函数和线性探测再散列法处理冲突的规则，逐步确定每个关键字的存储位置，重点分析关键字 20 的存储位置。
步骤 1：明确哈希表参数
哈希表长度为 11，索引范围为 0~10。
哈希函数：
H(key)=key%11
。
冲突处理：线性探测再散列，即冲突时依次检查下一个位置 
(H(key)+i)%11
（
i=1,2,...
），直到找到空位置。
步骤 2：依次插入关键字并确定位置
插入 23：
H(23)=23%11=1
（位置 1 为空，直接存储）。
存储位置：1。
插入 14：
H(14)=14%11=3
（位置 3 为空，直接存储）。
存储位置：3。
插入 35：
H(35)=35%11=2
（位置 2 为空，直接存储）。
存储位置：2。
插入 55：
H(55)=55%11=0
（位置 0 为空，直接存储）。
存储位置：0。
插入 20：
H(20)=20%11=9
（位置 9 为空，直接存储）。
存储位置：9。
插入 84：
H(84)=84%11=7
（位置 7 为空，直接存储）。
存储位置：7。
结论
关键字 20 的存储位置是 9。
答案：D

解析：本题考查排序算法的时间复杂度。
选项 A：直接插入排序最坏情况（逆序）时间复杂度为 O (n²)。
选项 B：快速排序最坏情况（有序或逆序）时间复杂度为 O (n²)。
选项 C：冒泡排序最坏情况时间复杂度为 O (n²)。
选项 D：堆排序在最好、最坏和平均情况下时间复杂度均为 O (nlog₂n)，故正确。

答案：C

解析：通过分析各排序方法的特点及题目中前三趟的排序结果，可判断采用的排序方法为快速排序，具体推理如下：

初始序列与排序结果分析
初始序列：(25,84,21,47,15,27,68,35,20)
第一趟结果：(20,15,21,25,47,27,68,35,84)
第二趟结果：(15,20,21,25,27,35,47,68,84)
第三趟结果：与第二趟一致（已完全有序）

各排序方法的排除

• 简单选择排序（A）：每趟选择最小元素放到已排序序列末尾。第一趟应将最小元素 15 放到首位，但第一趟结果首位为 20，故排除。
• 希尔排序（B）：基于增量分组插入排序，每趟结果不会呈现 “基准元素归位” 的特征，且第一趟结果与分组排序逻辑不符，故排除。
• 归并排序（D）：采用分治合并策略，第一趟需合并相邻子序列（如长度为 1 的子序列合并为长度为 2），但第一趟结果与合并逻辑不符，故排除。

快速排序的验证
快速排序的核心是 “选基准→分区（左小右大）→递归”：

• 第一趟：以 25 为基准，将比 25 小的元素（20,15,21）放左边，比 25 大的元素（47,27,68,35,84）放右边，25 归位（最终位置），结果符合第一趟输出。
• 第二趟：递归处理左子序列（20,15,21）和右子序列（47,27,68,35,84）。左子序列以 20 为基准，右子序列以 47 为基准，两者均归位，结果符合第二趟输出。
• 第三趟：剩余子序列已天然有序，故结果不变，符合第三趟输出。

综上，排序方法为快速排序，答案选 C。

主存容量 4GB=2³²，故主存地址总位数为 32 位。块大小 64B=2⁶，因此块内地址位数为 6 位。Cache 容量 16KB，块大小 64B，Cache 块数 = 16KB/64B=256 块。4 路组相联映射下，组数 = 256/4=64=2⁶，故组号位数为 6 位。标记位位数 = 32-6-6=20 位。综上，答案为 C。

x=+0110 的 5 位补码为 00110，y=-1010 的 5 位补码为 10110。补码相加：00110+10110=11100。结果 11100 的符号位为 1（表示负数），转换为原码为 10100（即 - 4）。两数符号相反，相加不可能溢出，故无溢出。答案为 B。

指令字长 32 位，操作码 8 位，寻址特征位 2 位，地址码位数 = 32-8-2=22 位。直接寻址时，地址码即为内存地址，按字节编址，故最大寻址范围为 2²²B。答案为 A。

非流水线执行时间 = 10×(t+t+t+t+t)=50t。流水线执行时间 =(段数 + 指令数 - 1)× 周期 =(5+10-1) t=14t。加速比 = 非流水线时间 / 流水线时间 = 50t/14t≈3.5。答案为 C。

8 个芯片并行工作时，每次可传输 8×8 位 = 64 位 = 8 字节。存取周期 20ns，每秒传输次数 = 1/20ns=5×10⁷次。带宽 = 5×10⁷×8B=4×10⁸B/s=400MB/s。答案为 A。

时钟频率 100MHz，即每秒 100×10⁶个周期。每个周期传输 2 字节，带宽 = 100×10⁶×2B=200×10⁶B/s=200MB/s。答案为 B。

CPU 的中断处理不仅包括外部设备的中断请求，还包括内部中断（如运算溢出、除数为零等）。因此 D 选项描述错误。答案为 D。

16 位补码的表示范围为 - 2¹⁵~+2¹⁵-1，即 - 32768~+32767。相对寻址中位移量为此范围，故寻址范围相同。答案为 A。

DRAM 集成度高、功耗低、速度慢，需定期刷新；SRAM 集成度低、功耗高、速度快，无需刷新。两者均为易失性存储器，断电后数据丢失。只有 B 选项正确。答案为 B。

控制器由程序计数器、指令寄存器、指令译码器、时序电路等组成。算术逻辑单元（ALU）属于运算器。答案为 C。

8 位补码阶码的最大正数为 01111111（即 127）。24 位补码尾数的最大正数为 0.111...111（23 个 1），即 1-2⁻²³。故最大正数为 (1-2⁻²³)×2¹²⁷。答案为 A。

C。解析：进程状态转换中，就绪状态的进程被调度程序选中后进入运行状态（A 可能）；运行中的进程因等待资源等原因进入阻塞状态（B 可能）；阻塞状态的进程获得所需资源后转为就绪状态（D 可能）；阻塞状态的进程无法直接进入运行状态，必须先转为就绪状态，再由调度程序调度运行，故 C 不可能。

C。解析：FIFO 页面置换算法是淘汰最早进入内存的页面。页面走向及缺页情况如下：1（缺）、2（缺）、3（缺）、4（缺，淘汰 1）、1（缺，淘汰 2）、2（缺，淘汰 3）、5（缺，淘汰 4）、1（不缺）、2（不缺）、3（缺，淘汰 1）、4（缺，淘汰 2）、5（不缺）。共 9 次缺页，故答案为 C。

D。解析：empty 信号量初始值为 n，表示空闲缓冲区数量，生产者生产前需 P (empty) 申请空闲缓冲区；full 信号量初始值为 0，表示已用缓冲区数量，生产者放入产品后，已用缓冲区数增加，应执行 V (full) 操作。mutex 用于互斥访问缓冲区，操作前后需分别执行 P (mutex) 和 V (mutex)。故答案为 D。

B。解析：绝对路径是从根目录开始描述文件位置的路径；相对路径是从当前工作目录开始描述文件位置的路径，使用相对路径可以简化文件路径的表示。故答案为 B。

C。解析：分页是将物理内存划分为大小固定的页框，进程的地址空间划分为与页框大小相同的页面，页面大小固定；分段是将进程的地址空间按逻辑意义划分为若干段，每段大小由程序逻辑决定，是可变的。故答案为 C。

D。解析：DMA 方式中，数据传输由 DMA 控制器直接控制，无需 CPU 干预数据传输过程，仅在传输开始和结束时需要 CPU 处理，大大减少了 CPU 的干预，适用于高速批量数据传输。在 DMA 方式下，CPU 可以与外设并行工作，故 D 错误。

C。解析：短作业优先调度算法优先调度运行时间短的作业。4 个作业的运行顺序为 1、4、5、6（同时到达，到达时间均为 0）。周转时间 = 完成时间 - 到达时间，分别为 1、1+4=5、5+5=10、10+6=16。平均周转时间为（1+5+10+16）÷4=32÷4=8，故答案为 C。

要计算采用 LRU（最近最久未使用）页面置换算法的缺页次数，需遵循以下步骤： 关键条件 内存块数：3（最多同时存放 3 个页面） 页面走向：1,2,3,4,1,2,5,1,2,3,4,5 LRU 算法：置换 “最近最久未使用” 的页面 分步分析 记录每次访问的页面是否在内存中，若不在则发生缺页，需根据 LRU 规则置换页面（内存满时）： 访问 1：内存空，装入 1。内存 =[1]，缺页次数 = 1。 访问 2：内存未满，装入 2。内存 =[1,2]，缺页次数 = 2。 访问 3：内存未满，装入 3。内存 =[1,2,3]，缺页次数 = 3。 访问 4：不在内存，内存满。最久未用是 1（最早访问且未再用），置换 1 装入 4。内存 =[2,3,4]，缺页次数 = 4。 访问 1：不在内存，内存满。最久未用是 2（最近未访问），置换 2 装入 1。内存 =[3,4,1]，缺页次数 = 5。 访问 2：不在内存，内存满。最久未用是 3（最近未访问），置换 3 装入 2。内存 =[4,1,2]，缺页次数 = 6。 访问 5：不在内存，内存满。最久未用是 4（最近未访问），置换 4 装入 5。内存 =[1,2,5]，缺页次数 = 7。 访问 1：在内存，更新为 “最近使用”。内存不变，不缺页。 访问 2：在内存，更新为 “最近使用”。内存不变，不缺页。 访问 3：不在内存，内存满。最久未用是 5（最近未访问），置换 5 装入 3。内存 =[1,2,3]，缺页次数 = 8。 访问 4：不在内存，内存满。最久未用是 1（最近未访问），置换 1 装入 4。内存 =[2,3,4]，缺页次数 = 9。 访问 5：不在内存，内存满。最久未用是 2（最近未访问），置换 2 装入 5。内存 =[3,4,5]，缺页次数 = 10。 结果 总缺页次数为 10 次。 答案：C

D。解析：连续结构支持随机访问，但文件增长困难；隐式链接和显式链接结构适合顺序访问，随机访问需要遍历链接，效率低；索引结构通过索引表记录文件块的位置，可直接通过索引表进行随机访问，最适合随机访问。故答案为 D。

C。解析：哲学家进餐问题中，若每个哲学家同时拿起一根筷子，会导致死锁。选项 A 会加剧死锁；选项 B 未解决资源竞争问题；选项 C 限制同时就餐的哲学家数量，可避免所有哲学家同时持有一根筷子的情况，有效避免死锁；选项 D 不能解决根本问题。故答案为 C。

C。TCP 和 UDP 报文段首部都有校验和字段，A 错误；UDP 不提供流量控制功能，B 错误；UDP 支持多种交互通信方式，C 正确；TCP 的拥塞控制机制会在网络拥塞时减少发送窗口，从而影响传输效率，D 错误。

B。要划分 4 个子网，需要借用 2 位主机位（2^2=4），原来的网络位是 24 位，所以子网掩码为 24+2=26 位，即 255.255.255.192。每个子网的主机位为 32-26=6 位，可容纳的主机数为 2^6-2=62 台，满足至少 40 台主机的要求，所以选 B。

C。HTTP 是无状态协议，A 正确；HTTP/1.1 支持持久连接，B 正确；GET 方法用于请求获取资源，POST 用于向服务器提交数据，C 错误；状态码 200 表示请求成功，D 正确。所以选 C。

C。数据链路层的功能包括封装成帧、流量控制、差错控制等，路由选择是网络层的功能，所以选 C。

C。TCP 三次握手：第一次握手，客户端发送 SYN=1，ACK=0 的报文段；第二次握手，服务器回应 SYN=1，ACK=1 的报文段；第三次握手，客户端发送 SYN=0，ACK=1 的报文段。所以第二次握手的标志位状态是 SYN=1，ACK=1，选 C。

B。IP 数据报固定首部长度为 20 字节，所以数据部分长度为 1800-20=1780 字节。MTU 为 1000 字节，每个分片的数据部分最大为 1000-20=980 字节。1780÷980=1.816，所以需要分 2 片，第一片数据部分 980 字节，第二片 1780-980=800 字节，选 B。

C。DNS 在进行区域传输时使用 TCP，查询时通常使用 UDP，A 错误；DNS 是将域名转换为 IP 地址的协议，B 错误；DNS 查询常结合递归和迭代查询，C 正确；本地域名服务器缓存的记录有过期时间，D 错误。所以选 C。

C。网络地址是 IP 地址与子网掩码进行按位与运算的结果。10.1.2.3 与 255.255.255.0 按位与后得到 10.1.2.0，所以选 C。

(1) 算法基本设计思想：
① 首先遍历数组，标记出所有峰的位置和谷的位置，分别存储在两个列表中（或直接在遍历过程中记录）。
② 为了高效找到最大差值，从后往前遍历数组，记录每个位置之后最小的谷值（即从当前位置到数组末尾的最小谷值），这样对于每个峰，只需查看其位置之后的最小谷值，即可得到该峰能形成的最大差值。
③ 遍历所有峰，计算峰值与该峰之后最小谷值的差值，跟踪最大差值，即为结果。若没有峰或谷，返回0。

(2) C语言算法实现：
```c
#include <stdio.h>
#include <limits.h>

int findMaxPeakValleyDiff(int A[], int n) {
    if (n < 3) return 0; // 数组长度不足，无法形成峰或谷
    
    // 预处理：从后往前记录每个位置之后的最小谷值
    int* minValleyAfter = (int*)malloc(n * sizeof(int));
    int currentMinValley = INT_MAX;
    minValleyAfter[n - 1] = INT_MAX; // 最后一个元素后无谷
    
    for (int i = n - 2; i >= 0; i--) {
        // 判断当前位置是否为谷
        if (i > 0 && A[i] < A[i - 1] && A[i] < A[i + 1]) {
            if (A[i] < currentMinValley) {
                currentMinValley = A[i];
            }
        }
        minValleyAfter[i] = currentMinValley;
    }
    
    int maxDiff = 0;
    // 遍历所有峰，计算最大差值
    for (int i = 1; i < n - 1; i++) {
        // 判断当前位置是否为峰
        if (A[i] > A[i - 1] && A[i] > A[i + 1]) {
            // 峰之后存在谷
            if (minValleyAfter[i] != INT_MAX) {
                int diff = A[i] - minValleyAfter[i];
                if (diff > maxDiff) {
                    maxDiff = diff;
                }
            }
        }
    }
    
    free(minValleyAfter);
    return maxDiff;
}
```

(3) 时间复杂度和空间复杂度：
- 时间复杂度：O(n)，其中n为数组长度。算法只需两次遍历数组（一次预处理最小谷值，一次遍历峰计算最大差值），每次遍历均为线性时间。
- 空间复杂度：O(n)，主要为存储每个位置之后最小谷值的数组minValleyAfter所占用的空间。

（1）晴天时，使用 Dijkstra 算法求解从城市 1 到城市 10 的最短路径。
初始化距离数组 dist，dist [1]=0，其余为无穷大。
以城市 1 为起点，更新相邻城市 2（dist=5）、3（dist=3）的距离。
选择距离最小的未访问城市 3，更新其相邻城市 5（dist=3+2=5）、6（dist=3+7=10）。
选择距离最小的未访问城市 2，更新其相邻城市 4（dist=5+4=9）、5（当前 dist=5 小于 5+6=11，不更新）。
选择距离最小的未访问城市 5，更新其相邻城市 7（dist=5+5=10）。
选择距离最小的未访问城市 6，更新其相邻城市 8（dist=10+4=14）。
选择距离最小的未访问城市 4，更新其相邻城市 7（当前 dist=10 小于 9+3=12，不更新）。
选择距离最小的未访问城市 7，更新其相邻城市 9（dist=10+2=12）。
选择距离最小的未访问城市 9，更新其相邻城市 10（dist=12+6=18）、8（当前 dist=14 小于 12+5=17，不更新）。
选择距离最小的未访问城市 8，无未更新的相邻城市。
最后得到从城市 1 到城市 10 的最短路径长度为 18，路径为 1-3-5-7-9-10。
（2）雨天时，无法通行的公路为 3-5、6-8。
判断连通性：此时城市 1-2-4-7-9-10-8-6-3 相互连通，所有城市均在该连通分量中，故所有城市能连通。
求从城市 1 到城市 10 的最短路径，使用 Dijkstra 算法：
初始化 dist [1]=0，其余为无穷大。
从城市 1 出发，更新城市 2（5）、3（3）。
访问城市 3，更新城市 6（3+7=10）。
访问城市 2，更新城市 4（5+4=9）、5（5+6=11）。
访问城市 4，更新城市 7（9+3=12）。
访问城市 5，更新城市 7（当前 12 小于 11+5=16，不更新）。
访问城市 6，无可达的新城市（6-8 无法通行）。
访问城市 7，更新城市 9（12+2=14）。
访问城市 9，更新城市 10（14+6=20）、8（14+5=19）。
得到最短路径长度为 20，路径为 1-2-4-7-9-10。
（3）晴天时求最小生成树，使用 Kruskal 算法：
按长度从小到大排序公路：3-5（2）、7-9（2）、1-3（3）、4-7（3）、6-8（4）、2-4（4）、1-2（5）、5-7（5）、8-9（5）、3-6（7）、9-10（6）。
依次选取不形成环的公路：3-5、7-9、1-3、4-7、6-8、2-4、1-2（形成环，舍弃）、5-7（形成环，舍弃）、8-9（形成环，舍弃）、3-6、9-10。
总长度为 2+2+3+3+4+4+7+6=31。
雨天时，排除 3-5、6-8 公路，求最小生成树：
排序剩余公路：7-9（2）、1-3（3）、4-7（3）、2-4（4）、1-2（5）、5-7（5）、8-9（5）、3-6（7）、9-10（6）、2-5（6）。
依次选取：7-9、1-3、4-7、2-4、1-2（形成环，舍弃）、5-7、8-9、3-6、9-10、2-5（形成环，舍弃）。
总长度为 2+3+3+4+5+5+7+6=35。

（1）计算主存地址各字段位数
主存地址总位数：主存容量为 1GB = 2³⁰B，按字节编址，因此主存地址共 30 位。
块内偏移位：块大小为 64B = 2⁶B，需 6 位表示块内偏移（确定块内具体字节）。
Cache 块数与块索引位：Cache 容量 32KB = 2¹⁵B，块大小 64B，故 Cache 块数 = 32KB / 64B = 512 = 2⁹，需 9 位块索引（确定 Cache 中的具体块）。
标记位：总地址位数 - 块索引位 - 块内偏移位 = 30 - 9 - 6 = 15 位（区分映射到同一 Cache 块的不同主存块）。
答案（1）：标记位 15 位，块索引位 9 位，块内偏移位 6 位。
（2）计算 Cache 命中率
需分析 4 次访问的命中情况（初始 Cache 为空）：
地址格式：主存块号 = 主存地址 / 64（取整数），Cache 块索引 = 主存块号 mod 512（因 Cache 共 512 块）。
0x00001234：十进制地址为 4660，主存块号 = 4660 // 64 = 72，Cache 块索引 = 72 mod 512 = 72。Cache 为空，不命中，调入主存块 72 到 Cache 块 72。
0x00001278：十进制地址为 4728，主存块号 = 4728 // 64 = 73，Cache 块索引 = 73 mod 512 = 73。Cache 块 73 为空，不命中，调入主存块 73 到 Cache 块 73。
0x00002234：十进制地址为 8756，主存块号 = 8756 // 64 = 136，Cache 块索引 = 136 mod 512 = 136。Cache 块 136 为空，不命中，调入主存块 136 到 Cache 块 136。
0x00001234：与第一次地址相同，主存块号 72，Cache 块 72 已存在该块，命中。
总访问 4 次，命中 1 次，命中率 = 1/4 = 25%。
答案（2）：25%。
（3）计算平均访问时间
平均访问时间需区分读、写操作（各占 50%），结合命中率、访问时间及脏块写回开销：
命中率：90%，不命中率：10%。
Cache 访问时间：10ns，主存访问时间：100ns，脏块写回时间 = 主存访问时间 = 100ns（仅写操作替换时，脏块概率 20%）。
读操作平均时间：
命中（90%）：时间 = 10ns；
不命中（10%）：需从主存调入（无脏块写回，因题目未提读操作脏块概率），时间 = 10 + 100 = 110ns；
读平均时间 = 0.9×10 + 0.1×110 = 20ns。
写操作平均时间：
命中（90%）：仅写 Cache，时间 = 10ns；
不命中（10%）：
脏块（20%）：先写回脏块（100ns），再调入主存块（100ns），最后写 Cache（10ns），时间 = 100 + 100 + 10 = 210ns；
非脏块（80%）：调入主存块（100ns）+ 写 Cache（10ns），时间 = 110ns；
写不命中平均时间 = 0.2×210 + 0.8×110 = 130ns；
写平均时间 = 0.9×10 + 0.1×130 = 22ns。
总平均访问时间：
读、写各占 50%，故平均时间 = 0.5×20 + 0.5×22 = 21ns。
答案（3）：21ns。
最终答案
（1）标记位 15 位，块索引位 9 位，块内偏移位 6 位；
（2）25%；
（3）21ns。

答案与解析  
（1）最小时钟周期时间（2分）
处理器的时钟周期时间由最慢流水段决定。各段延迟为：IF=2 ns, ID=2 ns, EX=3 ns, MEM=4 ns, WB=2 ns。最慢段是MEM段，延迟为4 ns。  
因此，最小时钟周期时间 \( T = 4  \text{ns} \)。  

（2）无冒险时执行100条指令的总时间（3分） 
在无任何冒险的情况下，k段流水线执行n条指令所需时钟周期数为 \( k + n - 1 \)。这里流水线段数k=5，指令数n=100。  
总时钟周期数 = \( 5 + 100 - 1 = 104 \)。  
时钟周期时间 \( T = 4  \text{ns} \)，因此总时间 = \( 104 \times 4 = 416  \text{ns} \)。  

（3）平均CPI计算（4分）
执行100条指令，其中每5条指令包含1条分支指令，因此分支指令数 = \( \frac{100}{5} = 20 \) 条。  
分支预测失败率为20%，因此失败的分支指令数 = \( 20 \times 0.2 = 4 \) 条。  
每个分支错误预测惩罚为2个时钟周期（冲刷已预取的指令），因此额外时钟周期数 = \( 4 \times 2 = 8 \) 个。  
基础执行情况（无分支失败时）CPI=1，总基础时钟周期数 = 100（对应100条指令）。  
总时钟周期数 = 基础周期数 + 额外周期数 = \( 100 + 8 = 108 \)。  
平均 CPI = \( \frac{\text{总时钟周期数}}{\text{指令数}} = \frac{108}{100} = 1.08 \)。  

（4）基于CPI的总时间计算（4分）
由（3）得平均 CPI = 1.08，指令数 = 100，因此总时钟周期数 = \( \text{CPI} \times \text{指令数} = 1.08 \times 100 = 108 \)。  
时钟周期时间 \( T = 4  \text{ns} \)（由（1）确定）。  
因此总时间 = \( \text{总时钟周期数} \times T = 108 \times 4 = 432  \text{ns} \)。  

（1）各进程的同步互斥操作伪代码如下：
P1:
repeat
生产 A 型产品（耗时 2 个时间单位）
P (emptyA)
P (mutex)
将 A 型产品放入缓冲区
V (mutex)
V (fullA)
until 生产完 3 个 A 型产品
P2:
repeat
生产 B 型产品（耗时 1 个时间单位）
P (emptyB)
P (mutex)
将 B 型产品放入缓冲区
V (mutex)
V (fullB)
until 生产完 3 个 B 型产品
C1:
repeat
P (fullA)
P (mutex)
从缓冲区取出 A 型产品
V (mutex)
V (emptyA)
消费 A 型产品（耗时 1 个时间单位）
until 消费完 3 个 A 型产品
C2:
repeat
P (fullB)
P (mutex)
从缓冲区取出 B 型产品
V (mutex)
V (emptyB)
消费 B 型产品（耗时 2 个时间单位）
until 消费完 3 个 B 型产品
解析：对于生产者进程，先生产产品，再通过 P 操作获取对应的空位信号量和互斥锁，放入产品后，通过 V 操作释放互斥锁和产品数量信号量。消费者进程则先通过 P 操作获取产品数量信号量和互斥锁，取出产品后，通过 V 操作释放互斥锁和空位信号量，再消费产品。这样能保证缓冲区操作的同步与互斥，以及不同类型产品数量的限制。
（2）总耗时计算过程如下：
0-2 时间单位：P1 优先级最高，执行生产第 1 个 A 型产品，此时 emptyA=1，fullA=1。
2-3 时间单位：P1 完成后，P2 执行，生产第 1 个 B 型产品，emptyB=1，fullB=1。
3-5 时间单位：P2 完成后，P1 执行生产第 2 个 A 型产品，emptyA=0，fullA=2。
5-6 时间单位：P1 完成后，P2 执行生产第 2 个 B 型产品，emptyB=0，fullB=2。
6-7 时间单位：P2 完成后，因 emptyA=0，P1 无法生产；P2 也因 emptyB=0 无法生产，轮到 C1 执行，消费第 1 个 A 型产品，fullA=1，emptyA=1，消费耗时 1 个时间单位。
7-8 时间单位：C1 完成后，P1 可生产，执行生产第 3 个 A 型产品，emptyA=0，fullA=2，耗时 2 个时间单位（到 9 时间单位）。
9-10 时间单位：P1 完成后，C1 执行消费第 2 个 A 型产品，fullA=1，emptyA=1，耗时 1 个时间单位。
10-11 时间单位：C1 完成后，C1 执行消费第 3 个 A 型产品，fullA=0，emptyA=2，耗时 1 个时间单位。
11-12 时间单位：C1 完成后，P2 因 emptyB=0 无法生产，轮到 C2 执行消费第 1 个 B 型产品，fullB=1，emptyB=1，耗时 2 个时间单位（到 13 时间单位）。
13-14 时间单位：C2 完成后，P2 执行生产第 3 个 B 型产品，emptyB=0，fullB=2，耗时 1 个时间单位。
14-16 时间单位：P2 完成后，C2 执行消费第 2 个 B 型产品，fullB=1，emptyB=1，耗时 2 个时间单位（到 16 时间单位）。
16-18 时间单位：C2 完成后，执行消费第 3 个 B 型产品，fullB=0，emptyB=2，耗时 2 个时间单位（到 18 时间单位）。
总耗时为 18 个时间单位。

（1）各进程首次进入运行状态的时间 P1：0ms（到达时间为 0ms，此时无其他进程，直接运行）。 P2：3ms（P1 运行结束后，就绪队列中仅有 P2，故开始运行）。 P3：5ms（P2 运行结束后，就绪队列中仅有 P3，故开始运行）。 P4：6ms（到达时 P3 剩余运行时间 4ms，P4 运行时间 1ms 更短，抢占 CPU 开始运行）。

（2）各进程的完成时间、周转时间和带权周转时间 进程 完成时间（ms） 周转时间（ms）= 完成时间 - 到达时间 带权周转时间 = 周转时间 / 运行时间 P1 8 8-0=8 8/3≈2.67 P2 11 11-2=9 9/2=4.5 P3 13 13-4=9 9/5=1.8 P4 15 15-6=9 9/1=9

（3）平均周转时间和平均带权周转时间 平均周转时间： \[ \frac{8 + 9 + 9 + 9}{4} = \frac{35}{4} = 8.75 \, \text{ms} \] 平均带权周转时间： \[ \frac{2.67 + 4.5 + 1.8 + 9}{4} \approx \frac{17.97}{4} \approx 4.49 \]

答案： （1）P1：0ms，P2：3ms，P3：5ms，P4：6ms。 （2）见表格。 （3）平均周转时间 8.75ms，平均带权周转时间约 4.49。

(1)各部门子网划分如下： 技术部：需要 50 台主机，至少需 6 位主机位（2^6-2=62），子网掩码为 255.255.255.192（/26），网络地址为 202.117.12.0/26。 市场部：需要 25 台主机，至少需 5 位主机位（2^5-2=30），子网掩码为 255.255.255.224（/27），网络地址为 202.117.12.64/27。 财务部：需要 10 台主机，至少需 4 位主机位（2^4-2=14），子网掩码为 255.255.255.240（/28），网络地址为 202.117.12.96/28。 解析：根据主机数量确定所需主机位，进而确定子网掩码，再从总地址块中划分出合适的子网地址。

(2)路由器 R1 的路由表如下： | 目的网络 | 子网掩码 | 下一跳接口 | | ---- | ---- | ---- | |202.117.12.0/26|255.255.255.192|E0| |202.117.12.64/27|255.255.255.224|E1| |202.117.12.96/28|255.255.255.240|E2| |0.0.0.0/0|0.0.0.0|S0| 解析：直连子网的路由项目的网络为对应子网地址，子网掩码为该子网的掩码，下一跳接口为连接该子网的接口；默认路由用于转发到外部网络，下一跳接口为 S0。

(3)主机 A 发送的报文段的确认号是 2000（确认主机 B 已发送的序列号到 1999）；发送的报文段的序列号范围是 1000 - 1099（1000+100-1）；主机 B 收到后，发送确认报文段的确认号是 1100（期望收到主机 A 下一个序列号为 1100 的报文段）。 解析：TCP 中确认号是期望收到对方下一个报文段的序列号，初始时主机 A 确认主机 B 的初始序列号 2000，即确认到 1999；发送报文段的序列号从本地初始序列号开始，长度为 100 字节，故范围是 1000 - 1099；主机 B 收到后，确认号为 1000 + 100 = 1100。