文章

65

粉丝

0

获赞

0

访问

1.5k

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


评分及理由

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

得分:0分

理由:学生的设计思想是使用双指针分别遍历两个数组,每次比较后移动较小值的指针,经过n次比较后找到中位数。这种方法实际上是在模拟合并两个有序数组的过程,但题目要求的是两个升序序列的中位数,根据定义应该是合并后序列的第n个元素(因为总长度为2n,中位数是第n个)。学生的算法在循环n次后返回的实际上是第n小的元素,这个思路是正确的。但是标准答案采用的是更高效的二分查找思想,时间复杂度为O(log n)。虽然学生的思路正确,但题目要求"在时间和空间两方面都尽可能高效的算法",学生的O(n)解法不如标准答案的O(log n)高效,但根据评分规则"思路正确不扣分",这里应该给满分。不过仔细分析发现,学生的描述"经过n次比较,找到中位数"确实正确,因此应得4分。

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

得分:6分

理由:学生的代码实现了双指针遍历的思路,基本逻辑正确。但存在以下问题:

  1. 代码中当i==n-1时返回较小的元素,这确实能返回第n小的元素,逻辑正确
  2. 变量命名清晰,注释合理
  3. 但是代码没有处理边界情况,比如当p或q达到n时的情况
  4. 代码风格良好,逻辑清晰

扣分:由于没有处理边界情况,扣3分。

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

得分:2分

理由:学生正确分析了时间复杂度为O(n)和空间复杂度为O(1),这与算法实现相符。

题目总分:4+6+2=12分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发