文章

282

粉丝

0

获赞

0

访问

47.7k

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


评分及理由

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

得分:4分

理由:学生的基本设计思想与标准答案一致。其思路为:先求两个链表的长度,计算长度差k,让长的链表先走k步,然后两个指针同步移动,直到指向同一结点,即为共同后缀的起始位置。该思想正确且清晰。

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

得分:6分

理由:算法整体思路正确,但存在一处逻辑错误。在第一个条件分支 if(La <= Lb) 中,当str1较短时,应该让指向较长链表str2的指针P2先走差值步,但学生代码中写的是 while(count--){ P2 = P2->next; },这是正确的。然而,在第二个条件分支 if(Lb < La) 中,当str2较短时,应该让指向较长链表str1的指针P1先走差值步,学生代码中写的是 while(count--){ P1 = P1->next; },这也是正确的。但问题在于,两个条件分支后的同步移动循环 while (P1!= P2) 是相同的,这会导致在第一个分支执行完后,如果P1和P2不相等,会进入第二个分支再次判断并可能执行,这是逻辑冗余,且如果两个链表长度相等,将不会进入任何一个分支,直接返回未初始化的P1(实际上P1和P2都指向第一个结点,但代码逻辑不清晰)。更严重的是,如果两个链表没有共同后缀,该代码可能陷入死循环或返回错误结果,因为未处理无共同后缀的情况(标准答案通过判断p->next!=NULL来避免)。此外,函数返回类型为PList(即LNode*),但返回的是找到的共同结点指针,这与题目要求的返回起始位置一致,可以接受。由于存在逻辑结构问题和未处理无共同后缀的边界情况,扣2分。

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

得分:1分

理由:学生回答时间复杂度为O(n),虽然表述不够精确(应为O(m+n)或O(len1+len2)),但考虑到其算法思想与标准答案一致,且O(n)在通常语境下可以表示线性复杂度,因此给满分。

题目总分:4+6+1=11分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发