41.(13 分) 有两个长度均为 n 的一维整型数组 A [n]、res [n]，计算 A [i] 与 A [j] (0≤i≤j≤n-1) 乘积的最大值，并将其保存到 res [i] 中。若 A []={1，4，-9，6}，则得到 res []={6，24，81，36}。现给定数组 A，请设计时间空间上尽可能高效的算法 CalMulMax，求 res 中各元素的值。函数原型为：void CalMulMax (int A []，int res []，int n)。
（1）给出算法的基本思想。(4 分)
（2）用 C/C++ 描述算法关键之处给出注释。(7 分)
（3）说明时间、空间复杂度。(2 分)
【皮皮灰评分标准】
你就是再不会做，也可以暴力解
我是真没想到那么多考生会去用快速排序？？
算法基本思想（4 分）
若考生清晰、准确地描述了能达到时间复杂度为的算法基本思想，可得 4 分。
若描述的算法思想存在一些不清晰的地方，但能大致体现出正确的方向，可酌情给 2 - 3 分。
若算法思想完全错误，得 0 分。
C/C++ 算法实现及注释（7 分）
若考生所给算法实现正确，且时间复杂度为，可给 7 分。
若算法实现正确，但时间复杂度超过（如），则最高可给 5 分。
若算法实现部分正确（例如逻辑有小错误，但整体思路可辨），可参照上述两种情况的相应给分标准酌情给分。
若算法实现完全错误，得 0 分。
时间和空间复杂度及评分（2 分）
若考生所估计的时间复杂度与所实现的算法一致，可给 1 分。
若时间复杂度分析错误，得 0 分。
若考生能正确分析空间复杂度，可再给 1 分。空间复杂度分析错误不影响已给的时间复杂度分析分数。
【皮皮灰解法】
可以考虑使用辅助数据结构来优化时间复杂度。例如，使用两个数组和，分别记录从右到左每个位置开始到末尾的最大正数和最小负数。
首先从右到左遍历一次数组来填充这两个辅助数组，然后再遍历一次数组来计算结果数组。
void CalMulMax(int A[], int res[], int n) {
// 初始化辅助数组
int maxFromRight[n];
int minFromRight[n];
maxFromRight[n - 1] = (A[n - 1] > 0)? A[n - 1] : 0;
minFromRight[n - 1] = (A[n - 1] < 0)? A[n - 1] : 0;
// 从右到左填充辅助数组
for (int i = n - 2; i >= 0; i--) {
if (A[i] > 0) {
maxFromRight[i] = (maxFromRight[i + 1] > A[i])? maxFromRight[i + 1] : A[i];
minFromRight[i] = (minFromRight[i + 1] < 0)? minFromRight[i + 1] : 0;
} else if (A[i] < 0) {
maxFromRight[i] = (maxFromRight[i + 1] > 0)? maxFromRight[i + 1] : 0;
minFromRight[i] = (minFromRight[i + 1] < A[i])? minFromRight[i + 1] : A[i];
} else {
maxFromRight[i] = maxFromRight[i + 1];
minFromRight[i] = minFromRight[i + 1];
}
}
// 计算结果数组res
for (int i = 0; i < n; i++) {
int product1 = (maxFromRight[i]!= 0)? A[i] * maxFromRight[i] : 0;
int product2 = (minFromRight[i]!= 0)? A[i] * minFromRight[i] : 0;
res[i] = (product1 > product2)? product1 : product2;
}
}时间复杂度：
填充辅助数组的循环时间复杂度为，计算结果数组的循环时间复杂度为。
总的时间复杂度为，成功将时间复杂度从降低到。
空间复杂度：
除了输入数组和结果数组外，使用了两个长度为的辅助数组和。
空间复杂度为，相比原始算法的空间复杂度有所增加，但实现了时间复杂度的优化。
42.AOE网，描述12个工程活动及持续时间
（1）完成该工程的最短时间是多少？哪些是关键活动？
（2）若以最短时间完成工程，则与活动e同时进行的活动可能有哪些？
（3）时间余量最大的活动是哪个？其时间余量是多少？
（4）假设工程从时刻0启动，因某种原因，活动b在时刻6开始，为保证工程不延期，在其它活动持续时间保持不变的情况下，b 的持续时间最多是多少？若不改变 b 的持续时间，则压缩哪个活动的持续时间也能保证工程不延期？
【皮皮灰解法】
(1) 12
a, e, m, n
(2) b, c, d
(3) j 6
（4）如果活动 b 在时刻 6 开始，需要重新计算 b 的最大允许持续时间，以确保工程不延期。如果 b 的持续时间不能改变，则需要找到可以压缩的活动来弥补 b 的延迟。
43.计算机 M 的字长为 32 位，采用字节编址。数据 cache 的数据区大小为 32KB，采用 8 路组相联映射方式，主存块大小为 64B。cache 命中时所需时间为 2 个时钟周期，发生缺失时的损失为 200 个时钟周期。该计算机采用页式虚拟存储管理，页的大小为 4KB。数组 d 的起始地址为 0180 0020H（VA31 ~ VA0）。
（1）在主存地址中，Cache 组号和块内地址分别占几位？VA 中的哪些位可作为 Cache 索引？
（2）d [100] 的虚拟地址（VA）是多少？d [100] 所在主存块对应的 Cache 组号是多少？
（3） 假设代码已经在 cache 中，变量 i 和 x 已装入内存，但不在 cache 中，那么 d [0] 在其主存块内的偏移量是多少？在执行 for 循环的过程中，访问 d 的 Cache 缺失率是多少？数组元素的平均访问时间是多少？（缺失率用百分比表示，保留两位小数）
（4）数组 d 分布在几个页中？若代码已在主存中，但 d 不在主存中，那么在执行 for 循环的过程中，访问 d 所引起的缺页次数是多少？
已知：int x, d [2048], i;
for (i = 0; i < 2048; i++)
d[i] = d[i] / x;
【皮皮灰解法】
Cache 映射方式：本题采用 8 路组相联映射方式，需要根据这种映射方式来计算 Cache 组号和块内地址的位数。
虚拟存储管理：页式虚拟存储管理，页大小为 4KB，需要考虑虚拟地址到物理地址的转换以及对 Cache 访问的影响。
地址计算：根据主存块大小、Cache 数据区大小等参数计算相关地址。
Cache 缺失率和平均访问时间：根据 Cache 命中和缺失的时钟周期数以及访问数据的方式来计算。
缺页次数：根据数组大小和页大小来计算。
44.接43题
机器级代码：
注释：
x存储在R2寄存器中。i存储在R4寄存器中。数组
d的首地址存储在R3寄存器中。
指令：
mov R1, (R3 + R4 * 4)：将-d[i]加载到R1寄存器中。scov R1, <-SEXT(R1)：对R1进行符号扩展。idiv R1, R1：执行R1 / R2操作。
问题：
当执行
idiv指令时，若d[i] = 0x87654321且x = 0xff，则在补码除法器中R、Q、Y的初始值（用十六进制表示）分别是多少？图b中哪个部分包含计数器？在补码除法器执行过程中，ALUop所控制的ALU运算有哪几种？假设
idiv执行过程中会检测并触发除法异常，那么执行idiv指令时，在哪些情况下会发生除法异常（需给出此时d[i]和x的十六进制机器数）？发生除法异常时，在异常响应过程中，CPU需要完成哪些操作？
【皮皮灰解法】
在补码除法中，被除数（这里）放在中，除数（这里）放在中，商初始为。
通常在补码除法器的控制逻辑部分会包含计数器，用于控制除法运算的步骤。
ALUop 所控制的 ALU 运算包括加法（用于恢复余数等操作）、减法（用于求部分余数等操作）等。
发生除法异常时，CPU 需要完成以下操作：
保存当前指令的地址（PC 值）到特定的寄存器或内存位置，以便后续能够返回到该指令重新执行（如果可能）。
跳转到异常处理程序的入口地址，执行异常处理程序。异常处理程序可能会进行一些错误处理，比如向操作系统报告错误，或者采取一些默认的处理措施（如返回一个默认值等）。
在异常处理程序执行完毕后，根据异常处理的结果，可能需要恢复到之前的执行状态，继续执行程序（如果异常被修复）或者终止程序（如果异常无法修复）。
45.三个人共同参与植树活动，其中甲负责挖树坑，乙负责将树苗放入坑中并填土，丙负责给新种的树苗浇水。整个植树过程依次包括挖树坑、放树苗、填土和浇水这几个步骤。现场有一把铁锹和一个水桶，铁锹用于挖树坑和填土，水桶用于浇水。当树坑数量小于 3 时，甲才能进行挖树坑的操作。假设初始时树坑数量为 0，铁锹和水桶都处于可用状态。请定义尽可能少的信号量，并用wait()和signal()操作来描述三人在植树过程中的同步与互斥关系，并解释所使用信号量的作用及其初始值。
【皮皮灰解法】
这是一个典型的进程同步与互斥问题，涉及到多个人（进程）对有限资源（铁锹、水桶）的操作和特定条件（树坑数量）下的工作流程。
需要定义信号量来控制进程的执行顺序和资源的访问。
定义信号量
设
emptyHole为表示空树坑数量的信号量，初始值为3，因为最多可以有 3 个树坑。设
spade为表示铁锹是否可用的信号量，初始值为1，因为只有一把铁锹。设
bucket为表示水桶是否可用的信号量，初始值为1，因为只有一个水桶。
【皮皮灰】不会有人不会写bucket吧
// 定义信号量
sem_t emptyHole;
sem_t spade;
sem_t bucket;
// 甲负责挖树坑
void* dig_hole(void* arg) {
while (1) {
sem_wait(&emptyHole); // 等待有空树坑
sem_wait(&spade); // 等待铁锹可用
// 模拟挖树坑操作
printf("甲：挖树坑\n");
sem_post(&spade); // 释放铁锹
}
return NULL;
}
// 乙负责放树苗和填土
void* plant_seedling(void* arg) {
while (1) {
sem_wait(&emptyHole); // 等待有空树坑
sem_wait(&spade); // 等待铁锹可用
// 模拟放树苗和填土操作
printf("乙：放树苗并填土\n");
sem_post(&spade); // 释放铁锹
sem_post(&emptyHole); // 空树坑数量加1
}
return NULL;
}
// 丙负责浇水
void* water(void* arg) {
while (1) {
sem_wait(&bucket); // 等待水桶可用
// 模拟浇水操作
printf("丙：浇水\n");
sem_post(&bucket); // 释放水桶
}
return NULL;
}46.某进程的虚拟地址空间如图，阴影部分为未占用区域，有 C 程序：
1.上述程序执行时，PCB 位于哪个区域，执行 scanf () 等待键盘输入时，该进程处于什么状态？
2.main () 函数的代码位于哪个区域？其直接调用的哪些函数的功能需要通过执行驱动程序实现？
3.变量 ptr 被分配在哪个区域？若变量 length 没有被分配在寄存器中，则会被分配在哪个区域？ptr 指向的字符串位于哪个区域？
【皮皮灰解法】
（1）
涉及进程控制块（PCB）的位置和进程在等待键盘输入时的状态。
当程序执行时，PCB 通常位于操作系统内核为进程分配的特定数据结构区域。
当执行
scanf等待键盘输入时，进程会进入阻塞状态，因为它在等待外部 I/O 操作完成。
（2）
询问
main函数代码的存储位置。在一般的进程虚拟地址空间中，
main函数的代码通常位于代码段（text segment）。直接调用的函数中，
malloc、scanf、strlen、printf和free这些函数的实现通常由 C 标准库提供，而这些库函数的底层功能（如内存分配、I/O 操作等）需要通过操作系统的执行驱动程序（如系统调用）来实现
（3）
涉及变量
ptr和length的内存分配位置。ptr是一个指针，通过malloc分配内存，所以ptr本身可能在栈区（stack），但它指向的内存区域在堆区。length如果没有被分配到寄存器中，通常会在栈区。ptr指向的字符串存储在堆区，因为这是malloc分配的内存空间。
47.
(1) 若忽略卫星信号中继、TR1 和 TR2 的调制解调开销，R1 到 R2 之间卫星链路的单向传播时延是多少？主机 H 向总部服务器传输数据时能够达到的最大吞吐量是多少？若忽略各层协议首部开销和以太网传播时延，H 向 sever 上传一个 4000 字节的文件至少需要多长时间？
(2) 基于 GBN 为卫星链路设计一个支持 R1 向 R2 发送数据的单向可靠链路层协议 SLP。SLP 数据帧长为 1500 字节，忽略 ACK 帧长度，若要求 SLP 单向信道利用率不低于 80%，那么发送窗口至少应为多少？SLP 帧序号至少应为多少？
(3) 总部给工程部分配了 IP 地址空间 10.10.10.0/24，并将其划分为 3 个子网，其中生活区子网数量不少于 120 个，作业子网和管理区子网的 IP 数量均不少于 60 个，且 H 已正确配置 IP。请问作业子网、管理区子网和生活区子网的地址分别是多少？
【皮皮灰解法】
（1）
（2）
（3）
