文章

119

粉丝

0

获赞

1

访问

9.0k

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


评分及理由

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

学生答案的基本设计思想是使用一个辅助数组visited来标记1到n的正整数是否出现,最后遍历visited数组找到第一个未标记的位置即为未出现的最小正整数。该思路正确且高效,时间复杂度为O(n),空间复杂度为O(n)。与标准答案(原地标记)的思路不同,但同样正确,因此不扣分。得3分。

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

学生代码实现了上述思想,但存在以下问题:
1. 辅助数组visited未初始化,其初始值可能不为0,导致逻辑错误(例如,未出现的正整数可能被误判为已出现)。这属于逻辑错误,应扣分。
2. 代码中只处理了1到n范围内的正整数,但忽略了负数和非正整数(如0或负整数)的处理,但根据思想部分,该代码仅对1到n范围内的数进行标记,这符合设计思想,且最终能正确返回结果(因为小于1的数不会影响visited标记,大于n的数也不会被标记,但缺失的最小正整数一定在1到n+1范围内)。然而,未初始化visited数组是严重错误。
扣分:未初始化数组可能导致错误,扣2分。
其他部分正确,包括分配内存、遍历和返回逻辑。得6分(8-2=6)。

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

学生未在答案中说明时间复杂度和空间复杂度,因此不得分。得0分。

题目总分:3+6+0=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发