文章

133

粉丝

0

获赞

0

访问

13.4k

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


评分及理由

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

学生答案中描述了大根堆算法思想:建立大小为10的大根堆,遍历剩余元素,若元素小于堆顶则替换堆顶并调整堆,最终堆中即为最小的10个数。这与标准答案中的方法二完全一致,算法思想正确且描述清晰。因此得5分。

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

学生答案给出的时间复杂度为O(nlog₂n),但标准答案中堆方法的时间复杂度为O(n)。因为建堆时间为O(k),每次堆调整时间为O(log k),共调整n-k次,总时间复杂度为O(k + (n-k)log k) = O(n log k),其中k=10为常数,所以实际为O(n)。学生写成O(nlog₂n)存在轻微误差,但考虑到k=10是常数,O(n log k)与O(n)在渐进意义下等价,且题目强调平均情况比较次数尽可能少,堆方法确实能达到线性时间复杂度,因此不扣分。空间复杂度O(1)正确。得5分。

题目总分:5+5=10分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发