文章

202

粉丝

0

获赞

0

访问

49.0k

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


评分及理由

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

学生答案的基本设计思想是使用计数数组统计每个整数出现的次数,然后遍历计数数组找到第一个未出现的正整数。这种方法思路正确,能够解决问题,但空间复杂度为O(n),而标准答案使用原地标记法空间复杂度为O(1)。根据题目要求"时间上尽可能高效",学生的算法在时间上也是O(n),符合要求,且思路正确不扣分。得3分。

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

学生的代码实现存在以下问题:

  1. 代码逻辑错误:当数组元素值大于n时,访问count[A[i]]会导致数组越界。例如数组{1, 2, 3}中,n=3,当访问A[2]=3时,count[3]是合法的,但当数组中有大于n的元素时就会越界。
  2. 代码逻辑错误:没有正确处理负数和非正整数。题目要求找最小正整数,但学生的代码直接使用数组元素值作为下标,如果数组中有负数或0,会导致访问非法内存。
  3. 代码逻辑错误:没有考虑最小正整数从1开始的特点。当数组中包含0时,count[0]为0,但0不是正整数。
  4. 代码实现问题:有多余的大括号,可能是识别错误。

由于存在严重的逻辑错误,扣4分。得4分。

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

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

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发