假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，an-1，an)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求：说明你所设计算法的时间复杂度与空间复杂度。

admin2017-11-20 48

问题假设有一带头结点的循环双链表表示的线性表L=(a₁，a₂，…，a_n-1，a_n)。
设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a₁，a₃，…，a_n，…，a₄，a₂)。要求：
说明你所设计算法的时间复杂度与空间复杂度。

选项

答案空间复杂度分析：除去链表本身的空间外，额外的空间消耗为O(1)。其实本题可以看成是原来链表的重新组合，并没有开辟新的空间。时间复杂度分析：整个过程相当于把链表遍历了一遍，所以时间复杂度为O(n)。

解析

转载请注明原文地址:https://jikaoti.com/ti/tLfjFFFM

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，an-1，an)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求：说明你所设计算法的时间复杂度与空间复杂度。

计算机408

学硕统考专业

氏族公社形成的条件和基本标志是()。

下面哪项条约没有涉及德国的赔款问题?()

在捍卫和传播生物进化论方面做出了贡献的是()。

陈云在哪次会议上发表了《目前财政经济的情况和克服困难的若干办法》的重要讲话?()

我国生铁冶炼技术最早出现于()。

文艺复兴运动兴起的时间是()。

林则徐主持编译的《四洲志》，介绍了世界各国的史地。鸦片战争后，主要以《四洲志》为基础成书的重要著作是()

在罗斯福新政期间，美国政府在森林中修筑铁路，力图为美国青年人提供更多的工作机会。这种举措有利于()。①缓和阶级矛盾和安定社会秩序②扩大消费，刺激经济复苏③根除资本主义经济危机④消除资本主义社会的基本矛盾

对汇编语言程序员来说，以下部件中不透明的是()。I．指令缓冲器；Ⅱ．移位器；Ⅲ．通用寄存器；Ⅳ．中断字寄存器；V．乘法器；Ⅵ．先行进位链；

可以作为致畸试验阳性对照物的是

虎杖的功效是()

患者王先生，长期卧床自理困难，最近护理时发现骶尾皮肤发红，除去压力无法恢复原来肤色，据他的情况，你的处理方法最好是

关于司法职业，下列哪一选项是错误的？(2008—卷一—50，单)

下列关于抵押人、抵押权人的表述中，正确的是()。

在一般情况下，各筹资方式的资本成本由大到小依次为()。

Thatyoungmanhasmadesomuchnoisethathe______nothavebeenallowedattendtheconcert.

Toacquirethemethodofscientificinvestigation,one______.Inductiveanddeductivemethodsusedindailylifeandinscienc

Forthispart,youareallowed30minutestowriteashortessayentitledOnOutdoorExerciseinModernLifefollowingtheoutli

假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，an-1，an)。 设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求： 说明你所设计算法的时间复杂度与空间复杂度。

计算机408

学硕统考专业

氏族公社形成的条件和基本标志是()。

下面哪项条约没有涉及德国的赔款问题?()

在捍卫和传播生物进化论方面做出了贡献的是()。

陈云在哪次会议上发表了《目前财政经济的情况和克服困难的若干办法》的重要讲话?()

我国生铁冶炼技术最早出现于()。

文艺复兴运动兴起的时间是()。

林则徐主持编译的《四洲志》，介绍了世界各国的史地。鸦片战争后，主要以《四洲志》为基础成书的重要著作是()

在罗斯福新政期间，美国政府在森林中修筑铁路，力图为美国青年人提供更多的工作机会。这种举措有利于()。①缓和阶级矛盾和安定社会秩序②扩大消费，刺激经济复苏③根除资本主义经济危机④消除资本主义社会的基本矛盾

对汇编语言程序员来说，以下部件中不透明的是()。I．指令缓冲器；Ⅱ．移位器；Ⅲ．通用寄存器；Ⅳ．中断字寄存器；V．乘法器；Ⅵ．先行进位链；

可以作为致畸试验阳性对照物的是

虎杖的功效是()

患者王先生，长期卧床自理困难，最近护理时发现骶尾皮肤发红，除去压力无法恢复原来肤色，据他的情况，你的处理方法最好是

关于司法职业，下列哪一选项是错误的？(2008—卷一—50，单)

下列关于抵押人、抵押权人的表述中，正确的是()。

在一般情况下，各筹资方式的资本成本由大到小依次为()。

Thatyoungmanhasmadesomuchnoisethathe______nothavebeenallowedattendtheconcert.

Toacquirethemethodofscientificinvestigation,one______.Inductiveanddeductivemethodsusedindailylifeandinscienc

Forthispart,youareallowed30minutestowriteashortessayentitledOnOutdoorExerciseinModernLifefollowingtheoutli

假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，an-1，an)。设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求：说明你所设计算法的时间复杂度与空间复杂度。