文章

389

粉丝

5

获赞

19

访问

26.7k

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


评分及理由

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

学生答案的基本设计思想是使用一个辅助数组B来标记正整数1到n是否出现,然后遍历B找到第一个未标记的位置。这种思路是正确的,能够解决问题,但空间复杂度为O(n),而标准答案使用原地标记的方法,空间复杂度为O(1)。根据题目要求“在时间上尽可能高效的算法”,但并未明确要求空间高效,因此该思路正确,不扣分。得3分。

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

学生答案只给出了部分代码片段,且不完整(如“B = ”未赋值),无法运行。关键步骤缺失,如辅助数组B的分配和初始化、遍历A时对负数和大于n的数的处理(学生只提到“0 < A[i] < n”,但实际应为“0 < A[i] <= n”)、以及遍历B查找的逻辑。代码描述不完整,无法实现功能。因此,根据完整性、正确性和可执行性,扣分严重。得2分(仅因思路正确给部分分)。

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

学生正确分析了时间复杂度O(n)和空间复杂度O(n),与标准答案的时间复杂度一致,但空间复杂度更高(标准答案为O(1))。题目要求“时间上尽可能高效”,但未对空间做严格要求,因此空间复杂度分析正确,不扣分。得2分。

题目总分:3+2+2=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发