文章

124

粉丝

0

获赞

0

访问

12.6k

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


评分及理由

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

得分:2分

理由:学生提出构建小根堆并循环10次取出堆顶元素的方法。这种方法虽然能正确找到最小的10个数,但效率较低。构建小根堆的时间复杂度为O(n),但每次取出堆顶元素后需要重新调整堆,调整10次的时间复杂度为O(10logn) = O(logn),总体时间复杂度为O(n + 10logn) = O(n)。然而,标准答案中提供了更优化的方法(插入排序思想或大根堆方法),这些方法在平均情况下比较次数更少。学生的算法虽然正确,但不够高效,因此扣3分。

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

得分:3分

理由:学生给出的时间复杂度O(nlogn)不正确。正确的时间复杂度应为O(n)(构建堆O(n) + 10次调整O(logn))。空间复杂度O(logn)基本正确,因为堆排序的递归调整可能需要O(logn)的栈空间,但标准答案中强调原地算法,空间复杂度为O(1)。由于时间复杂度错误,扣2分;空间复杂度部分正确,不额外扣分。

题目总分:2+3=5分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发