数据结构考研分类复习真题 第十章 答案[12]

采用直接插入排序算法因为记录序列已基本有序直接插入排序比较次数少且由于少量次序不对的记录与正确位置不远使直接插入排序记录移动次数也相对较少故选直接插入排序算法

各带标号语句的频度()n ()n ()(n+)(n)/ ()n(n)/ ()n

时间复杂度O(n⊃) 属于直接选择排序

将r+(即第个)后的元素向后移动并将放入r+处结果为

()使用二分法插入排序所要进行的比较次数与待排序的记录的初始状态无关不论待排序序列是否有序已形成的部分子序列是有序的二分法插入首先查找插入位置插入位置是判定树查找失败的位置失败位置只能在判定树的最下两层上

()一些特殊情况下二分法插入排序要比直接插入排序要执行更多的比较例如在待排序序列已有序的情况下就是如此

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []