首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。
admin
2016-03-29
49
问题
线性表(a
1
,a
2
,a
3
,…,a
n
)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。
分别给出算法各部分的时间复杂度。
选项
答案
在利用折半查找的方法查找x的过程中时间复杂度为O(nlog
2
n);交换元素位置时的时间复杂度为O(1);当查找不成功时,插入元素时的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/O2Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述工农武装割据存在与发展的原因和条件。
中共中央正式提出党在过渡时期总路线是在()。
我国最早的人工大运河邗沟是由()修建的。
第二次世界大战给全人类的启示是()①维护世界和平是当代各国人民的共同任务②必须坚持反对霸权主义和强权政治③必须发展和壮大世界和平力量④必须建立国际政治经济新秩序
在捍卫和传播生物进化论方面做出了贡献的是()。
战国初期,上党地区在下列哪一个国家的控制范围之内?()
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
荷兰国旗问题:设有一个仅红、白、蓝三种颜色的条块组成的条块序列,请编写一个时间复杂度为O(n)的算法,使得这些条块按红、白、蓝的顺序排好,即排成荷兰国旗图案。
下列的网络协议中,()的运输层协议是使用TCP的。
随机试题
可与两性霉素B合用的药物是
[2014年,第106题]一个典型的计算机网络系统主要是由()。
根据《地图审核管理规定》,下列地图中,由国务院测绘地理信息主管部门负责下列地图的审核的有()。
关于城市供热管网敷设,说法正确的是()。
工业安装工程的特征有()。
按照惯例,北华工商管理学院:每年一度的特等奖学金获得者的名额仅3名,奖金数额高达10000元。1998年,该校董事会关于评定本年度特等奖学金确定了如下的原则:只有连续3年获得过二等奖以上的奖学金并且本年度各门学科终考成绩平均得分在90分以上的,方可获该项特
《唐律疏议.杂律》:“诸许嫁女,已报婚书及有私约,而辄悔者,杖六十;诸为婚而女家妄冒者,徒一年。男家妄冒,加一等;诸有妻更娶妻者,徒一年;诸以妻为妾,以婢为妻者,徒二年;以妾及客女为妻,以婢为妾者,徒一年半,各还正之。诸同姓为婚者,各徒二年。缌麻以上,以奸
设矩阵B满足A2一AB=2B+4E,则B=_____.
下列关系运算中,能使经运算后得到的新关系中属性个数多于原来关系中属性个数的是()。
A、Sorry,Idon’tknow.B、Thanks.C、Ofcoursenot,makeyourselfathome.C
最新回复
(
0
)