文章

67

粉丝

0

获赞

0

访问

2.0k

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


评分及理由

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

学生给出的基本设计思想是:使用两个指针,每次比较两个序列当前元素,将较小元素的指针右移,直到找到第L个元素。这种方法本质上是合并两个有序序列的前L个元素,然后取最后一个元素作为中位数。但题目要求的是两个等长升序序列的中位数,根据定义应该是合并后序列的第L个元素(因为总长度为2L,中位数是第L个)。学生的思路虽然能解决问题,但不是最优解,时间复杂度为O(n),而标准答案采用二分思想可以达到O(log n)。不过题目要求"尽可能高效",学生的解法在时间效率上不如标准答案,但思路正确且能解决问题。扣1分。

得分:3分

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

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

  1. 代码逻辑错误:在比较时使用A[k] >= B[i],当A[k]较大时取A[k],这实际上是在找较大的元素而不是较小的元素,与描述不符
  2. 变量初始化问题:k和i都初始化为0,但实际应该分别指向两个序列的起始位置
  3. 逻辑错误:当A[k] >= B[i]时,应该取B[i]而不是A[k],因为要找的是较小的元素
  4. 边界问题:没有考虑指针越界的情况
  5. 代码不完整:缺少必要的分号

由于存在明显的逻辑错误,扣分较多。

得分:4分

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

学生正确分析了算法的时间复杂度为O(n)和空间复杂度为O(1),虽然不如标准答案的O(log n)高效,但分析正确。

得分:2分

题目总分:3+4+2=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发