首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有一带头结点的循环双链表表示的线性表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
2017-11-20
44
问题
假设有一带头结点的循环双链表表示的线性表L=(a
1
，a
2
，…，a
n-1
，a
n
)。
设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a
1
，a
3
，…，a
n
，…，a
4
，a
2
)。要求：
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
空间复杂度分析：除去链表本身的空间外，额外的空间消耗为O(1)。其实本题可以看成是原来链表的重新组合，并没有开辟新的空间。 时间复杂度分析：整个过程相当于把链表遍历了一遍，所以时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/AVRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1988年6月，苏联共产党第十九次代表会议的主题是()。
明末清初，著名学者()抗清失败，前往日本讲学，传播中国文化。
西安事变后，经中共的努力和斗争，蒋介石被迫接受的条件是()。
中国共产党召开七届二中全会的主要目的是()。
下列哪些机构是唐朝设立的管理新疆地区的机构?()①伊犁将军②乌里雅苏台将军③北庭都护府④安西都护府
关于“一战”后构筑的凡尔赛体系，说法不正确的是()。
世界近代史上，世界经济发展经历了两次大的飞跃，即第一次工业革命和第二次工业革命。阅读下面两段材料，回答问题：材料一工业革命的主角——蒸汽机，是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产，主要依靠以人力和经
记载了用竿标日测影以求日高的方法，并认识了勾股定理的算书是()。
在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。
某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下：假定int类型数据用32位补码表示，程序
随机试题
(profound)Itisnotpossibletowriteapagewithoutexperiencingpositivepleasureattherichnessandvariety,theflexibilit
子痫发生抽搐后，应注意及早发现心衰、脑出血、肺水肿、HELLP综合征、肾衰竭、弥散性血管内凝血等并发症。()
痫证患者，发作时昏仆抽搐吐涎，或有叫吼，平日情绪急躁，心烦失眠，咯痰不爽，口苦而干，便秘，舌红苔黄腻，脉弦滑数。治法为
A．大黄根茎B．生大黄片C．酒大黄D．熟大黄E．大黄炭红棕色或黄棕色
患者，女，36岁，近半年来总是心烦意乱，坐卧不宁，似乎全世界的重担都压在她身上，明知是主观过虑却不能自控，难以安心工作，颇感苦恼而就诊。目前辅以药物治疗，护士告知她该药见效慢，服药后需耐心等待症状缓解，该药是
()是相对彻底分权的组织形式。
Word中________为文档提供了预定格式。
语言理解的最高水平是()。
下列关于命令DOFORMXXNAMEYYLINKED的陈述中，正确的是( )。
A、Becauseheisasuperman.B、Becausehecatchestheupdraftofaairventneartheground.C、BecauseheisprotectedbyGod.D、
最新回复
(
0
)
