文章

26

粉丝

93

获赞

1

访问

1.5k

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


评分及理由

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

学生作答的基本设计思想是构造一个长度为两序列长度之和一半的数组,通过合并两个升序序列到新数组,然后返回新数组的最后一个元素(即第⌈(lenA+lenB)/2⌉个元素)作为中位数。这种方法虽然能够找到中位数,但并不是时间和空间尽可能高效的算法,因为题目要求高效(时间复杂度O(log n)和空间复杂度O(1)),而该方法的时间复杂度为O(n),空间复杂度为O(n),不符合要求。标准答案采用二分查找思想,每次比较两个序列的中位数并舍弃一半,效率更高。因此,该设计思想不够高效,扣2分。得分:2分。

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

学生提供的代码实现了合并数组的方法,但存在以下问题:
1. 代码中未处理指针越界的情况(例如,当i或j超过数组长度时,会导致访问越界)。
2. 返回的是tem[k-1],但k在循环结束后为(lenA+lenB)/2,因此返回的是新数组的最后一个元素,这确实是两个序列合并后前一半元素的最后一个,但题目要求的是两个序列所有元素的中位数(即第n小的数,因为两个序列等长,总长度为2n,中位数是第n小的数),而该方法正确返回了第n小的数(因为新数组长度正好为n,最后一个元素就是第n小的数)。但该方法需要O(n)额外空间,且效率不高。
3. 代码中使用了vector,但参数传递未指定类型(应为vector),但可能是识别错误,不扣分。
4. 与标准答案的高效算法(二分法)相比,该方法在时间和空间上均不足。但代码逻辑本身(除越界问题外)能正确得到中位数。
由于存在指针越界的逻辑错误(未处理数组边界),扣3分;因算法效率不符合题目要求(但题目要求“尽可能高效”,而该方法不是最优),再扣2分。得分:4分。

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

学生正确分析了算法的时间复杂度为O(n)和空间复杂度为O(n),但该复杂度不符合题目“尽可能高效”的要求(标准答案为O(log n)和O(1))。因此,分析正确但算法本身不够高效,扣1分。得分:1分。

题目总分:2+4+1=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发