（1）因为题目要求算法在时间上尽可能高效，所以基本设计思想是用空间换时间。构造一个包含n位的数组B，遍历给定的数组的同时，对数组出现的元素a，如果是正整数，则在数组A[a]上置1。没出现过的元素在数组B的对应元素下标的内容为0；遍历完一边数组之后，遍历构造的数组B，第一个出现0的数组下标就是数组中未出现的最小正整数。
（2）
void SearchMinnum(A,n)
{
B=（int*）malloc(n*sizeof((n));
while (i>=n)
{
if(A[i]>0)
{
B[i]=1;
}
}
for(i=0,i<=n,i++)
{
if(B[i]==0)
{
return i;
break;
}
}
}
(3)
因为构造辅助数组所以空间复杂度是n。时间复杂度是n。
评分及理由
（1）得分及理由（满分3分）
得分：2分
理由：学生的基本设计思想是使用辅助数组来标记出现的正整数，思路正确且符合时间高效的要求。但存在以下问题：
1. 没有明确指出辅助数组的大小应该是n+1（因为可能出现的正整数范围是1~n+1）
2. 没有考虑数组元素可能大于n的情况
3. 没有明确说明如何处理重复元素
思路基本正确但不够完善，扣1分。
（2）得分及理由（满分8分）
得分：3分
理由：代码实现存在较多逻辑错误：
1. 函数参数声明不完整，缺少参数类型
2. malloc分配错误，应该是(n+1)*sizeof(int)
3. while循环条件错误，应该是i < n
4. 标记逻辑错误，应该是B[A[i]] = 1，而不是B[i] = 1
5. for循环语法错误，应该使用分号而不是逗号
6. 循环条件应该是i <= n而不是i <= n
7. 没有初始化辅助数组B为0
8. 缺少必要的头文件包含
9. 函数没有返回值类型声明
由于存在多个严重逻辑错误，扣5分。
（3）得分及理由（满分2分）
得分：1分
理由：学生正确分析了时间复杂度为O(n)和空间复杂度为O(n)，但空间复杂度分析不够准确，实际应该是O(n)而不是简单的n。扣1分。
题目总分：2+3+1=6分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发