首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，aan—1，an)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求： 说明你所设计算法的时间复杂度与空间复杂度。
假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，aan—1，an)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求： 说明你所设计算法的时间复杂度与空间复杂度。
admin
2017-04-28
48
问题
假设有一带头结点的循环双链表表示的线性表L=(a
1
，a
2
，…，aa
n—1
，a
n
)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a
1
，a
3
，…，a
n
，…，a
4
，a
2
)。要求：
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
空间复杂度分析：除去链表本身的空间外，额外的空间消耗为O(1)。其实本题可以看成是原来链表的重新组合，并没有开辟新的空间。 时间复杂度分析：整个过程相当于把链表遍历了一遍，所以时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/wHRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
格拉古兄弟改革的内容和结果是什么?
开皇三年，隋文帝下令州县官吏根据户籍簿上登记的年龄，来核对本人体貌，以防诈老诈小逃避租役，是为()。
1907年召开的第二国际斯图加特代表大会上，争论最激烈的问题是()。
第二次世界大战给全人类的启示是()①维护世界和平是当代各国人民的共同任务②必须坚持反对霸权主义和强权政治③必须发展和壮大世界和平力量④必须建立国际政治经济新秩序
《齐民要求.序》中写道：“今采摭经传，爰及歌谣，洵之老成，验之行事，起自农耕，终于醯醢(酱醋)，资生之靡不毕书书；号日《齐民要术》……舍本逐末，贤哲所非……故商贾之事，阙而不录。”这段材料表明作者()。①采取古今资料的编撰原则②
近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。
毛泽东明确提出“中国革命斗争的胜利要靠中国同志了解中国情况”论断的著作是()。
阅读史料回答以下问题：天既哀大地生人之多艰，黑帝乃降精而救民患，为神明，为圣王，为万世作师，为万民作保，为大地教主。生于乱世，乃据乱世而立三世之法，而垂精太平。乃因其所生之国，而立三世之义，而注意于大地远近、大小若一之大一统。乃立元以统天，以天为
支持多道程序的操作系统，区别于其他操作系统的主要特征为()。
已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所
随机试题
慢性阻塞性肺疾病的预防不包括以下哪一点
下列关于浮动汇率说法错误的是()。
在某大型项目的招标中，甲公司欲和乙公司组成联合体进行投标，双方通过磋商基本达成合作意向，但在双方签订正式的联合体协议之前，丙公司以更为优惠的条件劝说甲公司放弃与乙公司的联合，甲公司转而与丙公司开始新的谈判磋商。但在招标文件规定的投标截止日前，丙公司由于排挤
根据证券投资基金法关于中国证监会行政许可事项的规定，下列事项中需要中国证监会核准的是()。
H啤酒成功地在一个拥有300万人口的C市收购了一家啤酒厂，不仅在该市取得了95%以上市场占有率的绝对垄断，而且在全省的市场占有率也达到了60%以上，成了该省啤酒业界名副其实的龙头老大。C市100公里内有一家雪花啤酒公司，3年前也是该省的老大。然而，
职业用语的基本要求是()。
数学教师：“二班学生一点不听话，我没得精力管那么多，不听课就算了，他讲他的，我讲我的。”语文教师：“二班学生要管得严，我上课他们就不敢闹，清风雅静的。”音乐教师：“我没得精神去骂他们，课实在是上不下来，我就找班主任来压阵。”接着，几位教师七嘴八舌地议论
如果某公司业绩较好，未来发展趋势被投资者普遍看好，现该公司决定增发新股，则该公司股票发行价格应采取以下哪种定价方式?()
8086 CPU执行一条指令需要几个时钟周期，Pentium CPU由于采用了______技术，在一个时钟周期中可以执行两条指令。
______isoneofthebestnaturalisticAmericannovels.
最新回复
(
0
)
