首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。
admin
2016-03-29
39
问题
线性表(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
学硕统考专业
相关试题推荐
二战后世界经济发展变化迅速,这种变化主要表现在()。①国际金融体系和贸易体系的形成②国家垄断资本主义的空前发展③形成以美苏冷战为特征的两极格局④科学技术推动生产力发展更为迅速
自794年日本迁都至平安京(今京都),至1185年镰仓幕府成立是日本历史上的()。
巴黎和会上,英国既与法国联合抵制美国称霸世界,又与美国联合反对法国过分削弱德国的要求,英国这样做的目的是()。
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说,向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传,可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
阅读材料,回答以下问题:材料一:甘地认为,非暴力抵抗是印度争取摆脱殖民桎梏的唯一正确办法;同时,他认为非暴力抵抗并不意味着对外国统治和其他罪恶的屈服。他写道:“我深信假如只有在怯懦和暴力两者之间加以选择时,我将劝人选择暴力……我宁愿要印度用暴力来保护自己
如何认识“农奴制再版”现象?
试述1929~1933年经济危机的根源和影响。
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
某计算机的Cache共有16块,采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节,按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
操作数地址存放在寄存器的寻址方式叫()。
随机试题
肾俞穴属于足少阴肾经。()
在日常生活活动训练中,将复杂的动作分解,让患者记住每一活动的各个步骤,以指导动作,该方法属于
A.地尔硫革B.洋地黄C.阿托品D.利多卡因E.胺碘酮治疗前壁心肌梗死并发短阵室速最好选用
下列哪项不是钙拮抗药的适应证
A、黄连的药用部位所属类型B、关木通的药用部位所属类型C、厚朴的药用部位所属类型D、辛夷的药用部位所属类型E、石斛的药用部位所属类型皮类是()
由我国政府财政贴息的助学贷款是()。
为避免浪费,风景名胜区内已建设的宾馆、招待所、培训中心、疗养院等建筑物,可继续保留。()
下列关于中国古代文房四宝的说法不正确的是()。
LookatthestatementsbelowandtheadvicetobusinessesontheoppositepageaboutusingothercompaniestoruntheirITservi
A、TheInternetmakestoomanythingsaccessibletopeople.B、HisgenerationishookedontheInternet.C、Someofhisfriendsmak
最新回复
(
0
)