文章

183

粉丝

0

获赞

1

访问

62.7k

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


评分及理由

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

得0分。学生的基本设计思想描述不清晰且存在逻辑错误。学生提到使用双指针同时遍历,当有一个指针到达尾部时停止,然后用指针p指向较长的链表并继续遍历,直到另一个指针也到达尾部,认为此时p指向共同后缀起始位置。这种思路无法正确找到共同后缀的起始位置,因为: 1. 在同步遍历过程中,当有一个链表先到达尾部时,另一个链表可能还未到达尾部,此时无法确定共同后缀的起始位置。 2. 后续的遍历逻辑只是简单地将p移动到较长链表的末尾,没有考虑两个链表的对齐和同步比较。 标准答案的正确思路是先计算两个链表的长度差,然后让长链表的指针先走长度差步,最后两个指针同步移动直到找到相同结点。

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

得0分。学生提供的代码实现存在多处逻辑错误: 1. for循环条件错误:在第一个for循环中,条件"i!=NULL&&j!=NULL"会导致循环在任一链表到达末尾时停止,但循环体内的if-else语句判断"i==NULL"永远为假(因为循环条件保证了i和j都不为空)。 2. 指针赋值逻辑错误:在循环体内,当i==NULL时p指向Str2->next,但实际上此时i不可能为空,这个判断永远不会执行。 3. 后续遍历逻辑错误:在第二个循环中,只是简单地将p指针移动到较长链表的末尾,没有进行任何比较操作,无法找到共同后缀起始位置。 4. 返回语句错误:最后返回p->next,但p已经指向链表末尾,p->next为NULL,无法返回正确的共同后缀起始位置。 代码整体逻辑与题目要求不符,无法正确找到共同后缀起始位置。

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

得0分。学生回答时间复杂度为O(n),但没有具体说明n的含义。即使按照学生的算法思路,时间复杂度也应该是O(m+n),其中m和n分别是两个链表的长度。更重要的是,由于算法本身是错误的,时间复杂度分析也就失去了意义。

题目总分:0+0+0=0分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发