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

admin2014-04-17 25

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

学硕统考专业

从1939年春天起，国共双方军队在驻防结合部的摩擦冲突不断升级，不是这一时期惨案的是()

英国发动鸦片战争的主要目的是()。

第二次世界大战后，世界形势变化的最大特点是()。

唐代府兵的基本单位是()。

()的设置是清王朝实行满汉联合、以汉制汉统治方式在军事上的具体体现

1901—1939年间美国历届政府在国内经济活动中职能作用的演变。

关于美国内战，不正确的说法是()。

著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的，密谋发动()。

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

下述哪种物质与吞噬细胞对细菌的杀伤降解无直接关系

与强迫停立位有关的是

膈的主动脉裂孔位置在

预研究氧氟沙星治疗细菌性感染的效果进行一临床试验，人选研究对象228人，全部完成试验，其中180人治愈，30人有效，15人好转，3人无效。有效率为

患者，男性，74岁。因儿子打官司而担忧渐出现夜眠差，情绪低落，悲观厌世，总担心打官司的事情，患者自觉很痛苦，生活缺乏主动性。该患者的主要护理问题

甲用10万元假币冒充真币送给国家工作人员乙，甲走后，乙立即发现了收受的是假币，但乙之后陆陆续续使用该笔假币购物。关于本案，下列说法正确的是?

()是指借款人的还款能力出现明显的问题，依靠其正常经营收入已无法保证足额偿还本息，即使执行担保，也可能会造成一定损失。

下列规定“国家培养青年、少年、儿童在品德、智力、体质等方面全面发展”内容的是()。

()是数学教学评价的本体功能，它对数学教学起着潜在的制约作用．

下列诗(词)句与抒情话语的修辞方式，对应恰当的一项是()。

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

计算机408

学硕统考专业

从1939年春天起，国共双方军队在驻防结合部的摩擦冲突不断升级，不是这一时期惨案的是()

英国发动鸦片战争的主要目的是()。

第二次世界大战后，世界形势变化的最大特点是()。

唐代府兵的基本单位是()。

()的设置是清王朝实行满汉联合、以汉制汉统治方式在军事上的具体体现

1901—1939年间美国历届政府在国内经济活动中职能作用的演变。

关于美国内战，不正确的说法是()。

著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的，密谋发动()。

(1)页面长度为1KB=210B，因此页内偏移地址占10位。主存大小为16KB=214B，所以物理地址占14位。0AC5H=0000101011000101B，除去后10位，得到页号为2，则查找页表可知物理块号为4，所以物理地址是0100101100

下述哪种物质与吞噬细胞对细菌的杀伤降解无直接关系

与强迫停立位有关的是

膈的主动脉裂孔位置在

预研究氧氟沙星治疗细菌性感染的效果进行一临床试验，人选研究对象228人，全部完成试验，其中180人治愈，30人有效，15人好转，3人无效。有效率为

患者，男性，74岁。因儿子打官司而担忧渐出现夜眠差，情绪低落，悲观厌世，总担心打官司的事情，患者自觉很痛苦，生活缺乏主动性。该患者的主要护理问题

甲用10万元假币冒充真币送给国家工作人员乙，甲走后，乙立即发现了收受的是假币，但乙之后陆陆续续使用该笔假币购物。关于本案，下列说法正确的是?

()是指借款人的还款能力出现明显的问题，依靠其正常经营收入已无法保证足额偿还本息，即使执行担保，也可能会造成一定损失。

下列规定“国家培养青年、少年、儿童在品德、智力、体质等方面全面发展”内容的是()。

()是数学教学评价的本体功能，它对数学教学起着潜在的制约作用．

下列诗(词)句与抒情话语的修辞方式，对应恰当的一项是()。

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