文章

35

粉丝

0

获赞

0

访问

3.4k

头像
2011年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年8月30日 16:58
阅读数 29


评分及理由

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

学生作答的基本设计思想是:使用双指针遍历两个序列,通过比较指针所指元素的大小,移动较小元素的指针,并记录比较次数,当比较次数达到序列长度L时,返回当前指针所指元素中较小的一个作为中位数。该思路与标准答案的二分查找思想不同,但能够正确找到中位数(因为两个序列等长且升序,中位数实际上是第L小的元素)。然而,该方法的效率较低(时间复杂度为O(n)),而题目要求“在时间和空间两方面都尽可能高效”,标准答案的二分方法(O(log n))更高效。但题目允许“思路正确不扣分”,因此这里不因思路不同而扣分。但学生答案中存在逻辑错误:比较次数count的递增方式有问题(在循环内递增了两次),且返回语句中误写为“A[p]>A[q]”而非“A[p]>B[q]”,但根据“误写不扣分”原则,不因此扣分。因此,本部分得4分。

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

学生提供的代码存在以下问题:
1. 函数未考虑边界情况(如序列长度为0),但题目假设L≥1,故不扣分。
2. 循环条件为“p < L && q < L”,但实际两个指针不会同时越界,因为每次只移动一个指针,且比较次数达到L时终止,逻辑正确。
3. 在循环体内,count先自增1,然后判断是否等于L;在else分支中移动指针后,没有再次自增count(第二次识别结果已修正此问题,但第一次识别结果中有多余的“count++”)。根据“误写不扣分”原则,视为识别错误,不扣分。
4. 返回语句中误写为“A[p]>A[q]”而非“A[p]>B[q]”,但根据上下文,应为与B[q]比较,视为误写,不扣分。
5. 代码最终返回的是第L次比较时两个指针所指元素的较小值,这恰好是第L小的元素(即中位数),逻辑正确。
因此,代码核心逻辑正确,但存在一些细节错误(误写),根据规则不扣分。本部分得9分。

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

学生正确给出了时间复杂度O(n)和空间复杂度O(1)。虽然标准答案的二分法更高效(O(log n)),但学生的方法确实具有O(n)时间复杂度和O(1)空间复杂度,且题目要求“尽可能高效”,但未强制要求最优,因此不扣分。本部分得2分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发