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

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

admin2013-04-26  100
问题 已知一个带有表头结点的单链表，结点结构为：

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：
根据设计思想和实现步骤，采用程序设计语言描述算法(使用c、c++或Java语言实现)，关键之处请给出简要注释。
选项
答案算法实现： 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分。
转载请注明原文地址:https://www.kaotiyun.com/show/jwxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)