文章

36

粉丝

0

获赞

0

访问

3.7k

头像
2022年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年9月24日 18:25
阅读数 87

  1. 算法思想:基于小顶堆的筛选

    1. 构建初始小顶堆:首先将数组 M构建成一个小顶堆。在小顶堆中,每个父节点的值都小于或等于其子节点的值,因此堆顶元素(即根节点)就是整个堆中的最小值

    2. 提取最小值并调整堆:取出堆顶元素(当前最小值),将其与堆的最后一个元素交换,然后缩小堆的大小(即排除已取出的元素),并对新的堆顶元素进行“下沉”调整,以恢复小顶堆的性质

    3. 重复提取:重复上述步骤 10 次,每次都能得到当前堆中的最小值。这 10 个被取出的元素就是数组 M中最小的 10 个数。

    过程简述

    1. 建堆:将整个数组 M调整成一个小顶堆。

    2. 取数:

      • 进行 10 次循环操作。

      • 每次循环中,将堆顶元素 M[0](当前最小值)与堆的最后一个有效元素交换。

      • 减小堆的大小(相当于排除已提取的最小值)。

      • 对新的堆顶元素进行“下沉”操作,以维护小顶堆结构。

    3. 结果:最后取出的 10 个元素即为所求。

  2. 平均情况下的时间复杂度为O(n),空间复杂度为O(1)


评分及理由

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

得分:2分

理由:学生使用了小顶堆的方法来解决问题,思路基本正确。但是存在以下问题:

  • 题目要求是找出最小的10个数,但不需要排序。学生的方法通过10次提取堆顶元素,实际上会对这10个数进行排序(从大到小的顺序提取),这与题目要求不完全一致
  • 更重要的是,学生的方法需要构建整个数组的小顶堆,时间复杂度为O(n),然后进行10次堆调整,每次调整时间为O(log n),总时间复杂度为O(n + k log n),其中k=10
  • 标准答案中使用的是大顶堆方法,只需要维护大小为10的堆,时间复杂度为O(n log k),在k=10且n很大时更优
  • 学生的算法思想描述不够精确,没有明确指出只需要维护一个大小为10的堆

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

得分:2分

理由:

  • 时间复杂度分析错误:学生给出的O(n)不正确。实际时间复杂度应为O(n...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发