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

admin2014-04-17 48

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

分析近代西欧在世界产生重大影响的优势。(江西师范大学2013年世界通史真题)

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

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

曹操统一北方的关键战役是()。

1925年10月签订《洛迦诺公约》后，法国外长白里安认为：“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。

表明第一次国共合作全面破裂的事件是()。

刘向子刘歆继承父业，完成了这一工作，并且写出了()一书，是我国第一部目录书。

与前两次工业革命相比，第三次科技革命在能源结构上的主要变化是()

改革开放以后，我国农村产业结构巨大的转变表现在()。

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数。(2)画出散列表。(

Someyearsagoindustrieshadmorefreedomthantheyhavenow,andtheydidnotneedtobeascarefulastheymusttoday.Theyd

腱反射和肌紧张的共同点是

多数国家实行的政府采购模式是()。

根据增值税法律制度的规定，下列各项中，不属于视同销售货物行为的是()。

基金监管职责分工的总体要求不包括()。

某家庭购买了一套价格为39万元的住宅，首期付款为房价的30％，余款向银行贷款，贷款期限为10年，贷款年利率为5％，按月等额还款。如果该家庭收入的25％用于还款，则该家庭月收入至少为()元，才能购买上述住宅。

下列关于C++预定义流对象的叙述中，正确的是()。

Christinewasrecentlydiggingthrougholdboxesinherstoreroompreparingtomovetoanewhouse.Inonebox,shecameacross

InsomepartsofLondon,missingabusmeans______foranotherhour.

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

计算机408

学硕统考专业

分析近代西欧在世界产生重大影响的优势。(江西师范大学2013年世界通史真题)

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

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

曹操统一北方的关键战役是()。

1925年10月签订《洛迦诺公约》后，法国外长白里安认为：“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。

表明第一次国共合作全面破裂的事件是()。

刘向子刘歆继承父业，完成了这一工作，并且写出了()一书，是我国第一部目录书。

与前两次工业革命相比，第三次科技革命在能源结构上的主要变化是()

改革开放以后，我国农村产业结构巨大的转变表现在()。

已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子a=0．75，散列函数的形式为H(K)=KMODP，回答下列问题：(1)构造散列函数。(2)画出散列表。(

Someyearsagoindustrieshadmorefreedomthantheyhavenow,andtheydidnotneedtobeascarefulastheymusttoday.Theyd

腱反射和肌紧张的共同点是

多数国家实行的政府采购模式是()。

根据增值税法律制度的规定，下列各项中，不属于视同销售货物行为的是()。

基金监管职责分工的总体要求不包括()。

某家庭购买了一套价格为39万元的住宅，首期付款为房价的30％，余款向银行贷款，贷款期限为10年，贷款年利率为5％，按月等额还款。如果该家庭收入的25％用于还款，则该家庭月收入至少为()元，才能购买上述住宅。

下列关于C++预定义流对象的叙述中，正确的是()。

Christinewasrecentlydiggingthrougholdboxesinherstoreroompreparingtomovetoanewhouse.Inonebox,shecameacross

InsomepartsofLondon,missingabusmeans______foranotherhour.

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