2025 年 5 月第 1 次 408 月考试卷 - 第41题回答
1、使用Hash映射表，构建一个Hash数组B【n】，逐个遍历A中的元素，然后每次元素出现一次，则对应的B【A【i】】++。最后遍历数组B，找出值为1的对应下标则为目标仅出现一次的元素。
2、
int func(int A [],int n){
int B[n+2];
for(int i=0;i<n+2;i++) B[i]=0;
for(int i=0;i<n;i++){
B[A[i]]++;//遍历A，A出现的元素则在B中对应的下标加1
}
for(int i=0;i<n;i++){
if(B[i]==1) printf(i,"仅出现一次的元素：&i"，end="\n")
}
}
3、3个并列的循环，每个循环运行次数为n，时间复杂度O（n）
创建了一个长度为n的Hash数组，空间复杂度O（n）
评分及理由
（1）得分及理由（满分3分）
得分：1分
理由：学生的设计思想虽然正确，但不符合题目要求的“时间上尽可能高效的算法”。题目中明确说明“相同元素一定相邻”，可以利用这一特性设计更高效的算法（如标准答案中的直接比较法），而Hash映射表的方法虽然可行，但未利用题目给出的关键条件，效率较低。
（2）得分及理由（满分8分）
得分：4分
理由：
- 代码逻辑基本正确，能够通过Hash映射表找到仅出现一次的元素。
- 代码中存在以下问题：
- 语法错误：
printf(i,"仅出现一次的元素：&i"，end="\n")格式不正确，应为printf("仅出现一次的元素：%d\n", i);。 - 未处理边界情况：如果目标元素是数组的最后一个元素，且未在Hash数组的遍历范围内（例如A中元素值大于n），则无法正确找到目标元素。
- 未返回值：函数声明为返回
int，但未返回目标元素的值。 - 未利用题目中“相同元素一定相邻”的条件，导致算法效率较低。
（3）得分及理由（满分2分）
得分：1分
理由：学生正确分析了时间复杂度为O(n)，但未说明空间复杂度为O(n)（虽然题目未明确要求，但标准答案的算法空间复杂度为O(1)，因此扣1分。
题目总分：1+4+1=6分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发