文章

30

粉丝

0

获赞

0

访问

9.8k

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

(1)我会选择创建一个同类型的,大小为10的数组result,用直接插入排序升序排序存放数组M中的头10个数变量,然后将result的第一个值创建一个min变量,然后从Z的第11个开始遍历数组,每当发现一个比min小的数字才将min更新并直接插入排序到result数组中。

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


评分及理由

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

得分:3分

理由:学生答案的思路基本正确,采用了维护一个大小为10的有序数组来保存最小元素,这与标准答案中的方法一(插入排序思想)相似。但是存在以下问题:

  • 学生提到"每当发现一个比min小的数字才将min更新",这里的min应该是result数组的最大值(即result[9]),而不是第一个值。因为result数组是升序排序,第一个值是最小值,最后一个值才是当前10个数中的最大值。这个逻辑错误会导致算法无法正确找到最小的10个数。
  • 算法描述不够精确,没有明确说明当发现比当前最大值小的元素时,需要替换最大值并重新排序。

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

得分:4分

理由:

  • 时间复杂度分析正确:O(n)是合理的,因为需要遍历n-10个元素,每个元素最多需要10次比较(插入排序)。
  • 空间复杂度分析正确:O(1)是合理的,因为只使用了固定大小的额外数组。
  • 但由于第一部分存在逻辑错误,此处适当扣分。

题目总分:3+4=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发