文章

92

粉丝

68

获赞

0

访问

11.4k

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

(1) 使用冒牌排序思想,每次把最小的取出来放到最后,循环10次后,数组最后10位就是保存的最小的10个数

(2)时间复杂度 O (10*n)   空间复杂度 O(1)


评分及理由

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

学生提出的算法思想是:使用冒泡排序思想,每次把最小的取出来放到最后,循环10次。这种方法在概念上可以找到最小的10个数,但存在以下问题:
1. 描述不够精确。“把最小的取出来放到最后”在冒泡排序中通常指通过相邻元素比较和交换,将最大元素“冒泡”到末尾。要找到最小的元素并放到末尾,效率很低。
2. 对于n>100000的情况,该算法需要进行约10*n次比较,虽然时间复杂度是O(n),但常数因子很大(10轮,每轮可能接近n次比较),在实践中比标准答案中的插入维护或堆方法效率低得多。
3. 算法没有说明如何维护和更新这10个最小数的集合,只是说“数组最后10位就是保存的最小的10个数”,这意味着原数组最后10位被覆盖,但未说明覆盖过程是否会影响后续查找。如果每次找到当前最小后将其交换到末尾,那么数组末尾10位确实是全局最小的10个,但原数组被破坏,且过程中比较次数并非最优。
鉴于学生给出了一个可行但非高效的算法,且描述较为粗略,扣2分。
得分:3分

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

学生给出的时间复杂度为O(10*n),即O(n),这与标准答案一致,但常数估计不准确(实际冒泡方式可能多于10*n次比较)。空间复杂度O(1)正确。
然而,由于算法思想部分存在缺陷,且时间复杂度表达不够规范(应写为O(n)),扣1分。
得分:4分

题目总分:3+4=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发