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

admin2017-04-28 75

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

1905年至1907年间，围绕中国究竟是采用革命手段还是改良方式这个问题，革命派与改良派进行论战的舆论阵地是()。

林则徐的反英国侵略的策略思想不包括()。

中古时代实行索贡巡行赋税征收方式的国家是()。

概述公元前8—前6世纪希腊海外殖民的背景、范围及影响。

在周初分封中，分封同姓诸侯国、异姓诸侯国，也分封圣王之后，下面属于圣王之后的封国为()。

1945年，联合国成立之时，创始会员国共有()个国家。

商朝号称青铜时代，下列叙述不符合当时的历史情况的是()

马克思说：巴黎公社“只不过是在特殊条件下的一个城市起义”。其含义是()。

提出电磁感应定律的是物理学家()。

下列属于慢性胃炎发病原因的有

不是大脑Willis环组成的是

芳香族氨基酸是

下列关于死刑复核程序的说法中，正确的有：

下列科目中，属于损益类的是()。

行政处分的适用对象只能是国家机关人员，不适用于社会团体中的工作人员。()

下列关于公司制期货交易所的说法正确的有()。

教育对学生成长的重要意义表现在()

A、 B、 C、 D、 D各图形的封闭区域数依次为1、1、2、2、3、(3)。

在个体身心发展的动力问题上，辩证唯物主义的观点是——，即内因和外因通过实践对个体身心发展起综合作用。

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

计算机408

学硕统考专业

1905年至1907年间，围绕中国究竟是采用革命手段还是改良方式这个问题，革命派与改良派进行论战的舆论阵地是()。

林则徐的反英国侵略的策略思想不包括()。

中古时代实行索贡巡行赋税征收方式的国家是()。

概述公元前8—前6世纪希腊海外殖民的背景、范围及影响。

在周初分封中，分封同姓诸侯国、异姓诸侯国，也分封圣王之后，下面属于圣王之后的封国为()。

1945年，联合国成立之时，创始会员国共有()个国家。

商朝号称青铜时代，下列叙述不符合当时的历史情况的是()

马克思说：巴黎公社“只不过是在特殊条件下的一个城市起义”。其含义是()。

提出电磁感应定律的是物理学家()。

下列属于慢性胃炎发病原因的有

不是大脑Willis环组成的是

芳香族氨基酸是

下列关于死刑复核程序的说法中，正确的有：

下列科目中，属于损益类的是()。

行政处分的适用对象只能是国家机关人员，不适用于社会团体中的工作人员。()

下列关于公司制期货交易所的说法正确的有()。

教育对学生成长的重要意义表现在()

A、 B、 C、 D、 D各图形的封闭区域数依次为1、1、2、2、3、(3)。

在个体身心发展的动力问题上，辩证唯物主义的观点是——，即内因和外因通过实践对个体身心发展起综合作用。

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