线性表(a1，a2，a3，…，an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。分别给出算法各部分的时间复杂度。

admin2019-08-15 31

问题线性表(a₁，a₂，a₃，…，a_n)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。
分别给出算法各部分的时间复杂度。

选项

答案在利用折半查找的方法查找x的过程中时间复杂度为O(nlog₂n)；交换元素位置时的时间复杂度为O(1)；当查找不成功时，插入元素时的时间复杂度为O(n)。

解析

转载请注明原文地址:https://kaotiyun.com/show/rlCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

罗马共和国早期平民反对贵族斗争过程中，废除债务奴隶制的是()。

20世纪30年代，美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势，维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外的事务

1941年～1942年，中共在根据地建设中，为争取抗战胜利奠定物质基础的措施是()。

赵匡胤了解高级将领发动兵变夺取政权的危险，他注意分散军权。回答问题：为了限制三帅的权力过大，宋代在中央设立()机构，主管全国的军队调动、训练、供给等事宜。

对汇编语言程序员来说，以下部件中不透明的是()。I．指令缓冲器；Ⅱ．移位器；Ⅲ．通用寄存器；Ⅳ．中断字寄存器；V．乘法器；Ⅵ．先行进位链；

CSMA／CD以太网中，发生冲突后，重发前的退避时间最大是()。

在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

设有带头结点的循环双链表表示的线性表L＝＝＝(a1，a2，……，an－1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L＝(a1，a3，……，an……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用

CSMA／CA是如何实现“冲突避免”的?

属于溢出性蛋白尿的是

A．大环内酯类B．喹诺酮类抗菌药C．头孢菌素类D．青霉素E．氨基糖苷类187．支原体肺炎首社区获得性肺炎链球菌肺炎首选

慢性溃疡性牙髓炎时，患牙龋洞的探诊为

最能确诊先天愚型的是

A．维生素C、吗啡类、水杨酸钠B．阿司匹林、硝酸甘油、青霉素类、巴比妥类C．甘油、乳酸、胃蛋白酶D．牛痘苗、脊髓灰质炎疫苗E．鱼肝油乳、氢氧化铝凝胶、松节油擦剂

下列情形中的(　　)不属于工程师的权力。

客户要在证券公司开展融资融券业务，可以由客户本人向证券公司营业部提出申请，也可以委托他人代理。

求I=，y=x及x=0所围成区域．

Byofferinglowerpricesandamenuofpersonalcommunicationsoptions,suchascalleridentificationandvoicemail,thenewte

ThenumberofpeoplewhosurftheInternetviamobiledevicesinChinahasforthefirsttime【C1】______thenumberusingcomputer

计算机408

学硕统考专业

罗马共和国早期平民反对贵族斗争过程中，废除债务奴隶制的是()。

20世纪30年代，美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势，维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外的事务

1941年～1942年，中共在根据地建设中，为争取抗战胜利奠定物质基础的措施是()。

赵匡胤了解高级将领发动兵变夺取政权的危险，他注意分散军权。回答问题：为了限制三帅的权力过大，宋代在中央设立()机构，主管全国的军队调动、训练、供给等事宜。

对汇编语言程序员来说，以下部件中不透明的是()。I．指令缓冲器；Ⅱ．移位器；Ⅲ．通用寄存器；Ⅳ．中断字寄存器；V．乘法器；Ⅵ．先行进位链；

CSMA／CD以太网中，发生冲突后，重发前的退避时间最大是()。

在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值()。

设有带头结点的循环双链表表示的线性表L＝＝＝(a1，a2，……，an－1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L＝(a1，a3，……，an……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用

CSMA／CA是如何实现“冲突避免”的?

属于溢出性蛋白尿的是

A．大环内酯类B．喹诺酮类抗菌药C．头孢菌素类D．青霉素E．氨基糖苷类187．支原体肺炎首社区获得性肺炎链球菌肺炎首选

慢性溃疡性牙髓炎时，患牙龋洞的探诊为

最能确诊先天愚型的是

A．维生素C、吗啡类、水杨酸钠B．阿司匹林、硝酸甘油、青霉素类、巴比妥类C．甘油、乳酸、胃蛋白酶D．牛痘苗、脊髓灰质炎疫苗E．鱼肝油乳、氢氧化铝凝胶、松节油擦剂

下列情形中的( )不属于工程师的权力。

客户要在证券公司开展融资融券业务，可以由客户本人向证券公司营业部提出申请，也可以委托他人代理。

求I=，y=x及x=0所围成区域．

Byofferinglowerpricesandamenuofpersonalcommunicationsoptions,suchascalleridentificationandvoicemail,thenewte

ThenumberofpeoplewhosurftheInternetviamobiledevicesinChinahasforthefirsttime【C1】______thenumberusingcomputer

下列情形中的(　　)不属于工程师的权力。