首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2019-08-01
26
问题
线性表(a
1
,a
2
,a
3
,…,a
n
)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
(3)分别给出算法备部分的时间复杂度。
选项
答案
(1)顺序存储的线性表递增有序,可以顺序查找,也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”,这里应使用折半查找方法。 (2)算法的设计如下: void SearchExchangeInsert(ElemType a[],ElemType x){ int low=0:int high=n一1;int mid; //low和high指向线性表下界和上界的下标 while(low<=high){ mid=(low+high)/2; //找中间位置 if(a[mid]==x)break; //找到x,退出while循环 else if(a[mid]
high){ //查找失败,插入数据元素x int i; for(i=n-1;i>high;i一一) a[i+1]=a[i]; //后移元素 a[low]=x; //插入x } //结束插入 } (3)在利用折半查找的方法查找x的过程中时间复杂度为O(nlog
2
n);交换元素位置时的时间复杂度为O(l);当查找不成功时,插入元素时的时间复杂度为O(n)。
解析
转载请注明原文地址:https://jikaoti.com/ti/dtGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
20世纪50年代到70年代初,西欧国家通过有效的社会经济政策,维持了经济相对稳定和持续发展。这些政策主要包括()①加强对经济的宏观管理②废除生产关系中封建落后因素③发展高科技和新兴产业④进行社会改革,稳定社会
国民党政府宣布民盟为“非法团体”,民盟总部被迫解散的时间是()。
下列关于马略军事改革的叙述,不正确的是()。
近现代以来,国际关系中先后出现了维也纳体系、凡尔赛一华盛顿体系和雅尔塔体系。关于这三个体系共同点的表述不正确的是()。
中世纪战争史上有过两次君士坦丁堡陷落,分别简述其发生的时间、征战的双方、导致的历史变动。
1941年~1942年,中共在根据地建设中,为争取抗战胜利奠定物质基础的措施是()。
对三国鼎立局面的形成起到关键性作用的战役是()。
魏晋南北朝时期,促进江南经济发展的有利条件是()。①大批北方农民南迁②江南地区战乱较少,相对安定③南方自然条件相对优越④南方统治者采取了发展经济的措施
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
随机试题
简述因自身利益导致注册会计师对职业道德基本原则产生不利影响的情形。
下列哪项不是常用的不良反应监测方法
患儿男,3个月。因“发热、气促3天、加重1天”入院。3天前无明显诱因下,发热39.6℃,伴轻咳,气促,唇周发绀,无寒战,无抽搐。曾在外院予青霉素,头孢噻肟钠抗感染等治疗。昨天热稍退,但气促发绀明显加重,伴呼气性呻吟。起病以来,精神困倦,烦躁,睡眠差,胃纳差
女,20岁。咳嗽、胸闷1周。查体:右下肺呼吸音消失。胸部X线片示右侧大量胸腔积液。该患者肺通气功能检查最不可能出现的结果是
下列诗句按其所描写节日的先后顺序.排列正确的是:①桃符呵笔写,椒酒过花斜②九日黄花酒,登高会昔闻③粽包分两髻,艾束著危冠④马上逢寒食.途中属暮春
市场利率上升时,债券交易价格会随之降低。()(中国人民大学2012真题)
Whomdoesthemanwanttotalkwith?
Readtheemailandmemobelow.Completetheform.Writeawordorphrase(inCAPITALLETTERS)oranumberonlines41-45o
Thenumberofstudentsinourdepartment(be)______morethan500.
Duringtheholidays,theconcertenjoyshuge(popular)______despitethehighticketprice.
最新回复
(
0
)