文章

164

粉丝

0

获赞

1

访问

91.3k

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

(1)采用大根堆思想,设置堆大小为10,遍历数组进行初始建堆后,再往后过程中,若有元素小于堆顶元素,则将堆定元素删除,调整堆后插入新元素再调整,因为此时说明已有10个比堆顶更小的元素,以此类推,知道整个数组完成,此时堆中元素即为所求

(2)若设置查询个数为t,时间复杂度为o(tlogt),空间复杂度为o(t)


评分及理由

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

得分:4分

理由:学生回答正确使用了大根堆的思想来解决问题,算法描述基本正确。具体来说:

  • 正确描述了使用大小为10的大根堆
  • 正确描述了遍历数组的过程
  • 正确描述了当遇到比堆顶小的元素时的处理逻辑

扣分原因:算法描述中"遍历数组进行初始建堆后"表述不够准确。标准做法是先用前10个元素建堆,然后从第11个元素开始遍历。虽然学生可能理解这个意思,但表述不够严谨。

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

得分:3分

理由:

  • 时间复杂度分析基本正确:O(tlogt)中的t应该是10(堆的大小),实际应该是O(nlogt),但考虑到t是常数,可以简化为O(n),学生的表述虽然不够精确但方向正确。
  • 空间复杂度分析错误:学生回答O(t),但实际使用原地算法时空间复杂度应该是O(1)。这是逻辑错误,需要扣分。

题目总分:4+3=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发