文章

238

粉丝

0

获赞

3

访问

33.1k

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


评分及理由

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

学生答案的基本设计思想是使用哈希表统计元素出现次数,然后遍历哈希表检查是否存在出现次数超过n/2的元素。这种方法虽然正确,但不符合题目要求的“尽可能高效的算法”中的“高效”指时间复杂度O(n)和空间复杂度O(1)的优化目标(标准答案使用摩尔投票法,空间复杂度为O(1))。但题目并未强制要求空间复杂度为O(1),且哈希表方法的时间复杂度为O(n),也是正确的解法。因此,思路正确,不扣分。得4分。

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

学生代码实现了哈希表方法,逻辑正确:初始化哈希表、统计次数、检查主元素。但存在以下问题:
1. 代码中使用了变长数组(int hash[n]),在C99标准中合法,但部分环境可能不支持。不过题目允许C/C++/Java,且学生明确使用C语言,因此不扣分。
2. 变量m定义为n/2,但整数除法会向下取整,而主元素要求m>n/2(严格大于)。例如n为偶数时,n/2是整数,但主元素需要至少n/2+1次出现。代码中条件为hash[i] > m,正确(因为m=n/2是整数,若hash[i]=n/2+1则大于m)。但需注意n为奇数时n/2向下取整,例如n=5时m=2,主元素需要至少3次,条件hash[i]>2正确。因此逻辑无误。
3. 代码未处理n=0的情况,但题目未明确要求边界,因此不扣分。
整体实现正确,但空间复杂度为O(n),不符合“尽可能高效”中的空间优化意图。但题目未明确要求空间复杂度O(1),且算法正确,因此扣1分(空间效率不足)。得6分。

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

学生正确分析了时间复杂度O(n)和空间复杂度O(n),与实现一致。得2分。

题目总分:4+6+2=12分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发