2025年考研408计算机统考真题在线评测（附答案）

第41题

（本题 13 分）设有两个长度均为 n 的一维整型数组 A 和 res，对数组 A 中的每个元素 A [i]，计算 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 分）

参考答案：

（1）算法的基本设计思想：从后向前扫描一趟数组 A，对每个 A [i]（0≤i≤n-1），分别找到从 A [n-1] 到 A [i] 中的最大值 Max 和最小值 Min，然后分情况处理：①若 A [i]≥0，则 A [i] 与 Max 相乘；②若 A [i]<0，则 A [i] 与 Min 相乘；相乘的结果保存在 res [i] 中。

（2）算法实现：

void calMulMax(int A[], int res[], int n)
 {
      int i, Max, Min;
      Max = Min = A[n - 1]; // 初始化最大值和最小值为数组最后一个元素
      for (i = n - 1; i >= 0; i--) // 从后向前扫描数组A
 {
        if (A[i] > Max) Max = A[i]; // 更新最大值
        else if (A[i] < Min) Min = A[i]; // 更新最小值
       if (A[i] >= 0) res[i] = A[i] * Max; // 根据A[i]的正负性选择相乘的数
        else res[i] = A[i] * Min;
    }
}

（3）时间复杂度为 O (n)；空间复杂度为 O (1)。

第42题

（本题 10 分）某工程包含 12 个活动，使用下图所示的 AOE 网描述，图中各边上标注了活动及其持续时间。请回答下列问题（活动均用活动名表示）：

（1）完成该工程的最短时间是多少？哪些活动是关键活动？（3 分）

（2）若以最短时间完成工程，则与活动 e 同时进行的活动可能有哪些？（3 分）

（3）时间余量最大的活动是哪个？其时间余量是多少？（2 分）

（4）假设工程从时刻 0 启动，因某种原因，活动 b 在时刻 6 开始。为了保证工程不延期，在其他活动持续时间均不变的情况下，b 的持续时间最多是多少？若不改变 b 的持续时间，则压缩哪个活动的持续时间也能保证工程不延期？（2 分）

参考答案：

（1）完成该工程的最短时间是 12。关键活动是 a、e、m、n。

（2）与 e 同时进行的活动可能有 b、c、d。

（3）时间余量最大的活动是 j，时间余量是 6。

（4）b 的持续时间最多是 4；压缩 k 的持续时间。

第43题

（本题 12 分）现有 C 语言程序 P 的部分代码如图所示。假定运行程序 P 的计算机 M 字长为 32 位，按字节编址，数据 Cache 的数据区大小为 32KB，采用 8 路组相联映射方式，主存块大小为 64B，Cache 的命中时间为 2 个时钟周期，缺失损失为 200 个时钟周期；采用页式虚拟存储管理方式，页大小为 4KB。数组 d 的起始虚拟地址 VA₃₁~VA₀为 01800020H。请回答下列问题：

（1）主存地址中 Cache 组号字段和块内地址字段分别占几位？虚拟地址中哪些位可作为 Cache 索引？（3 分）

（2）d [100] 的虚拟地址为多少？d [100] 所在主存块对应的 Cache 组号是多少？（2 分）

（3）假定执行 for 语句时对应代码已在 Cache，变量 i 和 x 已装入寄存器，数组 d 已调入主存但不在 Cache，则 d [0] 在其所在主存块内的偏移量是多少（用十六进制表示）？for 语句执行过程中，访问数组 d 的 Cache 缺失率和数组元素的平均访问时间分别是多少（Cache 缺失率的计算结果要求用百分比表示，保留两位小数）？（5 分）

（4）数组 d 分布在几个页中？若执行 for 语句时对应代码已在主存，但数组 d 还未调入主存，则执行 for 语句过程中，访问数组 d 所引起的缺页次数是多少？（2 分）

参考答案：

（1）Cache 组号字段占 6 位；块内地址字段占 6 位。虚拟地址中 VA₁₁~VA₆可作为 Cache 索引。

（2）d [100] 的虚拟地址为 018001B0H；Cache 组号是 000110B=6。

（3）d [0] 在其所在主存块内的偏移量为 20H；共发生 129 次 Cache 缺失，访问总次数为 2048×2=4096，Cache 缺失率为 129/4096≈3.15%；数组元素的平均访问时间约为 2+3.15%×200=8.3 个时钟周期。

（4）数组 d 分布在 3 页中；访问数组 d 所引起的缺页次数是 3。

第44题

（本题 11 分）对于题 43 中计算机 M 和程序 P，假定 P 的部分机器级代码如（a）图所示，其中，R0~R4 为通用寄存器，SEXT 表示按符号扩展；M 中补码除法器逻辑结构如（b）图所示。请回答下列问题：

（1）若执行题 （a）图中 idiv 指令的除运算时，d [i]=0x87654321、x=0xff，则补码除法器中寄存器 R、Q 和 Y 的初始内容分别是什么（用十六进制表示）？题 （b）图中哪个部件包含计数器？在补码除法器执行过程中，由 ALUop 所控制的 ALU 运算有哪几种？（6 分）

（2）假设 idiv 指令执行过程中会检测并触发除法异常，则执行 idiv 指令时，哪些情况下会发生除法异常（要求给出此时 d [i] 和 x 的十六进制表示机器数）？发生除法异常时，在异常响应过程中 CPU 需要完成哪些操作？（5 分）

参考答案：

（1）R 中初始内容是 FFFFFFH；Q 中初始内容是 87654321H；Y 中初始内容是 000000FFH。控制逻辑部件中包含计数器。由 ALUop 所控制的 ALU 运算有加运算、减运算。

（2）当 x 为 00000000H 时，发生除 0 异常；当 d [i] 为 80000000H 且 x 为 FFFFFFFFH 时，发生除运算溢出异常。CPU 检测到除法异常后，需要将断点和程序状态保存到内核栈或者特定寄存器中，关中断，最后跳转到内核中的除法异常处理程序执行。

第45题

（本题 7 分）甲、乙、丙三人一起植树，甲负责挖树坑，乙负责将树苗放入树坑中并填土，丙负责为新种的树苗浇水。植树的步骤依次为：挖树坑、放树苗、填土和浇水。现有铁锹和水桶各 1 个，铁锹用于挖树坑和填土，水桶用于浇水。当树坑的数量小于 3 时，甲才可以挖树坑。假设初始时树坑的数量为 0，铁锹和水桶均可用。请定义尽可能少的信号量，用 wait ()、signal () 操作描述植树过程中三人之间的同步或互斥关系，并说明所用信号量的作用及其初值。

参考答案：

信号量 empty：作用是控制可挖树坑的最大数量，确保树坑总数不超过 3，以此同步甲的挖坑行为 —— 只有当已挖树坑数小于 3 时，甲才能执行挖坑操作，其初值为 3。

信号量 pit：用于表示已挖好且尚未被乙使用的树坑数量，承担甲（树坑生产者）和乙（树坑消费者）之间的同步功能 —— 甲挖好树坑后会触发该信号量，乙需等待该信号量可用才能进行放树苗操作，其初值为 0。

信号量 seedling：表示已完成放树苗和填土步骤、等待丙浇水的树苗数量，实现乙（栽种生产者）和丙（浇水消费者）之间的同步 —— 乙栽种完成后触发该信号量，丙需等待该信号量可用才能进行浇水操作，其初值为 0。

信号量 spade：用于实现铁锹的互斥使用，因为铁锹既供甲挖树坑，又供乙填土，同一时间只能由一人使用，通过该信号量避免资源竞争，其初值为 1。

甲（挖树坑）

while (true) {
    wait(empty);       // 检查是否允许挖树坑（树坑数<3）
    wait(spade);       // 申请铁锹（互斥使用）
    挖树坑;            // 核心操作
    signal(spade);     // 释放铁锹
    signal(pit);       // 挖好1个树坑，通知乙可使用
}

乙（放树苗 + 填土）

while (true) {
    wait(pit);         // 等待甲挖好树坑
    放树苗;            // 无需竞争资源，直接执行
    wait(spade);       // 申请铁锹（填土用）
    填土;              // 核心操作
    signal(spade);     // 释放铁锹
    signal(empty);     // 树坑已使用，释放1个“可挖坑名额”
    signal(seedling);  // 栽种完成，通知丙可浇水
}

丙（浇水）

while (true) {
    wait(seedling);    // 等待乙栽种好树苗
    浇水;              // 水桶唯一且无竞争（仅丙使用），直接执行
}

第46题

（本题 8 分）某系统中进程的虚拟地址空间包括内核区、用户栈、运行时堆、可读写数据段、只读代码段等区域，其布局如图所示，图中阴影部分表示未占用区域。现有 C 语言程序的部分代码如下：

char*ptr;
void main()
{
int length;
ptr=(char *)malloc(100);
scanf("%s", ptr);
length=strlen(ptr);
printf("length=%d\n", length);
free(ptr);
}

请回答下列问题：

（1）上述程序执行时，其进程控制块位于哪个区域？执行 scanf () 等待键盘输入时，该进程处于什么状态？（2 分）

（2）main () 函数的代码位于哪个区域？其直接调用的哪些函数的功能需要通过执行驱动程序实现？（3 分）

（3）变量 ptr 被分配在哪个区域？若变量 length 没有被分配在寄存器中，则会被分配在哪个区域？ptr 指向的字符串位于哪个区域？（3 分）

参考答案：

（1）进程控制块位于内核区；该进程处于阻塞态。

（2）main () 函数的代码位于只读代码段；scanf () 和 printf () 的功能需要通过执行驱动程序实现。

（3）ptr 被分配在可读写数据段中；length 会被分配在用户栈中；ptr 指向的字符串位于运行时堆中。

第47题

（本题 9 分）某公司在承建国家重大工程项目时，工程部需要较长时间驻扎在偏远山区，工程部网络需要连接公司总部网络。假设综合考虑方案的技术可行性、安全性与经济成本等因素后，决定租用我国自主建设的天通一号卫星通信链路，连接工程部网络的路由器 R1 和公司总部网络的路由器 R2，如图所示。S1 和 S2 为千兆以太网交换机；TR1 和 TR2 是卫星信号地面收发设备，实现全双工调制解调。天通一号卫星轨道高度是 36000km，电磁波信号传播速度为 300000km/s。租用的卫星链路为 R1 和 R2 之间提供对称全双工信道，每个方向的数据传输速率为 200kb/s。请回答下列问题：

（1）若忽略卫星信号中继以及 TR1 和 TR2 调制解调的时间开销，则 R1 到 R2 之间卫星链路的单向传播时延是多少？主机 H 向总部服务器传输数据时可以达到的最大吞吐量是多少？若忽略各层协议数据包的首部开销以及以太网内的传播时延，则主机 H 向总部服务器上传一个 4000B 大小的工程进度报告文件，至少需要多长时间？（3 分）

（2）现需要基于 GBN 滑动窗口协议为卫星链路设计单向可靠的数据链路层协议 SLP，支持 R1 向 R2 发送数据，SLP 数据帧长为 1500B，忽略 ACK 帧长度。若要求 SLP 的单向信道利用率不低于 80%，则 SLP 的发送窗口至少为多少？SLP 帧的序号字段至少需要多少位？（3 分）

（3）若公司总部为工程部网络分配的 IP 地址空间是 10.10.10.0/24，工程部进一步将该 IP 地址空间分配给 3 个子网，其中生活区子网可分配 IP 地址数不少于 120 个，作业区子网和管理区子网可分配 IP 地址数均不少于 60 个，且主机 H 已正确配置了 IP 地址，则作业区子网、管理区子网和生活区子网的子网地址分别是什么（给出 CIDR 地址形式）？（3 分）

参考答案：

（1）单向传播时延 = 2×(36000×10³)/(300000×10³)=240ms；最大吞吐量 = 200kb/s；最少时间 = 240×10⁻³+(4000×8)/(200×10³)=400ms。

（2）设发送窗口为 Wₛ，序号字段位数为 k，根据信道利用率公式：(Wₛ×(1500×8)/(200×10³))/(2×240×10⁻³+(1500×8)/(200×10³))≥0.8，解得 Wₛ≥7.2，向上取整得 Wₛ≥8；对于 GBN 协议，需满足 2ᵏ≥Wₛ+1=9，故 k≥4，即序号字段至少需要 4 位。

（3）生活区子网地址：10.10.10.128/25（可分配 126 个地址）；作业区子网地址：10.10.10.64/26（可分配 62 个地址）；管理区子网地址：10.10.10.0/26（可分配 62 个地址）。