文章

250

粉丝

0

获赞

2

访问

39.7k

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

时间复杂度O(n),空间复杂度O(n)


评分及理由

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

学生答案的基本设计思想是使用辅助数组标记出现的正整数,然后遍历辅助数组找到第一个未标记的位置。这种方法虽然与标准答案(原地标记法)不同,但思路正确且能够解决问题,符合题目要求。因此得3分。

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

学生代码实现了辅助数组方法,但存在以下问题:
1. 辅助数组大小声明为temp[n+2],但初始化循环条件为x<=n+2,实际访问了n+3个位置,存在数组越界风险(应改为x 2. 处理负数时仅对temp[0]进行计数,但该计数结果并未用于后续查找最小正整数,逻辑冗余且不影响最终结果。
3. 返回语句中的break是无效代码(return后不会执行)。
4. 理论上当数组元素全为负数时,应返回1,但该代码通过辅助数组默认初始化为0的特性仍能正确返回1。

核心逻辑正确,主要扣分点在于数组越界风险。根据代码实现质量扣2分,得6分。

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

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

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发