文章

26

粉丝

93

获赞

1

访问

1.5k

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


评分及理由

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

学生给出的基本设计思想是:利用双指针合并两个升序序列为一个新序列,然后取新序列的中位数。这种方法虽然正确,但并不是题目要求的“在时间和空间两方面都尽可能高效的算法”。题目要求高效,而这种方法的时间复杂度为O(m+n),空间复杂度为O(m+n),与标准答案的O(log₂n)时间复杂度和O(1)空间复杂度相比,效率较低。因此,学生的思路虽然正确,但不符合题目对高效的要求。扣2分,得2分。

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

学生的代码实现了合并两个序列并取中位数的功能,但存在以下问题:
1. 代码中使用了`vector ten(m + n)`,这需要额外的O(m+n)空间,不符合空间高效的要求。
2. 合并逻辑有误:在比较`A[i]`和`B[j]`时,学生代码是降序合并(因为当`A[i] >= B[j]`时取`A[i]`),但题目要求升序序列,这会导致合并后的序列不是升序,从而中位数计算错误。这是一个逻辑错误。
3. 中位数位置计算:`ceil((m+n)/2)`在C++中整数除法会截断,导致结果不正确,应使用`(m+n-1)/2`或类似方式。
4. 代码中变量名`mmin`和`num`与函数名冲突,且识别结果中函数名不一致(第一次识别为`mmin`,第二次为`num`)。
由于存在严重的逻辑错误(降序合并)和空间低效问题,扣5分,得4分。

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

学生正确分析了算法的时间复杂度为O(m+n)和空间复杂度为O(m+n),但该复杂度并非高效实现,与标准答案不符。由于题目要求尽可能高效,而学生实现的是普通方法,但复杂度分析本身正确,因此扣1分,得1分。

题目总分:2+4+1=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发