文章

314

粉丝

1

获赞

107

访问

61.6k

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


评分及理由

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

学生作答的基本设计思想描述为:先让 P2 走到链表中间位置(n/2 向上取整的下一个位置),然后对后半部分链表进行原地逆置(头插法),并将链表断开,最后将逆置后的后半部分链表结点依次插入到前半部分链表的每两个结点之间。这一思路与标准答案“找到中点、反转后半段、合并两段”的核心思想一致,且满足空间复杂度 O(1) 的要求。因此,设计思想部分可得满分。
得分:3分

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

学生提供的代码存在多处逻辑错误和细节问题:
1. 函数参数中传入 n(链表长度),但题目要求算法不应依赖 n,应通过遍历自行确定长度或中点,此处与题目要求不符,属于设计缺陷,扣1分。
2. 在寻找中间结点的循环中,条件为 length <= n/2 +1,且初始 length=0,这样会导致 P2 实际移动到第 floor(n/2)+2 个结点(当 n 为偶数时可能越界),而不是正确的中间结点或后半段起点。这是一个严重的逻辑错误,扣2分。
3. 在断开链表时,使用 pre_P2->next = null,但此时 pre_P2 已经随 P2 移动,指向位置不正确,导致断点错误,扣1分。
4. 反转部分代码中,在创建 head2 后执行 P2 = null,导致后续 while 循环条件 P2!=null 直接不执行,反转操作完全失效,这是一个严重的逻辑错误,扣2分。
5. 合并部分的循环条件与指针移动逻辑存在错误:P1!=null 作为循环条件,但循环内 P1 = P1->next->next 可能访问空指针,且未处理合并结束后的剩余结点,扣1分。
6. 代码中使用了 null(应为 NULL),但根据“误写不扣分”原则,不扣分。
综合以上,代码部分存在较多逻辑错误,但整体框架与标准答案相似,因此给予部分分数。
得分:8 - 1 - 2 - 1 - 2 - 1 = 1分

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

学生正确指出时间复杂度为 O(n),与标准答案一致。
得分:2分

题目总分:3+1+2=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发