首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，an-1，an)。 设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求： 说明你所设计算法的时间复杂度与空间复杂度。
假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，an-1，an)。 设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求： 说明你所设计算法的时间复杂度与空间复杂度。
admin
2014-04-17
47
问题
假设有一带头结点的循环双链表表示的线性表L=(a
1
，a
2
，…，a
n-1
，a
n
)。
设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a
1
，a
3
，…，a
n
，…，a4，a
2
)。要求：
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
空间复杂度分析：除去链表本身的空间外，额外的空间消耗为O(1)。其实本题可以看成是原来链表的重新组合，并没有开辟新的空间。 时间复杂度分析：整个过程相当于把链表遍历了一遍，所以时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/JYxi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述第二国际建立的历史条件。
1971年9月美苏英法四国签署()，肯定了西柏林的占领制度，柏林问题得以解决。
下列事件发生最早的是()。
第二次世界大战后，世界形势变化的最大特点是()。
对三国鼎立到隋朝重新统一全国这段历史时期的政局，叙述正确的是()。①只有西晋有过短暂的统一②大多数时间是多个政权分立、南北对峙的复杂政局③西晋、北魏、东晋都有过短暂的统一④除三国分立以外，其他时间基本上处于统
巴黎公社采取的带有无产阶级专政性质的措施有()。①公社人员由民主选举产生②没收逃亡资本家的工厂，交给工人合作社管理③取消旧的国家机器，建立：亡人阶级自己的国家机构④工职人员年薪不得超过熟练工人的工资
东欧国家的私有化方式一般有四种，其中波兰采取的主要方式是()
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说，向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传，可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：写出图G的邻接矩阵A。
随机试题
迦梨陀娑的《沙恭达罗》中，沙恭达罗遭到了哪个重要人物的诅咒()
Timespentinabookshopcanbemostenjoyable,whetheryouareabook-loverormerelytheretobuyabookasapresent.Youmay
X线管焦点到成像介质的距离称为
HIV主要侵犯()
城市消防设施不包括()。
超高层建筑的建筑高度应大于()m。
按照国家统一的会计制度确认收入或利得的时点早于按照增值税制度确认增值税纳税义务发生时点的，应将相关销项税额计入的科目是()。
国家高技术研究发展计划是火炬计划。()
有人说：人的一生一定会出丑，你有何看法?结合自身谈谈你这一生中出的哪次丑让你记忆犹新。为什么?
A、Theirviewsonsoccerarechanging.B、Theirfamilymemberslikeotherteams.C、Theirinterestinsoccerisnotreal.D、Thetea
最新回复
(
0
)
