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

admin2014-04-17 55

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

学硕统考专业

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

苏州的踹工、织工、纸工、烛业工人，景德镇的陶瓷工、门头沟的煤矿工、北京的香工，云南的矿工、广州的织工、陕西的木工和铁工等，均爆发过反对雇主克扣工价、开除工匠和要求增加工银的()斗争。

下列对凡尔赛和约中有关德国疆界问题的表述，正确是()。

中共十六届五中全会提出，建设社会主义新农村的要求是生产发展和()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

周人重视婚姻，对婚礼尤为讲究。周代的婚礼有六项程序，即：①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()

国民党政府宣布民盟为“非法团体”，民盟总部被迫解散的时间是()。

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

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

荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

手三阴经的循行走向是()

热力管道穿越施工中，下列说法正确的是()。

某分项工程双代号时标网络计划如下图所示，其中工作C和I，的最迟完成时间分别为第()天。

对个人住房贷款楼盘项目的审查不包括()。

下面三个题基于student表和class表，student表的主键是学号，class表的主键是课程号。下列描述的操作中，哪一个操作不正确?

关于函数重载，下列叙述中错误的是()。

Hotelsshouldnotonlyprovidesaferoomsand(health)______food,butalsobeenvironment-friendly.

Theroomisinaterriblemess;it______cleaned.

Itwassurprisingthatheshowedsolittle______athissister’sdeath.

A、Sheisdeterminednottogetinvolvedasothers.B、Sheisworriedmoreaboutherstudythananythingelse.C、Sheisalittlea

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

计算机408

学硕统考专业

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

苏州的踹工、织工、纸工、烛业工人，景德镇的陶瓷工、门头沟的煤矿工、北京的香工，云南的矿工、广州的织工、陕西的木工和铁工等，均爆发过反对雇主克扣工价、开除工匠和要求增加工银的()斗争。

下列对凡尔赛和约中有关德国疆界问题的表述，正确是()。

中共十六届五中全会提出，建设社会主义新农村的要求是生产发展和()。

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

周人重视婚姻，对婚礼尤为讲究。周代的婚礼有六项程序，即：①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()

国民党政府宣布民盟为“非法团体”，民盟总部被迫解散的时间是()。

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

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

荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。

手三阴经的循行走向是()

热力管道穿越施工中，下列说法正确的是()。

某分项工程双代号时标网络计划如下图所示，其中工作C和I，的最迟完成时间分别为第()天。

对个人住房贷款楼盘项目的审查不包括()。

下面三个题基于student表和class表，student表的主键是学号，class表的主键是课程号。下列描述的操作中，哪一个操作不正确?

关于函数重载，下列叙述中错误的是()。

Hotelsshouldnotonlyprovidesaferoomsand(health)______food,butalsobeenvironment-friendly.

Theroomisinaterriblemess;it______cleaned.

Itwassurprisingthatheshowedsolittle______athissister’sdeath.

A、Sheisdeterminednottogetinvolvedasothers.B、Sheisworriedmoreaboutherstudythananythingelse.C、Sheisalittlea

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