文章

131

粉丝

0

获赞

0

访问

6.2k

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


评分及理由

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

学生答案描述了使用一个大小为10的数组来维护当前最小的10个数,遍历原数组,将每个数与数组中的数进行比较,将较大的数移出,最终得到最小的10个数。这本质上是一种基于选择或插入思想的算法,但描述较为简略,没有明确说明如何高效地“放入”和“移出”(例如,是使用插入排序思想维护有序数组,还是使用大根堆)。其核心思想(维护一个大小为k的集合来保存当前最小的k个数)是正确的,并且符合题目要求“平均情况下比较次数尽可能少”。因此,可以给分。但描述不如标准答案中的两种方法(插入排序思想或大根堆)具体和优化。考虑到题目要求“简单描述其算法思想”,且思想正确,扣1分以体现其描述不够精确(未明确指出维护结构是有序数组还是堆,而这两种结构在平均比较次数上有差异,堆更优)。
得分:4分

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

学生给出的时间复杂度为O(n),空间复杂度为O(1)。对于使用大小为10的固定数组的算法,无论内部是采用插入排序思想还是堆思想,在n远大于10的情况下,时间复杂度确实是O(n)(每个元素最多进行O(log 10)或常数次比较),空间复杂度是O(1)(额外空间固定)。这与标准答案的分析一致。
得分:5分

题目总分:4+5=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发