首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思想。 (
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思想。 (
admin
2023-02-06
24
问题
线性表(a
1
,a
2
,a
3
,…,a
n
)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
(3)分别给出算法各部分的时间复杂度。
选项
答案
(1)顺序存储的线性表递增有序,可以顺序查找,也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”,这里应使用折半查找方法。 (2)算法的设计如下: [*] (3)在利用折半查找的方法查找x 的过程中时间复杂度为O(nlog
2
n);交换元素位置时的时间复杂度为O(1);当查找不成功时,插入元素时的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/BbwD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下面不属于社会主义核心价值观的是()。
在成就测验的类型中,()是在教学过程中实施的,虽然也要让学生做题,对他们的作业评分,但其目的不是为学生划分等级,而是为了获取学生学习进步情况的有关信息,以便据此改进教学并促进学生学习。
根据下面资料,回答下列问题。【资料】某校初二学生刘军与同学相比,自控力较差、做事拖沓,为此经常被老师批评。一次批评中,班主任孙老师说他朽木不可雕,刘军顶嘴。孙老师气急了,踢了刘军小腿一脚,致其受伤。刘军就医后,孙老师主动承担了医疗费。之后,孙老师
信用联动奖惩:指有关部门或组织在法定范围内根据企业、个人信用记录,采取部门联动、社会协同等方式,对其依法联合实施奖励或惩戒的行为。下列属于信用联动奖惩的是:
下列年份中,在职职工参保人数同比增速大小排序错误的是:
一个不计厚度的圆柱型无盖透明塑料桶,桶高2.5分米,底面周长为24分米,AB为底面直径。在塑料桶内壁桶底的B处有一只蚊子,此时,一只壁虎正好在塑料桶外壁的A处,则壁虎从外壁A处爬到内壁B处吃到蚊子所爬过的最短路径长约为:
某装修公司订购了一条长为2.5m的条形不锈钢管,要剪裁成60cm和43cm长的两种规格长度不锈钢管若干根,所裁钢管的横截面与原来一样,不考虑剪裁时材料的损耗,要使剩下的钢管尽量少,此时材料的利用率为:
两个大人带四个孩子去坐只有六个位置的圆型旋转木马,那么两个大人不相邻的概率为:
音爆是飞行器在突破音障时,由于对空气的压缩无法迅速传播,会逐渐形成激波面,激波面上高度集中的声学能量引起巨大响声,让人耳感受到短暂而极其强烈的爆炸声。音爆只有在突破音障即超音速飞行时才会产生。音爆云则是以飞行器为中心轴、从机翼前段开始向四周均匀扩散的圆锥状
随机试题
在护患关系中护士扮演的角色包括()
患者,女,19岁。爬山时左踝部扭伤,导致局部肿胀、疼痛,立即来医院就诊,正确的处理措施是
A、便秘通B、龙荟丸C、润肠丸D、麻仁润肠丸E、苁蓉通便口服液用于老年便秘、产后便秘的是()
环形消防车通道至少有两处与其他车道相通,高层民用建筑的回车场面积不宜小于()。
房地产投资风险中的动态风险可通过()加以避免。
以下是中国古代一位帝王改革的内容:推行均田制,迁都洛阳,革除鲜卑旧俗,接受汉族先进文化,改革官制,严惩贪污。这位帝王是()。
地球:北极
Beautyhasalwaysbeenregardedassomethingpraiseworthy.Almosteveryonethinksattractivepeoplearehappierandhealthier,h
Readthetextbelowaboutworksharingandjobsharing.Inmostofthelines41—52thereisoneextraword.Itiseithergrammat
Aswithotherformsofnonverbalcommunication,theuseoftouchtocommunicatefeelingsandemotionsvarieswidelyfromculture
最新回复
(
0
)