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

admin2017-04-28 71

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

荷马时代的社会管理制度和经济生活。

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

“法西斯”一词的最初含义是()。

秦始皇焚书时未被列入焚书范围的是()。

美国工业革命的有利条件包括()。①美国自然资源丰富②独立战争后，美国创立了资产阶级共和制度③地理位置优越，远离动乱的欧洲④拥有潜在的广阔的国内市场

在阿拉伯()统治时期，阿拉伯军队曾与当时中国的唐朝军队发生冲突。

巴黎和会召开的时间是()。

下列对1918年德国十一月革命说法不正确的是()。

加尔文教传播到法国后，其信仰者被称为()。

智力超常儿童是指智商超过__________的儿童。

患者，男性，27岁。因腰部受伤后伤口持续溢出淡红色液体，血压100／70mmHg，脉搏100次／分，出现休克症状。左上腹有压痛，但无肌紧张和反跳痛。目前应采取的处理是

多数情况下，饲料中最合适的钙磷关系是，磷是钙的

吐泻不止，吐泻物如米泔水，面色苍白，目眶凹陷，手足厥冷，汗出肢挛，舌淡苔白，脉沉微细为

建设期结束后，甲公司应偿还开发贷款本金和利息共()万元。甲公司向银行申请的贷款，其种类为()。

关于可行性研究报告深度要求的说法，错误的是()

中国古代的充军刑创设于()。

当前目录下有“工资表”文件，现要将“职称”为“特级教师”奖金增加50元，则语句为：UPDATE工资表______WHERE职称=“特级教师”

FrancehaskeptintimatelinkswithitsformerAfricanterritories.

A—limitedliabilityJ—unfaircompetitionB—businessscopeK—wholesalerC—commercialchannelsL—uncollectibleaccountD—bu

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

计算机408

学硕统考专业

荷马时代的社会管理制度和经济生活。

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

“法西斯”一词的最初含义是()。

秦始皇焚书时未被列入焚书范围的是()。

美国工业革命的有利条件包括()。①美国自然资源丰富②独立战争后，美国创立了资产阶级共和制度③地理位置优越，远离动乱的欧洲④拥有潜在的广阔的国内市场

在阿拉伯()统治时期，阿拉伯军队曾与当时中国的唐朝军队发生冲突。

巴黎和会召开的时间是()。

下列对1918年德国十一月革命说法不正确的是()。

加尔文教传播到法国后，其信仰者被称为()。

智力超常儿童是指智商超过__________的儿童。

患者，男性，27岁。因腰部受伤后伤口持续溢出淡红色液体，血压100／70mmHg，脉搏100次／分，出现休克症状。左上腹有压痛，但无肌紧张和反跳痛。目前应采取的处理是

多数情况下，饲料中最合适的钙磷关系是，磷是钙的

吐泻不止，吐泻物如米泔水，面色苍白，目眶凹陷，手足厥冷，汗出肢挛，舌淡苔白，脉沉微细为

建设期结束后，甲公司应偿还开发贷款本金和利息共()万元。甲公司向银行申请的贷款，其种类为()。

关于可行性研究报告深度要求的说法，错误的是()

中国古代的充军刑创设于()。

当前目录下有“工资表”文件，现要将“职称”为“特级教师”奖金增加50元，则语句为：UPDATE工资表______WHERE职称=“特级教师”

FrancehaskeptintimatelinkswithitsformerAfricanterritories.

A—limitedliabilityJ—unfaircompetitionB—businessscopeK—wholesalerC—commercialchannelsL—uncollectibleaccountD—bu

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