文章

131

粉丝

21

获赞

0

访问

5.2k

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

(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分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发