首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带有表头结点的单链表,结点结构为: 假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
已知一个带有表头结点的单链表,结点结构为: 假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
admin
2013-04-26
92
问题
已知一个带有表头结点的单链表,结点结构为:
假设该链表只给出了头指针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
学硕统考专业
相关试题推荐
下列内容,哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张,从经济上瓜分世界
关于前期罗马帝国时期的经济状况的叙述,不正确的是()。
提出行星绕太阳运行为椭圆形轨道的天文学家是()。
新中国建立后发生的一次全局性、长时间的严重“左”倾错误是()。
二战后的半个世纪中,资本主义各国经济史上的五个周期阶段。
巴黎公社采取的带有无产阶级专政性质的措施有()。①公社人员由民主选举产生②没收逃亡资本家的工厂,交给工人合作社管理③取消旧的国家机器,建立:亡人阶级自己的国家机构④工职人员年薪不得超过熟练工人的工资
在西北地区,西北野战军采取了蘑菇战术与敌人周旋,这实际上是()。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
某主机的MAC地址为00.15.C5.C1.5E.28,IP地址为10.2.128.100(私有地址)。题47-a图是网络拓扑,题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。
随机试题
翻译者将翻译成中文的量表再翻译回去的步骤是()
梗阻性肝病时,下列哪一项指标升高最明显
制作锤造冠代型时,在模型的基牙上通常采用加蜡的方法恢复其外形和邻接关系,不应加蜡的部位为
实施清创术的最佳时机应该是
混凝土工程中,要泵送混凝土的坍落度不低于( )。
下列会计分录中,不属于复合会计分录的有()。
由于企业销售政策的调整,会导致销售过程中出现某些不确定因素,但这些不确定因素并不影响企业确认收入。()
如果以上市公司作为可比企业对非上市公司进行价值评估时,应在直接按照可比企业标准所得出评估价值的基础上,加上一定金额的控制权价值,减去与上市成本比例相当的金额,调整后的余额才可作为非上市公司的评估价值。()
公安部于2003年1月22日发布的加强公安机关内部管理的“五条禁令”规定:严禁在工作时间饮酒,违者予以纪律处分;造成严重后果的,予以辞退或者开除。()
计算机网络的资源子网的主要组成单元是【 】。
最新回复
(
0
)