文章

286

粉丝

0

获赞

2

访问

102.9k

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

1)首先实现一个堆排序 大根堆实现 将n个数里的前10个数建立初始大根堆 然后遍历数组M 每个元素与堆顶元素比较 如果小于堆顶元素则对顶元素出堆 对应数组元素入堆重新调整成大根堆 遍历完数组后最后留着大根堆里的是M中最小10个数

2)平均情况下时间复杂度o(n) 空间复杂度只用常数个辅助空间o(n)


评分及理由

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

学生描述的算法思想是:用前10个数建立大根堆,然后遍历剩余元素,若当前元素小于堆顶则替换堆顶并调整堆,最终堆中保留最小的10个数。这一思路与标准答案中的方法二(大根堆思想)完全一致,且描述清晰,符合题目要求“平均情况下比较次数尽可能少”。因此,本小题得满分5分。

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

学生给出的平均时间复杂度为O(n),正确。空间复杂度表述为“只用常数个辅助空间o(n)”,存在两处问题:一是“o(n)”应为“O(1)”,二是“o(n)”的小写o表示低阶无穷小,在此处用法错误。但结合上下文“常数个辅助空间”,其意图是表达原地算法、额外空间为常数,核心思想正确,但符号使用不规范且存在笔误。因此,酌情扣1分。本小题得4分。

题目总分:5+4=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发