文章

128

粉丝

0

获赞

0

访问

5.5k

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


评分及理由

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

学生答案的基本设计思想是:使用双指针分别指向两个序列的起始位置,通过比较指针所指元素的大小,每次将较小元素的指针后移一位,共移动⌈L/2⌉次后得到中位数。这种方法在思路上是正确的,能够找到两个升序序列的中位数,时间复杂度为O(L)。虽然与标准答案的二分法思路不同,但根据评分要求"思路正确不扣分",因此本部分得满分4分。

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

学生的代码实现存在以下问题:

  1. 代码中的break语句位置不当,当i或j等于L时break,但此时可能还没有完成⌈L/2⌉次移动
  2. 循环结束后,flag为true时返回S2[j],flag为false时返回S1[i],这个逻辑不正确。应该返回最后一次移动前较小元素的值
  3. 缺少对边界情况的处理,如当i或j达到L时如何处理
  4. 代码中a = (L/2) + 1的计算可能不准确,应该是向上取整

由于存在明显的逻辑错误,扣分较多。考虑到核心思路正确,但实现有缺陷,本部分得4分。

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

学生正确分析了时间复杂度为O(L),空间复杂度为O(1),这与算法实现一致。虽然时间复杂度不是最优的,但分析正确,因此本部分得满分2分。

题目总分:4+4+2=10分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发