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

admin2017-11-20 79

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

学硕统考专业

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

下列关于清朝军机处的叙述，不正确的是()。

1856年首创转炉炼钢新技术的是()。

在巴黎和会上，法国要求严厉制裁德国的目的是()。

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争，这一古老文件是（）。

三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

linkNODE(intitem，link1，linkr){lnikt=malloc(sizeof*t)；t-＞item=item；t-＞1=1；t-＞r=r；returnt；}lin

主要犯罪地

试述在货币供给中银行的主渠道作用。

A、与抑制幽门螺杆菌有关B、与抑制免疫过程的许多环节有关C、与促进黏液和HCO3-分泌，增强黏膜屏障有关D、与阻断胃壁细胞H2受体有关E、与增加抗体形成有关米索前列醇的抗消化性溃疡作用

A．百会B．大椎C．哑门D．至阳E．上星善于治疗暴喑、舌强不语的腧穴是

某地调查中小学生近视患病情况，抽查小学生400名，近视患者105名，抽查中学生340名，近视患者60名。欲研究中、小学近视患病率有无区别，应选用

下列各项中，符合房产税法有关规定的有()。(2009年)

A、B、C、5D、B原数列各项可改写为分母为6，分子依次是1，2，3，4的平方，所以所求为。

GlobalWarmingSmokeiscloudingourviewofglobalwarming,protectingtheplanetfromperhapsthree-quartersofthegre

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

计算机408

学硕统考专业

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

下列关于清朝军机处的叙述，不正确的是()。

1856年首创转炉炼钢新技术的是()。

在巴黎和会上，法国要求严厉制裁德国的目的是()。

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争，这一古老文件是（）。

三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev

linkNODE(intitem，link1，linkr){lnikt=malloc(sizeof*t)；t-＞item=item；t-＞1=1；t-＞r=r；returnt；}lin

主要犯罪地

试述在货币供给中银行的主渠道作用。

A、与抑制幽门螺杆菌有关B、与抑制免疫过程的许多环节有关C、与促进黏液和HCO3-分泌，增强黏膜屏障有关D、与阻断胃壁细胞H2受体有关E、与增加抗体形成有关米索前列醇的抗消化性溃疡作用

A．百会B．大椎C．哑门D．至阳E．上星善于治疗暴喑、舌强不语的腧穴是

某地调查中小学生近视患病情况，抽查小学生400名，近视患者105名，抽查中学生340名，近视患者60名。欲研究中、小学近视患病率有无区别，应选用

下列各项中，符合房产税法有关规定的有()。(2009年)

A、B、C、5D、B原数列各项可改写为分母为6，分子依次是1，2，3，4的平方，所以所求为。

GlobalWarmingSmokeiscloudingourviewofglobalwarming,protectingtheplanetfromperhapsthree-quartersofthegre

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