文章

101

粉丝

0

获赞

1

访问

30.5k

头像
2013年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年10月31日 16:51
阅读数 45

(1)采用一个辅助数组大小为b[n],遍历a[n],将a[i]出现的次数依次存入b[a[i]]中,之后遍历b[i],寻找其最大元素,若其最大元素>n/2,则对应下标+1即为主元素,否则输出-1

(2)int b[n]=0;

int result=0;

int false=-1;
for(int i=0;i<n;i++)
{

b[a[i]]++;
}

for(int i=0;i<n;i++)
{

int max1=0;

if(b[i]>max1) b[i]=max1;result=i+1;
}
if(max1>n/2)cout<<result;
else cout<<false;
(3)时间复杂度与空间复杂度均为O(n)


评分及理由

(1)得分及理由(满分4分)

得分:2分

理由:学生的基本设计思想是使用辅助数组统计每个元素的出现次数,然后找出出现次数最多的元素并判断是否超过n/2。这种方法思路正确,能够解决问题,但并不是题目要求的"尽可能高效的算法"。标准答案使用的是Boyer-Moore投票算法,时间复杂度O(n),空间复杂度O(1),而学生的方案空间复杂度为O(n),不符合"尽可能高效"的要求。因此扣2分。

(2)得分及理由(满分7分)

得分:3分

理由:学生的代码实现存在多处逻辑错误:
1. 变量max1在每次循环中都初始化为0,无法正确记录最大值
2. 赋值语句"b[i]=max1"逻辑错误,应该是"max1=b[i]"
3. 变量result的赋值位置错误,应该在找到最大值时记录
4. 缺少对数组b的初始化(虽然思路中提到但代码未体现)
5. 输出格式不完整
虽然基本思路正确,但由于存在多处逻辑错误,严重影响了算法的正确性,因此扣4分。

(3)得分及理由(满分2分)

得分:2分

理由:学生正确分析了算法的时间复杂度和空间复杂度,均为O(n),这与学生所采用的算法思路是一致的,因此给满分。

题目总分:2+3+2=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发