文章

26

粉丝

93

获赞

1

访问

1.5k

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


评分及理由

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

得2分。学生的设计思想是构造一个新数组,通过合并两个序列的前半部分来找到中位数。这种方法虽然正确,但并不是最优解,因为题目要求时间和空间都尽可能高效。标准答案采用二分查找思想,时间复杂度为O(log₂n),空间复杂度为O(1),而学生的方案时间复杂度为O(n),空间复杂度为O(n),效率较低。因此,虽然思路正确,但未达到“尽可能高效”的要求,扣2分。

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

得5分。学生的代码实现了合并两个序列前半部分的功能,但存在以下问题:
1. 代码中使用了未定义的类型"Vector",应为"vector"(可能是识别错误,但根据上下文判断为误写,不扣分)。
2. 新数组长度计算错误:题目中序列是等长的,设长度为n,则中位数位置应为第n个(因为总长度为2n,中位数是第n个),但学生代码中数组长度为(lenA+lenB)/2,即n,正确。但返回的是tem[k-1],即第n个元素,正确。
3. 但代码未考虑边界情况,例如当某个序列元素全部被合并时,可能发生越界(例如如果A序列所有元素都小于B序列,则i可能超出lenA)。代码中未处理这种情况,存在逻辑错误,扣2分。
4. 代码注释和逻辑基本清晰,但效率不高,与标准答案的高效算法不符,再扣2分。

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

得2分。学生正确分析了时间复杂度和空间复杂度,均为O(n),与代码实现一致。

题目总分:2+5+2=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发