首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设线性表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
38
问题
设线性表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
学硕统考专业
相关试题推荐
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
每棵树都能唯一地转换成相对应的二叉树,由树转换成的二叉树中,一个结点N的左孩子是它在原树对应结点的()。
测得一个以太网数据的波特率是40Mbps,那么其数据率是()。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,一1,4,一4,…,j2,一j2(j0时,Hi=(H(key)+di)%m当di
在集中式总线仲裁中,()方式响应时间最快。
以下关于计算机存储器件的叙述,()是不正确的。
假定在一个处理机上执行的操作如下:这些作业假定按A、B、C、D、E次序先后几乎同时(时间差相对时间片大小忽略不计)到达。(1)给定相应的图示来说明分别用FcFS、RR(时间片=1)、SJF和非抢占优先调度算法(最小优先数有最高优先权)调度这些作业的情
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
下列关于RISC的叙述中,错误的是()。
随机试题
中耳的结构组成包括()。
关于诊断早期妊娠,下列说法错误的是
大多数药物经代谢转化为
关于报复陷害罪的说法,下列哪些选项是正确的?()
《地下水质量标准》(GB/T14848-93)依据我国地下水水质现状、人体健康基准值及地下水质量保护目标,并参照了生活饮用水、工业、农业用水水质最低要求,将地下水质量总共划分为五类,其中()地下水反映地下水化学组分的天然低背景含量,适用于各种用途。
根据《汽车库、修车库、停车场设计防火规范》,车位数为8个,总建筑面积为1000m2的修车库属于()。
A公司对存货分项目采用成本与可变现净值孰低进行计量。2017年12月31日,A、B、C三种存货的情况分别为:A存货成本15万元,可变现净值12万元;B存货成本18万元,可变现净值22.5万元;C存货成本27万元,可变现净值22.5万元。A、B、C三种存货已
某物业服务企业为二级资质,则可以确定的是()。
在心理学实验中,要求特征(demandcharacteristics)是影响实验效果的因素之一。反映要求特征的典型例子包括
执行下列序列后屏幕显示()。STORE5T0XSTORE‘X=15’T0Y?TYPE(‘Y’)
最新回复
(
0
)