文章

75

粉丝

78

获赞

0

访问

4.1k

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


评分及理由

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

得分:4分。学生的基本设计思想描述清晰:先计算两个链表的长度,然后让长的链表先走长度差步,之后两个指针同步向后移动,直到指向同一结点(即共同后缀起始位置)或遍历结束。该思路与标准答案一致,且时间上尽可能高效。

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

得分:7分。学生的代码(以第二次识别的Java代码为准)整体逻辑正确,实现了设计思想,但存在以下问题:
① 代码中计算链表长度时,指针 p 和 q 遍历后已到达链表尾部,之后又重新赋值为头结点,这一点处理正确。
② 但在对齐操作中,标准答案是从头结点开始,让长链表的指针先走到与短链表剩余长度相同的位置(即第 m-n+1 个结点),而学生的代码中,指针 p 和 q 初始指向的是头结点(st1 和 st2),然后直接向后移动长度差步。如果链表带头结点,那么头结点本身不存储数据,学生的移动方式会导致指针实际多移动了一步(因为长度计算包含了头结点?这里需要分析)。仔细看学生的长度计算:while (p != null) { len1++; p = p.next; } 如果链表带头结点,则 p 从 st1(头结点)开始,第一次循环就计数,所以 len1 包含了头结点。而标准答案中 Length(str1) 通常不计头结点(题目说 str1 和 str2 分别指向两个单词所在单链表的头结点,头结点不存单词数据)。因此学生的长度计算多计了头结点,导致后续对齐时指针移动步数错误,可能错过共同后缀起始点或导致错误。这是一个逻辑错误,扣1分。
③ 其他部分,如同步遍历和返回共同结点,逻辑正确。代码注释较少,但关键步骤可理解,不扣分。

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

得分:1分。学生正确给出了时间复杂度 O(max{len1, len2}),与标准答案一致。

题目总分:4+7+1=12分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发