首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用直接插入排序对下面4个序列进行递增排序,元素比较次数最少的是( )。
用直接插入排序对下面4个序列进行递增排序,元素比较次数最少的是( )。
admin
2019-12-10
30
问题
用直接插入排序对下面4个序列进行递增排序,元素比较次数最少的是( )。
选项
A、94,32,40,90,80,46,21,69
B、32,40,21,46,69,94,90,80
C、21,32,46,40,80,69,90,94
D、90,69,80,46,21,32,94,40
答案
C
解析
对于直接插入排序,原始序列越接近有序,则比较次数越少,观察序列,C选项最接近有序。
说明:本题目测即可,如果要严格来比较,则可用线性代数中求逆序数的方法,序列逆序数越小则越接近有序。对于序列中某个元素a,其逆序数为序列中a之后比a小的元素的个数,整个序列的逆序数为所有元素逆序数之和。
对于A,各元素逆序数为94:7;32:1;40:1;90:4;80:3;46:1;21:0;69:0。
因此,序列A的逆序数为7+1+1+4+3+1+0+0=17。
对于B,各元素逆序数为32:1;40:1;21:0;46:0;69:0;94:2;90:1;80:0。
因此,序列A的逆序数为1+1+0+0+0+2+1+0=5。
对于C,各元素逆序数为21:0;32:0;46:1;40:0;80:1;69:0;90:0;94:0。
因此,序列A的逆序数为0+0+1+0+1+0+0+0=2。
对于D,各元素逆序数为90:6;69:4;80:4;46:3;21:0;32:0;94:0;40:0。
因此,序列A的逆序数为6+4+4+3+0+0+0+0=17。 可以看出C选项序列的逆序数最小,即C选项最接近有序,所需比较次数最少。
转载请注明原文地址:https://kaotiyun.com/show/yQ3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
元素a,b,c,d,e依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素d开头的序列个数是____。
下图是某存储芯片的引脚图,请回答:(1)这个存储芯片的类型(是RAM还是ROM)?这个存储芯片的容量?(2)若地址线增加一根,存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别。(4)
任意给定1,2…….,n指定为一棵树的先根遍历序列;同时任意给定这n个数值(1,2…….,n)的一个排列p1,p2…….pn为这棵树的后根遍历序列。(1)根据这样的先根遍历序列和后根遍历序列,是否都可以得到一棵树?如果能够,请简述理由(不要求形式化证明)
若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点,则下面最节省运算时间的存储方式是()。
假设二叉树采用二叉链表存储结构存储,试设计一个算法,求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。
利用逐点插入建立序列(50,72,43,85,75,20,35,45.,65,30)对应的二叉排序树以后,要查找元素30要进行元素间的比较次数是()。
如下图所示为一个TCP主机中的拥塞窗口的变化过程,这里最大数据段长度为1024字节,请回答如下问题:该TCP协议的初始阀值是多少?为什么?
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
原码两位乘中,符号位单独处理,参加操作的数是()。
随机试题
领导科学在我国真正形成于我国进入改革开放和社会主义现代化建设时期,是__________________的必然产物。
CAD的含义是________________。
患者,男性,35岁,不洁性生活史后7天后出现尿道口发痒,红肿,随后尿道流出脓性分泌物,可能的诊断为
滴眼剂使用正确的是
下列有关氨基糖苷类抗生素的叙述错误的是
较坚硬岩或较软硬岩层,岩体较完整,中厚层结构属于()级公路隧道围岩。
社会工作者张丽主要从事青少年社会工作,则她针对青少年的改变及发展性需要,可以开展的各类小组有()。
若关系模式R(U,F)中的所有非主属性对任何候选关键字都不存在传递依赖,则称关系R是属于第三范式的。()
甲每5天进城一次,乙每9天进城一次,丙每12天进城一次,某天三人在城里相遇,那么下次相遇至少要:
MissPage’sattitudetowardBlackFridayisThe"holidayseason"(Paragraph13)probablyrefersto
最新回复
(
0
)