首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，an-1，an)。 设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求： 说明你所设计算法的时间复杂度与空间复杂度。
假设有一带头结点的循环双链表表示的线性表L=(a1，a2，…，an-1，an)。 设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a1，a3，…，an，…，a4，a2)。要求： 说明你所设计算法的时间复杂度与空间复杂度。
admin
2017-11-20
71
问题
假设有一带头结点的循环双链表表示的线性表L=(a
1
，a
2
，…，a
n-1
，a
n
)。
设计在时间和空间上都尽可能高效的算法，将线性表L改造成L=(a
1
，a
3
，…，a
n
，…，a
4
，a
2
)。要求：
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
空间复杂度分析：除去链表本身的空间外，额外的空间消耗为O(1)。其实本题可以看成是原来链表的重新组合，并没有开辟新的空间。 时间复杂度分析：整个过程相当于把链表遍历了一遍，所以时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/AVRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
电子计算机的发展经过了四代，①电子数值积分计算机(ENIAC)；②集成电路计算机；③大规模集成电路计算机；④晶体管计算机；⑤人工智能计算机，其先后顺序是()。
1988年起，苏联民族矛盾激化，民族分离运动加剧，第二次较大规模的民族冲突是()。
南洋兄弟烟草公司的创办者之一是()。
下列事件：①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订，按照时间顺序排列正确的是()。
下面有关兵制的内容，与唐玄宗有关的是()
阅读材料，回答以下问题：第四章总统第二十九条临时大总统、副总统由参议院选举之。以总员四分之三以上出席，得票满投票总数三分之二以上者为当选。第三十条临时大总统代表临时政府，总揽政务，公布法律。第三十一条临时大总统为执行法律或基于法
世界近代史上，世界经济发展经历了两次大的飞跃，即第一次工业革命和第二次工业革命。阅读下面两段材料，回答问题：材料一工业革命的主角——蒸汽机，是经验和科学相结合的产物。科学对工业革命的发展做出重大贡献。工场手工业的生产，主要依靠以人力和经
(1)根据无类IP地址的规则，每个网段中有两个地址是不分配的：主机号全0表示网络地址，主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2，即254台。该网络要划分为两个子网，每个子网要120台主机，因此主机位数X应该满足下面三个条件：
编写判定给定的二叉树是否是二叉排序树的函数。
某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下：假定int类型数据用32位补码表示，程序
随机试题
患者，51岁，男，急性前壁心肌梗死，起病第2天发生心房颤动。心室率184/min，BP84/60mmHg，气急发绀，宜首选的治疗措施为
内墙外观质量的检查以距墙80cm---100cm进行观察检查。当出现风裂或龟裂时，可不进行处理，通过住户装修解决。（）
绞吸挖泥船施工按其定位方式不同，可分为()。
下列有关总会计师的权限的说法正确的有( )。
对于时下流行的“月光族”，最需要进行的是（）
伪满洲国
王某为购买出租车向甲银行贷款5万元，并以该出租车设立了抵押，并办理了登记。在春节期间，因下雪路滑，王某不慎出了车祸，乘客受伤，车辆也遭受严重损失，由乙修理厂修理，共花费修理费5000元。由于车辆受损，无法营运，王某不但无力偿还已到期的贷款，而且连支付修理
FalseFearofBigFishManypeoplebelievesharks(鲨鱼)aredangerousandwillalwaystrytohurtorevenkillhumans.【B1】_____
A、10yuan.B、20yuan.C、40yuan.C
A、Astormcanhardlychangethedirectionofanoceancurrent.B、Thelossofsneakersinthestormputthecompanyinthefinanc
最新回复
(
0
)
