文章
131
粉丝
21
获赞
0
访问
5.2k
 
(1)遍历链表并计算出两个链表的长度m和n,让更长的链表前移|m-n|,然后建立sum=0,同时遍历链表,当str1当前节点和str2当前节点的data值相同时,sum加1,如果不同,则将sum至0。遍历至链表表尾,得出公共后缀的长度。让更短的链表前移表长减sum得到共同后缀的起始位置。
(2)
(3)时间复杂度O(n)。
评分及理由
(1)得分及理由(满分4分)
得分:2分
理由:学生的基本设计思想部分正确。正确之处包括:①计算两个链表长度;②让长链表先移动差值步使两个链表剩余长度相等。但存在逻辑错误:学生提出通过比较节点data值并累加sum来记录公共后缀长度,然后通过移动指针找到起始位置。这种方法在多个不连续匹配时会被错误重置sum,且最终移动步数的计算逻辑错误(应该是从对齐位置同步移动直到找到第一个公共节点,而不是根据sum值移动)。由于核心思路部分正确但存在明显逻辑错误,扣2分。
(2)得分及理由(满分8分)
得分:4分
理由:代码实现了部分正确逻辑:①正确计算链表长度;②正确让长链表先移动差值步。但存在以下严重逻辑错误:
1. while循环条件错误:在同步遍历时使用`q->next!=NULL && p->next!=NULL`,但没有在循环内移动指针,会导致死循环
2. sum计数逻辑错误:通过比较data值判断公共后缀不可靠,且sum被错误重置
3. 返回位置计算错误:最后根据sum值移动指针的逻辑完全错误
4. 函数返回类型应为指针类型
由于代码存在严重逻辑错误但实现了部分正确功能,给4分。
(3)得分及理由(满分1分)
得分:0分
理由:学生回答时间复杂度为O(n),但实际正确时间复杂度应为O(m+n)或O(max(m,n))。学生的答案与实现的算法复杂度不一致,且表述不准确,因此不得分。
题目总分:2+4+0=6分
登录后发布评论
暂无评论,来抢沙发