文章

292

粉丝

0

获赞

2

访问

79.6k

头像
2022年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年10月30日 17:59
阅读数 162


评分及理由

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

学生答案中提出使用小根堆算法来查找最小的10个数,但具体实现思路存在问题。标准答案中使用的是大根堆来维护最小的k个数,而学生提出构建小根堆并反复提取最小值,这种方法需要构建整个数组的小根堆(时间复杂度O(n)),然后执行10次提取操作(每次O(log n)),总时间复杂度为O(n + k log n)。虽然思路正确,但并不是最优方案,因为题目只要求最小的10个数,而学生的方法需要构建整个堆,比较次数较多。不过,由于题目允许思路正确不扣分,且核心使用了堆结构,因此不扣分。但学生没有详细描述如何维护最小的10个数,而是描述了完整堆排序的过程,这与题目要求不完全匹配。综合考虑,给予3分。

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

学生给出的时间复杂度为O(nlog₂n),这是构建整个堆并进行k次提取的时间复杂度,但实际最优方案的时间复杂度应为O(n)(使用大根堆维护最小k个数)。学生的时间复杂度分析不准确,因此扣2分。空间复杂度学生给出O(n),这是正确的,因为堆排序需要原地操作,不需要额外空间,但通常表述为O(1),这里不扣分。综合考虑,给予3分。

题目总分:3+3=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发