文章

122

粉丝

1

获赞

100

访问

30.0k

头像
2022年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年11月4日 15:54
阅读数 84


评分及理由

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

得分:0分

理由:学生提出使用冒泡排序10趟来获取最小的10个数,这种方法在理论上是可行的,但效率很低。冒泡排序每趟只能确定一个最大(或最小)元素的位置,要获取最小的10个元素需要完整排序整个数组或至少进行10趟排序,每趟需要比较n次,总比较次数为O(10n)=O(n)。然而,题目要求平均情况下比较次数尽可能少,冒泡排序虽然时间复杂度为O(n),但常数因子很大,不是最优解。标准答案提供了插入维护或堆维护的方法,这些方法在平均情况下比较次数更少。因此该算法思想不符合题目要求"比较次数尽可能少"。

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

得分:3分

理由:学生正确给出了时间复杂度O(n)和空间复杂度O(1)。时间复杂度分析基本正确,因为10趟冒泡排序确实是O(10n)=O(n)。空间复杂度O(1)也正确,因为冒泡排序是原地排序。但由于算法思想不是最优,扣2分。

题目总分:0+3=3分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发