首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3…,an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素,请设计一个时间复杂度最低的算法。找到x后,将其与后继元素位置相交换。如果线性表中没有x,将其插入表中并使表中元素仍递增有序。
线性表(a1,a2,a3…,an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素,请设计一个时间复杂度最低的算法。找到x后,将其与后继元素位置相交换。如果线性表中没有x,将其插入表中并使表中元素仍递增有序。
admin
2014-07-18
53
问题
线性表(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
学硕统考专业
相关试题推荐
李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。
西藏自治区的设立时间是()。
对三国鼎立到隋朝重新统一全国这段历史时期的政局,叙述正确的是()。①只有西晋有过短暂的统一②大多数时间是多个政权分立、南北对峙的复杂政局③西晋、北魏、东晋都有过短暂的统一④除三国分立以外,其他时间基本上处于统
国民政府对日宣战的时间是()。
中国历史上第一部资产阶级革命法典《临时约法》公布的时间是()。
北魏建立和统一的时间分别是()。
对三国鼎立到隋朝重新统一全国这段历史时期的政局,叙述正确的是()。①只有西晋有过短暂的统一②大多数时间是多个政权分立、南北对峙的复杂政局③西晋、北魏、东晋都有过短暂的统一④除三国分立以外,其他时间基本上处于统
随机试题
能够分辨1mm微粒的显微镜是
处方的有效期限一般为处方最长有效期不得超过
某市公安机关在侦查王某盗窃一案时,需要对王某窃得的一件文物进行鉴定,鉴定共耗费了2个月的时间。依照《刑事诉讼法》的规定,以下对这段鉴定时间的看法正确的是哪项?
由于无粘结预应力筋一般为曲线配筋,故应采用( )。
注册会计师在对被审计单位的应付账款进行审计时,一般应选择的函证对象有()。
奥苏伯尔的学习理论认为,学生学习的实质是()。
(青海)如下图,AB是⊙O的直径,PD切⊙O于点C,交AB的延长线于点D,且CO=CD,则∠PCA的度数是____________.
2018年年底,全国1827个县(县级市)共设有县级医院15474所、县级妇幼保健机构1907所、县级疾病预防控制中心2090所、县级卫生监督所1822所,四类县级卫生机构共有卫生人员303.9万人。 全国3.16万个乡镇共设3.6万个乡镇卫生
文化是一个国家、一个民族的________。历史和现实都表明,一个________和背叛自己历史文化的民族,不仅不可能发展起来,而且很可能上演一幕幕历史悲剧。文化自信是更基础、更广泛、更深厚的自信,是更基本、更深沉、更持久的力量。填入画横线部分最恰当的一项
在某公司人力资源部就职的张晓鸣需要制作一份供新员工培训时使用的PowerPoint演示文稿。按照下列要求,并参考“完成效果.docx”文件中样例的效果,完成演示文稿的制作。插入图片“公司logo.jpg”于所有幻灯片的右下角,并适当调整其大小。
最新回复
(
0
)