首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。
admin
2016-03-29
43
问题
线性表(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
学硕统考专业
相关试题推荐
1978年直接领导和发动真理标准问题讨论的中央领导人是()。
对《魏玛宪法》的内容和影响叙述不正确的是()。
简述第二国际建立的社会历史条件。
奥斯曼国家的第一个苏丹是()。
第二次世界大战给全人类的启示是()①维护世界和平是当代各国人民的共同任务②必须坚持反对霸权主义和强权政治③必须发展和壮大世界和平力量④必须建立国际政治经济新秩序
克里特文明的文字类型是()。
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
武则天时期,为了管理天山以北的广大区域而设立了()。
某汽车轮渡口,过江渡船每次能载10辆车过江。过江车辆分为客车类和汽车类,上渡船有如下规定:同类车先到先上船,客车先于货车上船,且每上4辆客车,才允许上一辆货车,若等待客不足4辆,则以货车代替,若无货车等待允许客车都上船。写一算法模拟渡口管理。
分页存储管理中,页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间),会给页表的设计带来什么样的新问题?请给出一种解决方法,分析它的优点和缺点。
随机试题
设备运杂费通常是由()等构成的。
王先生,患急性胰腺炎,今日上午8:00开始补液1000ml。按60滴/分速度输入(1ml按15滴计算),该液体应何时输完( )
经食物传播的传染病的流行特征
子宫肌瘤寒湿凝滞证治法是子宫肌瘤瘀热交阻证治法是
申请土地使用权、所有权和土地他项权利登记时,申请者必须向土地管理部门提交的文件资料中不包括()。
关于挤塑聚苯板燃烧性能的下列说法,错误的是:[2017—009]
事故处理需要进行设计变更的应()。
选择性货币政策工具包括()。
《地心引力》因其真实地展现了宇航员完成航天飞行任务的故事而斩获多项奥斯卡奖。其中,航天飞机以很高的速度绕地球飞行,宇航员能够离开航天飞机在太空行走而不被甩掉的原因是()。
男性,68岁。排尿费力10年,昨日饮酒后一夜不能排尿,下腹胀痛。查体:膀胱膨胀达脐下1指伴轻压痛。有关前列腺直肠指检,错误的是
最新回复
(
0
)