首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设线性表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
29
问题
设线性表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
学硕统考专业
相关试题推荐
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
图的D搜索类似于BFS。不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。用邻接表作为存储结构,写一个D搜索算法;
(某系统有三个进程P1,P2,P3并发工作,其中P1执行过程中需要使用资源S3,S1;P2需要使用资源S1,S2;P3需要使用资源S2,S3。如何避免这种后果,列出所有可能的方法。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70},其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
如下图所示的AOE网,求:哪些是关键活动?
给定页面请求序列RS—cadbebabcd,页框为4,起始为空,写出LRU页面置换过程。
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;};将两个升序单链表归并为一个升序单链表。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50ms,输
设某多道程序系统中有用户使用的内存1000M,打印机1台。系统采用可变分区动态分配算法管理内存,而对打印机采用静态分配。假设输入输出操作时间忽略不计,采用最短剩余时间优先的进程调度算法,进程最短剩余时间相同时采用先来先服务的算法,进程调度时机选择在进程执
随机试题
(2010年4月)在我国刑法中,_______属于主刑。
毛泽东指出,中国无产阶级应该懂得:他们自己虽然是一个最有觉悟和最有组织性的阶级,但是如果单凭自己一个阶级的力量,是不能胜利的。而要胜利,他们就必须在各种不同的情形下团结一切可能的革命阶级和阶层,组织革命的统一战线。毛泽东之所以这样认为,是因为(
与结核分枝杆菌抗酸性相关的成分是
天海公司根据生效判决书向法院申请强制执行。执行开始后,天海公司与四通公司达成和解协议。和解协议约定,将80万元债务减少为70万元。协议生效之日起1个月内还清。协议生效1个月后,四通公司并未履行协议的约定。下列做法哪一个是正确的:()
中国证监会受理证券公司的从事中间介绍业务的申请后,应当在()个工作日内做出批准或者不予批准的决定。
民事行为被确认无效或被撤销的法律后果不包括()。
下列关于无形资产的会计处理中正确的是()。
面对当前严峻的食品安全形势,我国已经颁布了一系列政策法规,并正在采取多项措施来保障食品的安全。()
Internet网使用的通信协议是______。
Wateristhegiverand,atthesametime,thetakeroflife.Itcoversmostofthesurfaceoftheplanetweliveonandfeatures
最新回复
(
0
)