首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
递增序列A(a1,a2,…,abn)和B(b1,b2,…,bn)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为_____________时,归并过程中元素的比较次数最多。
递增序列A(a1,a2,…,abn)和B(b1,b2,…,bn)的元素互不相同,若需将它们合并为一个长度为2n的递增序列,则当最终的排列结果为_____________时,归并过程中元素的比较次数最多。
admin
2021-01-13
21
问题
递增序列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://kaotiyun.com/show/fCCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图,回答以下问题,将解答填入答题纸的对应栏内。【说明】某电子商务系统采用以数据库为中心的集成方式改进购物车的功能,详细需求如下:1.加入购物车。顾客浏览商品,点击加入购物车,根据商品标识从商品表中读取商品信息,并
阅读以下说明和程序流程图,将应填入(n)处的字句写在答题纸对应栏内。【说明】假定用一个整型数组表示一个长整数,数组的每个元素存储长整数的一位数字,则实际的长整数m表示为:m=a[k]×10k-2+a[k一1]×10k-3+…+a[3]×10+a[2]其
阅读以下函数说明和Java代码,将应填入(n)处的字句写在答题纸对应栏内。【说明】很多时候,希望某些类只有一个或有限的几个实例,典型解决方案是所谓单身(Singleton)模式。但在多线程情况下,Singleton模式有可能出现问题,需要进行同步检查。
某基于微处理器的住宅系统,使用传感器(如红外探头、摄像头等)来检测各种意外情况,如非法进入、火警、水灾等。房主可以在安装该系统时配置安全监控设备(如传感器、显示器、报警器等),也可以在系统运行时修改配置,通过录像机和电视机监控与系统连接的所有传感
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某慕课教育平台欲添加在线作业批改系统,以实现高效的作业提交与批改,并进行统计。学生和讲师的基本信息已经初始化为数据库中的学生表和讲师表。系统的主要功能如下。(1)提交作业。验证
阅读下列说明和C++代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某软件系统中,已设计并实现了用于显示地址信息的类Address(如图5—1所示),现要求提供基于。Dutch语言的地址信息显示接口。为了实现该要求并考虑到以后可能还会出现新的
阅读下列说明,回答问题l至问题3,将解答填入答题纸的对应栏内。【说明】某销售公司当前的销售业务为商城实体店销售。现该公司拟开展网络销售业务,需要开发一个信息化管理系统。请根据公司现有业务及需求完成该系统的数据库设计。【需求描述】(1)记录公司所有员
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某文件管理系统中定义了类OfficeDoc和DocExplorer。当类OfficeDoc发生变化时,类DocExplorer的所有对象都要更新其自身的状态
结点数目为n的二叉查找树(二叉排序树)的最小高度为(52)、最大高度为(53)。
为了大幅度提高处理器的速度,当前处理器中采用了指令及并行处理技术,如超标量(Superscalar),它是指(1)。流水线组织是实现指令并行的基本技术,影响流水线连续流动的因素除数据相关性、转移相关性外,还有(2)和(3);另外,要发挥流水线的效率,还必须
随机试题
有关TCP和UDP的说法中错误的是()
医疗机构取得麻醉药品、第一类精神药品购用印鉴卡,说法正确的是
A.低张性宫缩乏力B.高张性宫缩乏力C.原发性宫缩乏力D.继发性宫缩乏力E.正常宫缩
门静脉与腔静脉之间的交通支,临床上最具有重要意义的是
某工业引进项目,基础数据如下:1.项目的建设期为2年,该项目的实施计划为:第一年完成项目全部投资的40%,第二年完成60%,第三年项目投产并且达到100%设计生产能力,预计年产量为3000万t。2.全套设备拟从国外进口,重量1850t,装运
本工程是54m+128m+54m预应力混凝土系杆拱连续梁高架桥工程,上部结构主纵梁为箱形断面的预应力混凝土连续梁,采用预埋金属波纹管成孔。系杆拱采用圆端形钢管混凝土拱结构,吊索采用预应力高强度钢丝。系杆拱设于中跨,通过吊索与主纵梁组成整体受力结构,钢拱每侧
甲公司(非投资性主体)为乙公司、丙公司的母公司,乙公司为投资性主体,拥有两家全资子公司,两家子公司均不为乙公司的投资活动提供相关服务,丙公司为股权投资基金,拥有两家联营企业,丙公司对其拥有的两家联营企业按照公允价值考核和评价管理层业绩。不考虑其他因素,下列
Whenwillshowersreachsouth-westEnglandandthesoutherncoastofWales?
A、Theinventordecideswhotheexpiredpatentgoesto.B、Theinventormaystriveforalongervalidtimespan.C、Theinventorwi
TheAbortionClinicShootings:Why?A)Asthenationheardwithsorrowthenewsofthedeplorableshootingspreeatabortionfaci
最新回复
(
0
)