文章

179

粉丝

0

获赞

0

访问

8.8k

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


评分及理由

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

得分:1分

理由:学生的基本设计思想是“从第一个元素开始遍历,找出每个元素重复次数,若次数 > n/2 则为主元素”。这个思路是朴素(暴力)解法,虽然正确,但题目要求“尽可能高效的算法”,而标准答案给出了时间复杂度为 O(n) 的摩尔投票算法。学生的思路效率较低(O(n²)),未能达到题目对“高效”的要求,因此不能给满分。但思路本身能解决问题,故给1分。

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

得分:2分

理由:学生按照自己的思路实现了代码,但存在多处逻辑错误和语法错误:
1. 函数声明为 `void` 类型,但代码中使用了 `return A[i]` 和 `return -1`,返回值类型不匹配。
2. 内层循环中,`if (count > n/2)` 的判断放在内层循环内,且一旦满足就 `return A[i]`,这会导致统计不完整(例如,可能后面还有更多相同元素,但未统计完就提前返回,不过对于判断是否大于 n/2 来说,提前返回理论上可以,但代码中 `count` 只统计了从 `i` 到 `j` 的重复次数,未统计 `i` 之前的,实际上 `count` 应从0开始并统计整个数组)。
3. 外层循环每次将 `count` 重置为1,但未统计 `A[i]` 在 `i` 之前出现的次数,因此统计方式错误。
4. 代码中 `printf` 和 `return` 语句写在同一行,且 `return -1; printf("-1")` 存在语法错误(两次识别结果均有此问题)。
5. 整体算法虽然能通过双重循环找出出现次数最多的元素,但实现有缺陷,且效率低。根据评分标准,实现部分正确但存在明显错误,酌情给2分。

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

得分:2分

理由:学生正确分析了自己算法的时间复杂度为 O(n²),空间复杂度为 O(1),与所实现的算法一致,因此给满分2分。

题目总分:1+2+2=5分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发