文章

80

粉丝

93

获赞

1

访问

7.6k

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


评分及理由

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

得分:0分

理由:学生作答的基本设计思想是使用归并排序的思路,将两个序列合并到一个辅助数组中,然后取第L个位置的元素作为中位数。但题目要求的是两个等长升序序列的中位数,且要求时间空间高效。标准答案采用二分查找思想,时间复杂度为O(log₂n),空间复杂度为O(1)。学生的思路虽然正确(能得到中位数),但不符合题目"尽可能高效"的要求,因为其时间复杂度为O(n),空间复杂度为O(L),效率较低。根据题目要求,这种低效的算法设计思想不能得分。

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

得分:0分

理由:代码实现存在多处逻辑错误:
1. 函数参数定义错误:int[]&A和int[]&B不是合法的C/C++语法
2. 数组声明错误:int[] tem[L]语法错误
3. 逻辑错误:在if-else分支中,当A[i] < B[j]时只将A[i]放入数组,但没有移动i指针
4. 语法错误:else if后面没有条件表达式
5. 算法逻辑不完整:没有处理当一个序列遍历完后的情况
6. 中位数位置计算错误:两个长度为L的序列合并后长度为2L,中位数应该是第L个元素(从1开始计数)

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

得分:0分

理由:学生分析的时间复杂度O(n)和空间复杂度O(L)虽然正确反映了其算法的复杂度,但由于算法本身不符合题目高效要求,且代码实现存在严重错误,因此不能得分。

题目总分:0+0+0=0分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发