文章

273

粉丝

0

获赞

1

访问

58.8k

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


评分及理由

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

学生答案的基本设计思想是使用一个辅助数组pos来记录1到n范围内每个正整数出现的次数,然后遍历pos数组找到第一个出现次数为0的位置,即为未出现的最小正整数。这种方法思路正确,能够解决问题,与标准答案的哈希标记法虽然实现方式不同,但都是有效的O(n)时间复杂度算法。因此得3分。

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

学生提供的C语言代码实现了上述思想:

  • 正确分配了大小为n+2的辅助数组pos
  • 使用memset初始化数组为0
  • 正确遍历原数组,统计1到n范围内数字的出现次数
  • 从1到n+1遍历pos数组,找到第一个出现次数为0的位置
  • 正确释放内存并返回结果

代码逻辑完整正确,能够处理题目中的测试用例。但代码缺少对n≤0的边界情况处理,考虑到题目明确n≥1,这个缺陷不影响主要功能。根据评分标准,思路正确的不扣分,因此得8分。

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

学生正确分析了算法的时间复杂度为O(n),空间复杂度为O(n)。这与实际代码表现一致,分析准确。因此得2分。

题目总分:3+8+2=13分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发