文章

260

粉丝

0

获赞

0

访问

24.3k

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


评分及理由

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

学生答案中提出使用小根堆的方法,但具体实现思路不完整。标准答案中采用大根堆维护最小的10个数,每次比较新元素与堆顶(最大值),若新元素更小则替换并调整堆,这样只需维护大小为10的堆。而学生答案中描述的是将所有n个数构建小根堆,然后输出前10个,这种方法虽然能得到最小10个数,但构建整个堆的时间复杂度为O(n),而输出前10个需要10次删除堆顶操作,每次O(log n),总时间复杂度为O(n + 10log n) = O(n),但学生答案中写的时间复杂度为O(n log n),与标准方法的时间复杂度不符。由于思路基本正确但描述不够精确,且时间复杂度计算错误,扣2分。

得分:3分

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

学生答案中时间复杂度写为O(n log n),但实际采用小根堆方法构建堆的时间复杂度为O(n),输出前10个最小元素的时间复杂度为O(10 log n) = O(log n),总时间复杂度应为O(n + log n) = O(n)。空间复杂度写为O(log n),但堆排序的空间复杂度通常为O(1)(原地排序),或者如果考虑递归深度则为O(log n)。学生答案中的空间复杂度描述不准确,但考虑到可能是指递归栈空间,扣1分。时间复杂度错误较严重,扣2分。

得分:2分

题目总分:3+2=5分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发