文章

87

粉丝

0

获赞

1

访问

17.1k

头像
2013年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年8月17日 21:12
阅读数 89

(1)设置一个辅助数组b[n]初始化均为0,对序列A进行遍历,每遍历一个元素值为j,将b[j]中的元素+1.然后遍历b数组,找到符合题面中m>n/2的元素,若找到则返回数组下标i,否则返回-1
(2)

int result=-1;
int b[n]=[0];

for(int i=0;i<n;i++)
{
    b[a[i]]++;
}
for(int i=0;i<n;i++)
{
     if(b[i]>n/2) result=i;
}
cout<<result;
(3)时间复杂度为O(n),空间复杂度为O(n)


评分及理由

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

得分:3分

理由:学生的设计思想与标准答案不同,但思路正确且可行。学生提出使用辅助数组统计每个元素的出现次数,然后遍历辅助数组找到主元素。这种方法虽然空间复杂度较高,但逻辑正确。扣1分是因为没有提到如何高效地找到候选主元素(如标准答案中的两阶段策略),但整体思路可行。

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

得分:5分

理由:学生的代码实现了其设计思想,但存在以下问题:

  • 代码中未处理数组初始化问题(如int b[n]=[0]语法错误,应为int b[n] = {0};)。
  • 未明确说明输入和输出方式(如函数返回值或打印结果)。
  • 代码未封装为函数,不符合题目要求(题目要求设计算法并输出结果)。

扣2分主要是由于语法错误和代码结构不完整。

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

得分:2分

理由:学生正确分析了算法的时间复杂度(O(n))和空间复杂度(O(n)),与标准答案一致。

题目总分:3+5+2=10分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发