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

admin2014-04-17 34

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

论述印度非暴力运动的过程和失败原因。

在下列各项中，哪些属于苏俄实行“新经济政策”的前提条件?()。①有巩固的工农联盟②国家掌握了一切经济命脉③国民经济已明显恢复④帝国主义武装干涉已被粉碎

关于“尊王攘夷”运动，不正确的说法是()。

《凡尔赛和约》中，战胜国以何种方式处置德国的全部海外殖民地?()。

最早测量子午线的长度，并主持修订了当时最先进历法《大衍历》的是僧人()。

刘向子刘歆继承父业，完成了这一工作，并且写出了()一书，是我国第一部目录书。

1916年研究短波无线电通信，为现代远距离无线电通信奠定了基础的发明家是()。

1543年发表解剖学专著《人体结构论》的是()。

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争。这一古老文件是()

患者，男，64岁。近一月来寒热持续不解，恶寒较甚，发热无汗，身楚倦怠，咳嗽，咳痰无力，舌淡苔白，脉浮无力。治疗方剂宜首选()

乳腺癌的共同声像图特点是

某工程单代号网络图如图2-1所示，说法正确的是()。

采用工料单价法编制施工图预算时，措施费应在()时计算。

下列各项中，属于城镇土地使用税特点的有()。

以下功能是金融市场的宏观经济功能的是()。

政策性金融机构特有的职能包括()。

下列关于一人有限责任公司的表述中，不符合《公司法》对其所作特别规定的是()。

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

计算机408

学硕统考专业

论述印度非暴力运动的过程和失败原因。

在下列各项中，哪些属于苏俄实行“新经济政策”的前提条件?()。①有巩固的工农联盟②国家掌握了一切经济命脉③国民经济已明显恢复④帝国主义武装干涉已被粉碎

关于“尊王攘夷”运动，不正确的说法是()。

《凡尔赛和约》中，战胜国以何种方式处置德国的全部海外殖民地?()。

最早测量子午线的长度，并主持修订了当时最先进历法《大衍历》的是僧人()。

刘向子刘歆继承父业，完成了这一工作，并且写出了()一书，是我国第一部目录书。

1916年研究短波无线电通信，为现代远距离无线电通信奠定了基础的发明家是()。

1543年发表解剖学专著《人体结构论》的是()。

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争。这一古老文件是()

患者，男，64岁。近一月来寒热持续不解，恶寒较甚，发热无汗，身楚倦怠，咳嗽，咳痰无力，舌淡苔白，脉浮无力。治疗方剂宜首选()

乳腺癌的共同声像图特点是

某工程单代号网络图如图2-1所示，说法正确的是()。

采用工料单价法编制施工图预算时，措施费应在()时计算。

下列各项中，属于城镇土地使用税特点的有()。

以下功能是金融市场的宏观经济功能的是()。

政策性金融机构特有的职能包括()。

下列关于一人有限责任公司的表述中，不符合《公司法》对其所作特别规定的是()。

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