首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2012年上半年上午试题61)递增序列A(a1,a2,…,an)和B(b1,b2,…,bn)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为________时,归并过程中元素的比较次数最多。
(2012年上半年上午试题61)递增序列A(a1,a2,…,an)和B(b1,b2,…,bn)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为________时,归并过程中元素的比较次数最多。
admin
2019-07-12
70
问题
(2012年上半年上午试题61)递增序列A(a
1
,a
2
,…,a
n
)和B(b
1
,b
2
,…,b
n
)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为________时,归并过程中元素的比较次数最多。
选项
A、a
1
,a
2
,…,a
n
,b
1
,b
2
,…,b
n
B、b
1
,b
2
,…,b
n
,a
1
,a
2
,…,a
n
C、a
1
,b
1
,a
2
,b
2
,…,a
i
,b
i
,…,a
n
,b
n
D、a
1
,a
2
,…,a
i
/2,b
1
,b
2
,…,b
i/2
,a
i/2+1
,a
i/2+2
,…a
n
,b
i/2+1
,b
i/2+2
,…,b
n
答案
C
解析
归并排序是将两个排好序的序列合并成一个有序的序列。由选项A给出的结果可知,递增序列B的每一个元素都比A中的元素要大,也就是说a
i
(1≤i≤n)比b
1
小,在排序的过程中,只需要将a
i
与b
1
进行比较,共比较了n次。由选项B给出的结果可知,递增序列B的每一个元素都比A中的元素要小,在排序的过程中,只需要将b
i
(1≤i≤n)与a
1
进行比较,共比较了n次。由选项C给出的结果可知,a
i
<b
i
<a
i+1
,在排序的过程中,将a
1
与b
1
进行比较,a
1
小,然后将a
2
与b
1
进行比较,a
2
大,则已排好的部分为a
1
b
1
,共比较了2次;然后将a
2
与b
2
进行比较,a
2
小,再将a
3
与b
2
进行比较,a
3
大,则已排好的部分为a
1
b
1
a
2
b
2
,共比较了4次;以此类推,完全排好时共比较了2(n-1)+1=2n-1次。由选项D给出的结果可知,递增序列B的前i/2个元素都比A中的前i/2个元素要大,但比A中的后i/2个元素要小,B的后i/2个元素都比A中的后i/2个元素要大,因此在排序的时候,A中的前i/2个元素只需与b
1
进行比较,当比较到a
i/2+1
时,a
i/2+1
比b
1
大,则已排好的部分为a
1
,a
2
,…,a
i/2
,共比较了i/2+1次;然后将b
2
,b
3
,…,b
i/2
与a
i/2+1
进行比较,都比a
i/2+1
小,当比较到b
i/2+1
时,b
i/2+1
比a
i/2+1
大,则已排好的部分为a
1
,a
2
,…,a
i/2
,b
1
,b
2
,…,b
i/2
,共比较了i+1次;然后将a
i/2+2
,a
i/2+3
,…,a
n
分别与b
i/2+1
进行比较,共比较了n-i/2-2次,完全排好时共比较了i+1+n-i/2-2=n+i/2-1次。
转载请注明原文地址:https://kaotiyun.com/show/VmCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和数据流图,回答问题1至问题4,将解答填入答题纸的对应栏内。[说明]某基于微处理器的住宅安全系统,使用传感器(如红外探头、摄像头等)来检测各种意外情况,如非法进入、火警、水灾等。房主可以在安装该系统时配置安全监控设备(如
阅读以下说明和图,填补流程图中的空缺。【说明】某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示,即汽车底盘进入装配线,零件在多个工位装配,结束时汽车自动完成下线工作。(1)e0和e1表示底盘分别进入装配线0和
阅读下列说明和Java代码,将应填入(n)处的字句写在对应栏内。【说明】已知某企业的采购审批是分级进行的,即根据采购金额的不同由不同层次的主管人员来审批,主任可以审批5万元以下(不包括5万元)的采购单,副董事长可以审批5万元至10万元(不包括
阅读下列说明和C++代码,将应填入(n)处的字句写在对应栏内。【说明】已知某企业欲开发一家用电器遥控系统,即用户使用一个遥控器即可控制某些家用电器的开与关。遥控器如左下所示。该遥控器共有4个按钮,编号分别是0至3,按钮0和2能够遥控打开电器1和
下面是快速排序的伪代码,请填补其中的空缺;伪代码中的主要变量说明如下。A:待排序数组p,r:数组元素下标,从p到rq:划分的位置x:枢轴元素i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴
阅读下列说明,回答问题1至问题3,将解答填入对应栏内。【说明】某地区举行篮球比赛,需要开发一个比赛信息管理系统来记录比赛的相关信息。【需求分析结果】1.登记参赛。球队的信息。记录球队的名称、代表地区、成立时间等信息。系统记录球队每个队员
阅读以下说明,回答问题,将解答填入对应的解答栏内。[说明]计算下列源代码的McCabe环数,画出控制流程图并用罗马数字标出区域。readx,y,z;type=“scalene”;if(x==yorx==zo
收费部门业务活动数据流图如图8-6所示,图中缺少了与“票根上缴”相关的数据流,请指出该数据流的起点和终点。收费部门业务活动数据库的部分关系模式设计如下,请根据说明补充完整,并给出其主键。A.员工((1)、姓名、(2)、(3))B.队别
请使用[说明]中给出的词汇,将该房屋租赁服务系统顶层数据流图(见图5-10)中(1)~(4)空缺处的数据流补充完整。该房屋租赁服务系统第0层数据流图(见图5-11)中缺失了一些数据流,请指出所缺失数据流的名称、起点和终点。
读下列说明和Java代码,将应填入(n)处的字句写在对应栏内。【说明】已知某类库开发商捉供了一套类库,类库中定义了Application类和Document类,它们之间的关系如下图所示,其中,Application类表示应用程序自身,而Docu
随机试题
与西药利尿药联用,可减轻因应用西药利尿药而导致的口渴等副作用的是()。
某男,66岁,体检中发现空腹血糖6.3mmol/L,无自觉症状,医生建议他做葡萄糖耐量试验,试验结果被确诊为糖尿病病人经过两年综合治疗,到医院复查,医生想了解病人近一段时间血糖控制情况,建议他抽血检查糖化血红蛋白。请问糖化血红蛋白可以反映多长时间血糖控
评价化学毒物急性毒性大小最重要的参数是
咯血最常见于
根据案例背景,回答以下问题。某高校新校区修建了6栋学生住宅楼,建成使用后产生了严重的地基不均匀沉降。经初步调查,事故可能与住宅楼地下存在古河道、工程地质勘察单位对该古河道淤泥质土承载力判断失误有关。关于该事故的处理:该事故处理过程应当包括(
有位投资者重点考察了A城和B城。在A城,他坐在街头擦皮鞋,擦皮鞋大婶先把他的一只鞋的鞋带解开,擦完等他付了钱才系上。这个细节让他不得不怀疑这个城市市民的道德水准一一定是有人擦完鞋没付钱跑掉过。在B城,他搭了5次出租车,下车前,5位机都提示:先生,请带好您的
遗传密码的摆动性是指
在考生文件夹下,打开文档WORD1.DOCX,按照要求完成下列操作并以该文件名(WORD1.DOCX)保存文档。将文中所有错词“业经”替换为“液晶”;将标题段文字(“大型TFT液晶显示器市场将复苏”)设置为小三号楷体、34红色、加粗、居中并添加黄色阴影
Influenzaiscausedbyavirus______oneperson______anotherindropletscoughedorsneezedintotheair.Itischaracterizedby
[A]apparent[B]automatic[C]Consequently[D]Decidedly[E]decline[F]delightful[G]enrollments[H]financial[I]intimate[J]junior[K]prof
最新回复
(
0
)