首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和算法,将应填入(n)处的语句写在答题纸的对应栏内。 【说明】 为了减少直接插入排序关键字的比较次数,本算法使用了二分(折半)插入法对一个无序数组R[1.n]进行排序。排序思想是对一个待插入元素,先通过二分法(折半)找到插入位置
阅读下列算法说明和算法,将应填入(n)处的语句写在答题纸的对应栏内。 【说明】 为了减少直接插入排序关键字的比较次数,本算法使用了二分(折半)插入法对一个无序数组R[1.n]进行排序。排序思想是对一个待插入元素,先通过二分法(折半)找到插入位置
admin
2009-02-15
20
问题
阅读下列算法说明和算法,将应填入(n)处的语句写在答题纸的对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数,本算法使用了二分(折半)插入法对一个无序数组R[1.n]进行排序。排序思想是对一个待插入元素,先通过二分法(折半)找到插入位置,后移元素后将该元素插入到恰当位置(假设R[]中的元素互不相同)。
【算法】
1.变量声明
X:DataType
i,j,low,high,mid,R[0..n])
2.每循环一次插入一个R
循环:i以1为步长,从2到n,反复执行
①准备
X<-R
;(1);high<-i-1;
②找插入位置
循环:当(2)时,反复执行
(3);
若X.key<R[mid].key
则high<-mid-1
否则 (4)
③后移
循环:j以-1为步长,从(5),反复执行
R[j+1]<-R[j]
④插入
R[low]<-X
3.算法结束
选项
答案
(1)low<-1 (2) low<=high (3)mid<-int((low+high)/2) (4)low<-mid+1 (5)i-1到low
解析
这是一个通过自然语言描述二分插入排序的过程。整个过程由一个大循环来完成,在大循环中又包含两个循环,第一个循环是一个二分查找过程,第二循环是后移过程。
查找过程是在有序序列R[1].R[i-1]中查找R
的过程,这是一个典型的折半查找过程。初始时指针low指向第一个元素,即R [1],指针hish指向第后一个元素,因此(1)空处应填写“low-1”。要查找R
,先与中间元素进行比较,中间元素使用mid指向,因此,(3)空处应填入“mid<-int((low+high)/2)”。当R
<R[mid]时,则在前半部分查找,将high<-mid-1,如果R
>R[mid]时,则在后半部分查找,因此(4)空处应填“low<-mid+1”。那什么时候结束呢?显然,一种情况是已经找该元素,由于题目中已经假设元素互不相同,这种情况不会发生,二是没有找到该元素,即指针low和指针high之间的没有元素了,所以(2)空处应填写“low≤high”。(5)空所在循环是进行数据移动,结合下面语句,可以判断循环是从i-1开始,到什么时候结束呢?通过分析,可以知道,最终要把R
放在R[low]的位置,循环要到low时结束,因此(5)空处应填写“i-1到low”。
转载请注明原文地址:https://kaotiyun.com/show/UEjZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
在Excel工作表中,已输入的数据如下所示:按回车键后,B6单元格显示的值为()。
Excel中,快捷功能按钮的功能是(51)。
Word“格式”菜单下的字体命令不可以设置(47)。
设有关系R、S、T如下所示,则(55)________________。
若Word2010菜单命令右边有“…”符号,表示________________。
某软件公司规定,该公司软件产品的版本号由二至四个部分组成:主版本号次版本号[.内部版本号][.修订号]。对该公司同一软件的以下四个版本号中最新的版本号是(
下面关于幻灯片打印的叙述中,正确的是______。
在Windows7中,若删除桌面上某个应用程序的快捷方式图标,则(31)。
认真阅读下列说明,根据网页显示的效果图,并解释其中用下划线标出的语句的含义。[说明]某在线娱乐公司用ASP实现了一个用于在线点播电影的网页,主页文件名为“index.asp”,网页运行的效果如下图所示。程序中使用的Acess数据表结构如下
随机试题
三面刃铣刀圆柱面齿槽前刀面不平整的主要原因可能是工作台零位不准。()
A.高热、B超发现肝右叶肿物内不均匀液性回声B.血清AFP升高,B超发现肝右叶实性肿物C.B超发现肝右叶囊性肿物,卡松尼(Casoni)试验阳性D.B超发现肝及肾多发囊性肿物原发性肝癌
含硫胺素最多的是亚油酸含量最高的部位是
(2010年多项选择第44题)根据我国合同法,旅客运输过程中发生的下列旅客伤亡事件中,应由承运人承担赔偿责任的是()。
黄老师到上海参加技能培训活动,回来后教研组的其他老师想分享他的培训资料,遭到黄老师拒绝,这种做法表明黄老师()。
规定追捕盗、贼及其他犯罪者的法律是()
[2001年GRK真题](1)一(2)基于以下题干:一份教育部的调查报告指出,城市儿童的心理素质,特别是承受挫折的能力,普遍比乡村儿童差,这是由城市儿童的生活条件一般比乡村儿童较为优越造成的。作为一个长期从事儿童生理心理研究的学者,我不能同意此种看法。我认
Themassmediaisabigpartofourculture,yetitcanalsobeahelper,adviserandteachertoouryounggeneration.Themass
阅读以下关于面向对象系统建模的叙述,回答下列问题。【说明】某软件企业为影音产品销售公司W开发一套在线销售系统,以提升服务的质量和效率。项目组经过讨论后决定采用面向对象方法开发该系统。在设计建模阶段需要满足以下设计要求:(1)w公司经常
Onepuzzleofthissombereconomyistheexistenceofunfilledjobsinthemidstofmassunemployment.Youmightthinkthatwith
最新回复
(
0
)