首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
admin
2017-01-04
57
问题
线性表(a
1
,a
2
,a
3
,…,a
n
)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容:
(1)用最少的时间在表中查找数值为x的元素。
(2)若找到将其与后继元素位置相交换。
(3)若找不到将其插入表中并使表中元素仍递增有序。
选项
答案
(1)顺序存储的线性表递增有序,可以顺序查找,也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”,这里应使用折半查找方法。 void SearchExchangelnsert(ElemType a[];ElemType x) ∥a是具有n个元素的递增有序线性表,顺序存储。本算法在表中查找数值为x的 //元素,如查到则与其后继交换位置;如查不到,则插入表中,且使表仍递增有序 { low=0: high=n一1, //low和high指向线性表下界和上界的下标 while(low<=high) { mid=(low+high)/2; //找中间位置 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[mid+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中一维数组下标从O开始,若说有凡个元素的一维数组,其最后一个元素的下标应是n—1。最后,本算法可以写成三个函数,即查找函数、交换后继函数与插入函数,写成三个函数显得逻辑清晰、易读。
解析
转载请注明原文地址:https://kaotiyun.com/show/ahRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
法国《人权宣言》的主要内容有哪些?
试述卡德纳斯改革的背景、内容、性质及意义。
我国对资本主义工商业采取和平赎买的政策内容和成功意义。
简述大化改新的内容并对其评价。
1901年6月,发表《立宪法议》,首先提出君主立宪要求的是()。
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
设某多道程序系统中有用户使用的内存1000M,打印机1台。系统采用可变分区动态分配算法管理内存,而对打印机采用静态分配。假设输入输出操作时间忽略不计,采用最短剩余时间优先的进程调度算法,进程最短剩余时间相同时采用先来先服务的算法,进程调度时机选择在进程执
随机试题
下列疾病时胸水检查为漏出液的是
工程建设项目风险从产生风险的原因及其性质,风险可分为()。
在判断下列资产是否存在可能发生减值的迹象时,不能单独进行减值测试的是()。
参加职工基本养老保险的个人死亡后,其个人账户中的余额可以全部依法继承。()(2013年)
解释心理测验分数的基础是()。
企业劳动争议的协商的特征包括()。
一名妇女回到家中,看到丈夫在厨房里疯狂地晃着身体。似乎腰间有根电线直连电热壶,为了救他于危难之中,她就近从门边上抄起一块厚木板朝他劈去,把他的胳膊劈成两段,其实此前他一直快乐地听着随身听。在波恩的两名动物权利保护者正在抗议那种把猪送到屠宰场的残忍行径时,两
这些年来,国产胶卷在国内市场的占有率逐渐减少,经研究发现:外国胶卷厂的广告比国内胶卷厂的广告更能吸引消费者的关注。因此,国产胶卷制造商计划通过改进广告改变商品形象,以增加市场占有率。以下哪项如果为真,将最不利于国产胶卷制造商上述计划的成功?
在Open语句中可以用Output和Append两种方式打开顺序文件,其主要区别是
Mrs.Nancywaswakenedmidnightbytheringingofthephoneseveralhoursaftertheshipthatherhusbandwasonhadbeen______
最新回复
(
0
)