首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设线性表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
76
问题
设线性表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
,…)。要求:
给出算法的基本设计思想。
选项
答案
算法的基本设计思想:先观察L(a
1
,a
2
,a
3
,……,a
n-2
,a
n-1
,a
n
)和L’(a
1
,a
n
,a
2
,a
n-1
,a
3
,a
n-2
,……),发现L’是由L摘取第一个元素,再摘取倒数第一个元素……依次合并而成的。为了方便链表后半段取元素,需要先将L后半段原地逆置[题目要求空间复杂度为O(1),不能借助栈],否则每取最后一个结点都需要遍历一次链表。①先找出链表L的中间结点,为此设置两个指针p和q,指针p每次走一步,指针q每次走两步,当指针q到达链尾时,指针p正好在链表的中间结点;②然后将L的后半段结点原地逆置。③从单链表前后两段中依次各取一个结点,按要求重排。
解析
转载请注明原文地址:https://kaotiyun.com/show/tU3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
写出单总线结构计算机中指令M()VER1,R2(含义是将寄存器R1中内容写入寄存器R2中)的操作步骤。
如下图所示的AOE网,求:是否存在某项活动,当其提高速度后能使整个工程缩短工期?
同步通信比异步通信数据传输率高的原因是()。
设某系统有两种磁盘配置:一种单磁盘结构,一种4磁盘组阵列结构。每个磁盘每磁道64个扇区,每扇区1024字节,转速为10000rpm。找道时间为6ms。两种结构的磁盘控制器每次访问的延迟时间均为lms。设I/O系统的性能只与磁盘和控制器有关,单磁盘中连续访问
假定在一个处理机上执行的操作如下:这些作业假定按A、B、C、D、E次序先后几乎同时(时间差相对时间片大小忽略不计)到达。(1)给定相应的图示来说明分别用FcFS、RR(时间片=1)、SJF和非抢占优先调度算法(最小优先数有最高优先权)调度这些作业的情
下列关于RISC的叙述中,错误的是()。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离1w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
设森林F中有三棵树,第一、第二、第三棵树的结点个数分别为N1,N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是()。
某博物馆最多可容纳500人同时参观,有一个出入口,该出入口一次仅允许一个人通过。参观者的活动描述如下:cobegin参观者进程i:{进门;参观;出门;}coend请添加必要的信号量和P、V(或wait()、signal())操作,以实现
随机试题
以调节气机升降为主要作用的脏腑是
维果茨基提出的关于教育和教学的重要问题不包括()。
甄选成员面谈时提出的主要问题不包括()。
小学生注意的特点有哪些?
2014年,全社会用电量55233亿千瓦时。分产业看,第一产业用电量994.亿千瓦时,同比下降0.2%;第二产业用电量40650亿千瓦时,同比增长3.7%;第三产业用电量6660亿千瓦时,同比增长6.4%;城乡居民生活用电量6928亿千瓦时,同比增长2.2
智力技能的特点是______。
外汇汇率的直接标价是指以一定单位的外国货币为标准来计算应付出多少单位本国货币。()
廉租房
国外某教授最近指出,长着一张娃娃脸的人意味着他将享有更长的寿命,因为人们的生活状况很容易反映在脸上。从1990年春季开始,该教授领导的研究小组对1826对70岁以上的双胞胎进行了体能和认知测试,并拍下了他们的面部照片。在不知道他们确切年龄的情况下,三名研究
Anewanalysisoffederalmoneythatpublicschoolsreceiveforlow-incomestudentsshowsthatarecordnumberofthenation’ss
最新回复
(
0
)