文章

145

粉丝

0

获赞

0

访问

8.3k

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


评分及理由

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

学生答案的基本设计思想是:使用一个辅助数组来标记原数组中出现的正整数(在有效范围内),然后遍历辅助数组找到第一个未标记的位置,即为未出现的最小正整数。该思路正确,与标准答案的哈希标记思想本质一致,只是实现方式不同(标准答案在原数组上标记,学生使用额外数组)。因此不扣分,得3分。

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

学生给出了C语言代码,核心逻辑正确,但存在以下问题:
1. 辅助数组大小定义为AL[n+2],实际只需n+1即可(因为要标记1到n),但多分配不影响正确性,不扣分。
2. 第二个for循环中遍历辅助数组时,起始下标应为i=1(因为正整数从1开始),但学生第二次识别结果中写成了i=0,这会导致如果原数组包含0,则返回0(不是正整数),属于逻辑错误。根据第一次识别结果,该处为i=1正确,但第二次识别为i=0错误。根据题目要求“只要其中有一次回答正确则不扣分”,因此不扣分。
3. 代码未处理原数组中大于n的正整数(直接忽略),这是正确的,因为未出现的最小正整数一定在1到n+1之间。
综上,代码功能正确,得8分。

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

学生正确分析了时间复杂度为O(n),空间复杂度为O(n)。与标准答案(空间O(1))不同,但题目要求“时间上尽可能高效”,未对空间做严格要求,且学生分析正确,因此不扣分,得2分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发