文章

295

粉丝

0

获赞

1

访问

81.9k

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


评分及理由

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

得分:4分

理由:学生答案的核心算法思想是使用大小为10的大根堆来维护最小的10个数,这与标准答案中的方法二(大根堆思想)一致,思路正确。算法描述基本清晰:先构建大根堆,然后遍历后续元素,若当前元素小于堆顶则替换并调整堆。这是解决“查找最小k个数”问题的经典高效方法之一。

扣分原因:答案中存在一处明显的逻辑错误。在描述比较和交换条件时,学生答案写道“①t≤M[i],则跳过;②t > M[i],则将t与M[i]交换”。这里“t”的含义不明确,根据上下文推断,“t”很可能是指堆顶元素。然而,正确的逻辑应该是:如果当前遍历的元素 M[i] 小于 堆顶元素,则用 M[i] 替换堆顶并调整堆;否则(即 M[i] 大于或等于堆顶)则跳过。学生的描述“t > M[i]” 与正确的逻辑“堆顶 > M[i]”恰好相反,这是一个关键性的逻辑错误,因此扣1分。

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

得分:5分

理由:学生正确给出了算法的时间复杂度为 O(n) 和空间复杂度为 O(1)。对于使用大小为常数k(此处k=10)的大根堆算法,构建初始堆为O(k),后续n-k次遍历,每次堆调整最坏为O(log k),总时间复杂度为O(k + (n-k)log k) = O(n log k)。由于k=10是常数,log k也是常数,因此简化为O(n)。空间复杂度为原地操作,仅使用常数额外空间,即O(1)。这与标准答案的分析结果一致。

题目总分:4+5=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发