计算机科学与技术操作系统考研真题答案
11．对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（ ）。A．排序的总趟数B．元素的移动次数C．使用辅助空间的数量D．元素之间的比较次数【答案】D查看答案【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。折半插入排序的时间复杂度仍为O（n2）,所以两者之间的不同只可能是元素之间的比较次数。12．假定基准程序A在某计算机上的运行时间为100秒，其中90秒为CPU时间...