【正确答案】正确答案：算法的基本设计思想： 问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k个结点的位置。算法的基本设计思想：定义两个指针变量p和q。初始时均指向头结点的下一个结点(链表的第一个结点)。p指针沿链表移动，当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。

【正确答案】正确答案：算法的详细实现步骤：①count=0，p和q指向链表表头结点的下一个结点：②若p为空，转⑤；③若count等于k，则q指向下一个结点：否则，count=count+1；④p指向下一个结点，转②；⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，说明k值超过了线性表的长度，查找失败，返回0；⑥算法结束。

【正确答案】正确答案：算法实现： typedef int ElemType ; ／／链表数据的类型定义 typedef struct LNode{ ／／链表结点的结构定义 ElemType data， ／／结点数据 struct Lnode*link; ／／结点链接指针 } *LinkList； int Search—k(LinkList list，int k){ ／／查找链表list倒数第k个结点，并输出该结点data域的值 LinkList p=lis七一>link，q=list一>link， ／／指针p、q指示第一个结点 int COunt=O； while(p!=NULL){ ／／遍历链表直到最后一个结点 if(COUntlink;p=p一>link； ／／之后让p、q同步移动 )／／while if(COUntdata); return 1； } }／／Search—k

【答案解析】解析：算法程序题，如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分15分；若采用两遍或多遍扫描才能得到正确结果的，最高给10分：若采用递归算法得到正确结果的，最高给10分：若实现算法的空间复杂度过高(使用了大小与k有关的辅助数组)，但结果正确，最高给10分。