2025 年 10 月第 1 次 408 月考试卷 - 第41题回答
1.双层循环进行求值，遍历O(n^2)次，当外层循环遍历到A[i]时，内层循环从A[i]到A[0]反向求交替和，取最大者。
2.
void calMaxAlternatingSum(int A[], int res[], int n){
for(int i = 0; i<n;i++){
int sign = (i % 2)==0?1:-1;
int local_sum = A[i];
res[i]=local_sum;
int j = i-1;
while(j-- >0){
sign *=-1;
local_sum += sign * A[j] + local_sum;
if(local_sum>res[i]){
res[i]=local_sum;
}
}
}
时间复杂度o(n^2)，空间复杂度o(1)
评分及理由
（1）得分及理由（满分4分）
得分：0分
理由：学生的设计思想是采用双层循环暴力求解，时间复杂度为O(n²)。这与题目要求的"尽可能高效的算法"相违背，标准答案使用动态规划达到O(n)时间复杂度。学生的算法设计思想没有达到题目对效率的要求，且没有正确理解交替和的计算方式。
（2）得分及理由（满分7分）
得分：0分
理由：学生的代码实现存在严重逻辑错误：
- 交替和计算错误：代码中"local_sum += sign * A[j] + local_sum"这一行明显错误，应该是"local_sum += sign * A[j]"，多加了local_sum导致计算完全错误
- 循环条件错误：while(j-- >0)会导致j跳过第一个元素，应该是while(j >= 0)
- 符号计算错误：sign的初始化和变化逻辑不正确，没有正确实现交替和的定义
- 代码无法正确运行，存在多处逻辑错误
（3）得分及理由（满分2分）
得分：1分
理由：学生正确分析了自己算法的时间复杂度O(n²)和空间复杂度O(1)，虽然算法效率不高，但复杂度分析正确，因此给1分。
题目总分：0+0+1=1分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发