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

admin2017-11-20 76

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

选项

答案空间复杂度分析：除去链表本身的空间外，额外的空间消耗为O(1)。其实本题可以看成是原来链表的重新组合，并没有开辟新的空间。时间复杂度分析：整个过程相当于把链表遍历了一遍，所以时间复杂度为O(n)。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/AVRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

东汉时期成书的崔定()主要是地主经营田庄的家历，但是，书中所记农业技术经验也很丰富，为后人所取法。

克里特文明的文字类型是()。

下列有关《布列斯特和约》的说法中，错误的一项是()。

“改土归流”政策的根本目的是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

下列关于第二三次科技革命的说法，不正确的是()。

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

五四运动后，马克思主义在中国广泛传播。1920年在上海出版了最早的《共产党宣言》中文全译本，译者是()

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

举例说明《史记》刻画人物性格的经典手法。

烧伤渗出期液体渗出的速度，一般以伤后多少小时内最快

化脓性脑膜炎和结核性脑膜炎的主要区别为

HDPE膜材料质量抽样检验样品应由()单位送到国家认证的专业机构检测。

关于操作风险的定性信息披露的内容是指()。

财政拨款结余是指单位取得的同级财政拨款项目支出结余资金的调整、结转和滚存情况。()(2016年改编)

汉明帝永平十二年(公元69年)，()率卒几十万修治黄河、汴渠，使黄泛地区广大土地重新得到耕种。

Doyouthinkthegirlgotherticket?

It’snosecretthatmanychildrenwouldbehealthierandhappierwithadoptiveparentsthanwiththeparentsthatnaturedealtt

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

计算机408

学硕统考专业

东汉时期成书的崔定()主要是地主经营田庄的家历，但是，书中所记农业技术经验也很丰富，为后人所取法。

克里特文明的文字类型是()。

下列有关《布列斯特和约》的说法中，错误的一项是()。

“改土归流”政策的根本目的是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

下列关于第二三次科技革命的说法，不正确的是()。

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

五四运动后，马克思主义在中国广泛传播。1920年在上海出版了最早的《共产党宣言》中文全译本，译者是()

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

举例说明《史记》刻画人物性格的经典手法。

烧伤渗出期液体渗出的速度，一般以伤后多少小时内最快

化脓性脑膜炎和结核性脑膜炎的主要区别为

HDPE膜材料质量抽样检验样品应由()单位送到国家认证的专业机构检测。

关于操作风险的定性信息披露的内容是指()。

财政拨款结余是指单位取得的同级财政拨款项目支出结余资金的调整、结转和滚存情况。()(2016年改编)

汉明帝永平十二年(公元69年)，()率卒几十万修治黄河、汴渠，使黄泛地区广大土地重新得到耕种。

Doyouthinkthegirlgotherticket?

It’snosecretthatmanychildrenwouldbehealthierandhappierwithadoptiveparentsthanwiththeparentsthatnaturedealtt

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