文章

191

粉丝

0

获赞

0

访问

18.4k

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


评分及理由

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

学生答案的基本设计思想是使用一个辅助数组B来标记出现过的正整数,然后遍历B找到第一个未标记的位置作为结果。这种方法与标准答案的"负号标记"方法不同,但思路正确且能够解决问题。虽然使用了额外的O(n)空间,但题目要求"时间上尽可能高效",并未限制空间使用,因此该思路正确。得3分。

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

学生用C/C++风格代码实现了算法,但存在几个问题:
1. 代码中未处理非正整数的情况,只检查了A[i]>0,但忽略了等于0的情况(根据题目描述,最小正整数从1开始,0不算正整数)
2. 数组B的大小为n+2,但实际只需要n+1(因为要包含下标1到n+1)
3. 遍历B时下标从1开始正确,但最后一个循环的条件应该是i<=n+1
4. 返回0作为安全返回不合理,应该返回n+1

由于核心逻辑正确但存在上述问题,扣3分。得5分。

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

学生正确分析了时间复杂度和空间复杂度,均为O(n),与实际情况相符。得2分。

题目总分:3+5+2=10分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发