文章

305

粉丝

0

获赞

0

访问

64.6k

头像
2019年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年12月11日 09:05
阅读数 175


评分及理由

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

学生给出了基本设计思想:将后半部分逆置,然后用两个指针分别从头和中间开始重新排列。这与标准答案的思路一致,即找到中点、反转后半段、合并两个链表。因此得3分。

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

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

  1. 函数名使用了“reserve”,应为“reverse”(但识别可能误写,且不影响逻辑,不扣分)。
  2. function中,参数head是带头结点的单链表头指针,但reserve(P1)调用时,P1此时指向的是前半部分的最后一个结点(即第k个结点),而reserve函数期望传入的是带头结点的链表头指针。这里直接传入P1会导致逆置操作错误,因为P1作为“头结点”使用,但实际它只是一个普通结点,其next指向后半部分的第一个结点。标准答案中是将后半部分断开并反转,而学生代码没有显式断开,且reserve函数会改变传入头结点的next指向,这里逻辑不清晰,会导致链表连接错误。
  3. 合并部分的循环条件while(P1->next!= NULL)存在问题:当后半部分逆置后,P1指向的是原后半部分的最后一个结点(即逆置后的第一个结点),而循环中P1->next可能会提前变为NULL,导致合并不完整。标准答案中是用两个指针分别遍历两个链表直到后半部分链表为空。
  4. 合并操作中的指针操作复杂且可能出错,例如n1->next = P2;n2->next = n1;的意图是交替插入,但逻辑与标准答案不同,且未正确处理前后连接。

由于存在明显的逻辑错误(尤其是逆置和合并部分),扣分。考虑到学生整体思路正确,但实现有缺陷,给予4分(扣4分)。

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

学生正确给出了时间复杂度O(n),得2分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发