首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2019-08-01
75
问题
线性表(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
学硕统考专业
相关试题推荐
下列对1918年德国十一月革命说法不正确的是()。
下列法律文件中,规定内阁对君主负责的是()。
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。(1)分别画出寻址方式由操作码指出和寻址方式由专用字
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构
采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51;(1)构造散列表(画示意图);(2)装填因子;(3)等概
DNS作为一种分布式系统,所基于的模式是()。
在子网192.168.4.0/30中,能接收目的地址为192.168.4.3的IP分组的最大主机数是____。
对于下列关键字序列,不可能构成某二叉排序树中一条查找路径的序列是____。
随机试题
患儿,7个月。发热4天,体温最高为39℃,当地医院诊断为"上感",静滴3天头孢唑啉及病毒唑,今晨热退,但见面、颈及躯干皮肤有红色斑丘疹。诊断为患儿,9岁。发热,咽痛1日就诊,体检:体温38.9℃,咽部充血,双扁桃腺肿大Ⅱ度,有脓性分泌物,舌红,乳头粗,
胎盘组成为
中药以“四气”和“五味”表示其性能。性味偏盛的药物,临床应用时往往会给病人带来一定的副作用。如太寒伤阳,太热伤阴,过辛耗气,过甘生湿,过酸损齿,过苦伤胃,过咸生痰。药物经过炮制,可以改变或缓和药物偏盛的性味,达到改变药物作用的目的。麸炒之后能缓和辛燥之
监理工程师应当按照工程监理规范的要求,采取()等形式,对建设工程实施监理。
以下关于城市维护建设税税收优惠政策的说法,正确的有()。
下列税种由国家税务局系统负责征管的有()。
党的十八大以来,以习近平同志为核心的党中央,面对新常态下经济工作面临的挑战,坚持稳增长、促改革、调结构、惠民生、防风险并举,对经济工作进行了全面布局,做出了一系列重大战略部署,成效日益彰显。经济运行处在合理区间,更为可贵的是发展转型步伐加快,一些新的经济增
习近平指出,共产党员特别是党员领导干部要做共产主义远大理想和中国特色社会主义共同理想的坚定信仰者和忠实践行者。下列关于共同理想与远大理想之间的关系,说法正确的有()。
若已建立以下链表结构,指针p、s分别指向如图所示结点则不能将s所指结点插入到链表末尾的语句组是
MeaninginLiteratureInreadingliteraryworks,weareconcernedwiththe’meaning’ofoneliterarypieceoranother.Howev
最新回复
(
0
)