选择题 22.  有字符序列(Q,H,C,Y,P,A,M,S,R,D,F,x),那么新序列(F,H,C,D,P,A,M,Q,R,S,Y,X)是下列______算法一趟扫描结果。
【正确答案】 B
【答案解析】 对于选项A,堆排序的思想是对于给定的n个记录,初始时把这些记录看作一棵顺序存储的二叉树,然后将其调整为一个大顶堆,然后将堆的最后一个元素与堆顶元素(即二叉树的根结点)进行交换后,堆的最后一个元素即为最大记录;接着将前n-1个元素(即不包括最大记录)重新调整为一个大顶堆,再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录,重复该过程,直到调整的堆中只剩一个元素时为止,该元素即为最小记录,此时可得到一个有序序列。
   对于选项B,快速排序的原理如下:对于一组给定的记录,首先,通过一趟排序后,将原序列分为两部分,其中前半部分的所有记录均比后半部分的所有记录小,然后再依次对前后两部分的记录进行快速排序,递归该过程,直到序列中的所有记录均有序为止。
   对于选项C,希尔排序的实质是分组插入排序,该方法又称缩小增量排序,基本思想如下:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成),分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因此,直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的。
   对于选项D,冒泡排序的原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟排序后,最大或最小的数字被交换到了最后一位,针对所有的元素重复以上的步骤,每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
   所以,本题的答案为B。