首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2019-08-01
43
问题
线性表(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
学硕统考专业
相关试题推荐
西汉初年代表黄老政治思想的著作,是陆贾的()。认为“道莫大于无为,行莫大于谨敬”。
马克思说:巴黎公社“只不过是在特殊条件下的一个城市起义”。其含义是()。
1962年2月,中共中央发出《关于改变农村人民公社基本核算单位问题的指示》,规定人民公社的基本核算单位是()。
根据1931年的威斯敏斯特法,英国()。
近现代以来,国际关系中先后出现了维也纳体系、凡尔赛一华盛顿体系和雅尔塔体系。关于这三个体系共同点的表述不正确的是()。
1941年~1942年,中共在根据地建设中,为争取抗战胜利奠定物质基础的措施是()。
晚清时期下列武装力量出现的先后顺序是
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述,不确切的是()。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
试比较脱机I/O和联机I/O。
随机试题
成本费用核算的基本要求规定:实行成本核算的事业单位必须坚持()
某犯罪集团多次抢劫银行,数额巨大,打死打伤数人。对此案的审理,人民法院最多应该在多长的时间内宣判:
关于刑讯逼供罪的认定,下列哪些选项是错误的?()(2012年卷二第60题)
工料单价法计价程序不包括以()为计算基础的工料单价法计价程序。
物业服务定价成本中的人员费用包括()。
进行房地产市场预测时,首先应该()。
下列关于外币交易会计处理的表述中,错误的是()。
教师按一定的教学要求向学生提出问题,要求学生回答,并通过问答的形式来引导学生获取或巩固知识的方法是()。
许多人说秋天最容易惹起人的烦恼、伤感,所以古今的词人墨客,都是在秋天大发________,摇头摆尾呜呼噫嘻,舞弄笔墨。我恰恰相反,我觉得秋天是一年中最________最美丽的季节。填入画线部分最恰当的一项是:
我国在特别行政区内实行的制度由()。
最新回复
(
0
)