首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设线性表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
43
问题
设线性表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
学硕统考专业
相关试题推荐
(某系统有三个进程P1,P2,P3并发工作,其中P1执行过程中需要使用资源S3,S1;P2需要使用资源S1,S2;P3需要使用资源S2,S3。如何避免这种后果,列出所有可能的方法。
设有一个双向链表h,每个结点中除有prior,data和next三个域外,还有一个访问频度域freq,在链表被起用之前,每个结点中的freq域都被初始化为零。每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域中的值加一,并调整表中
已知二叉树采用二叉链表方式存放,要求返回二叉树T的后序遍历访问的第一个结点,是否可不用递归且不用栈来完成?请简述原因。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(10gn)的算法,确定树中第k个结点的位置。
当向一棵m阶的B一树做插入操作时,若一个结点中的关键字个数等于(),则必须分裂成两个结点,当向一棵m阶的B一树做删除操作时,若一个结点中的关键字个数等于(),则可能需要同它的左兄弟或右兄弟结点合并成一个结点。
关于分页系统,回答下列问题:在什么情况下,上述两种页面淘汰算法执行效果是一样的?为什么?
给定序列{3,5,7,9,11,13,15,17},按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情况下查找成功的平均查找长度。
给定序列{3,5,7,9,11,13,15,17},按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。
设计一个判别表达式中左右括号是否配对出现的算法,采用()数据结构最佳。
某博物馆最多可容纳500人同时参观,有一个出入口,该出入口一次仅允许一个人通过。参观者的活动描述如下:cobegin参观者进程i:{进门;参观;出门;}coend请添加必要的信号量和P、V(或wait()、signal())操作,以实现
随机试题
A.温中健脾B.行气利水C.二者均是D.二者均非(2003年第109,110题)水肿脾阳虚衰证的治法是()
下列各项中,应直接计入当期生产成本的是()。
营养不良小儿治疗原则包括
关于孕妇阴道检查说法错误的是
十二经脉中,阴经与阴经的交接部位在
广告心理学告诉我们,人类获得的()以上的信息来自于视觉。
下列关于死刑的说法中,错误的是()。
某画家从来不在其作品上标明日期,其作品的时间顺序现在才开始在评论文献中形成轮廓。最近,将该画家的一幅自画像的时间定为1930年一定是错误的,1930年时该画家已经63岁了,然而画中年轻、黑发的男子显然是画家本人,但却绝不是63岁的男子。以下哪项是上述
情景:你刚迁入新居,欲把此事告诉你的美国朋友Andy。任务:请你用英语给Andy发一封50个词左右的电子邮件,告诉他:新居的情况;新居的环境;新居的地址DearAndy,...Li
A、Heisnotcooperative.B、Hewillbeinhisofficeallafternoon.C、Hehasnotreadanyofthearticleshimself.D、Healreadyb
最新回复
(
0
)