1、在下列算法中，（）算法可能出现下列情况：在最后一趟开始之前，所有元素都不在最终位置上。
- A：堆排序
- B：冒泡排序
- C：直接插入排序
- D：快速排序
解析
在直接插入排序中，若待排序列中的最后一个元素应插入表中的第一个位置，则前面的有序子序列中的所有元素都不在最终位置上。
答案：C
2、对序列{98,36,-9,0,47,23,1,8,10,7}采用希尔排序，下列序列（）是增量为4的一趟排序结果。
- A：{98,7,-9,0,47,23,1,8,98,36}
- B：{-9,0,36,98,1,8,23,47,7,10}
- C：{36,98,-9,0,23,47,1,8,7,10}
- D：以上都不对
解析
增量为4意味着所有相距为4的记录构成一组，然后在组内进行直接插入排序，经观察，只有选项A满足要求。
答案：A
3、用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是（）。
- A：2
- B：3
- C：4
- D：5
解析
首先，第二个元素为1，是整个序列中的最小元素，因此可知该希尔排序为从小到大排序。然后考虑增量问题，
- 若增量为2，则第1+2个元素4明显比第1个元素9要小，A排除；若增量为3，则第i,i+3,i+6（i=1,2,3）个元素都为有序序列，符合希尔排序的定义；
- 若增量为4，则第1个元素9比第1+4个元素7要大，C排除；
- 若增量为5，则第1个元素9比第1+5个元素8要大，D排除。
故选B。
答案：B
4、一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准，从小到大得到的一次划分结果为（）。
- A：（38,40,46,56,79,84）
- B：（40,38,46,79,56,84）
- C：（40,38,46,56,79,84）
- D：（40,38,46,84,56,79）
解析
以46为基准元素，首先从后向前扫描比46小的元素，并与之进行交换，而后从前向后扫描比46大的元素并将46与该元素交换，得到（40,46,56,38,79,84）。此后，继续重复从后向前扫描与从前往后扫描的操作，直到46处于最终位置，答案选C。
答案：C
5、快速排序算法在（）情况下最不利于发挥其长处。
- A：要排序的数据量太大
- B：要排序的数据中含有多个相同值
- C：要排序的数据个数为奇数
- D：要排序的数据已基本有序
解析
当待排序数据为基本有序时，每次选取第n个元素为基准，会导致划分区间分配不均匀，不利于发挥快速排序算法的优势。相反，当待排序数据分布较为随机时，基准元素能将序列划分为两个长度大致相等的序列，这时才能发挥快速排序的优势。
答案：D
6、对数据序列{8,9,10,4,5,6,20,1,2}采用冒泡排序（从后向前次序进行，要求升序），需要进行的趟数至少是（）。
- A：3
- B：4
- C：5
- D：8
解析
从后向前“冒泡”的过程为，第一趟{1,8,9,10,4,5,6,20,2}，第二趟{1,2,8,9,10,4,5,6,20}，第三趟{1,2,4,8,9,10,5,6,20}，第四趟{1,2,4,5,8,9,10,6,20}，第五趟{1,2,4,5,6,8,9,10,20}，经过第五趟冒泡后，序列已经全局有序，故选C。
实际每趟冒泡发生交换后可以判断是否会导致新的逆序对，如果不会产生，则本趟冒泡之后序列全局有序，所以最少5趟即可。
答案：C
7、对下列4个序列，以第一个关键字为基准用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是（）。
- A：92,96,88,42,30,35,110,100
- B：92,96,100,110,42,35,30,88
- C：100,96,92,35,30,110,88,42
- D：42,30,35,92,100,96,88,110
解析
对各序列分别执行一趟快速排序，可做如下分析（以A为例）：由于枢纽值为92，因此35移动到第一个位置，96移动到第六个位置，30移动到第二个位置，再将枢纽值移动到30所在的单元，即第五个位置，所以A中序列移动的次数是4。
同样也可以分析出B中序列的移动次数为8，C中序列的移动次数为4，D中序列的移动次数为2。
答案：B
8、对n个关键字进行快速排序，最大递归深度为（）,最小递归深度为（）。
- A：1
- B：n
- C：
- D：n
解析
快速排序过程构成一个递归树，递归深度即递归树的高度。枢纽值每次都将子表等分时，递归树的高为；枢纽值每次都是子表的最大值或最小值时，递归树退化为单链表，树高为n。
答案：B，C
9、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）。
- A：递归次数与初始数据的排列次序无关
- B：每次划分后，先处理较长的分区可以减少递归次数
- C：每次划分后，先处理较短的分区可以减少递归次数
- D：递归次数与每次划分后得到的分区的处理顺序无关
解析
递归次数与各元素的初始排列有关。若每次划分后分区比较平衡，则递归次数少；若区分不平衡，递归次数多。递归次数与处理顺序是没有关系的。
答案：D
10、为实现快速排序算法，待排序序列宜采用的存储方式是（）。
- A：顺序存储
- B：散列存储
- C：链式存储
- D：索引存储
解析
绝大部分内部排序只适用于顺序存储结构。快速排序在排序的过程中，既要从后向前查找，又要从前向后查找，因此宜采用顺序存储。
