文章

296

粉丝

0

获赞

0

访问

21.5k

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


评分及理由

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

得0分。学生的基本设计思想是采用双指针法,通过逐个比较A和B的元素来寻找中位数。但这种方法的时间复杂度为O(L),而题目要求尽可能高效,标准答案采用二分法可以达到O(log₂n)的时间复杂度。学生的思路虽然正确,但效率较低,不符合题目对"尽可能高效"的要求。此外,学生的算法逻辑存在根本性错误:中位数应该是合并后序列的第L个元素(因为总长度为2L,中位数是第L个),但学生的算法通过比较当前指针位置的值并移动指针,无法保证找到正确的中位数。

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

得0分。学生的代码实现存在严重逻辑错误:

  1. 算法逻辑错误:学生试图通过比较A[i]和B[j]的大小来决定移动哪个指针,但这种方法无法保证找到正确的中位数。例如,当A=[1,3,5],B=[2,4,6]时,学生的算法会得到错误结果。
  2. 参数设计错误:函数参数应该是序列长度n,而不是中位数位置L(实际上应该是n,因为两个序列各有n个元素,总长度为2n,中位数是第n个)。
  3. 初始化逻辑错误:p初始化为A[0]和B[0]中的较大值没有合理依据。
  4. 核心逻辑错误:每次循环只移动一个指针,无法正确处理两个序列的合并顺序。

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

得0分。学生分析的时间复杂度为O(L)(即O(n)),虽然分析正确,但由于算法本身是错误的,所以此项不得分。空间复杂度分析正确为O(1),但同样因为算法错误而不得分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发