计算机考研考生需要掌握计算机知识点的重难考点，形成完整的计算机知识体系。对于复习备考，大家应该抓住考点、得分点，以拿高分为主要目的。以下是学府考研网为大家整理的“2022计算机考研：每日一练（42）”的内容，希望对大家的考研复习有所帮助。

已知一个带有表头结点的单链表，结点结构为：

假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中 倒数第 k 个位置上的结点( k 为正整数)。若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只 返回 0。要求：

⑴ 描述算法的基本设计思想；

⑵ 描述算法的详细实现步骤；

⑶ 根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C++或Java 语言实现），关键之处请 给出简要注释。

解答：

（1）算法的基本设计思想（ 5 分）： 问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第 k  个结点的位置。算法的基

本设计思想是：定义两个指针变量 p 和 q，初始时均指向头结点的下一个结点（链表的第一个结点）。p 指针沿 链表移动；当 p 指针移动到第 k 个结点时，q 指针开始与 p 指针同步移动；当 p 指针移动到最后一个结点时，q 指针所指示结点为倒数第  k 个结点。以上过程对链表仅进行一遍扫描。

（2）算法的详细实现步骤（ 5 分）：

① count=0，p 和 q 指向链表表头结点的下一个结点；

② 若 p 为空，转⑤；

③ 若 count 等于 k，则 q 指向下一个结点；否则，count=count+1；

④ p 指向下一个结点，转②；

⑤ 若 count 等于 k，则查找成功，输出该结点的 data 域的值，返回 1；否则，说明 k 值超过了线性表的长 度，查找失败，返回 0；

⑥ 算法结束。

（3）算法实现（5  分）：

typedef int ElemType;       ∥链表数据的类型定义

typedef struct LNode{       ∥链表结点的结构定义

ElemType       data;         ∥结点数据

struct Lnode  *link;        ∥结点链接指针

} *LinkList;

int  Search_k(LinkList list, int k){

∥查找链表 list 倒数第 k 个结点，并输出该结点 data 域的值

LinkList p = list->link, q = list->link; ∥指针 p、q 指示第一个结点

int count = 0;

while(p != NULL){     ∥遍历链表直到最后一个结点

if(count < k) count++;     ∥计数，若 count < k 只移动 p else q = q->link; p =  p->link;                    ∥之后让 p、q 同步移动

} ∥while if(count < k)

return  0;    ∥查找失败返回 0

else { ∥否则打印并返回 1 printf(“%d”,q->data); return  1;

}

} ∥Search_k 提示：算法程序题，如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数，如果能 用

伪代码写出自然更好，比较复杂的地方可以直接用文字表达。 若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分 15  分；若采用两遍或多遍扫描才能得到

正确结果的，最高分 10 分。若采用递归算法得到正确结果的，最高给 10  分；若实现算法的空间复杂度过高（使用了大小与 k 有关的辅助数组），但结果正确，最高给 10 分。

以上便是学府考研为考生整理的“2022计算机考研：每日一练（42）”的相关内容，正确的考前复习方法能让备考事半功倍，在这里学府小编预祝各位考生考试顺利，梦想成真。更多计算机考研信息可查看计算机栏目！

推荐阅读：

2022计算机考研：这些关于计算机考研的常识你都应该清楚！

2022考研常识问答知识基础篇汇总

2022考研专业课如何高效的进行复习