文章
26
粉丝
0
获赞
0
访问
369
评分及理由
(1)得分及理由(满分4分)
得0分。学生的基本设计思想是将两个序列合并后排序,再取中位数。这种方法虽然正确,但时间和空间效率不高,不符合题目要求的“尽可能高效”的条件。标准答案采用二分查找思想,时间复杂度为O(log₂n),而学生的方法时间复杂度为O(n log n),空间复杂度为O(n),明显效率较低。因此,设计思想不符合题目要求,不得分。
(2)得分及理由(满分9分)
得0分。学生提供的代码实现了合并后排序的方法,但存在多个逻辑错误:
1. 快速排序函数Qsort中,基准元素p的选择和分区逻辑有误。例如,初始条件if(L >= R) return; 正确,但分区过程中指针移动和交换逻辑不标准,可能导致排序错误。
2. 在Find函数中,数组A的大小为2*L,但Qsort调用时参数为Qsort(A,0,2*L-1),正确,但返回A[L]是第L+1个元素(索引从0开始),对于合并后长度为2L的数组,中位数应是第L个元素(索引L-1)和第L+1个元素(索引L)的平均值?但题目中序列是等长升序,且定义中位数位置为⌈L/2⌉,但合并后中位数位置应为第L个(因为总长度2L,中位数是第L和L+1的平均?)。但学生直接返回A[L],对于L=5(序列长度5),合并后长度10,中位数应是第5和第6的平均,但这里返回A[5](第6个元素),错误。
3. 因此,代码逻辑错误,不能正确得到中位数。
尽管学生方法思路正确(合并排序),但实现有误,且不符合高效要求,因此不得分。
(3)得分及理由(满分2分)
得1分。学生正确说明了时间复杂度为O(n log n)和空间复杂度为O(L)(即O(n)),但空间复杂度写为O(L)实际是O(2L)=O(n),正确。但时间复杂度因算法效率低,且部分正确,给1分。
题目总分:0+0+1=1分
登录后发布评论
暂无评论,来抢沙发