首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
admin
2019-08-15
73
问题
线性表(a
1
,a
2
,a
3
,…,a
n
)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容:
(1)用最少的时间在表中查找数值为x的元素。
(2)若找到将其与后继元素位置相交换。
(3)若找不到将其插入表中并使表中元素仍递增有序。
选项
答案
(1)顺序存储的线性表递增有序,可以顺序查找,也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”,这里应使用折半查找方法。 void SearchExchangeInsert(ElemType a[];ElemType x) /a是具有n个元素的递增有序线性表,顺序存储。本算法在表中查找数值为x的//元素,如查到则与其后继交换位置;如查不到,则插入表中,且使表仍递增有序 { low=0; high=n—l; //low和high指向线性表下界和上界的下标 while(low<=high) { mid=(low+high)/2i //找中间位置 if(a[mid]==x)break; //找到x,退出while循环 else if(a[mid]<x)low=mid+1;//到中点mid的右半去查 else high=mid一1; //到中点mid的左半去查 } if(a[mid]==x&&mid!=n) //若最后一个元素与x相等,则不存在与其后继交换的操作 { t=a[mid]; a[mid]=a[mid4-1]; a[mid+1]=t; } //数值x与其后继元素位置交换 if(low>high) //查找失败,插入数据元素x { for(i=n-1;i>high;i一一) a[i+1]=a[i]; //后移元素 a[i+1]=x; //插入x } ∥结束插入 } ∥结束本算法 (2)算法讨论 首先是线性表的描述。算法中使用一维数组a表示线性表,未使用包含数据元素的一维数组和指示线性表长度的结构体。若使用结构体,对元素的引用应使用a.elem[i]。另外,元素类型就假定是ElemType,未指明具体类型。其次,C中一维数组下标从0开始,若说有n个元素的一维数组,其最后一个元素的下标应是n-1。最后,本算法可以写成三个函数,即查找函数、交换后继函数与插入函数,写成三个函数显得逻辑清晰、易读。
解析
转载请注明原文地址:https://kaotiyun.com/show/ylCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
全国高校院系调整的具体时间是()。
论述秦国商鞅变法的内容、过程以及重要意义。
有一个仓库,可以存放A和B两种产品,但要求:(1)每次只能存入一种产品(A或B);(2)-N<A产品的数量-B产品的数量<M。其中,N和M是正整数。试用P,V操作描述产品A与产品B的入库过程。
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
若线性表最常用的运算是查找第i个元素及其前驱的值,则采用()存储方式节省时间。
现有一个长度为3000B的IP数据报,其IP头部的长度为20B,该IP数据报如在最大帧长度为1518B的以太网中进行传输,那么为了正确传输,需要将其拆分的数据报个数是()。
设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0
在无噪声情况下,若某通信链路的带宽为3kHz,采用4个相位,每个相位具有4种振幅的QAM调制技术,则该通信链路的最大数据传输速率是____。
简述操作系统的主要作用。
随机试题
大学生郑某、杨某、郭某、孙某毕业居决定自丰创业,成立一家合伙企业,郑某以劳务出资,杨某以知识产权出资,郭某现金出资5万元,孙某以实物出资5万元,四人签订了合伙协议,则下列说法正确的是:
女性,54岁,间断性突发右侧闪电样疼痛2个月,疼痛位于右侧眼眶与口角间,常于进食、刷牙、洗脸时发作,每次持续1~2分钟,发作间期无症状,每日发作1~3次。如选择手术治疗,哪种手术方式为最理想的手术方式
最适用于降低肥胖型糖尿病患者血糖的药物是
实施反倾销税的条件之一是倾销进口与国内产业损害间存在因果关系。关于这一条件的下列表述何者为错误?()
关于非结构构件抗震设计的下列叙述,不正确的是()。
已知某双代号网络计划中,该工作ES=4天、EF=6天、LS=7天、LF=9天,则该工作的总时差为()。
对列人《法检目录》的出口商品,由检验检疫机构实施强制性检验,对合格商品机构给予签发《出境货物通关单》,此通关单必须在海关申报时交海关关员审核,若没有提供纸质通关单,即使检验检疫机构电脑有合格记录,海关也不予以放行。()
孔子评价()“尽美矣,又尽善也”。
A、Youcangrowvegetablesvertically.B、Youcanraiseplantsinaconfinedarea.C、Youcanplantawidevarietyofplantstogeth
Forthispart,youareallowed30minutestowriteashortessayentitledOntheInfluenceofMicroblog.Youshouldwriteatlea
最新回复
(
0
)