文章

79

粉丝

0

获赞

0

访问

3.4k

头像
2009年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年10月2日 17:15
阅读数 10

1)使用两个指针*p和*q,因为不知道链表长度,先将q向前移动k位,后面的p和q则同步每次向后移动一位结点。当q达到最后一个结点的时候,p指向的则是倒是第k个结点。

2)

1. 创建两个指针p和q,q用来先遍历,p用来指向倒数第k个。

2. 用循环先让q向前k步,如果q在走k步前就结束了,说明这个链表长度小于k,直接返回0表示失败。然后后面再一个循环,当q->link不为空的时候,p和q同时向后。

3. 当q->link为空,遍历结束。p指向的就是倒数第k个。取出那个结点的值并输出,返回1.

3)

int searchK(LList &list, int K){
    LNode *p=list->link, *q=list->link;
    
    for(int i = 0; i<k; i++){    //前进k步
        if(q) q=q->link;
        else return 0;
    }
    while(q){
        p=p->link;
        q=q->link;
    }
    printf("%d",p->data);
    return 1;

}

评分及理由

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

得分:5分

理由:学生的基本设计思想描述清晰准确,与标准答案一致。使用两个指针p和q,先让q向前移动k位,然后p和q同步移动,当q到达链表末尾时p指向倒数第k个结点。这是一趟扫描的高效算法。

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

得分:5分

理由:学生的详细实现步骤描述完整,包含了指针初始化、q先移动k步的循环、p和q同步移动的循环、边界条件判断等关键步骤,与标准答案思路一致。

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

得分:4分

理由:代码整体逻辑正确,但存在一个逻辑错误:在while循环中,当q为NULL时,p指向的实际上是倒数第k+1个结点,而不是倒数第k个结点。正确的做法应该是当q->link不为空时继续循环,或者调整指针初始位置。此外,代码中使用了"LList"类型,可能是识别错误,不扣分。

题目总分:5+5+4=14分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发