文章

427

粉丝

0

获赞

3

访问

66.0k

头像
2022年(408)计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年12月14日 21:24
阅读数 66

利用大根堆排序,每次选出十个数中最大的元素 依次遍历n个数后 堆中的十个数就是n个数中最小的十个

时间复杂度o(n)空间复杂度o(1)


评分及理由

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

学生描述了使用大根堆的方法来查找最小的10个数,算法思想基本正确:维护一个大小为10的大根堆,堆顶是当前堆中最大的数,遍历后续元素,若比堆顶小则替换堆顶并调整堆。这与标准答案中的方法二一致。但描述过于简略,没有说明初始堆的构建过程(例如前10个元素如何形成大根堆),也没有提及遍历的起始位置(应从第11个元素开始比较)。鉴于核心思想正确,扣1分。得4分。

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

学生给出的时间复杂度O(n)和空间复杂度O(1)是正确的。对于大根堆方法,建大小为10的堆是O(1),遍历n-10个元素,每次调整堆的代价是O(log 10)=O(1),因此总时间复杂度为O(n)。空间复杂度为原地操作,O(1)。因此得5分。

题目总分:4+5=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发