文章

56

粉丝

0

获赞

0

访问

7.1k

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


评分及理由

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

学生给出了算法的基本设计思想:先分别计算两个链表的长度m和n,然后让较长的链表的指针先移动|m-n|步,之后两个指针同步移动,直到找到相同的结点(即公共后缀起始位置)。该思路与标准答案一致,正确且清晰。因此,得4分。

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

学生代码中存在以下逻辑错误:
1. 在计算链表长度时,指针p和q在循环中没有移动(缺少p=p->next和q=q->next),导致死循环和错误长度计算。扣2分。
2. 在同步移动p和q寻找公共结点时,循环体内错误地执行了两次移动(p=p->next和q=q->next执行了两次:一次在循环条件内,一次在循环条件外),这会导致跳过公共结点或越界。扣3分。
3. 代码最后部分(p=p->next; q=q->next;)在循环结束后执行是多余的,且可能访问空指针,逻辑错误。扣1分。
4. 结构体定义中使用了J LNode(可能是笔误,应为} LNode),但根据上下文可判断为误写,不扣分。
代码整体思路正确,但实现有严重逻辑错误。扣除错误分后,得2分(8-2-3-1=2)。

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

学生给出的时间复杂度为O(n),但未说明n的含义(实际应为O(m+n))。然而,根据算法步骤,正确时间复杂度应为O(m+n),学生表述不准确。但考虑到学生可能用n代表总长度,且答案中体现了线性复杂度,给0.5分(扣0.5分)。

题目总分:4+2+0.5=6.5分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发