首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用直接插入排序对下面4个序列进行递增排序,元素比较次数最少的是( )。
用直接插入排序对下面4个序列进行递增排序,元素比较次数最少的是( )。
admin
2019-12-10
17
问题
用直接插入排序对下面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
学硕统考专业
相关试题推荐
假定不采用Cache和指令预取技术,且机器处于“开中断”状态,则在下列有关指令执行的叙述中,错误的是____。
对于下列关键字序列,不可能构成某二叉排序树中一条查找路径的序列是____。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。Pl每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中:P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
一个快速以太网交换机的端口速率为100Mbps,若该端口可以支持全双工传输数据,那么该端口实际的传输带宽是()。
某图形显示器的分辨率为640×480,刷新频率为50Hz,且假定水平回扫期和垂直回扫期各占水平扫描周期和垂直扫描周期的20%,试计算图形显示器的行频、水平扫描周期、每个像素的读出时间和视频带宽。若分辨率提高到1024×768,刷新频率提高到60Hz,再次计
采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51;(1)构造散列表(画示意图);(2)装填因子;(3)等概率
下列叙述正确的个数是()。1)向二排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B一树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右子树的高度差的绝对值
关于Hash查找说法不正确的有()个。Ⅰ.采用链地址法解决冲突时,查找一个元素的时间是相同的Ⅱ.采用链地址法解决冲突时,若插入操作规定总是在链首,则插入任一个元素的时间是相同的Ⅲ.用链地址法解决冲突易引起聚集(堆积)现象
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算
随机试题
商业秘密必须具有【】
夜热早凉,热退无汗,热自阴来,以下何方主之
A.VossiusringB.SoemmeringringC.MorgagniancataractD.CouchingoflensE.Elaschnigpearls挫伤性白内障在瞳孔缘部色素上皮细胞脱落而形成的混浊()
优惠利率是指低于一般利率水平的利率。()
当前,在以零部件生产和注重工艺专业化为主要内容的产业内,国际分工的主要形式是()。
商业信用是购买方占用卖方资金而形成的借贷关系。()
改革的实质和目的是()。
A、 B、 C、 B所给出的问题是一个表示请求的疑问句(MayI…),所以表示同意的选项(B)的回答“Sure”是符合语境的恰当选择。注意不要只听到了schedule就误选了(A),也不要将copy误听为coffee而
A、MostBritishholidaysaremarkedonthecalendar.B、AllBritishholidaysarebasedonlocalcustomsandtraditions.C、Differen
A、Shewantstohaveapromotion.B、Shehopestoearnmoremoney.C、Shewasmoreinterestedininternationalfinance.D、Shewase
最新回复
(
0
)