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

admin2016-03-29 36

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

洋务运动的主要作用集中在()

春秋大国争霸与战国兼并战争如何区别?

世界古代历史上，对东西方文化交流、传播作出突出贡献的是()

武则天时期，为了管理天山以北的广大区域而设立了()。

1543年发表解剖学专著《人体结构论》的是()。

编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

明朝擅长“易圆以方”“易整以散”装饰手法的画家是（）。[江西2018][云南2018]

具有政策的规定性，还要特别反映一个国家教育的根本性质、总的指导思想和教育工性的总方向的是()。

商业用地的土地使用权出让最高年限为()

机械通气时使用反比通气有利于肺泡复张和气体弥散，有类似__________的作用。

片剂的特殊检查项目主要有（）

法国在鲁尔冒险失败后，财政危机加剧，进一步引起全国人民的普遍不满。因此，以为首的国民联盟政府在1924年5月的议会选举中失败，“左翼联盟”获胜。6月，以为总理的“左翼联盟”政府上台执政。

Theideathatpeoplemightbechosenorrejectedforjobsonthebasisoftheirgenesdisturbsmany.Such【C1】______may,however,

网络协议是为了网络数据交换而制定，它的主要组成要素是Ⅰ．语法Ⅱ．规则Ⅲ．语义Ⅳ．约定Ⅴ．时序

LastweekIvisitedoneofmyoldneighborhoodsinWashingtonD.C.Ihadn’tbeentherefortwentyyearsandasIwalkedalongt

"SymbioticRelationships"Symbiosisisaclose,long-lastingphysicalrelationshipbetweentwodifferentspecies.Inotherwo

计算机408

学硕统考专业

洋务运动的主要作用集中在()

春秋大国争霸与战国兼并战争如何区别?

世界古代历史上，对东西方文化交流、传播作出突出贡献的是()

武则天时期，为了管理天山以北的广大区域而设立了()。

1543年发表解剖学专著《人体结构论》的是()。

编写一个算法，实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

明朝擅长“易圆以方”“易整以散”装饰手法的画家是（）。[江西2018][云南2018]

具有政策的规定性，还要特别反映一个国家教育的根本性质、总的指导思想和教育工性的总方向的是()。

商业用地的土地使用权出让最高年限为()

机械通气时使用反比通气有利于肺泡复张和气体弥散，有类似__________的作用。

片剂的特殊检查项目主要有（）

法国在鲁尔冒险失败后，财政危机加剧，进一步引起全国人民的普遍不满。因此，以________为首的国民联盟政府在1924年5月的议会选举中失败，“左翼联盟”获胜。6月，以________为总理的“左翼联盟”政府上台执政。

Theideathatpeoplemightbechosenorrejectedforjobsonthebasisoftheirgenesdisturbsmany.Such【C1】______may,however,

网络协议是为了网络数据交换而制定，它的主要组成要素是Ⅰ．语法Ⅱ．规则Ⅲ．语义Ⅳ．约定Ⅴ．时序

LastweekIvisitedoneofmyoldneighborhoodsinWashingtonD.C.Ihadn’tbeentherefortwentyyearsandasIwalkedalongt

"SymbioticRelationships"Symbiosisisaclose,long-lastingphysicalrelationshipbetweentwodifferentspecies.Inotherwo

法国在鲁尔冒险失败后，财政危机加剧，进一步引起全国人民的普遍不满。因此，以为首的国民联盟政府在1924年5月的议会选举中失败，“左翼联盟”获胜。6月，以为总理的“左翼联盟”政府上台执政。