首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2019-08-01
64
问题
线性表(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
学硕统考专业
相关试题推荐
“二战期间,美国研制了原子弹并用于实践;1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道;德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。
永元四年(公元92年),汉和帝用宦官()掌握的一部分禁军,消灭了窦氏势力。郑众从此参与预政事,并受封为侯,这是宦官用权和封侯的开始。
在五四运动中,站在最前列,起了先锋作用的是()。
张居正改革期间,调任抗倭名将()镇守蓟门,对安定北方发挥了积极作用。
标志着整风运动开始向反“右派”斗争转变的重要文件是()。
全国高校院系调整的时间是()。
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
在4×100米接力赛中,4个运动员之间存在如下关系:运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交棒给运动员3;运动员3也只有接到运动员2传来的接力棒后才能往前跑,他跑完100米
某计算机的Cache共有16块,采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节,按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
试比较脱机I/O和联机I/O。
随机试题
某物质被肾小球自由滤过后,既不被肾小管重吸收,也不被肾小管分泌,其血浆清除率
非住宅国有建设用地使用权期限届满,国有建设用地使用权人未申请续期或者申请续期未获批准的,注销登记申请人为()。
当采用螺纹连接而被连接件太厚不宜制成通孔,且连接不需经常拆卸时,往往采用()。
学校教育制度简称学制,指一个国家各级各类学校的教育系统,它具体规定各级各类学校的性质、任务、修业年限以及它们之间的关系。但是没有规定入学条件。()
(2014年真题)根据我国现行宪法的规定,有权制定基本法律的国家机关是()。
以下关于列表和字符串的描述,错误的是
ProperstreetbehaviorintheUnitedStatesrequiresanicebalanceofattentionandinattention.Youaresupposedtolookata
Apple’slaunchoftheiPadisagambleinmorewaysthanone.Tostartwith,it’sobviouslyabetthattherearemillionsofpeo
Thefamilyis【B1】______.Inthepast,grandparents,parentsandchildrenusedtolivetogether,andtheyhadanextendedfamily.
A、Thedevelopmentofelectronicmusicalinstruments.B、Therelativecostsofdifferenttypesofmusicalinstruments.C、Theperfo
最新回复
(
0
)