首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2019-08-01
44
问题
线性表(a
1
,a
2
,a
3
,…,a
n
)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
(3)分别给出算法备部分的时间复杂度。
选项
答案
(1)顺序存储的线性表递增有序,可以顺序查找,也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”,这里应使用折半查找方法。 (2)算法的设计如下: void SearchExchangeInsert(ElemType a[],ElemType x){ int low=0:int high=n一1;int mid; //low和high指向线性表下界和上界的下标 while(low<=high){ mid=(low+high)/2; //找中间位置 if(a[mid]==x)break; //找到x,退出while循环 else if(a[mid]
high){ //查找失败,插入数据元素x int i; for(i=n-1;i>high;i一一) a[i+1]=a[i]; //后移元素 a[low]=x; //插入x } //结束插入 } (3)在利用折半查找的方法查找x的过程中时间复杂度为O(nlog
2
n);交换元素位置时的时间复杂度为O(l);当查找不成功时,插入元素时的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/kACi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1938年,英、法、德、意在德国召开会议讨论对捷克斯洛伐克的苏台德地区的问题,这次会议被称为(),它把英法的绥靖政策推到了顶峰,加速了二战的爆发。
张居正改革期间,调任抗倭名将()镇守蓟门,对安定北方发挥了积极作用。
下列不属于苏联高度集中的经济政治体制产生的条件的是()。
胡适与李大钊“问题与主义”论战主要的阵地是()。
1962年2月,中共中央发出《关于改变农村人民公社基本核算单位问题的指示》,规定人民公社的基本核算单位是()。
魏晋南北朝时期,促进江南经济发展的有利条件是()。①大批北方农民南迁②江南地区战乱较少,相对安定③南方自然条件相对优越④南方统治者采取了发展经济的措施
赋税是我国古代国家宏观管理经济的重要手段。据此回答问题:哪位皇帝的即位首次应用了秘密立储制?()
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:我国银行最早的雏形是唐朝时期出现的()
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
随机试题
三尖瓣关闭不全不会引起
2012年,中国多个城市爆发针对日本“钓鱼岛国有化”示威游行事件。根据我国《集会游行示威法》,下列说法中正确的是哪一项?()
交流系统用单芯电力电缆的(),应同时满足电缆金属护层的正常感应电压不超过允许值,并使按持续工作电流选择电缆截面尽可能较小的原则来确定。
1月24日,收到捐赠固定资产一台,合计4900元,请填制记账凭证。
广州物流(从化)有限公司(企业编码4401915031)进口白柳桉木一批,于2006年4月4日载运货物的“DAHE/048”轮进口,4月16日由广州物流(从化)有限公司向从化海关(关区代码5125)申报。收货单位:番禺伟达家具厂。手册号:C512511
杠杆收购基金在杠杆收购中的职责是()。I.谈判收购价格Ⅱ.决定出售公司的时机Ⅲ.监督高层管理者的活动Ⅳ.通过一个结束性事件完成交易
商业的介入对文学作品改编的影响有目共睹。在影视改编的过程中,影视开始疏离文学,解构了文学的内涵,将其核心诉求转向迎合世俗大众的情感和审美趣味,并且已经达到了肆无忌惮和毫无顾忌的程度。对文学母体肢解已经成为影视改编的普遍场景。当然,这也反证了影视作品难以阻挡
Writingforanhistoricalseriesistricky,andtheoutcomeisnotalwaysasuccess.ThebestoverallEuropeanhistoryinEnglis
CableModem是一种专门为利用()网进行数据传输而设计的。
保护好京杭大运河,对于传承人类文明、促进社会和谐发展具有极其重大的意义。
最新回复
(
0
)