首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设线性表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
67
问题
设线性表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
学硕统考专业
相关试题推荐
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。要求:描述算
计算机操作系统中,若WAIT、SIGNAL操作的信号量S初值为3,当前值为一2,则表示当前有()个等待信号量S的进程。
关于DMA方式和通道方式,下列说法中错误的是()。
某计算机系统的内存储器由(2ache和主存构成,Cache的存取周期为45纳秒,主存的存取周期为200纳秒。已知在一段给定的时间内,CPU共访问内存4500次,其中340次访问主存。问:如果Cache为8行,主存16块,分别采用三种方式映射主存的第9块
写出单总线结构计算机中指令M()VER1,R2(含义是将寄存器R1中内容写入寄存器R2中)的操作步骤。
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:设该Cache的命中率为98%,如果Cache的速度是主存的5倍,则该机采用Cache时存储系统的速度是不采用
Cache用组相联映射,一块大小为128字节,Cache共64块,4块分一组。主存有4096块,主存地址供需()位。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:请说明系统并不一定死锁。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离1w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
某银行的营业厅有多个柜员窗口,可以同时办理业务。银行的营业厅中安排有n张座椅供储户休息等候。每个储户在进入营业厅时会在排队机上取得一个号码,若此前没有客户,则排队机就会唤醒一个柜员为储户服务,当没有储户时柜员便可以休息。若储户较多,则所有柜员均会参与服务,
随机试题
在线性电路中,功率计算也可用叠加定理。()
幼儿能正确地分辨基本颜色的年龄是()
Historiansoftensuspectthat______.
急性心肌梗死最常见的心律失常是
紫草膏除化腐生肌外,又能
甲将自己的一套房屋租给乙住,乙又擅自将房屋租给丙住。丙是个飞镖爱好者,因练飞镖将房屋的墙面损坏。下列哪些选项是正确的?(2009—卷三—60,多)
产品质量担保形式有()。
牛顿是一位伟大的科学家,他取得了巨大成就,走在时代前列,为全人类揭示了宇宙的本质和演化规律,但这些都离不开前人的智慧。所以他曾经说过:“假若我能比别人嘹望得略为远些,那是因为我站在巨人们的肩膀上。”这句话说明
[*]
A、Jackhasameetingtoattend.B、Jacksaveshismoneybyridinghisbiketowork.C、Jackissavinghismoneytobuyabike.D、J
最新回复
(
0
)