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

admin2014-04-17 41

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

学硕统考专业

下面条约没有涉及德国的赔款问题的是()。

下列关于胡司战争的叙述错误的一项是()。

从鸦片战争的过程和结局可以看出，()是决定战争胜败的关键。

上海机器织布局

西欧早期资产阶级反封建斗争以反天主教会的方式进行，主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

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

这个标志是何含义？

设函数z=xey，则=()

一男性病人，近3天来便后肛门外脱出一肿物，疼痛剧烈，排便、坐、走、咳嗽等均感疼痛而致坐卧不安。最可能的诊断是

药品检验机构出具虚假报告的有关处罚包括()

屈赞与曲玲协议离婚并约定婚生子屈曲由屈赞抚养，另口头约定曲玲按其能力给付抚养费并可随时探望屈曲。对此，下列哪些选项是正确的?(2016年卷三第65题)

人们在观察物体时，视线的移动对看清和看准物体有一定影响。一般来说，眼睛的水平运动速度比垂直运动速度()；视线运动的顺序习惯于从左到右、从上到下、()。

下面属于产业组织创新间接影响的是(　　)。

下列有关审计证据质量的说法中，错误的是()。

WhilewesterngovernmentsworryoverthethreatofEbola,amorepervasivebutfarlessharmful【C1】______isspreadingthrought

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

计算机408

学硕统考专业

下面条约没有涉及德国的赔款问题的是()。

下列关于胡司战争的叙述错误的一项是()。

从鸦片战争的过程和结局可以看出，()是决定战争胜败的关键。

上海机器织布局

西欧早期资产阶级反封建斗争以反天主教会的方式进行，主要原因是()①天主教会是最有势力的封建主集团②天主教会是封建的精神工具③天主教会日益腐败④近代自然科学的兴起

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

在请求页式系统中，一程序的页面走向(访问串或引用串)为2，3，4，5，2，3，6，2，3，4，5，6，设分配给该程序的存储块数为m。试分别计算m=3和m=4时，FIFO和LRU两种替换算法的缺页(页故障)数，并给出：结果说明了什么?

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

这个标志是何含义？

设函数z=xey，则=()

一男性病人，近3天来便后肛门外脱出一肿物，疼痛剧烈，排便、坐、走、咳嗽等均感疼痛而致坐卧不安。最可能的诊断是

药品检验机构出具虚假报告的有关处罚包括()

屈赞与曲玲协议离婚并约定婚生子屈曲由屈赞抚养，另口头约定曲玲按其能力给付抚养费并可随时探望屈曲。对此，下列哪些选项是正确的?(2016年卷三第65题)

人们在观察物体时，视线的移动对看清和看准物体有一定影响。一般来说，眼睛的水平运动速度比垂直运动速度()；视线运动的顺序习惯于从左到右、从上到下、()。

下面属于产业组织创新间接影响的是( )。

下列有关审计证据质量的说法中，错误的是()。

WhilewesterngovernmentsworryoverthethreatofEbola,amorepervasivebutfarlessharmful【C1】______isspreadingthrought

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

下面属于产业组织创新间接影响的是(　　)。