首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
admin
2019-08-15
31
问题
线性表(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://jikaoti.com/ti/l3GjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
二战后,美苏关系从盟友走向对抗,其根源是()
“一战”期间,中国民族资本主义迅速发展的重要作用是()。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:(1)请说明系统处于不安全状态;(2
设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][O]的存储地址为860,则a[3][5]的存储地址为()。
对汇编语言程序员来说,以下部件中不透明的是()。I.指令缓冲器;Ⅱ.移位器;Ⅲ.通用寄存器;Ⅳ.中断字寄存器;V.乘法器;Ⅵ.先行进位链;
问:下列IEEE单精度浮点数所表示的十进制数分别是多少?(1)1011110101000000000000000000000(2)010l0101011000000000000000000000(3
随机试题
流行性出血热少尿期最致命的水电解质及酸碱紊乱是
甲企业采用计划成本进行材料的日常核算。月初结存材料的计划成本为160万元,成本差异为超支40万元。当月购入材料一批,实际成本为220万元,计划成本为240万元。当月领用材料的计划成本为200万元,当月领用材料应负担的材料成本差异为()万元。
当事人为了重复使用而预先拟定,并在订立合同时未与对方协商的条款是()。
金融市场为市场参与者提供了防范资产风险和收入风险的手段,这是金融市场的()。
讲授数学教学模式的基本操作过程有五个环节,分别为组织教学——__________——讲授新课——____________——小结、布置作业.
交通安全管理工作主要是对城市道路交通实行管理,预防和查处交通事故,保证交通安全与畅通。()
临终关怀是指为临终患者提供医疗、护理、心理、社会等多方位的关怀照顾,使每个患者的生命受到尊重,症状得到控制,生命质量得到提高。根据上述定义,下列不属于临终关怀的是()。
计算机软件分系统软件和应用软件两大类,其中属于系统软件核心的是
Hehadtoteach______waysofdoingbusinesswith.foreigners.
ReadthetextbelowandanswerQuestions8-14.*Onlyonediscountmayapplytoeachfare.CHANGESANDREFUNDSTicketsmaybere
最新回复
(
0
)