首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3…,an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素,请设计一个时间复杂度最低的算法。找到x后,将其与后继元素位置相交换。如果线性表中没有x,将其插入表中并使表中元素仍递增有序。
线性表(a1,a2,a3…,an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素,请设计一个时间复杂度最低的算法。找到x后,将其与后继元素位置相交换。如果线性表中没有x,将其插入表中并使表中元素仍递增有序。
admin
2014-07-18
32
问题
线性表(a
1
,a
2
,a
3
…,a
n
)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素,请设计一个时间复杂度最低的算法。找到x后,将其与后继元素位置相交换。如果线性表中没有x,将其插入表中并使表中元素仍递增有序。请回答下列问题:
(1)给出算法的主要思想;
(2)写出算法的实现函数;
(3)总结所用算法的时间和空间复杂度。
选项
答案
(1)顺序存储的线性表递增有序,可以顺序查找,也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”,这里应使用折半查找方法。 (2)算法实现如下: void SearchExchangeInesert(ElemType a[],ElemType x) ∥a是具有n个元素的递增有序线性表,顺序存储。本算法在表中查找数值为x的元素,如查到则与其后继交换位置;如查不到,则插入表中,且使表仍递增有序 low=0: high=n-1://low和high指向线性表下界和上界的下标 while(low<=high){ mid=(low+high)/2;//找中间位置 if(a[mid]==x)break;//找到x,退出while循环 else if(a[mid]
high)//查找失败,插入数据元素x V{ for(i=n-1;i>high;i--) a[i+1]=a[i];//后移元素 a[i+1]=x;//插入x }∥结束插入 }∥结束本算法 (3)折半的时间复杂度为0(10gn),如果不存在x的情况下,在线性表中插入元素的时候,时间复杂度取决于x插入的位置,最坏情况下为0(n)。算法实现过程中使用的辅助空间为常量,空间复杂度为0(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/paxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
第一国际开展了哪些活动?其内部经历了哪些主要斗争?
李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。
对三国鼎立到隋朝重新统一全国这段历史时期的政局,叙述正确的是()。①只有西晋有过短暂的统一②大多数时间是多个政权分立、南北对峙的复杂政局③西晋、北魏、东晋都有过短暂的统一④除三国分立以外,其他时间基本上处于统
外国侵略者通过不平等条约取得的特权中,按时间先后顺序排列应是()。①外国商船和军舰可以在长江各口岸自由航行②外国人可以在通商口岸开设工厂③可在通商口岸建立教堂④领事裁判权和片面最惠国待遇
中国历史上第一部资产阶级革命法典《临时约法》公布的时间是()。
北魏建立和统一的时间分别是()。
对三国鼎立到隋朝重新统一全国这段历史时期的政局,叙述正确的是()。①只有西晋有过短暂的统一②大多数时间是多个政权分立、南北对峙的复杂政局③西晋、北魏、东晋都有过短暂的统一④除三国分立以外,其他时间基本上处于统
洋务运动时期,首批赴欧海军留学生派出的时间是()。
随机试题
患者,男,45岁。以突起头痛、头晕、呕吐半小时急诊入院。查体:浅昏迷,呼吸有大蒜味,皮肤湿冷,双侧瞳孔缩小,双肺可闻及散在湿啰音,有肌颤。入院后,实验室检测血CHE活力为正常的50%,治疗2h后复查恢复到正常的90%,临床症状明显好转。中毒可能性大的是
下列关于阴阳平衡的描述不正确的是
患者,男性,63岁。刺激性咳嗽3个月,伴痰中带血丝,X线胸片示右上肺叶部分不张,纤维支气管镜检查见右肺上叶支气管开口处有菜花样肿物,质脆,易出血,病理报告未回。最可能的诊断是患者,男性,40岁。发现左侧肺门处有一直径5cm肿块、伴有胸闷气急、发热,颈部
A.盈利性互联网药品交易服务B.非盈利性互联网药品交易服务C.经营性互联网药品信息服务D.非经营性互联网药品信息服务E.互联网药品交易服务根据《互联网药品信息服务管理办法》通过互联网向上网用户有偿提供药品信息服务的活动,属于(
产自蒙古的纯种奶牛每年平均出产400升牛奶。如果蒙古种的牛与欧洲种的牛进行杂交,杂交生出的牛每年平均可出产2700升牛奶。一家国际机构计划通过鼓励推广把蒙古的牛与欧洲种的牛进行杂交来提高蒙古奶牛行业的利润。以下哪项如果为真.对该机构计划的可行性提出了最严
垄断利润是垄断资本家凭借其在社会生产和流通中的垄断地位而获得的超过平均利润的高额利润,具体来说,垄断利润的来源包括
Despiteyourbestintentionsandefforts,itis【B1】______:Atsomepointinyourlife,youwillbewrong.【B2】_______canbehar
以下关于OSPF协议的描述中,错误的是()。
ポッケトに財布が()から、出してくれませんか。
ASalesLetterJilinElectricAppliancesImport&ExportCorp.Changchun,ChinaMarch7,2006SmithTradingCo.NewYorkU.S.A.
最新回复
(
0
)