文章

35

粉丝

0

获赞

0

访问

1.4k

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


评分及理由

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

得分:0分

理由:学生的设计思想是使用双指针合并两个升序序列,然后取合并后数组的第L个元素(索引L-1)。这与题目要求的高效算法不符,因为题目要求时间和空间都尽可能高效,而这种方法需要O(L)的额外空间,并且时间复杂度为O(L),没有达到最优的O(log₂n)时间复杂度。标准答案采用二分查找思想,每次比较两个序列的中位数并舍弃一半元素,不需要合并整个数组。

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

得分:0分

理由:学生实现的代码基于合并两个数组的思路,虽然代码逻辑正确(能够合并两个升序数组并返回第L个元素),但不符合题目对高效算法的要求。关键问题包括:①使用了O(L)的额外空间,而最优解应为O(1);②时间复杂度为O(L),而最优解应为O(log₂n);③没有利用序列等长的特性进行优化。此外,代码返回的是p[L-1],但两个长度为L的序列合并后中位数应该是第L个元素(因为总长度为2L,中位数是第L个),这一点计算正确,但方法整体不符合高效要求。

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

得分:1分

理由:学生正确分析了所实现算法的时间复杂度O(L)和空间复杂度O(L),但未达到题目要求的最优复杂度。由于复杂度分析本身正确,但算法不是最优解,因此给予部分分数。

题目总分:0+0+1=1分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发