首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带有表头结点的单链表,结点结构为: 假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
已知一个带有表头结点的单链表,结点结构为: 假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
admin
2013-04-26
56
问题
已知一个带有表头结点的单链表,结点结构为:
假设该链表只给出了头指针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(COUnt
link;p=p一>link; //之后让p、q同步移动 )//while if(COUnt
data); return 1; } }//Search—k
解析
算法程序题,如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数,如果能用伪代码写出自然更好,比较复杂的地方可以直接用文字表达。若所给出的算法采用一遍扫描方式就能得到正确结果,可给满分15分;若采用两遍或多遍扫描才能得到正确结果的,最高给10分:若采用递归算法得到正确结果的,最高给10分:若实现算法的空间复杂度过高(使用了大小与k有关的辅助数组),但结果正确,最高给10分。
转载请注明原文地址:https://kaotiyun.com/show/jwxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
德国法西斯能够通过合法方式夺取政权,主要原因有()。①垄断资产阶级要求建立极权统治②纳粹党利用了人民对现状的不满③骗人的宣传欺骗了社会的信任④通过国会纵火案打击了共产党
第一次鸦片战争中英国侵略中国的路线是()。
文艺复兴运动兴起的时间是()。
新中国建立后发生的一次全局性、长时间的严重“左”倾错误是()。
简评斯大林《苏联社会主义经济问题》。
分析第二次工业革命的特点及历史影响。
阅读下列材料,回答问题:材料一:我们与希特勒或他们的匪帮永不会谈,永不斡旋,我们将在陆地上、海洋上、天空中与他们作战。直到把笼罩阴云于大地的一切敌人消灭为止……任何为反对纳粹主义而战斗的国家或人民,我们都支援。任何与希特勒为伍的人或国家都是我们的敌人。我
1854年,英国外交大臣致函英国驻华公使说:“为了适应外商对农业产品已增加了的需要,新的贸易市场尚待开辟。”1856年,法国外长则指令法国驻华代办强调“商业关系的推广”,并强调“这是一个关系到至高无上权益的问题”。这说明()。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
在下列查找的方法中,平均查找长度与结点个数n无关的查找方法是()。
随机试题
急性尿路感染的治疗关键在于
甲是某搬运场司机,在搬运场驾车作业时违反操作规程,不慎将另一职工轧死。对甲的行为应当如何处理?()(2005/2/20)
We______soasnottowaketheroommates.
下列哪项属于湿淫证的致病特点
桩冠长度至少应为根长的A.1/3~1/2B.1/2~2/3C.2/3~3/4D.1/3E.1/2
患者男性,57岁,患痹证5年余,经久不愈,肢体关节疼痛,屈伸不利,关节肿大、僵硬、变形,甚则肌肉萎缩,筋脉拘急,肘膝不得伸,舌质暗红,脉细涩。瘀血征明显者,可加用
下列关于诉的分类的说法正确的是:()
中国人民银行可以建议国务院银行业监督管理机构对银行业金融机构进行检查监督,后应当在收到建议之日起()内予以回复。
某市水务公司和甲单位同在A行开户,本月甲单位向水务公司支付水费50万元,另甲单位由于资金困难,向A银行申请贷款100万元,期限为6个月,银行经审无误办理,后因种种原因甲单位该笔贷款不能按期归还,需要办理展期手续。根据以上资料,回答下列问题:该客户支付5
Thefollowingparagraphsaregiveninawrongorder.ForQuestions41-45,youarerequiredtoreorganizetheseparagraphsintoa
最新回复
(
0
)