文章

45

粉丝

0

获赞

0

访问

4.7k

头像
2022年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年9月24日 16:18
阅读数 53

1.时间自底向上建小根堆,即使用堆排序

2.堆排序时间复杂度o(nlogn),需要建堆,空间复杂度o(n)


评分及理由

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

学生答案得分为:2分。
理由:学生提出的“自底向上建小根堆”即堆排序方法,虽然是一种可行的排序算法,但题目要求是查找最小的10个数,而不是对整个数组排序。堆排序会对所有n个元素进行排序,其比较次数远大于最优解。题目要求“平均情况下的比较次数尽可能少”,而堆排序的时间复杂度为O(n log n),并非最优。更优的算法是使用大小为10的大根堆来维护最小的10个数(如标准答案方法二),其时间复杂度为O(n log k),其中k=10,远优于O(n log n)。因此,学生的算法思想虽然正确,但不符合题目对比较次数的优化要求,存在逻辑错误,扣3分。

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

学生答案得分为:2分。
理由:学生给出的时间复杂度O(n log n)对于堆排序算法本身是正确的,但如上所述,该算法并非本题最优解,因此时间复杂度的分析虽然正确但不符合题目优化目标。空间复杂度O(n)的表述不准确,因为堆排序通常是原地排序,空间复杂度应为O(1),学生此处存在逻辑错误。综合考虑,时间复杂度分析部分得1分(算法正确但非最优),空间复杂度分析错误扣1分,本小题得2分。

题目总分:2+2=4分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发