文章

103

粉丝

93

获赞

1

访问

8.8k

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


评分及理由

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

学生答案的基本设计思想是:创建一个长度为n+1的辅助数组,遍历原数组,将正数按值存放到辅助数组对应位置,然后遍历辅助数组找到第一个缺失的正整数。这个思路是正确的,能够解决问题,但使用了额外的O(n)空间,而标准答案使用了原地标记法,空间复杂度为O(1)。根据题目要求"在时间上尽可能高效的算法",虽然学生的思路时间复杂度为O(n)符合要求,但空间效率不如标准答案。不过题目并未明确要求空间效率,且思路正确,因此不扣分。得分:3分。

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

学生的代码实现存在几个问题:

  1. 数组索引错误:代码中for(int i=1;i应该从0开始遍历原数组,而不是从1开始,这会导致漏掉第一个元素。
  2. 辅助数组未初始化:int B[n+1]未初始化,其值是不确定的,后续判断if(B[i]==0)不可靠。
  3. 逻辑缺陷:当原数组中存在重复的正整数时,辅助数组的对应位置会被重复写入,但不影响结果判断。
  4. 代码注释缺失:题目要求"关键之处给出注释",但学生代码没有任何注释。

由于存在明显的逻辑错误(索引错误和未初始化数组),扣分较多。但核心算法思路正确,给予部分分数。得分:4分。

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

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

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



登录后发布评论

暂无评论,来抢沙发