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

admin2019-08-15 25

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

中国第一条自行设计修建的铁路是在（）。

三国时期，三国称帝的先后顺序是()。

下列关于社会大分工不正确的说法是()。

关于塞尔维乌斯改革的叙述中，不正确的是()。

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

已知散列函数为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散列

假定变量i、f和d的数据类型分别为int、float和double(int用补码表示，float和double分别用IEEE754单精度和双精度浮点数格式表示)，已知i=785，f=1．5678e3，d=1．5e100。若在32位机器中执行下列关系表达式，

以太网交换机中的端H／MAC地址映射表是()。

呈请破案报告书的正文部分主要应写明哪些内容?

Ihopetogetatoolherepairedthismachinewith.

蒋某原系某军区军官，因为不守军事纪律而被开除，赋闲在家时蒋某一直愤恨该军区。某日和众朋友大醉后，携众人大闹该军事禁区。下列说法正确的是：()

边际税率是指(　　)。

()的著作《坛经》，是历史上除佛经外，唯一被尊称为“经”的佛教典籍。

为更好地建设国际一流旅游城市，提升北京作为国际旅游目的地的竞争力，北京市自2015年7月1日起实施()政策。

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。

Katherine:Linda!Ihaven’tseenyouforages.Howareyou?Linda:Fine.Andyou?Katherine:Prettygood.How’sFrank?Linda:O

计算机408

学硕统考专业

中国第一条自行设计修建的铁路是在（）。

三国时期，三国称帝的先后顺序是()。

下列关于社会大分工不正确的说法是()。

关于塞尔维乌斯改革的叙述中，不正确的是()。

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

已知散列函数为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散列

假定变量i、f和d的数据类型分别为int、float和double(int用补码表示，float和double分别用IEEE754单精度和双精度浮点数格式表示)，已知i=785，f=1．5678e3，d=1．5e100。若在32位机器中执行下列关系表达式，

以太网交换机中的端H／MAC地址映射表是()。

呈请破案报告书的正文部分主要应写明哪些内容?

Ihopetoget____________atool____________herepairedthismachinewith.

蒋某原系某军区军官，因为不守军事纪律而被开除，赋闲在家时蒋某一直愤恨该军区。某日和众朋友大醉后，携众人大闹该军事禁区。下列说法正确的是：()

边际税率是指( )。

()的著作《坛经》，是历史上除佛经外，唯一被尊称为“经”的佛教典籍。

为更好地建设国际一流旅游城市，提升北京作为国际旅游目的地的竞争力，北京市自2015年7月1日起实施()政策。

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。

Katherine:Linda!Ihaven’tseenyouforages.Howareyou?Linda:Fine.Andyou?Katherine:Prettygood.How’sFrank?Linda:O

Ihopetogetatoolherepairedthismachinewith.

边际税率是指(　　)。