文章

281

粉丝

0

获赞

0

访问

46.5k

头像
2011年(408)计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年12月3日 10:02
阅读数 2


评分及理由

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

学生给出的基本设计思想是:通过双指针遍历两个升序序列,每次比较当前指针所指元素,将较小的指针向后移动,同时计数,当计数达到中位数位置时,比较当前两个指针所指元素,返回较小的那个作为中位数。这种方法本质上是合并两个有序序列并找到第k小元素(k为中位数位置),思路正确,但并非题目要求的时间空间尽可能高效的最优解(最优解为二分查找,时间复杂度O(log n))。然而根据打分要求第3点“思路正确不扣分”,此处思路正确,因此得满分4分。

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

学生根据设计思想给出了C语言代码实现。代码逻辑清晰,能够正确实现所述思路:计算中位数位置k,用双指针i、j遍历数组,计数器count记录已处理的元素总数,当count达到k时,比较A[i]和B[j]并返回较小者。代码在边界条件下(如两个数组元素交替大小)也能正确工作。但存在一个潜在问题:当A[i] == B[j]时,代码在count未达到k时的else分支中执行的是“else j++”,这会导致跳过A[i]而选择B[j]向后移动,虽然不影响最终中位数结果(因为相等时移动任意一个均可),但逻辑上不够严谨。不过,根据题目要求“关键之处给出注释”,学生注释较少,但代码本身可读性尚可。考虑到代码正确实现了所述思路,且没有原则性错误,根据打分要求,不因非最优解而扣分。但代码在循环结束后没有返回值(理论上循环一定会因count==k而返回,但编译器可能认为有路径无返回值),这是一个小瑕疵。综合评定,扣1分。得8分。

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

学生正确说明了算法的时间复杂度为O(L)(即O(n)),空间复杂度为O(1)。分析正确,得满分2分。

题目总分:4+8+2=14分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发