首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2019-08-01
65
问题
线性表(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]<x)low=mid+1; //~tj中点mid的右部去查 else high=mid一1: //到中点mid的左部去查 } if(a[mid]==x&&mid!=n){ //若最后一个元素与x相等, //则不存在与其后继交换的操作 t=a[mid]; a[mid]=a[mid+1]; a[mid+1]=t; } //数值x与其后继元素位置交换 if(low>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(1);当查找不成功时,插入元素时的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/x8Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
斯大林时期的经济体制最本质的特点是()。
下列科技文化成就,产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为楷书④马钧发明翻车
关于清代我国疆域的叙述,下列()不正确。
达芬奇、米开朗基罗、拉斐尔称为“文艺复兴三杰",与启蒙思想家相比,他们
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
[*]对应的微指令如下:ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备,这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求,请回答下列问题:(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
设某计算机有四个中断源,优先顺序按1→2→3→4降序排列,若1、2、3、4中断源的服务程序中对应的屏蔽字分别为1110、0100、0110、1111,试写出这四个中断源的中断处理次序(按降序排列)。若四个中断源同时有中断请求,画出CPU执行程序的轨迹。
随机试题
磁共振现象为成像技术提供了一种全新思路:将人体置于特殊磁场中,用无线电射频脉冲激发人体内氢原子核,引起氢原子核共振,并吸收能量;在停止射频脉冲后,氢原子核按特定频率发出射电信号,并将吸收的能量释放出来,被人体外的接收器收录,经电子计算机处理获得图像。
患者,女,38岁。失眠2年余,伴见月经超前,量多色淡,心悸怔忡,健忘神疲,体倦食少。面色萎黄,舌质淡,脉细弱;治疗应首选
患者,男性,43岁,肾挫裂伤,担心误工想尽快工作,护士对其有关休息的正确指导是()。
刘娜是定居美国的中国公民.因在深圳有生意,2013年2月赴深圳购房。在中国一次商务用餐时,因朋友与他人争议,刘娜帮助友人却误伤了他人,该人将刘娜诉诸中国某法院。依我国相关法律规定,下列哪些选项是正确的?()
目前,我国税款征收的方式主要有()。
招标人在国际招标业务中既可选定中标人也可宣布招标失败,进而拒绝全部投标。()
竞业限制的人员限于()。
根据所给材料,回答问题。矛盾普遍存在于客观世界中,模糊性亦寓于万物运动之中。鸡蛋可以孵鸡,当小鸡未啄出蛋壳时,总不能说它仍是蛋,亦不可称之为鸡,突变的事物会呈现短暂的模糊性,而另一些事物放到漫长的时间里考察也会使模糊性突出显现。铅块上放
1851年,中国爆发的一场伟大的农民战争是()
新民主主义经济纲领规定,对民族工商业实行的政策是()
最新回复
(
0
)