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

admin2017-11-20 39

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

选项

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

解析

转载请注明原文地址:https://kaotiyun.com/show/AVRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

近代英国思想家洛克的代表作是

1946年5月，中共中央发布的实现“耕者有其田”政策的重要文件是()。

下列关于湘军的叙述中不正确的是()。

胡适与李大钊进行“问题与主义之争”的主战场是()。

近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。

周人重视婚姻，对婚礼尤为讲究。周代的婚礼有六项程序，即：①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()

论述古王国君主专制的表现。

两汉时期，下列没有通过丝绸之路传入西方的技术是()。

在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()

在对热敏性混合液进行精馏时必须采用加压分离。

经营者提供商品或者服务有欺诈行为的,应当按照消费者的要求增加赔偿其受到的损失,增加赔偿的金额为消费者购买商品的价款或接受服务的费用的一倍。()

胃溃疡行毕Ⅱ氏胃大部切除术后5天，出现上腹膨胀感和呕吐，呕吐物含大量胆汁。可能的原因是

血液病患者继发感染最常见的病原体是

中医诊断的基本原则是

按CFR术语成交，卖方承担的义务有()。

年度总额内的个人结汇和境内个人购汇，凭()在银行办理。

咀嚼有哪些作用？幼儿园为什么不宜举行吃饭速度的比赛？

采用扩展关系数据模型的方法建立的数据库系统，称作______。

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

计算机408

学硕统考专业

近代英国思想家洛克的代表作是

1946年5月，中共中央发布的实现“耕者有其田”政策的重要文件是()。

下列关于湘军的叙述中不正确的是()。

胡适与李大钊进行“问题与主义之争”的主战场是()。

近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。

周人重视婚姻，对婚礼尤为讲究。周代的婚礼有六项程序，即：①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()

论述古王国君主专制的表现。

两汉时期，下列没有通过丝绸之路传入西方的技术是()。

在下面哪本著作中以异化劳动理论的形式阐述了一种新的科学世界观的雏形?()

在对热敏性混合液进行精馏时必须采用加压分离。

经营者提供商品或者服务有欺诈行为的,应当按照消费者的要求增加赔偿其受到的损失,增加赔偿的金额为消费者购买商品的价款或接受服务的费用的一倍。()

胃溃疡行毕Ⅱ氏胃大部切除术后5天，出现上腹膨胀感和呕吐，呕吐物含大量胆汁。可能的原因是

血液病患者继发感染最常见的病原体是

中医诊断的基本原则是

按CFR术语成交，卖方承担的义务有()。

年度总额内的个人结汇和境内个人购汇，凭()在银行办理。

咀嚼有哪些作用？幼儿园为什么不宜举行吃饭速度的比赛？

采用扩展关系数据模型的方法建立的数据库系统，称作______。

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