首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
admin
2019-08-15
76
问题
线性表(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://www.kaotiyun.com/show/ylCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
20世80年代,被称为“机器人王国”的国家是()。
二里头文化是我国考古史上的重大发现,具有重大的意义。根据所学知识,回答问题:二里头文化在类型上可以分为()
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
一台主机申请了一个到www.ab@C@edu.cn的连接,为了获取服务器的IP地址,首先要进行DNS查询,下图为本次查询的过程,请回答如下问题:(1)由个人主机发送给本地DNS服务器的数据是采用什么传输层协议发送的?利用了哪个端口?(2
某计算机系统字长为32位,包含2个选择通道和1个字节多路通道,每个选择通道上连接了2台磁盘机和2台磁带机,字节多路通道上连接了2台行式打印机、2台读卡器、10台终端。假定各设备的传输率如下:磁盘机:800KB/s磁带机:200KB/s
写出单总线结构计算机中指令MOVER1,R2(含义是将寄存器R1中内容写入寄存器R2中)的操作步骤。
由元素序列(27,16,75,38,51)构造平衡二叉树,则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。要求:描述算
随机试题
习近平指出:“实现中华民族的伟大复兴,就是中华民族近代以来最伟大的梦想。”中国共产党是中国人民和中华民族的先锋队,十八大以来党中央掀起反腐风暴并取得重大战果,受到广大人民的赞赏和信任。这说明,要实现民族复兴的“中国梦”,尤其要
行政机关进行检查的过程,有误的是()。
一、背景某机电安装公司承建一幢写字楼机电安装工程,工程内容包括建筑电气、给水排水、通风空调、电梯等安装。该工程于2012年6月通过竣工验收后投入使用。该公司工程部计划在当年11月对此工程进行回访。然而8月份接到业主电话:通风空调机房的新
下列可使企业债务增加的有()。
IMF贷款的授信条件和额度对所有成员国都是一视同仁。()
电子商务的功能包括()。
根据劳动合同法律制度的规定,下列关于试用期约定的表述中,正确的有()。
关于罪刑相适应原则,下列说法错误的是()。
我们的一些科普文章常常激不起公众的兴趣,原因之一便是枯燥。要把科普文章写得“郁郁乎文哉”,就需要作家的笔。科学的飞速发展,为文学写作提供了一座富矿。相信有眼光的文学家一旦领略科学题材的广阔富饶,便会陶醉在它的无限风光中乐而忘返。 这段文字谈论的是( )
Istestanxietydestructive?Canwemaketestanxietyworkforus?Theanswertobothofthesequestionsisyes.Testanxietyof
最新回复
(
0
)