首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用直接插入排序对下面4个序列进行递增排序,元素比较次数最少的是( )。
用直接插入排序对下面4个序列进行递增排序,元素比较次数最少的是( )。
admin
2019-12-10
32
问题
用直接插入排序对下面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
学硕统考专业
相关试题推荐
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。要求:
单处理机系统中,可并行的是____。I进程与进程Ⅱ处理机与设备Ⅲ处理机与通道Ⅳ设备与设备
某机器字长为16位,主存按字节编址,转移指令采用相对寻址,由两个字节组成,第一字节为操作码字段,第二字节为相对位移量字段。假定取指令时,每取一个字节PC自动加1。若某转移指令所在主存地址为2000H,相对位移量字段的内容为06H,则该转移指令成功转移后的目
快速排序算法中,如何选取一个界值(又称为轴元素),影响着快速排序的效率,而且界值也并不一定是被排序序列中的一个元素。例如,我们可以用被排序序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。
在含有15个结点的平衡二叉树上,查找关键字为28(存在该结点)的结点,则依次比较的关键字有可能是()。
适合多道程序运行的存储管理方法中,存储保护主要是()。
以下关于计算机存储器件的叙述,()是不正确的。
下列关于RISC的叙述中,错误的是()。
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
以下是计算两个向量点积的程序段:floatdotproduct(floatx[8],floaty[8]){floatsum=0.0;inti;for(i=0;i<8;i++)sum+=x[i]*y[i]
随机试题
关于CT诊断脊椎创伤的描述,错误的是
行政方法的主要特征是()
Asscientistslearnmoreaboutthecausesofearthquakes,theybecomebetterabletopredictthem.Firstofall,theyknowthat
颈部喉中间腔CT轴扫,甲状软骨的影像形态为
单纯性高血压患者血压高于多少时则应先治疗后拔牙
以下不是舌乳头的是()
甲公司辅助生产车间的制造费用不通过“制造费用”科目核算,直接记入“辅助生产成本”科目。该公司锅炉和机修两个辅助生产车间之间相互提供产品和劳务。锅炉车间的成本按供汽量比例分配,机修车间的修理费用按修理工时比例进行分配。该公司2019年5月有关辅助生产成本的资
建立和完善社会主义市场经济体制,必须要有配套的改革,在上层建筑领域中()。
某市宣传部举办为期一周的专题讲座,讲座时间是周一到周六,一共有四个专题,分别是:宏观政策、社情调查、网络办公以及文化传播。已知一天只能安排一个专题讲座,再加上要考虑教师的时间安排,此次讲座在总体上必须满足以下条件:(1)每个专题至少进行一次;(2)每个
在一个单链表中删除p所指结点时,应执行以下操作:q=p->next:p->data=p->next->data;p->next=______;free(q);
最新回复
(
0
)