文章

113

粉丝

0

获赞

6

访问

55.2k

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


评分及理由

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

学生答案提出使用小根堆来查找最小的10个数,具体方法是建立小根堆后重复输出堆首元素10次。这种方法在理论上是可行的,但存在逻辑错误:每次输出堆首元素后,需要重新调整堆结构(即删除堆顶元素并重新堆化),而学生答案没有明确描述这一关键步骤。此外,这种方法需要修改原数组(删除元素)或使用额外空间来存储输出的元素,与标准答案中原地算法的要求不完全一致。考虑到思路基本正确但存在关键步骤缺失,扣2分。

得分:3分

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

学生答案给出的时间复杂度为O(log n),这是不正确的。建立小根堆的时间复杂度为O(n),而每次删除堆顶元素并重新堆化的时间复杂度为O(log n),重复10次的总时间复杂度应为O(n + 10 log n) = O(n),但学生只提到了10 log n部分,忽略了建堆的O(n)操作。空间复杂度O(1)的表述正确,但基于时间复杂度的错误,扣3分。

得分:2分

题目总分:3+2=5分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发