文章

17

粉丝

0

获赞

0

访问

1.3k

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


评分及理由

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

学生答案的设计思想是使用归并排序的思路,将两个有序序列合并成一个大的有序数组,然后取中间位置的元素作为中位数。这种方法思路正确,但并不是题目要求的"在时间和空间两方面都尽可能高效"的算法。标准答案采用的是二分查找思想,时间复杂度为O(log₂n),而学生的归并方法时间复杂度为O(n),效率较低。但根据评分规则"思路正确不扣分",学生的思路是正确的,只是效率不够高。因此得4分。

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

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

  1. 代码逻辑错误:while循环条件为"i < L || k < L",但循环内部只处理了j和k的移动,没有正确处理边界情况
  2. 变量使用错误:在else分支中,应该是k++而不是j++(第一次识别中有此错误,第二次识别已修正)
  3. 代码不完整:缺少返回中位数的语句,函数没有返回值
  4. 内存泄漏:分配了S数组但没有释放
  5. 参数命名不规范:使用S₁和S₂不符合C语言标识符规范

根据代码实现的完整性和正确性,扣除相应分数。考虑到核心归并逻辑基本正确,但实现不完整且有多处错误,得4分。

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

学生正确分析了时间复杂度为O(n),但空间复杂度分析错误。归并方法需要额外的O(n)空间,而不是O(1)。因此得1分。

题目总分:4+4+1=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发