首页
登录
从业资格
用插入排序和归并排序算法对数组<3,1,4,1,5,9,6,5>进行从小到大排序
用插入排序和归并排序算法对数组<3,1,4,1,5,9,6,5>进行从小到大排序
考试题库
2022-08-02
28
问题
用插入排序和归并排序算法对数组<3,1,4,1,5,9,6,5>进行从小到大排序,则分别需要进行( )次数组元素之间的比较。A.12,14B.10,14C.12,16D.10,16
选项
A.12,14
B.10,14
C.12,16
D.10,16
答案
A
解析
插入排序的基本思想是逐个将待排序元素插入到已排序的有序表中。假设n个待排序元素存储在数组R[n+1]中(R[0]预留),则:
(1)初始时数组R[1..1]中只包含元素R[1],则数组R[1..1]必定有序;
(2)从i=2到n,执行步骤3;
(3)此时,数组R被划分成两个子区间,分别是有序区间R[1..i-1]和无序区间R[i..n],将当前无序区间的第1个记录R
插入到有序区间R[1..i]中适当的位置上,使R[1..i]变为新的有序区间。
在实现的过程中,设置监视哨R[0],并从R[i-1]到R[0]查找元素R
的插入位置
那么用插入排序对数组<3,1,4,1,5,9,6,5>进行排序的过程为:
原元素序列:监视哨(3),1,4,1,5,9,6,5
第一趟排序:1(1,3),4,1,5,9,6,51插入时与3比较1次
第二趟排序:4(1,3,4),1,5,9,6,54插入时与3比较1次
第三趟排序:1(1,1,3,4),5,9,6,51插入时分别与4、3、1比较1次,共比较3次
第四趟排序:5(1,1,3,4,5),9,6,55插入时与4比较1次
第五趟排序:9(1,1,3,4,5,9),6,59插入时与5比较1次
第六趟排序:6(1,1,3,4,5,6,9),56插入时与9和5分别比较1次,共比较2次
第七趟排序:5(1,1,3,4,5,5,6,9)5插入时与9,6,5分别比较1次,共比较3次。
那么整个排序过程需要比较的次数为12次。
归并排序的思想是将两个相邻的有序子序列归并为一个有序序列,然后再将新产生的相邻序列进行归并,当只剩下一个有序序列时算法结束。其基本步骤如下:
(1)将n个元素的待排序序列中每个元素看成有序子序列,对相邻子序列两两合并,则将生成n/2个子有序序列,这些子序列中除了最后一个子序列长度可能小于2外,其他的序列长度都等于2;
(2)对上述n/2个长度为2的子序列再进行相邻子序列的两两合并,则产生n/4个子有序序列,同理,只有最后一个子序列的长度可能小于4;
(3)第i趟归并排序为,对上述n/i个长度为i的子序列两两合并,产生n/2i个长度为2i的子有序序列;
(4)重复执行此步骤,直到生成长度为n的序列为止。
那么用归并排序对数组<3,1,4,1,5,9,6,5>进行排序的过程为:
原元素序列:3,1,4,1,5,9,6,5
第一趟排序:[1,3],[1,4],[5,9],[5,6]比较4次
第二趟排序:[1,1,3,4],[5,5,6,9]前半部分比较3次,后半部分比较3次
第三趟排序:[1,1,3,4,5,5,6,9]5分别与1,1,3,4比较一次,共比较4次,后面的序列都不小于5,因此可以直接复制到结果序列。
所以整个排序过程需要比较的次数为14次。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2410312.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
在信息管理中,哪些是信息进行加工处理的最基本方式:__()__①变化、排序、核
MD5是()算法,对任意长度的输入计算得到的结果长度为(请作答此空)位。A.5
假设所有的作业同时到达,平均周转时间最短的调度算法是()。A.先来先服务
()排序又被称为缩小增量排序,是对直接插入排序方法的改进。A.简单选择 B.
关于二叉排序树的说法,错误的是( )。A.对二叉排序树进行中序遍历,必定得到结
已知有序数组a的前10000个元素是随机整数,现需查找某个整数是否在该数组中。以
根据历史数据,确定一个就诊人员是否可能患心脏病,可以采用( )算法。A.C4.
关于聚类算法K-Means和DBSCAN的叙述中,不正确的是( )。A.K-M
以下加密算法中适合对大量的明文消息进行加密传输的是( )A.RSA B.SH
已知有序数组a的前10000个元素是随机整数,现需查找某个整数是否在该数组中。以
随机试题
Weareallconcernedforthe(secure)______ofthepassengersontheaircraft.Se
所示刚架支座A下移量为a,转角为α则B端竖向位移( )。 A、与h、l、
操作风险专项报告由相关业务部门负责编写,分析报告各项业务或产品中存在的风险隐患,
下列各项,不属妊娠绝对禁用药物的是()A.大戟 B.巴豆 C.麝香
下列关于证券公司柜台市场信息披露的说法,错误的是()。A.涉及客户隐私的信息不
十九畏中,巴豆畏A.甘草 B.朴硝 C.藜芦 D.牵牛子 E.郁金
如果将全社会固定资产投资完成额转化成固定资本形成总额,则需要额外扣除的项目有(
下列关于汽车库,修车库的火灾危险性描述中,错误的是()。A.起火快,燃烧猛
人在每一瞬间,将心理活动选择了某些对象而忽略了另一些对象。这一特点指的是注意的(
缩泉丸的药物组成是A.益智仁、乌药、山药 B.菟丝子、乌药、山药 C.益智仁
最新回复
(
0
)