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

admin2014-04-17 42

问题假设有一带头结点的循环双链表表示的线性表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年8月23日，苏德双方签了()和《秘密附属议定书》，划定了双方在东欧的势力范围。这一条约使德国得以进攻波兰，使第二次世界大战终于爆发。

(北魏孝文帝)“初谋南迁，恐众心恋旧，乃示为大举，因以胁定群情，外谋南伐，其实迁也。1日人怀土，多不所愿，内惮南征，无敢言者。于是定都洛阳。”上引材料不能说明的问题是()。

论述斯巴达的阶级结构、政治制度和社会风尚

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

电子计算机的发展经过了：①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。

以下()协议完成了从网卡到IP地址的映射。

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

外国法院作出的发生法律效力的判决、裁定，需要我国的人民法院承认和执行的，可以由当事人直接向我国有管辖权的下列哪个法院申请承认和执行?

患者，女，35岁。发现糖尿病3年。因外阴瘙痒严重，影响睡眠前来就诊。妇科检查：阴道黏膜红肿，白带呈干酪样，剥离后可见阴道上有小溃疡，宫颈光滑。首选的治疗药物是

患者，男性，55岁，矽肺。因呼吸困难3天入院。患者曾在采矿场做采石工长达10年。那么患者所患的矽肺与其职业有关，可认定为

依据《全国生态环境保护纲要》，下列区域中，不属于重要生态功能区的()。

下列关于增加值的表述中错误的是()。

Therehasbeena______lackofcommunicationbetweentheunionandthemanagement.

根据安德森对知识的分类，其中对事实、定义、规则和原理等的描述属于()。(2013·河南)

()是中国共产党在中央机关设立的最早的保卫组织。

下列诗句与作者对应不正确的选项是()。

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

计算机408

学硕统考专业

汉章帝会群儒于白虎观，讨论经义，由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书，这部书系统地吸收了阴阳五行和谶纬之学，形成今文经学派的主要观点。

日本推行锁国体制的原因及影响。

1939年8月23日，苏德双方签了()和《秘密附属议定书》，划定了双方在东欧的势力范围。这一条约使德国得以进攻波兰，使第二次世界大战终于爆发。

(北魏孝文帝)“初谋南迁，恐众心恋旧，乃示为大举，因以胁定群情，外谋南伐，其实迁也。1日人怀土，多不所愿，内惮南征，无敢言者。于是定都洛阳。”上引材料不能说明的问题是()。

论述斯巴达的阶级结构、政治制度和社会风尚

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

电子计算机的发展经过了：①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。

以下()协议完成了从网卡到IP地址的映射。

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

外国法院作出的发生法律效力的判决、裁定，需要我国的人民法院承认和执行的，可以由当事人直接向我国有管辖权的下列哪个法院申请承认和执行?

患者，女，35岁。发现糖尿病3年。因外阴瘙痒严重，影响睡眠前来就诊。妇科检查：阴道黏膜红肿，白带呈干酪样，剥离后可见阴道上有小溃疡，宫颈光滑。首选的治疗药物是

患者，男性，55岁，矽肺。因呼吸困难3天入院。患者曾在采矿场做采石工长达10年。那么患者所患的矽肺与其职业有关，可认定为

依据《全国生态环境保护纲要》，下列区域中，不属于重要生态功能区的()。

下列关于增加值的表述中错误的是()。

Therehasbeena______lackofcommunicationbetweentheunionandthemanagement.

根据安德森对知识的分类，其中对事实、定义、规则和原理等的描述属于()。(2013·河南)

()是中国共产党在中央机关设立的最早的保卫组织。

下列诗句与作者对应不正确的选项是()。

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