首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2019-08-01
28
问题
线性表(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
学硕统考专业
相关试题推荐
“二战期间,美国研制了原子弹并用于实践;1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道;德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。
西汉初年代表黄老政治思想的著作,是陆贾的()。认为“道莫大于无为,行莫大于谨敬”。
洋务运动期间,军事企业主要采取的方式是()。
新文化运动前期的指导思想是()。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
魏晋南北朝时期,促进江南经济发展的有利条件是()。①大批北方农民南迁②江南地区战乱较少,相对安定③南方自然条件相对优越④南方统治者采取了发展经济的措施
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构
假脱机技术(SPOOLing)中,被利用来做虚拟设备的是()。
随机试题
Thepairofshoesthatmymotherboughtformehasbeenwornout—theyneed________.
A.去除病变牙冠髓组织,保留正常牙髓组织B.去除病变的冠髓,保留完整的根髓C.尽可能去除牙根内的牙髓D.彻底去除根管内的感染物质E.保留全部牙髓组织干髓术
患者,女性,45岁,缺失,前牙区Ⅲ。深覆,余留牙无异常。义齿的基托最好选用
妊娠期高血压疾病的基本病理变化是()。
制图综合的基本方法是()。
模拟喷放试验采用干粉灭火剂和自动启动方式,干粉用量不少于();当现场条件不允许喷放干粉灭火剂时,可采用()。
打开报表平台。新建并保存报表文件.以“1月管理费用明细表.srp”为名称保存在考试文件夹下。
商业银行操作风险的特点是()。
根据有关法律规定,下列选举一律采取无记名投票方法的有()。
马赫主义认为真理是“社会地组织起来的经验”,凡是多数人承认的就是真理;实用主义认为“有用即真理”。以下关于这两种观点的说法,正确的是
最新回复
(
0
)