首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为x的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增
admin
2017-01-04
55
问题
线性表(a
1
,a
2
,a
3
,…,a
n
)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容:
(1)用最少的时间在表中查找数值为x的元素。
(2)若找到将其与后继元素位置相交换。
(3)若找不到将其插入表中并使表中元素仍递增有序。
选项
答案
(1)顺序存储的线性表递增有序,可以顺序查找,也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”,这里应使用折半查找方法。 void SearchExchangelnsert(ElemType a[];ElemType x) ∥a是具有n个元素的递增有序线性表,顺序存储。本算法在表中查找数值为x的 //元素,如查到则与其后继交换位置;如查不到,则插入表中,且使表仍递增有序 { low=0: high=n一1, //low和high指向线性表下界和上界的下标 while(low<=high) { mid=(low+high)/2; //找中间位置 if(a[mid]==x)break; //找到x,退出while循环 else if(a[mid]<x)low=mid+1;//到中点mid的右半去查 else high=mid—1: //到中点mid的左半去查 } if(a[mid]==x&&mid!=n) //若最后一个元素与x相等,则不存在与其后继交换的操作 { t=a[mid]; a[mid]=a[mid+1]; a[mid+1]=t; } //数值x与其后继元素位置交换 if(low>high) //查找失败,插入数据元素x { for(i=n-1;i>high;i一一) a[i+1]=a[i]; //后移元素 a[i+1]=x; //插入x } ∥结束插入 } ∥结束本算法 (2)算法讨论 首先是线性表的描述。算法中使用一维数组a表示线性表,未使用包含数据元素的一维数组和指示线性表长度的结构体。若使用结构体,对元素的引用应使用a.elem[i]。另外,元素类型就假定是ElemType,未指明具体类型。其次,C中一维数组下标从O开始,若说有凡个元素的一维数组,其最后一个元素的下标应是n—1。最后,本算法可以写成三个函数,即查找函数、交换后继函数与插入函数,写成三个函数显得逻辑清晰、易读。
解析
转载请注明原文地址:https://kaotiyun.com/show/ahRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列改革内容不是在《天朝天亩制度》中提出的一项是()
简述大化改新的内容并对其评价。
巴黎和会上,英国既与法国联合抵制美国称霸世界,又与美国联合反对法国过分削弱德国的要求,英国这样做的目的是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
设某多道程序系统中有用户使用内存1000M,打印机1台。系统采用可变分区动态分配算法管理内存,而对打印机采用静态分配。假设输入输出操作时间忽略不计,采用最短剩余时间优先的进程调度算法,进程最短剩余时间相同时采用先来先服务的算法,进程调度时机选择在进程执行结
随机试题
嗜铬细胞瘤患者只可能表现为高血压,不会出现低血压。
心脏电复律时两电极板距离不应小于()。
患者,男性,70岁。有慢性阻塞性肺气肿病史。咳嗽、咯脓痰伴气急加重2周,今晨神志恍惚,体检:嗜睡,口唇发绀,两肺湿性啰音,心率116次/分,血压185/105mmHg。最可能的诊断是
正常胃液呈
男,39岁农民。持续发热10天,体温呈稽留热。体检:精神萎靡,反应淡漠,体温39.5℃,心率76次/分,肝肋下1.5cm,脾肋下2cm。外周血WBC1.4×109/L,中性粒细胞0.44,淋巴细胞0.60,肥达氏反应0抗体1:80,H抗体1:160,ALT
保证江河、湖泊在汛期安全运用的上限水位是指()。
采用价值工程原理控制成本时,下列各项中能提高价值的途径有()。
审查政府的法规、命令和决定的监督是()。
业主是指区分所有建筑物内或者在一个建筑区划内拥有一个或者一个以上专有建筑物空间或者房屋的所有权人。业主可以是自然人、法人和其他组织,可以是本国公民或组织,也可以是外国公民或组织。业主是在区分所有权制度下的一个法律概念。根据上述定义,下列不属于业主的是(
对以下四个序列用直接插入排序方法由小到大进行排序时,元素比较次数最少的是(61)。
最新回复
(
0
)