首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和算法,将应填入(n)处的语句写在答题纸的对应栏内。 【说明】 为了减少直接插入排序关键字的比较次数,本算法使用了二分(折半)插入法对一个无序数组R[1.n]进行排序。排序思想是对一个待插入元素,先通过二分法(折半)找到插入位置
阅读下列算法说明和算法,将应填入(n)处的语句写在答题纸的对应栏内。 【说明】 为了减少直接插入排序关键字的比较次数,本算法使用了二分(折半)插入法对一个无序数组R[1.n]进行排序。排序思想是对一个待插入元素,先通过二分法(折半)找到插入位置
admin
2009-02-15
21
问题
阅读下列算法说明和算法,将应填入(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
程序员下午应用技术考试
软考初级
相关试题推荐
在某机床上加工一批零件,要求其直径控制在1.5±0.2cm。检验员定时抽查测量了产品的直径,并绘制了如下的质量控制图。检验结论是:有()次检查发现质量问题,需要进一步查明原因并改进。
下面不属于软件开发过程的是______。
在Excel中,选中某单元格并输入123,回车后此单元格的显示内容为¥123,则可知此单元格的格式被设成了(54)。
在Excel中,若A1单元格中的函数为"=IF("教授">"助教",TRUE,FALSE)",按回车键后,A1单元格中的显示内容为______。
下列关于数据库系统的说法中,(62)是错误的。
在Word2007中,字符样式应用于__________。
在Word2010中,()快捷键可以选定当前文档中的全部内容。
某班级有40名学生,本次数学考试大多在80分上下。老师为了快速统计平均分,对每个学生的分数按80分为基准,记录其相对分(多出的分值用正数表示,减少的分值用负数表示,恰巧等于80分时用0表示),再统计出各种相对分的人数,如下表:根据上表可推算出,这次考试
在Excel2007中,如果在A1单元格输入“计算机”,在A2单元格输入“软件资格考试”,在A3单元格输入“=A1&A2”,按回车键后,结果为______。
计算机使用了一段时间后,系统磁盘空间不足,系统启动时间变长,系统响应延迟,应用程序运行缓慢,此时,需要对系统进行优化。(28)________________不属于系统优化工作。
随机试题
Cultureisthesumtotalofallthetraditions,customs,beliefs,andwaysoflifeofagivengroupofhumanbeings.Inthis【C1】
患者,男,28岁。需拔除右下智齿,选择的麻醉方法是
普查及早期发现宫颈癌最简单最重要的方法是
除哪项外,均为兼行气作用的活血化瘀药
A.食积便秘B.血虚便秘C.气虚便秘D.脾约便秘E.冷积便秘大黄附子汤主治的是()
A.异烟肼B.异烟腙C.乙胺丁醇D.对氨基水杨酸钠E.吡嗪酰胺在体内被水解成羧酸,抑制结核杆菌生长的药物是()。
某公司有女职工和未成年工。根据《劳动法》,下列对女职工和未成年工特殊保护的做法中,正确的是()
帮助学生适应大学生活模式的方法有哪些?
下列关于职业道德与职业技能关系的说法,不正确的是()。
Athrongofbeardedmen,insad-coloredgarmentsandgraysteeple-crownedhats,intermixedwithwomen,somewearinghoodsandot
最新回复
(
0
)