在下列算法中，（）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。A、堆排序B、冒泡排序C、插入排序D、快速排序

正确答案：D
解析：此题考的是各种排序算法。

正确答案：A
解析：对于选项A，冒泡排序将被排序的记录数组R[1..n)垂直排列，每个记录R[i]看作是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。由此可见，冒泡排序第1趟排序之后，最轻的“气泡”一定会被浮到最上面，即能把数据表中最大或最小元素放在其最终位置上。故本题应该选择A。对于选项B，基数排序的基本思想是：从低位到高位依次对待排序的关键码进行分配和收集，经过d趟分配和收集，就可以得到一个有序序列。所以，基数排序第1趟排序之后，得到的是以数据表中各元素的个位进行排序的结果，不一定能把数据表中最大或最小元素放在其最终位置上。对于选项C，快速排序的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序第1趟排序之后，只能使某个关键元素被插入到一个位置，使得该位置之前的所有元素均小于(或大于)关键元素，之后的所有元素均大于(或小于)关键元素。所以，也不一定能把数据表中最大或最小元素放在其最终位置上。对于选项D，归并排序是将两个或两个以上的有序子表合并成一个新的有序表。所以，归并排序第1趟排序之后，只能得到两两有序的一个序列，并不能把数据表中最大或最小元素放在其最终位置上。

正确答案：A
[解析]B、C、D三种排序在一趟排序结束后都能选出一个元素，放在其最终位置上，只有插入排序，做一趟排序完成的是把当前待排序列中的第一个元素插入到有序序列的适当位置，但并不能保证这个位置是最终位置．

答案：B

解析：

答案：B

解析：

答案：D

解析：

参考答案：B

正确答案：C
解析：在插入排序中，如果待排序列中的最后一个元素其关键字值为最小，则在最后一趟开始之前，前n-1个排好序的元素都不在其最终位置上，与排好序后的位置相差一个位置。因此，本题正确答案为选项C。

答案：A

解析：

答案：C

解析：

答案：D

解析：