首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思
admin
2018-08-12
28
问题
线性表(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
学硕统考专业
相关试题推荐
“我不想变成上帝,或居住在永恒之中,或者把天地抱在怀里,属于人的那种光荣对我就够了。我自己是凡人,我只要求凡人的幸福。”这句话体现的思想是()
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
全国高校院系调整的具体时间是()。
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
下列选择中,()不是操作系统关心的主要问题。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
随机试题
简述个体自身的主观能动性在人的身心发展中的作用。
血浆胶体渗透压的形成主要取决于血浆中的
腹痛伴里急后重可见于
甲、乙、丙因涉嫌绑架犯罪被逮捕。该案经人民检察院审查起诉,认为丙犯罪证据不足,不符合起诉条件,于是作出不起诉决定。该不起诉决定宣布后,发生哪些法律后果?()
依据《中华人民共和国水污染防治法》,对超过重点水污染物排放总量控制指标的地区,有关人民政府环境保护部门应当()。
在Kano模型中,()是质量的竞争性元素。
方案设计的基本方法有()。
西安凤栖原西汉家族墓地于2010年被评为全国十大考古新发现之一。记者从陕西省考古研究院了解到,西安凤栖原西汉家族墓地的贵妇墓考古发掘已近尾声,贵妇不仅身着丝绸衣物戴着精美玉镯和金指环,而且随葬有许多精美的漆器。因此记者得出结论:两千多年前西汉贵妇“很爱美”
下面关于常成员函数的说法中正确的是()。
Farewell,Libraries?Amazon,corn’srecentannouncementthatsalesofe-booksattheonlinemegastorehadovertakensalesof
最新回复
(
0
)