文章

172

粉丝

0

获赞

0

访问

26.1k

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

1)同一个指针地址使一样的,所以停止的条件当str1==str2。而两个链表长度不同,他们相差n-m个指针位,所以可以先让长的那个单词的指针现象前n-m位。然后后面同时逐步向前,相等的时候就是后缀起始点。

2)

LNode findSuffix(LLink &A, LLink &B, int n, int m){
    LNode *k, *str1=A, *str2=B;
    if(n>m)
    for(int i=0;i<n-m;i++)    str1=str1->next;    //str1往前差额
    if(m>n)
    for(int i=0;i<m-n;i++)    str2=str2->next;    //str2往前差额
    while(str1!=str2){        //同时向后找相交处
        str1=str1->next;    
        str2=str2->next;
    }
    k = str1;                //返回k后缀起始点

    
    return k;
}

3)时间复杂度O(n)


评分及理由

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

得分:3分

理由:学生的基本设计思想正确,指出了需要先让长链表移动长度差值的步骤,然后同步遍历找到共同结点。但是描述不够精确,没有明确说明需要先计算链表长度,而是直接使用参数n和m(题目未提供),且没有提到需要从第一个公共结点开始比较。扣1分。

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

得分:5分

理由:

  • 代码基本实现了对齐后同步遍历的思想,逻辑大体正确
  • 但存在以下逻辑错误:
    • 函数参数中直接使用n和m(链表长度),但题目要求的是给定头结点str1和str2,没有提供长度参数,需要自行计算长度(-2分)
    • 循环移动指针时,应该是从当前结点开始移动,但学生代码中str1和str2初始指向头结点,移动后可能错过第一个公共结点(-1分)
    • 返回类型应该是LinkNode*,但函数声明为LNode,类型不一致
  • 代码缺少长度计算函数,无法独立运行

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发