文章

54

粉丝

21

获赞

0

访问

4.0k

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

(1)A和B等长,那么两个序列的中位数即A和B中第n大的元素,令i=0,j=0,循环遍历A和B,若A[i]<B[j],则i++,否则j++,直到找到第n个元素为止。

(2)

(3)循环了L次,所以时间复杂度为O(L);并没有建立数组,所以空间复杂度为O(1)。


评分及理由

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

得0分。学生的基本设计思想是使用双指针遍历两个数组,通过比较A[i]和B[j]的大小来移动指针,直到找到第n个元素。这种方法的时间复杂度为O(n),虽然正确但不符合题目要求的"尽可能高效"(标准答案采用二分法达到O(log₂n))。由于题目明确要求时间和空间都尽可能高效,而学生的方法在时间效率上明显低于最优解,因此不能得分。

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

得3分。代码实现存在多处问题:
1. 函数参数不完整,缺少序列长度参数
2. 变量L未定义
3. 逻辑错误:当n+1==L时返回的是A[i]或B[j],但此时i或j已经自增,实际返回的是下一个元素
4. 边界情况处理不当,可能导致数组越界
5. 代码无法正确处理所有情况
考虑到代码基本实现了双指针遍历的思路,但存在严重逻辑错误,给予3分。

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

得1分。时间复杂度分析正确为O(L),空间复杂度分析正确为O(1)。但由于时间复杂度分析中使用了L而不是n,且未说明L与n的关系(题目中序列长度为n),扣1分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发