首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
admin
2019-08-15
63
问题
线性表(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
学硕统考专业
相关试题推荐
下列不是春秋时代齐国管仲改革的内容的是()。
洋务运动时期,首批赴欧海军留学生派出的时间是()。
曾经来华留学,并在日本大化改新中发挥重要作用的是()。
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题西周建立之后,派遣同姓贵族和异姓贵族及归顺的异族首领到各地区,建立国家以藩屏护卫周室,分别分在卫、鲁、唐、燕的贵族是()
1946年3月5日,英国前首相丘吉尔在富尔敦发表了(),发出第一个明白无误的“冷战”信号。
如果互联的局域网高层分别采用TCP/IP协议与SPX/IPX协议,那么我们可以选择的多个网络互联设备应该是()。
下面包含在TCP头中而不包含在UDP头中的信息是()。
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:该指令系统最多可有多少条指令?该计算机最多有
已知L为没有头结点的单链表中第一个结点的指针,每个结点数据域存放一个字符,该字符可能是英文字母字符或数字字符或其它字符,编写算法构造三个以带头结点的单循环链表表示的线性表,使每个表中只含同一类字符。(要求用最少的时间和最少的空间)。
在散列表中,当装填因子非常接近1时,线性探测类似于()查找。
随机试题
商品耳环石斛的原植物是
现浇结构楼板的底模和支架拆除时,当设计无要求时,对跨度大于8m的梁混凝土强度达到()时方可拆除。
项目进度控制的依据是()。
非储备外汇减少就意味着国内需求增加,非储备外汇增加就意味着国内需求减少。()
贷款人有下列()情形时,银监会可以采取《中华人民共和国银行业监督管理法》第三十七条规定的监管措施。
教育心理学普遍认为西方第一本《教育心理学》出版于【】
男性在40多岁甚至更年轻时就出现患心脏病和严重的冠状动脉疾病的可能性,而女性在50岁以及经历了绝经期后才会真正开始面对这种风险,这让女性在遭遇无论对男性还是女性而言都是第一杀手的心脏疾病之前,赢得了更多的时间。经过研究,女性第一次心脏病发作的时间比男性晚了
随着计算机技术向着千万亿次乃至更高的级别迈进,处理器速度已经超越了传输速度,这就在应用领域产生了一个技术瓶颈,阻碍了应用的进一步发展。任何尝试过拨号上网看流媒体视频的人都有所体会,再快的处理器也不能提高文件加载速度。而在大数据和云计算的当今,在服务器之间有
KeepingCutFlowers1Whileeverybodyenjoysfreshcutflowersaroundtheirhouse,fewpeopleknowhowtokeepthemforaslon
(1)Allovertheworld,yourchancesofsuccessinschoolandlifedependmoreonyourfamilycircumstancesthanonanyotherfa
最新回复
(
0
)