首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3…,an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素,请设计一个时间复杂度最低的算法。找到x后,将其与后继元素位置相交换。如果线性表中没有x,将其插入表中并使表中元素仍递增有序。
线性表(a1,a2,a3…,an)中元素值递增有序(没有重复元素)且按顺序存储于计算机内。如果想在当前的线性表中查找数值为x的元素,请设计一个时间复杂度最低的算法。找到x后,将其与后继元素位置相交换。如果线性表中没有x,将其插入表中并使表中元素仍递增有序。
admin
2014-07-18
34
问题
线性表(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
学硕统考专业
相关试题推荐
第一国际开展了哪些活动?其内部经历了哪些主要斗争?
西藏自治区的设立时间是()。
下面条约没有涉及德国的赔款问题的是()。
到1869年为止,人类已发现了多少种化学元素()。
国民政府对日宣战的时间是()。
外国侵略者通过不平等条约取得的特权中,按时间先后顺序排列应是()。①外国商船和军舰可以在长江各口岸自由航行②外国人可以在通商口岸开设工厂③可在通商口岸建立教堂④领事裁判权和片面最惠国待遇
北魏建立和统一的时间分别是()。
晚清时期下列武装力量出现的先后顺序是
随机试题
关于温度敏感神经元的叙述,错误的是
下列表述正确的一项是()
宣扬恐怖主义、极端主义,煽动实施恐怖活动罪
绝缘的电气指标主要是绝缘电阻,任何情况下绝缘电阻不得低于每伏工作电压()。
风管制作时,应针对风管的()采取相应的加固措施。
某公司2008年度有关财务资料如下:该公司采用剩余股利政策,其目标资本结构为自有资本占60%,借人资本占40%。2009年该公司的投资计划所需资金为5000万元。2008年该公司的存货周转率为()次。
学校教育制度简称学制,指一个国家各级各类学校的教育系统,它规定()。
根据资料,回答以下问题。根据所给资料,下列说法中正确的有:(1)2003~2011年,我国GDP、人均GDP及实际增长率走势一致(2)2004~2011年,我国GDP、人均GDP同比增长量逐年递增(3)2003~2011年,我国人口自然增长率最
41030105420( )
北京某高校学工处将于2010年4月29日(星期五)19:30-21:30在校国际会议中心举办题为“领慧讲堂——大学生人生规划”就业讲座,邀请了资深专家赵左蕈先生担任演讲嘉宾。请根据上述关于活动的描述,利用MicrosoftWord制作一份宣传海报(宣传海
最新回复
(
0
)