文章

316

粉丝

0

获赞

0

访问

46.4k

头像
2022年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年10月27日 21:06
阅读数 16

1):利用维护大根堆,来保留n中的最小的10个数,首先取最初的10个元素构建大根堆,接着每次遍历一个元素都要和堆顶元素进行比较如果小于则删除堆顶元素并插入该元素然后调整堆使其满足大根堆定义,一直往后进行同样的操作直到遍历完100000个元素,最后大根堆留下的元素就是最小的10个数;

3):时间复杂度是o(nlogn),空间复杂度是o(1);


评分及理由

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

得分:5分

理由:学生描述的算法思想与标准答案中的方法二(大根堆方法)完全一致。具体步骤包括:取前10个元素构建大根堆,然后遍历剩余元素,若当前元素小于堆顶则替换堆顶并调整堆,最终堆中保留最小的10个数。算法思想正确且描述清晰,符合题目要求。

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

得分:3分

理由:学生给出的时间复杂度O(n log n)不正确。根据标准答案,使用大根堆方法的时间复杂度应为O(n),因为构建初始堆的时间为O(k)(k=10为常数),后续每个元素的比较和堆调整时间为O(log k),总时间为O(n log k) = O(n)(因为k=10是常数)。空间复杂度O(1)正确,因为算法是原地操作。由于时间复杂度分析错误,扣2分。

题目总分:5+3=8分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发