首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设线性表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
61
问题
设线性表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
学硕统考专业
相关试题推荐
图的D搜索类似于BFS。不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。用D搜索方法搜索下图,设初始出发的结点为1,写出顶点的访问次序,当从某
计算机操作系统中,若WAIT、SIGNAL操作的信号量S初值为3,当前值为一2,则表示当前有()个等待信号量S的进程。
某计算机系统的内存储器由(2ache和主存构成,Cache的存取周期为45纳秒,主存的存取周期为200纳秒。已知在一段给定的时间内,CPU共访问内存4500次,其中340次访问主存。问:Cache的命中率是多少?
已知二叉树采用二叉链表方式存放,要求返回二叉树T的后序遍历访问的第一个结点,是否可不用递归且不用栈来完成?请简述原因。
进程由就绪态转换为运行态是由()引起的。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,一1,4,一4,…,j2,一j2(j0时,Hi=(H(key)+di)%m当di
如下图所示为一个TCP主机中的拥塞窗口的变化过程,这里最大数据段长度为1024字节,请回答如下问题:在14次传输的时候阀值为多少?
给定页面请求序列RS—cadbebabcd,页框为4,起始为空,写出LRU页面置换过程。
指令系统字长16位,每个地址码为6位,采用扩展操作码的:疗式,试设计14条二地址指令,100条一地址指令,100条零地址指令。计算操作码的平均长度。
已知AOE网中顶点v1,v2,v3,…v7分别表示7个时间,有向线段a1,a2,a3,…a10。分别表示10个活动,线段旁的数值表示每个活动花费的天数,如图10-1所示。请填写表10-1、表10-2两个表格,并用顶点序列表示出关键路径,给出关键活动。
随机试题
心房纤颤发生后至少可使心排血量下降
A、《黄帝内经》B、宋国宾《医业伦理学》C、孙思邈《备急千金要方》D、希波克拉底《希波克拉底誓言》E、帕茨瓦尔《医学伦理学》奠定西方医学人道传统的文献是
关于物资需求计划的说法,正确的是()。
根据《注册建造师管理规定》,注册建造师的下列行为违法的有()。
下列哪一条符合儿童动作发展的规律()
14世纪欧洲学校的课程有算数、几何、天文等,到16世纪增加了地理和力学,17世纪又增加代数、三角、物理和化学等。这说明对教学内容变化产生影响的是()
设矩阵A、B的行数都是m.证明:矩阵方程AX=B有解的充分必要条件是r(A)=r(A┆B).
下列关于世界上第一台电子计算机ENIAC的叙述中,错误的是()。
FoodandYourLifeStagesThenutritionalneedsofthehumanbodychangeatdifferentlifestages.Tobefitandhealthy,it
HowtoBuildTeamSpiritandGetBestSalesPerformanceA)Itisawell-knownfactthatanorganisationcanachieveagreatersuc
最新回复
(
0
)