2022年计算机学科专业基础综合试题 - 第42题回答
1）：利用维护大根堆，来保留n中的最小的10个数，首先取最初的10个元素构建大根堆，接着每次遍历一个元素都要和堆顶元素进行比较如果小于则删除堆顶元素并插入该元素然后调整堆使其满足大根堆定义，一直往后进行同样的操作直到遍历完100000个元素，最后大根堆留下的元素就是最小的10个数;
3):时间复杂度是o(nlogn),空间复杂度是o(1)；
评分及理由
（1）得分及理由（满分5分）
学生描述使用大根堆维护最小的10个数的算法思想，与标准答案中的方法二一致。具体步骤包括：取前10个元素构建大根堆，然后遍历剩余元素，若当前元素小于堆顶则替换堆顶并调整堆。该思路正确且完整，符合题目要求，因此得5分。
（2）得分及理由（满分5分）
学生给出的时间复杂度为O(nlogn)，但标准答案中时间复杂度为O(n)。实际上，构建初始堆的时间为O(k)（k=10），后续每个元素最多调整堆一次，调整时间为O(logk)，总时间为O(nlogk)，由于k=10是常数，因此时间复杂度为O(n)。学生将时间复杂度错误地写为O(nlogn)，存在逻辑错误，扣2分。空间复杂度O(1)正确，不扣分。因此本小题得3分。
题目总分：5+3=8分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发