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

admin2017-04-28 79

问题假设有一带头结点的循环双链表表示的线性表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

学硕统考专业

第一国际开展了哪些活动?其内部经历了哪些主要斗争?

在印度独立和巴勒斯坦建国问题上，英国扮演了什么角色?有什么影响?

()是一部上起传说中的黄帝，下迄汉武帝时期的中国通史，是中国历史上第一部内容完整、结构周密的历史著作。

关于希腊古风时代和古典时代的叙述不正确的是()。

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

在巴黎和会上获利最大的两个国家是()。

明成祖时期大力推崇理学，以国家力量编写了几部理学的大部头著作，下面不属于其中的是()。

下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。

1936年，张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成

2002年1月张某在其承包的土地上未经审批私自设立生活垃圾处理场，2007年12月该土地因到期而被收回，2010年5月该生活垃圾处理场被县城市管理综合行政执法局发现，该行政机关仍然可对张某进行处罚。（）

______________，一夫当关，万夫莫开。(李白《蜀道难》)

A、胃寒B、气滞C、食积D、胃气虚E、血瘀胃脘胀满疼痛，暖气酸腐，不欲食，证属

《纽约公约》某缔约国仲裁机构做出的仲裁裁决欲在我国得到承认与执行，下列说法正确的是：

无机结合料基层路拌法施工中关于接缝的处理，下列叙述中错误的是()。

设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为______。

PlaidFashionVocabularyandExpressionspreppyworstedyarnnerdcultureGaelicsuspender

Fortheemployee,beingplacedinapositionthatiscomfortableandmeetsexpectationswillmakethejoblessstressfulandall

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

计算机408

学硕统考专业

第一国际开展了哪些活动?其内部经历了哪些主要斗争?

在印度独立和巴勒斯坦建国问题上，英国扮演了什么角色?有什么影响?

()是一部上起传说中的黄帝，下迄汉武帝时期的中国通史，是中国历史上第一部内容完整、结构周密的历史著作。

关于希腊古风时代和古典时代的叙述不正确的是()。

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

在巴黎和会上获利最大的两个国家是()。

明成祖时期大力推崇理学，以国家力量编写了几部理学的大部头著作，下面不属于其中的是()。

下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。

1936年，张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成

2002年1月张某在其承包的土地上未经审批私自设立生活垃圾处理场，2007年12月该土地因到期而被收回，2010年5月该生活垃圾处理场被县城市管理综合行政执法局发现，该行政机关仍然可对张某进行处罚。（）

______________，一夫当关，万夫莫开。(李白《蜀道难》)

A、胃寒B、气滞C、食积D、胃气虚E、血瘀胃脘胀满疼痛，暖气酸腐，不欲食，证属

《纽约公约》某缔约国仲裁机构做出的仲裁裁决欲在我国得到承认与执行，下列说法正确的是：

无机结合料基层路拌法施工中关于接缝的处理，下列叙述中错误的是()。

设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为______。

PlaidFashionVocabularyandExpressionspreppyworstedyarnnerdcultureGaelicsuspender

Fortheemployee,beingplacedinapositionthatiscomfortableandmeetsexpectationswillmakethejoblessstressfulandall

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