文章

63

粉丝

0

获赞

0

访问

13.0k

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

(1)由于我们需要找出M中最小的10个数,所以我们可以采用堆排序的思想,将数组中的元素变成一个小根堆,则每次根节点就是目前数组当中最小的元素;我们每次取出根节点的数字,然后调整小根堆,又会得到第二小的数字,以此类推,经过10次,我们可以得到M中最小的10个数。

(2)空间复杂度即堆的大小为O(n),时间复杂度即建堆的时间+10*调整堆的时间,即O(logn)。


评分及理由

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

得分:2分

理由:学生使用了小根堆的思路,但算法描述存在逻辑错误。题目要求找到最小的10个数,使用小根堆需要先构建整个数组的小根堆(时间复杂度O(n)),然后连续10次取出堆顶元素(每次调整堆O(logn)),总共需要O(n + 10logn)时间。但这种方法需要修改原数组,且空间复杂度为O(1)。然而,标准答案中使用的是大根堆来维护最小的10个数,这种方法只需要O(nlog10)的时间复杂度,效率更高。学生的算法虽然能正确得到结果,但效率不如标准答案,且没有说明如何维护最小的10个数,而是直接构建整个堆,这在n很大时效率较低。

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

得分:1分

理由:学生分析的时间复杂度和空间复杂度存在错误。空间复杂度应为O(1)(原地算法),但学生写成了O(n)。时间复杂度分析也不准确,建堆时间为O(n),10次调整堆为O(10logn),总时间复杂度应为O(n + 10logn),但学生简化为O(logn),忽略了建堆的O(n)项。

题目总分:2+1=3分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发