首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2019-08-01
46
问题
线性表(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
学硕统考专业
相关试题推荐
1938年,英、法、德、意在德国召开会议讨论对捷克斯洛伐克的苏台德地区的问题,这次会议被称为(),它把英法的绥靖政策推到了顶峰,加速了二战的爆发。
通过论战体现出来的革命派与改良派的共同之处有()。①都反对帝国主义的侵略,但又都替侵略者开脱罪责②都不敢正面提出反对帝国主义的口号,反而寄希望于帝国主义的支持和赞助③都反对封建专制制度,主张建立民主政体,但又都对反封建的艰巨性缺乏认识
戊戌政变发生的时间是()。
古埃及第24朝法老波克利斯进行改革,宣布废除奴隶制,债权人只能索取债务人的财产作抵偿,而不能占有债务人的人身,因为财产属于个人,而公民人身属于国家,国家需要他们服役。该改革旨在
1928年10月,国民党中央常务委员会通过的废除议会制度的文件是()。
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
中国共产党在大革命失败后,根据中国革命的新特点,明确了“工农武装割据”的思想,其核心内容不包括()。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
设有两个子网202.118.133.0/24和202.118.130.0/24,如果进行路由汇聚,得到的网络地址是()。
假定某采用页式虚拟存储管理的计算机系统中,主存储器容量为1GB,被分为262144块物理块,物理块号为0,1,2,……,262143。某进程的地址空间占4页,逻辑页号为0,1,2,3,被分配到主存储器的第20,45,101,58号物理块中。回答:
随机试题
溃疡性结肠炎必有的症状是()
治疗坐骨神经痛应选取的主穴为
下列有关口对口人工呼吸的叙述不正确的是
口服地西泮不能应用于
薄、楔束的功能是
人民法院在审判过程中,如果有被告经依法传唤,无正当理由而拒不到庭的,人民法院可以将其拘传。人民法院依法拘传被告人下列做法哪些不符合刑事诉讼法相关规定?
按照PDCA循环开展项目质量管理工作时,P阶段的工作内容是()。
货物查验结束后,报关员在阅读“海关进出境货物查验记录单”时,应注意的情况包括()。
某公司月成本考核例会上,各部门经理正在讨论、认定直接人工效率差异的责任部门。根据你的判断,该责任部门应是()。
ShouldPetsBeForbiddeninDormitory?1.现在很多大学生在寝室养宠物2.有人赞成,有人则反对3.我的观点
最新回复
(
0
)