文章

292

粉丝

0

获赞

2

访问

78.7k

头像
2011年(408)计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年11月24日 17:38
阅读数 84


评分及理由

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

得分:0分

理由:学生提出的算法思想是使用双指针从头遍历两个序列,通过计数器控制比较次数来寻找中位数。这种方法实际上是在模拟归并排序的合并过程,但只进行部分比较。然而,这种方法无法正确找到两个升序序列的中位数。题目要求的是两个序列合并后的中位数,而学生的算法在计数器减到0时返回两个指针指向的较大值,这并不保证是正确的中位数。例如,对于序列A=[1,3,5]、B=[2,4,6],按照该算法会返回4,但实际中位数应该是3.5(或取整为3)。因此,基本设计思想存在根本性错误。

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

得分:0分

理由:基于错误的设计思想,代码实现也无法正确解决问题。代码逻辑是设置计数器count初始为L-1,然后通过比较A[i]和B[j]的值来移动指针并减少计数器,当计数器为0时返回两个指针指向的较大值。这种方法无法保证找到正确的中位数,因为:1)它没有考虑两个序列合并后的整体排序;2)返回值的逻辑不符合中位数的定义;3)对于偶数长度的序列,中位数应该是中间两个数的平均值,而代码直接返回单个值。因此,代码实现存在根本性逻辑错误。

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

得分:1分

理由:学生正确分析了算法的时间复杂度为O(n)和空间复杂度为O(1)。虽然算法本身是错误的,但对这个错误算法的时间空间复杂度分析是正确的,因此给予1分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发