文章
104
粉丝
160
获赞
0
访问
2.5k

评分及理由
(1)得分及理由(满分5分)
得分:3分。
理由:学生回答中提到了“大根堆”这一核心数据结构,这是解决“查找最小k个数”问题的有效方法之一,思路基本正确。但是,学生的算法描述存在关键性逻辑错误。标准算法是:先用前10个元素构建一个大根堆,然后遍历剩余元素,若当前元素小于堆顶(即当前堆中最大元素),则用该元素替换堆顶并调整堆,以始终保持堆中为已遍历部分中最小的10个数。学生的描述“每次输入新元素之前将堆顶输出”是错误的,这会导致堆的大小不断变化,最终无法正确得到最小的10个数。由于存在核心逻辑错误,扣除2分。
(2)得分及理由(满分5分)
得分:2分。
理由:学生正确识别出算法基于“大根堆”,其时间复杂度通常与堆操作(log k)和遍历(n)相关。然而,学生的结论“时间复杂度为O(nlogn)”是错误的。对于大小为10的固定堆,每次堆调整的时间复杂度为O(log 10),即O(1)。遍历n个元素,总时间复杂度应为O(n)。学生给出的O(n log n)是高估了,这是一个复杂度分析错误。空间复杂度方面,学生回答O(n)是不准确的。该算法在原数组上操作(或仅使用一个固定大小的堆),额外空间复杂度应为O(1)或O(k),即O(1)。因此,本小题存在两处错误,扣除3分。
题目总分:3+2=5分
登录后发布评论
暂无评论,来抢沙发