首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带有表头结点的单链表,结点结构为: 假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
已知一个带有表头结点的单链表,结点结构为: 假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
admin
2013-04-26
77
问题
已知一个带有表头结点的单链表,结点结构为:
假设该链表只给出了头指针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
学硕统考专业
相关试题推荐
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
科学技术革命包括三个既有联系又有区别的过程,下列不属于三个过程的是()。
根据《国际联盟盟约》的内容分析其实质。
从1939年春天起,国共双方军队在驻防结合部的摩擦冲突不断升级,不是这一时期惨案的是()
关于荷马时代的叙述,不正确的是()。
欧洲历史上第一部系统完备的法典是()。
花剌子密不是()。
东欧国家的私有化方式一般有四种,其中波兰采取的主要方式是()
分页存储管理中,页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间),会给页表的设计带来什么样的新问题?请给出一种解决方法,分析它的优点和缺点。
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
随机试题
某市公安局经市规划局批准,在居民区旁盖一栋高大的办公楼,由于距离过近,致使大批居民的住宅无法采光。于是居民将城市规划局诉至法院。法院经审查认为规划局的批准行为违法。此时法院应如何处理()。
患者,男,62岁,以“咳嗽、咳痰、胸闷、呼吸困难”为主诉就医,问诊“有吸烟史30年,2年前从水泥厂退休”。肺功能检查FEV1占预计值35%。诊断为慢性阻塞性肺疾病。针对该患者,治疗方案应选择
customsclearance
Onceuponatimeapoorfarmertakingasackofwheattothemill.Hedidnotknow【56】todowhenitslippedfromhishorseandf
不能用于治疗支气管哮喘发作的药物是
中国公民程某2014年1~12月份每月工资5000元,12月份除当月工资以外,还取得全年一次性奖金60000元。程某2014年年终奖金应缴纳个人所得税()元。
选择和运用教学方法的依据有哪些?
我国×省人大常委会制定了《×省食品卫生管理条例》。对此,下列说法错误的是()
Iwon’tbelieveyou______Iseeitwithmyowneyes.
A、Theywerepossiblycausedbyman.B、Theyweremostlycausedbyvolcanoes.C、Theywerecertainlycausedbynature.D、Weknowno
最新回复
(
0
)