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

admin2023-02-06 84

问题线性表(a₁，a₂，a₃，…，a_n)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
(3)分别给出算法各部分的时间复杂度。

选项

答案(1)顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。 (2)算法的设计如下： [*] (3)在利用折半查找的方法查找x 的过程中时间复杂度为O(nlog₂n)；交换元素位置时的时间复杂度为O(1)；当查找不成功时，插入元素时的时间复杂度为O(n)。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

()主张应该关注非预期的效果，评价重点放在课程计划实际结果上，更多地关注课程计划满足实际需要的程度。

教学过程的规律有哪些?()

2018年2月，中央一号文件《中共中央国务院关于实施乡村振兴战略的意见》发布，下列有关实施乡村振兴战略的说法，错误的是()。

一份合乎规范的教案，其结构主要包括四部分，即概况，教学进程，板书、板画设计或教学媒体的运用以及()。

学习者为了提高学习的效果和效率，有目的、有意识地制订有关学习过程的复杂方案。这称为()。

已有研究指出，口头言语发展的关键期是()。

一个教师道德修养达到高度自觉程度的标志是()。

某装修公司订购了一条长为2．5m的条形不锈钢管，要剪裁成60cm和43cm长的两种规格长度不锈钢管若干根，所裁钢管的横截面与原来一样，不考虑剪裁时材料的损耗，要使剩下的钢管尽量少，此时材料的利用率为：

两个大人带四个孩子去坐只有六个位置的圆型旋转木马，那么两个大人不相邻的概率为：

铁吸收最快的部位是()

对土地使用者而言，随着使用者可使用年期减少和初始土地使用权价格的摊销，其土地使用权价格会()。

某建设工程项目在施工过程中出现混凝土强度不足的质量问题，采用逐层深入排查的方法，分析确定其最主要原因。这种方法是（）。

对泡沫灭火系统形式的选择，说法正确的是()。

A国人在B国境内劫持了C国飞机，迫降于D国境内，该A国人逃到我国境内，我国法院依照刑法对A国人追究刑事责任。这体现了我国刑法的()。

设4元齐次方程组(I)为且已知另一4元齐次线性方程组(Ⅱ)的一个基础解系为α1=(2，一1，a+2，1)T，a2=(一1，2，4，a+8)T．求方程组(I)的一个基础解系；

BathBathbybusSeethesplendorofGeorgianBathfromanopen-topbus,Busesdepartevery10minutesandoperateonahopo