首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设有一带头结点的循环双链表表示的线性表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
32
问题
假设有一带头结点的循环双链表表示的线性表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
学硕统考专业
相关试题推荐
苏台德问题
1907年召开的第二国际斯图加特代表大会上，争论最激烈的问题是()。
毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。
19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。
下列关于第二三次科技革命的说法，不正确的是()。
论述新石器时代及其文化类型。
完整地表述电磁场理论的物理学家是()。
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令，平均每条指令需要5个机器周期，其中3个周期必须访问内存，内存读写需一个机器周期，假定CPU在95％的时间内持续执行“背景程序”，且这段时间内不执行I／O指令。现
某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1
某虚拟存储系统中有一个进程共有6页(0～5)，其中代码占3页(0～2)，数据占1页(3)，数据堆占1页(4)，用户栈占1页(5)。它们依次存放在外存的22，23，25，26存储块。当前，代码页已经分配在物理内存的66，67，87页，数据页为31，并已经进行
随机试题
多数初孕妇开始感觉胎动自
对家庭所在的社会文化传统“规定”而形成的权威，属于
实质性脏器损伤的临床表现不包括
休克扩容后，出现下列哪项应警惕急性肾损伤
需备麻醉床的病人是
[2011年第049题]哥特式教堂结构体系是中世纪工匠的伟大成就，获得这个成就的主要原因是：
甲(14周岁)运用自己丰富的想象力创作了一部小说，得到学校500元的物质奖励。该获奖行为()
下列各选项中，不属于Internet应用的是（）。
A、美国B、中国C、日本D、法国B录音末尾提到“不仅在茶的故乡——中国……”，所以选B。
Inthatcountry,gueststendtofeeltheyarenothighly______iftheinvitationtoadinnerpartyisextendedonlythreeorfo
最新回复
(
0
)
