文章

122

粉丝

1

获赞

100

访问

29.9k

头像
2009年(408)计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年11月8日 17:40
阅读数 63

表头结点不记录为链表总长度,先用一个变量保存链表长度,通过遍历链表获得链表长度,再返回倒数第 k 个位置上结点,即查找链表长度 -k +1 的结点。查找成功返回 1,否则返回 0。

typedef struct Node{
    int data;
    struct Node* next;
}Node, *LinkList;

int func(LinkList list, int k){
    if(list == null) return 0;
    Node *p = list->next;//指向头结点下一个结点
    int length = 0;//存储链表长度
    while (p != null){ //判断当前指针是否为空
        p = p->next;
        length++;//链表长度加1
    }
    int i = 0; //做为与length -k +1比较的变量
    p = list; //将p指针重新指向头结点
    while (p != null && i < length -k +1){//当i=length -k +1退出循环
        p = p->next;
        i++;
    }
    printf("输出查找结果%d", p->data);
}

 


评分及理由

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

得分:2分

理由:学生描述的基本设计思想是通过遍历链表获取长度,再计算倒数第k个节点的位置进行查找。这种方法思路正确,但需要两遍扫描链表,不符合题目要求的"尽可能高效的算法"(标准答案采用一遍扫描)。虽然思想可行,但效率较低,因此扣3分。

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

得分:2分

理由:学生给出了详细的实现步骤,包括计算链表长度和定位目标节点两个主要步骤。步骤描述基本清晰,但同样因为需要两遍扫描而效率不高,且没有考虑边界情况(如k值过大),因此扣3分。

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

得分:2分

理由:代码实现基本正确,但存在以下问题:
1. 当k值大于链表长度时,第二个循环中p可能为null,访问p->data会导致运行时错误
2. 函数...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发