首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
递增序列A(a1，a2，…，abn)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为_____________时，归并过程中元素的比较次数最多。
递增序列A(a1，a2，…，abn)和B(b1，b2，…，bn)的元素互不相同，若需将它们合并为一个长度为2n的递增序列，则当最终的排列结果为_____________时，归并过程中元素的比较次数最多。
admin
2021-01-13
51
问题
递增序列A(a
1
，a
2
，…，ab
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
i
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次。由选项A给出的结果可知，递增序列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
n
分别与b
i/2+1
进行比较，共比较了n一i／2—2次，完全排好时共比较了i+1+n—i／2—2=n+j／2—1次。
转载请注明原文地址:https://www.kaotiyun.com/show/fCCZ777K
本试题收录于：
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图，回答以下问题，将解答填入答题纸的对应栏内。【说明】某航空公司会员积分系统(CFrequentFlyer)的主要功能描述如下：乘客只要办理该航空公司的会员卡，即可成为普卡会员(CBasic)。随着飞行里程数的积累，可以从普卡会员升级到
阅读下列说明和数据流图，回答问题l至问题3，将解答填入答题纸的对应栏内。【说明】图书管理系统旨在用计算机对图书进行管理，包括图书的购入、借阅、归还以及注销。管理人员可以查询某位读者、某种图书的借阅情况，还可以对当前图书借阅情况进行一些统计，给出统计表格
阅读下列函数说明和C++代码，将应填入(n)处的字句写在答题纸对应栏内。【说明】在销售系统中常常需要扣印销售票据，有时需要在一般的票据基础上打印脚注。这样就需要动态地添加一些额外的职责。如下展示了Decorator(修饰)模式。Salesorder对象
阅读下列说明和图，回答问题l至问题3，将解答填入答题纸的对应栏内。【说明】C市刚开通了地铁线，为方便乘客，计划开发自动售票系统。该公司在每一个地铁站放置了多台自动售票机，每一台售票机有一唯一编号，售票记录统一汇总主机。自动售票机只发售从该站起始的各种
阅读以下说明和图，回答问题l至问题3．将解答填入答题纸的对应栏内。【说明】某时装邮购提供商拟开发订单处理系统，用于处理客户通过电话、传真、邮件或web站点所下订单。其主要功能如下：(1)增加客户记录。将新客广信息添加到客户文件，并分配一个客户号以备后
阅读以下说明和C代码，根据要求回答问题1～问题3。【说明】某工程计算中要完成多个矩阵相乘(链乘)的计算任务。两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算Am×n*Bn×p，需要m
某大型商场内安装了多个简易的纸巾售卖机，自动出售2元钱一包的纸巾，且每次仅售出一包纸巾。纸巾售卖机的状态图如图16-2所示。采用状态(State)模式来实现该纸巾售卖机，得到如图16-3所示的类图。其中类State为抽象类，定义了投币、退币、
阅读下列说明和图，回答问题1至问题4，将解答填入答题纸的对应栏内。【说明】某慕课教育平台欲添加在线作业批改系统，以实现高效的作业提交与批改，并进行统计。学生和讲师的基本信息已经初始化为数据库中的学生表和讲师表。系统的主要功能如下。(1)提交作业。验证
某宾馆拟开发一个宾馆客房预订子系统，主要是针对客房的预订和入住等情况进行管理。【需求分析结果】(1)员工信息主要包括员工号、姓名、出生年月、性别、部门、岗位、住址、联系电话和密码等信息。岗位有管理和服务两种。岗位为“管理”的员工可以更改(添加、删除和修
某宾馆拟开发一个宾馆客房预订子系统，主要是针对客房的预订和入住等情况进行管理。【需求分析结果】(1)员工信息主要包括员工号、姓名、出生年月、性别、部门、岗位、住址、联系电话和密码等信息。岗位有管理和服务两种。岗位为“管理”的员工可以更改(添加、删除和修
随机试题
喷雾水枪不可扑救带电设备火灾、可燃粉尘火灾及部分油品火灾等。()
开放性管理信息系统的出现，为了防止未经授权者非法接触需要保密的信息，要求我们在实施管理信息系统时要进行()
患者，女性，48岁，主诉右颊部肿块，检查：右腮腺区可及一活动性肿块，2cm×2cm，质中，界清，无明显压痛。如果要检查腮腺导管口的情况，如何寻找其位置
我国古代最杰出的医德经典是
社保经办机构和定点医疗机构签订协议的有效期为外配处方保存备查的时间为
发展房地产业，调整住房供应结构，按照()原则，加强对房地产一、二级市场和租赁市场的调控。
外商提供的纯棉面料进口时，海关准予保税的额度可以是()。台方不作价提供的工业缝纫机，作为加工贸易不作价设备备案的步骤和条件为()。
超市采购两种不同口味的散装巧克力共X斤，售价分别为30元/斤和50元/斤，预计总收入为Y元。如将其混合后以40元/斤的价格销售，总收入将为1.25Y元。问采购了30元/斤的巧克力多少斤?
战术结构主要是由战术观念、战术指导思想、战术意识、战术知识、战术形式和战术行动等六个要素构成的。
山区
最新回复
(
0
)
