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

admin2014-04-17 63

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

学硕统考专业

简述第二国际建立的历史条件。

下列各组条约的时间排列顺序正确的是()①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》

唐朝时，中国和非洲也有来往。下列有关这方面的证据中最具说服力的是()

俄国进行社会主义革命最基本、最主要的前提条件是()。

洋务运动时期，首批赴欧海军留学生派出的时间是()。

结合学界已有成果，评析李鸿章晚清外交活动。(北京大学2013年中国史真题)

隋朝建立了三省六部制，其中负责审议的部门是()。

曾在1978年5月10日《理论动态》上发表的《实践是检验真理的唯一标准》一文，以后又在《光明日报》、《人民日报》、《解放军报》转载，这篇文章的初稿作者是()。

隋朝大运河中哪一段河道的地理位置最接近于春秋时期即已开通过的运河()?

已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：写出图G的邻接矩阵A。

蒙古族的三大历史巨著是()。

造血微环境不包括

可在下列哪个部位记录到腓肠神经感觉电位(逆向法)

设备安装工程概算的编制方法主要有()。

深入：浅尝辄止

函数Mid(“计算机等级考试”，4，2)的执行结果是______。

Nowadays,oursocietyisbeingreshapedbyinformationtechnologies—computers,telecommunicationsnetworks,andotherdigitalsy

Ifyoulooktotheleft,youwillseeariverofgreat(wide)______.

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

计算机408

学硕统考专业

简述第二国际建立的历史条件。

下列各组条约的时间排列顺序正确的是()①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》

唐朝时，中国和非洲也有来往。下列有关这方面的证据中最具说服力的是()

俄国进行社会主义革命最基本、最主要的前提条件是()。

洋务运动时期，首批赴欧海军留学生派出的时间是()。

结合学界已有成果，评析李鸿章晚清外交活动。(北京大学2013年中国史真题)

隋朝建立了三省六部制，其中负责审议的部门是()。

曾在1978年5月10日《理论动态》上发表的《实践是检验真理的唯一标准》一文，以后又在《光明日报》、《人民日报》、《解放军报》转载，这篇文章的初稿作者是()。

隋朝大运河中哪一段河道的地理位置最接近于春秋时期即已开通过的运河()?

已知有6个顶点(顶点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：写出图G的邻接矩阵A。

蒙古族的三大历史巨著是()。

造血微环境不包括

可在下列哪个部位记录到腓肠神经感觉电位(逆向法)

设备安装工程概算的编制方法主要有()。

深入：浅尝辄止

函数Mid(“计算机等级考试”，4，2)的执行结果是______。

Nowadays,oursocietyisbeingreshapedbyinformationtechnologies—computers,telecommunicationsnetworks,andotherdigitalsy

Ifyoulooktotheleft,youwillseeariverofgreat(wide)______.

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