2018年（408）计算机学科专业基础综合试题 - 第41题回答
1.用一个长度为n+1的 初值为0 count数组统计数组A中正整数元素出现的次数 2. 遍历统计完的count数组 找到第一个值为0的下标即可
int func(int A[],int n){
int count[n+1];
for(int i=0;i<n+1;i++)
count[i]=0;
for(int j=0;j<n;j++){
if(count[A[j]]==0）{
count[A[j]]++;
}
}
for(intk=1;k<n+1;k++){
if(count[k]==0)
return k;
}
}
时间复杂度O(N) 空间O(N)
评分及理由
（1）得分及理由（满分3分）
得分：2分
理由：学生的基本设计思想是使用计数数组来统计正整数出现的次数，然后找到第一个未出现的正整数。这个思路是正确的，能够解决问题，但相比标准答案的空间复杂度更高（O(n) vs O(1)）。由于题目要求"在时间上尽可能高效的算法"，虽然时间复杂度都是O(n)，但空间效率较低，因此扣1分。
（2）得分及理由（满分8分）
得分：6分
理由：学生的代码实现基本正确，但有以下几个问题：
- 代码语法错误：count[A[j]]==0）中的右括号是中文全角字符，应该扣1分
- 逻辑错误：只统计了第一次出现的元素（if(count[A[j]]==0)条件），但题目要求是找出未出现的最小正整数，应该统计所有正整数，这里逻辑不完整，扣1分
- 变量命名不规范，缺少必要的注释
- 没有处理负数和0的情况，如果数组中有负数，A[j]可能是负数，会导致数组越界
（3）得分及理由（满分2分）
得分：2分
理由：学生正确分析了算法的时间复杂度为O(n)和空间复杂度为O(n)，分析准确。
题目总分：2+6+2=10分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发