文章

101

粉丝

0

获赞

2

访问

33.4k

头像
2018年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年12月13日 17:02
阅读数 280


评分及理由

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

学生给出了使用辅助数组标记出现过的正整数的思路,基本思想正确,能够解决问题。但该思路需要额外的O(n)空间,而标准答案采用了原地标记法,空间复杂度更优。不过题目要求“时间上尽可能高效”,并未明确限制空间,且该思路时间复杂度为O(n),符合要求。因此,基本设计思想正确,得3分。

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

学生根据设计思想给出了C语言代码描述,关键步骤清晰。但代码中存在以下问题:
1. 第一次识别结果中,malloc(sizeof(A))是错误的,因为sizeof(A)得到的是指针大小,而非数组总字节数。第二次识别结果已修正为malloc(sizeof(int) * n),正确。
2. 代码未对辅助数组B进行初始化(虽然文字说明中提到了初始化,但代码中未体现)。这会导致如果数组A中某些正整数未出现,B中对应位置可能不是0,从而可能返回错误结果。这是一个逻辑错误。
3. 代码逻辑基本完整,包含了返回n+1的情况。
由于存在未初始化辅助数组的逻辑错误,扣2分。得6分。

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

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

题目总分:3+6+2=11分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发