首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设线性表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
40
问题
设线性表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,写出顶点的访问次序,当从某
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。要求:描述算
某计算机系统的内存储器由(2ache和主存构成,Cache的存取周期为45纳秒,主存的存取周期为200纳秒。已知在一段给定的时间内,CPU共访问内存4500次,其中340次访问主存。问:如果Cache为8行,主存16块,分别采用三种方式映射主存的第9块
设有一个双向链表h,每个结点中除有prior,data和next三个域外,还有一个访问频度域freq,在链表被起用之前,每个结点中的freq域都被初始化为零。每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域中的值加一,并调整表中
设有一缓冲池P,P中含有10个可用缓冲区,一个输入进程将外部数据读入P,另有一个输出进程将P中数据取出并输出(如下图所示)。若进程每次操作均以一个缓冲区为单位,试用记录型信号量写出两个进程的同步算法,要求写出信号量的设置。输入进程输出进程L:读入数据L1;
如下图所示的AOE网,求:完成此工程最少需要多少天(设边上权值为天数)?
把程序地址空间中使用的逻辑地址变成内存中物理地址称为()。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,一1,4,一4,…,j2,一j2(j0时,Hi=(H(key)+di)%m当di
给定页面请求序列RS—cadbebabcd,页框为4,起始为空,写出LRU页面置换过程。
设某系统有两种磁盘配置:一种单磁盘结构,一种4磁盘组阵列结构。每个磁盘每磁道64个扇区,每扇区1024字节,转速为10000rpm。找道时间为6ms。两种结构的磁盘控制器每次访问的延迟时间均为lms。设I/O系统的性能只与磁盘和控制器有关,单磁盘中连续访问
随机试题
A、Anationalteachingprize.B、Aninternationalwritingprize.C、TheGlobalTeacherPrize.D、TheNobelPrize.C新闻中提到,HananAl-Hr
按照参加谈判的人数规模来划分,可以将谈判分为()
腰椎正位摄影要点中,错误的是
玉屏风散与牡蛎散相同的功用是
考试作弊者取消当场考试成绩及后续考试资格,并且()不得再次报考。
刘老师是某高中刚入职的班主任。她所带的高一(2)班学生的学业状况呈现两极分化态势,部分学生学业优良,学习积极性很高,刘老师感到非常高兴;而部分学生的学业则比较糟糕,还存在程度不等的厌学、逃学现象,这让刘老师感到很头疼.不知该如何调动起这些学生的学习兴趣。在
人们对儿童的认识和看法随着时代的变化不断发展,简述现代儿童观的内涵。
用于发布经会议讨论通过并要求贯彻执行的事项的一项下行公文是()。
阅读下面材料,回答下列问题。2012年6月4日,中华全国总工会决定,追授杭州英雄司机吴斌全国五一劳动奖章,以表彰先进,弘扬正气。中央文明委发出《关于广泛开展向张丽莉、吴斌、高铁成同志学习活动的通知》。《通知》指出,学习张丽莉、吴斌、高铁成,就是要
Mostchildrenwithhealthyappetitesarereadytoeatalmostanythingthatisofferedthemandachildrarelydislikesfood【C1】_
最新回复
(
0
)