首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2018-08-12
62
问题
线性表(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
学硕统考专业
相关试题推荐
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
宁夏回族自治区的设立时间是()。
周人重视婚姻,对婚礼尤为讲究。周代的婚礼有六项程序,即:①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()
全国高校院系调整的具体时间是()。
下列选择中,()不是操作系统关心的主要问题。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
高度为7的AVL树最少有()个结点。
假定在一个处理机上执行的操作如下:作业估计服务时间片优先数A103B11C23D14E52这些
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
随机试题
在含有大量脂肪油类药物的片剂处方中,应选用的吸收剂是
肛门坐浴的作用不包括
网络图中,中间节点()。
在下列关于“基差”的叙述中,不正确的是()
对于数据组2,4,4,5,3,7,4,5,3,8,其众数、中位数与平均数分别是()。
根据以下资料,回答以下问题。我国2012年7月份外贸出口同比仅增长1%,主要原因是当月我国对欧盟的出口大幅度下降所导致,预计下半年中国外贸形势将更加严峻。2012年1~7月,我国进出口总值21683.7亿美元,比去年同期增长7.1%。其
在回归分析中,决定系数等于
A.条件(1)充分,但条件(2)不充分。B.条件(2)充分,但条件(1)不充分。C.条件(1)和条件(2)单独都不充分,但条件(1)和条件(2)联合起来充分。D.条件(1)充分,条件(2)也充分。E.条件(1)和条件(2)单独都不充分,条件(1)和
设f(x)二阶可导,f(1)=0,令φ(x)=x2f(x),证明:存在ξ∈(0,1),使得φ’’(ξ)=0.
Theoutbreakwasthoughttohavebeenstarted
最新回复
(
0
)