文章

21

粉丝

0

获赞

2

访问

1.1k

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


评分及理由

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

学生答案的基本设计思想是使用一个长度为n的辅助数组统计每个元素出现的次数,然后遍历统计数组找到出现次数超过n/2的元素。这种方法思路正确,能够正确找出主元素,符合题目要求。但是与标准答案中更优化的摩尔投票法(空间复杂度O(1))相比,空间复杂度较高。不过题目要求的是"尽可能高效的算法",并没有明确要求空间复杂度必须为O(1),且学生的算法时间复杂度为O(n)也是高效的。因此按照"思路正确不扣分"的原则,给予满分4分。

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

学生代码实现正确:
- 正确创建了统计数组B并初始化为0
- 正确遍历原数组进行计数
- 正确遍历统计数组判断主元素条件
- 正确返回主元素或-1
代码逻辑完整正确。但存在一个小问题:在C语言中,变长数组(VLA)不能直接初始化为0(int B[n] = {0};),这在实际编译中可能会有问题。不过考虑到这是识别结果,且核心算法逻辑正确,按照"识别错误不扣分"的原则,不因此扣分。给予满分7分。

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

学生正确分析了时间复杂度为O(n)和空间复杂度为O(n),分析准确。给予满分2分。

题目总分:4+7+2=13分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发