文章

26

粉丝

0

获赞

0

访问

369

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


评分及理由

(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分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发