文章

296

粉丝

0

获赞

0

访问

21.3k

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


评分及理由

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

学生作答描述了一个基于插入排序思想的算法:使用大小为10的数组B存储当前最小的10个数,并保持有序。遍历数组M剩余元素时,若当前元素小于B中最大值(B[9]),则替换并重新排序。该思路与标准答案中的方法一基本一致,算法思想正确。但学生提到使用直接插入排序进行重新排序,这在最坏情况下每次插入需要O(k)时间(k=10),但k为常数,因此整体时间复杂度仍为O(n),符合要求。由于思路正确且描述清晰,得5分。

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

学生正确给出了时间复杂度O(n),因为需要遍历n个元素,每次插入操作的时间复杂度为O(1)(因为k=10是常数)。但空间复杂度标注为O(n)是不正确的,因为算法只使用了一个固定大小为10的辅助数组B,与n无关,空间复杂度应为O(1)。因此扣1分,得4分。

题目总分:5+4=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发