首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 分别给出算法各部分的时间复杂度。
admin
2019-08-15
63
问题
线性表(a
1
,a
2
,a
3
,…,a
n
)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。
分别给出算法各部分的时间复杂度。
选项
答案
在利用折半查找的方法查找x的过程中时间复杂度为O(nlog
2
n);交换元素位置时的时间复杂度为O(1);当查找不成功时,插入元素时的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/rlCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列哪两个国家是第二次工业革命的发源地和“中心”?
解放军渡江战役中横渡长江的东西两个攻击点是()。
1918年美国总统威尔逊提出“十四点原则”,内容有“海洋上的航行有绝对自由”、“取消一切经济障碍和确立贸易条件的平等”、“成立一个一般性的各国联合组织”。其最终目的是()。
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
高度为7的AVL树最少有()个结点。
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
以太网交换机进行转发决策时使用的PDU地址是()。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50ms,输
设计一个判别表达式中左右括号是否配对出现的算法,采用()数据结构最佳。
随机试题
电刷磨出与滑环吻合的弧面,其接触面积应达到()%以上,才能保证电刷与滑环贴合良好。
同时传递电子和质子的辅酶有()(1996年)
男性,26岁。主动脉瓣关闭不全。该患者可有以下临床表现,除了
关于Χ线强度的叙述,错误的是
石决明、草决明的共同作用是
施工中,容易造成瓦斯积聚的做法是()。
物流中心与境外之间进出的货物,除实行出口被动配额管理和中华人民共和国参加或者缔结的国际条约及国家另有明确规定的以外,______。
由于投资的特定经济主体中包括国家,从特定企业的角度看,投资不一定要考虑收益。()
非物质文化遗产的形式、内容、表现手法乃至传统技艺,都必须尽量是原汁原昧,随便地“________”就失去了本来的文化意义了。就好像京剧,加入西洋器乐或其他剧种的表演技法、剧目等,只能算是移植、开发新艺术形式,而不是保护和传承了。再如国画加油彩,茶道添歌舞,
早く子供______寝させた方がいいですよ。
最新回复
(
0
)