数据结构题目收录（二十二）

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：${\log }_{2}n$
• D：n${\log }_{2}n$

解析

快速排序过程构成一个递归树，递归深度即递归树的高度。枢纽值每次都将子表等分时，递归树的高为${\log }_{2}n$；枢纽值每次都是子表的最大值或最小值时，递归树退化为单链表，树高为n。

答案：B，C

9、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）。

• A：递归次数与初始数据的排列次序无关
• B：每次划分后，先处理较长的分区可以减少递归次数
• C：每次划分后，先处理较短的分区可以减少递归次数
• D：递归次数与每次划分后得到的分区的处理顺序无关

解析

递归次数与各元素的初始排列有关。若每次划分后分区比较平衡，则递归次数少；若区分不平衡，递归次数多。递归次数与处理顺序是没有关系的。

答案：D

10、为实现快速排序算法，待排序序列宜采用的存储方式是（）。

• A：顺序存储
• B：散列存储
• C：链式存储
• D：索引存储

解析

绝大部分内部排序只适用于顺序存储结构。快速排序在排序的过程中，既要从后向前查找，又要从前向后查找，因此宜采用顺序存储。

答案：A