首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2018-08-12
61
问题
线性表(a
1
,a
2
,a
3
,…,a
n
)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
(3)分别给出算法各部分的时间复杂度。
选项
答案
(1)顺序存储的线性表递增有序,可以顺序查找,也可折半查找。题目要求“用最少的时间在表中查找数值为戈的元素”,这里应使用折半查找方法。 (2)算法的设计如下: void SearchExchangelnse~(ElemType a[],ElemType x) { int low=0;int high=n-l;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(1);当查找不成功时,插入元素时的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/9cRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
埃及曾两次被波斯帝国征服,波斯第二次征服埃及的时间是()。
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
美国工业革命的有利条件包括()。①美国自然资源丰富②独立战争后,美国创立了资产阶级共和制度③地理位置优越,远离动乱的欧洲④拥有潜在的广阔的国内市场
全国高校院系调整的具体时间是()。
支持多道程序的操作系统,区别于其他操作系统的主要特征为()。
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
假定在一个处理机上执行的操作如下:作业估计服务时间片优先数A103B11C23D14E52这些
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
随机试题
弦脉与革脉的共同特征主要表现在
滚动轴承内圈在轴上的固定是用于转速高且轴向载荷大的场合。()
在DNA分子中连接一个基本单位的是
患者虚烦失眠,心悸不安,头目眩晕。咽干口燥,舌红。脉弦细,治宜首选
关于日平均最高容许浓度的论述哪一项是不正确的
()科目编码必须按财政部的统一编码方案进行编制。
环球公司2009年3月份部分账户期初余额如表1所示,同时3月份发生以下经济业务。要求:(1)编制各笔经济业务的会计分录。①用银行存款偿付前欠货款30000元。②购买固定资产一台,价款210000元,款项尚未支付。(不考虑增值税)③结转本月份完
(2001年)设y=f(x)在(一1,1)内具有二阶连续导数且f"(x)≠0,试证:
下列叙述中错误的是()。
L"Universestvasteetilest______depenserquelavieexisteailleursquesurTerre.
最新回复
(
0
)