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

╰半橙微兮° 2024-03-31 09:36 67阅读 0赞

#### 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 \\log\_2n log2n
 *  D：n log ⁡ 2 n \\log\_2n log2n

###### 解析 ######

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