文章

297

粉丝

0

获赞

1

访问

178.0k

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


评分及理由

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

学生答案的基本设计思想是:将两个序列归并后取中位数。这种方法虽然正确,但时间和空间复杂度并非最优。题目要求“在时间和空间两方面都尽可能高效的算法”,而标准答案采用二分查找思想,时间复杂度为O(log₂n),空间复杂度为O(1),明显更高效。学生答案的思路未达到题目对高效性的要求,因此扣2分。得分:2分。

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

学生答案的代码实现存在多个错误:
1. 函数Merge没有返回值(应为void或返回k),但学生代码中使用了赋值语句“C[] = Merge(...)”,这是语法错误。
2. 在Find函数中,变量i未初始化就被使用(在if(i%2==0)中),这会导致未定义行为。
3. 中位数位置计算错误:对于长度为2L的归并数组(总长度为偶数),中位数应为第L个元素(索引从0开始是L-1),但学生代码中使用了条件判断和错误计算(例如i=L/2或(L/2)+1),逻辑混乱。
4. 代码未处理数组索引从0开始的问题,且归并后的数组长度为2L,但学生代码中直接使用L进行计算,导致中位数位置错误。
这些错误表明代码无法正确实现功能,因此扣分严重。但考虑到学生正确实现了归并操作(尽管效率不高),给予部分分数。得分:3分。

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

学生正确分析了归并算法的时间复杂度O(n)和空间复杂度O(n),但未达到题目要求的“尽可能高效”(标准答案为O(log₂n)和O(1))。因此扣1分。得分:1分。

题目总分:2+3+1=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发