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

admin2017-11-20 60

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

学硕统考专业

以下内容不属于中国共产党为解决中西部落后问题，巩固发展国防事业而采取的三线建设的是()。

魏晋南北朝的手工业技术有所进步，下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料

以下关于阿兹特克文化的叙述，不正确的是()。

中华人民共和国恢复在联合国合法席位的时间是()。

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

下列有关西欧封建社会的表述，错误的一项是()。

一个C语言程序在一台32位机器卜运行。程序中定义了三个变量x、y和z，其中x和z为int型，y为short型。当x=127，y=一9时，执行赋值语句z=x+y后，x、y和z的值分别是____。

某计算机采用虚拟页式存储技术，系统为每一个进程提供65536B的地址空间，页面大小为4096B，某一个进程的代码段有32768B，数据段16396B，堆栈段在进程创建时为1024B，运行中最大会增长到15284B。那么，对这个进程正确的描述是()。

强调心理发展连续性的学者更倾向于将发展看作一个质变的过程。()

下列T型管的护理，哪些正确()

男性，50岁，因急性心急肌梗死一周就诊，冠脉造影示前降支近端完全闭塞，右冠状动脉80%狭窄，室壁瘤形成

确定药物归经理论的依据是

下面关于股票性质描述错误的是()。

设η1，η2，η3为3个n维向量，已知n元齐次方程组AX＝0的每个解都可以用η1，η2，η3线性表示，并且r(A)＝n－3，证明η1，η2，η3为AX＝0的一个基础解系．

Whata(self)______boyyouare;lettheotherchildrenshareyourtoys.

A、Becausethereplanesflyhigherthanattheequator.B、Becausetheretheeyescanreachabout4,000metres.C、Becausetherepl

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

计算机408

学硕统考专业

以下内容不属于中国共产党为解决中西部落后问题，巩固发展国防事业而采取的三线建设的是()。

魏晋南北朝的手工业技术有所进步，下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料

以下关于阿兹特克文化的叙述，不正确的是()。

中华人民共和国恢复在联合国合法席位的时间是()。

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

下列有关西欧封建社会的表述，错误的一项是()。

一个C语言程序在一台32位机器卜运行。程序中定义了三个变量x、y和z，其中x和z为int型，y为short型。当x=127，y=一9时，执行赋值语句z=x+y后，x、y和z的值分别是____。

强调心理发展连续性的学者更倾向于将发展看作一个质变的过程。()

下列T型管的护理，哪些正确()

男性，50岁，因急性心急肌梗死一周就诊，冠脉造影示前降支近端完全闭塞，右冠状动脉80%狭窄，室壁瘤形成

确定药物归经理论的依据是

下面关于股票性质描述错误的是()。

设η1，η2，η3为3个n维向量，已知n元齐次方程组AX＝0的每个解都可以用η1，η2，η3线性表示，并且r(A)＝n－3，证明η1，η2，η3为AX＝0的一个基础解系．

Whata(self)______boyyouare;lettheotherchildrenshareyourtoys.

A、Becausethereplanesflyhigherthanattheequator.B、Becausetheretheeyescanreachabout4,000metres.C、Becausetherepl

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