文章

27

粉丝

0

获赞

0

访问

1.2k

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


评分及理由

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

得分:0分

理由:学生的基本设计思想存在逻辑错误。题目要求找出两个等长升序序列的中位数,而学生的思路是"先遍历A数组求得A的长度n,则两个序列的中位数为第n个元素",这个理解是错误的。两个等长序列合并后的中位数应该是第n个元素(因为总共有2n个元素,中位数是第n个),但学生没有正确理解中位数的定义。此外,采用双指针依次比较的方法虽然能解决问题,但时间复杂度为O(n),不是最优解,标准答案要求的是尽可能高效的算法(O(log₂n))。由于基本设计思想存在根本性错误,此项不得分。

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

得分:2分

理由:学生的代码实现存在多处逻辑错误:
1. 函数返回值类型应为int,第一次识别中写成了void
2. 算法逻辑错误:在比较A[i]和B[j]时,应该移动较小的那个指针,但学生代码中逻辑混乱
3. 当A[i] <= B[j]时,应该移动i指针;当A[i] > B[j]时,应该移动j指针,但学生的代码逻辑不清晰
4. 虽然代码能够运行并返回一个结果,但无法正确找到两个序列的中位数

给予2分是因为:
- 代码基本结构正确,使用了双指针思想
- 空间复杂度控制得当(O(1))
- 但核心算法逻辑错误,无法正确解决问题

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

得分:1分

理由:学生正确分析了时间复杂度为O(L)(即O(n))和空间复杂度为O(1),时间复杂度分析正确但非最优,空间复杂度分析正确。由于时间复杂度分析基本正确但未达到题目要求的"尽可能高效"的标准,扣1分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发