首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设线性表L=(a1,a2,a3,…,an-2,an-1,an)采用带头结点的单链表保存,链表中结点定义如下: 请设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各结点,得到线性表L’=(a1,an,a2,an-1,a3,an-2,…)
设线性表L=(a1,a2,a3,…,an-2,an-1,an)采用带头结点的单链表保存,链表中结点定义如下: 请设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各结点,得到线性表L’=(a1,an,a2,an-1,a3,an-2,…)
admin
2020-06-17
58
问题
设线性表L=(a
1
,a
2
,a
3
,…,a
n-2
,a
n-1
,a
n
)采用带头结点的单链表保存,链表中结点定义如下:
请设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各结点,得到线性表L’=(a
1
,a
n
,a
2
,a
n-1
,a
3
,a
n-2
,…)。要求:
说明你所设计的算法的时间复杂度。
选项
答案
第1步找中间结点的时间复杂度为O(n),第2步逆置的时间复杂度为O(n),第3步合并链表的时间复杂度为O(n),所以该算法的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/jU3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
在散列表中,当装填因子非常接近1时,线性探测类似于()查找。
如下图所示的AOE网,求:是否存在某项活动,当其提高速度后能使整个工程缩短工期?
进程由就绪态转换为运行态是由()引起的。
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:主存地址位数为多少?
TCP/IP网络协议主要在OSI模型中进行操作的层次是()。
一个SPOOLING系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。进程1通过输入缓冲区为进程P输人数据,进程P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长度的数据块为单位,这些数据块均存储在同一个磁盘上,因此,SPP
栈S最多只能容纳4个元素,现在6个元素按A,B,C,D,E,F的顺序进栈,下列哪一个序列是可能的出栈序列()?
随机试题
材料11978年,中国正徘徊在一个新的十字路口,中国发展的逻辑是什么?中国现代化到底要通过何种方式抵达?自近代以来盘桓在中华民族头上的问题,再次成为时代之问。时间定格在这一刻。中国上百台印刷机转动,不同的报头之下,出现了同一个标题;校园的阅报
A.产后10天B.产后4周C.产后24小时D.产后4~6周E.产后6周产后最容易发生心衰的时间是
关于成人呼吸窘迫综合征患者呼吸变化的描述,下列错误的是()
某工地水泥从两个地方采购,其采购量及有关费用如下表所示,则该工地水泥的单价为()元/t。
会计职业道德是促进会计法律制度形成和遵守的重要保证。()
【2017福建】主张“泛智教育”理想,并提出把一切知识教给一切人类的教育家是()。
实践作为检验真理的标准,既是确定的,又是不确定的,其不确定性是因为()。
简述西安事变和平解决的历史意义。
设A=的3个特征值为1,2,3,则[].
有三位见习医生.他们在同一家医院中担任住院医生。(1)一星期中只有一天三位见习医生同时值班。(2)在一周之内,没有一位见习医生连续三天值班。(3)任两位见习医生在一星期中同一天休假的情况不超过一次。(4)第一位见习医生在星期日、星期
最新回复
(
0
)