文章

35

粉丝

0

获赞

0

访问

6.7k

头像
2018年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年11月9日 05:07
阅读数 103


评分及理由

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

学生给出的设计思想是使用辅助数组来标记出现的正整数,然后遍历辅助数组找到第一个未标记的位置。这种方法思路正确,能够解决问题,并且时间复杂度为O(n),符合题目要求的时间高效。虽然与标准答案的原地标记方法不同,但根据评分规则“思路正确不扣分”,因此不扣分。得3分。

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

学生代码实现了设计思想,使用辅助数组aid来记录正整数是否出现。代码逻辑清晰,关键步骤有注释。但存在以下问题:
1. 代码中只处理了正整数的绝对值,但未考虑负数和非正整数的情况。例如,输入数组包含负数时,取绝对值后可能将负数转换为正数并错误标记,导致结果不准确(如数组{-5, 3, 2, 3}中,-5取绝对值后变为5,标记aid[5]=1,但5可能超出范围,且未出现的最小正整数应是1,但代码可能错误返回其他值)。这属于逻辑错误,扣2分。
2. 辅助数组大小为n+1,但未限制标记范围在1到n之间,如果数组元素绝对值大于n,会导致数组越界或错误标记(例如,数组元素为1000时,aid[1000]可能越界)。这属于逻辑错误,扣2分。
代码整体结构正确,实现基本符合设计思想,但上述错误影响正确性。扣除4分后,得4分。

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

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

题目总分:3+4+2=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发