2. 考研
  3. 用直接插入排序对下面4个序列进行递增排序，元素比较次数最少的是( )。

用直接插入排序对下面4个序列进行递增排序，元素比较次数最少的是( )。

admin2019-12-10  20
问题 用直接插入排序对下面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://jikaoti.com/ti/l6DjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)