首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2019-08-01
45
问题
线性表(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
学硕统考专业
相关试题推荐
20世纪50年代到70年代初,西欧国家通过有效的社会经济政策,维持了经济相对稳定和持续发展。这些政策主要包括()①加强对经济的宏观管理②废除生产关系中封建落后因素③发展高科技和新兴产业④进行社会改革,稳定社会
商朝号称青铜时代,下列叙述不符合当时的历史情况的是()
概述第二帝国时期法国经济发展的特点。
屋大维的权力达到顶峰是在获得了哪一称号之后?()
如果互联的局域网高层分别采用TCP/IP协议与SPX/IPX协议,那么我们可以选择的多个网络互联设备应该是()。
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。(1)分别画出寻址方式由操作码指出和寻址方式由专用字
磁盘机由6个盘片组成,其中专设1个盘面为伺服面,其他的盘面作为记录数据的盘面。盘存储区域内直径为6.1cm,外直径为12.9cm,道密度为220TPM,位密度为6000bpm,平均寻道时间为10ms,磁盘转速为7200RPM。假定7π=3,试计算:
以下关于图的说法正确的是()。.I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在Ⅲ在.AOE网中一定只有一条
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:转移指令的目标地址范围是多少?
某网络的IP地址空间为192.168.5.0/24,采用定长子网划分,予网掩码为255.255.255.248,则该网络中的最大子网个数、每个子网内的最大可分配地址个数分别是____。
随机试题
A.淋巴结结构破坏,大量单一肿瘤性细胞增生B.淋巴结结构破坏,多种炎细胞及R-S细胞增生C.淋巴结内瘤细胞排列成滤泡结构D.淋巴结结构破坏,大量原始粒细胞浸润滤泡性非霍奇金淋巴瘤
A.Ⅰ/甲B.Ⅰ/乙C.Ⅱ/甲D.Ⅱ/乙E.Ⅲ/丙阑尾穿孔术后切口化脓,应记录为
伴有左心室肥厚的高血压患者降压应首选
以下对城市排水体制的选择不合理的是()。
概算定额手册的内容包括()。
借贷记账法具有以下优点( )。
已知数列{an}的前n项和Sn=n2+kn(k∈N*),且Sn的最大值为8。(1)确定常数k,求an;(2)求数列{}的前n项和Tn。
(1)用热水洗去木屑(2)将纸从印版上揭起并阴干(3)把纸覆盖在版面上,用刷子轻轻刷纸(4)用刷子蘸墨汁均匀刷于版面上(5)将有字的一面贴在木板上,由刻字工逐字雕刻(6)将书稿写于纸上
Ononeoftheshelvesofanolddresser,incompanywitholdanddustysauce-boats,jugs,dishesandplates,andpaidbills,res
DearManager,Iamwritingtoyoutocomplainabouttheserviceinyourhotel.Ihadaterriblestayinroom2532ofOrange
最新回复
(
0
)