文章

280

粉丝

1

获赞

8

访问

87.0k

头像
2018年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年9月26日 14:56
阅读数 191


评分及理由

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

学生答案的基本设计思想是使用哈希表统计1~n的正整数出现情况,然后遍历哈希表找到第一个未出现的正整数。这个思路是正确的,能够解决问题。虽然与标准答案(原地标记法)不同,但根据评分要求“思路正确不扣分”,因此不扣分。得3分。

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

学生代码存在以下逻辑错误:
1. `memset(0, hash, sizeof(hash))` 参数顺序错误,正确应为 `memset(hash, 0, sizeof(int)*(n+1))`。此处会导致哈希表初始化失败,属于逻辑错误,扣2分。
2. 在遍历数组时,直接使用 `hash[S[i]]++`,但数组S中的元素可能为负数或大于n,会导致数组越界。例如输入{-5,3,2,3}时,S[0]=-5,访问hash[-5]越界。这是严重逻辑错误,扣4分。
3. 最后返回逻辑有误:如果所有1~n都出现,应返回n+1,但学生代码中`res`计数多余,且返回判断`res==0?0:(n+1)`中,`res==0`的情况不会发生(因为至少i=1时res会递增),实际总是返回n+1,虽然结果正确但逻辑冗余,不扣分。
代码描述基本正确但存在关键错误,扣除6分,得2分。

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

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

题目总分:3+2+2=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发