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

1、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为以“趟”。下列序列中，不可能是快速排序第二趟结果的是（）。

• A：5,2,16,12,28,60,32,72
• B：2,16,5,28,12,60,32,72
• C：2,12,16,5,28,32,72,60
• D：5,2,12,28,16,32,72,60

解析

答案：D

2、简单选择排序算法的比较次数和移动次数分别为（）。

• A：O(n)，O(${\log }_{2}n$)
• B：O(${\log }_{2}n$)，O($n^2$)
• C：O($n^2$)，O(n)
• D：O(n${\log }_{2}n$)，O(n)

解析

答案：C

3、设线性表中每个元素有两个数据项$k_1$和$k_2$，现对线性表按以下规则进行排序：先看数据项$k_1$，$k_1$值小的元素在前，大的元素在后；在$k_1$值相同的情况下，再看$k_2$，$k_2$值小的在前，大的元素在后。满足这种要求的排序方法是（）。

• A：先按$k_1$进行直接插入排序，再按$k_2$进行简单选择排序
• B：先按$k_2$进行直接插入排序，再按$k_1$进行简单选择排序
• C：先按$k_1$进行简单选择排序，再按$k_2$进行直接插入排序
• D：先按$k_2$进行简单选择排序，再按$k_1$进行直接插入排序

解析

本题思路来自基数排序的LSD，首先应该确定$k_1$、$k_2$的排序顺序，若先排$k_1$再排$k_2$，则排序结果不符合题意，排除A和C。

再考虑算法的稳定性，当$k_2$排好序后，再对$k_1$排序，若对$k_1$排序采用的算法是不稳定的，则对于$k_1$相同而$k_2$不同的元素可能会改变相对次序，从而不一定能满足题设要求。

直接插入排序算法是稳定的，而简单选择排序算法是不稳定的，故只能选D。

答案：D

4、在含有n个关键字的小根堆中，关键字最大的记录有可能存储在（）位置。

• A：n/2
• B：n/2+2
• C：1
• D：n/2-1

解析

这是小根堆，关键字最大的记录一定存储在这个堆所对应的完全二叉树的叶子结点中；又因为二叉树中的最后一个非叶子结点存储在$\lfloor n/2\rfloor$中，所以关键字最大记录的存储范围为$\lfloor n/2\rfloor$+1~n，所以应该选B。

答案：B

5、向具有n个结点的堆中插入一个新元素的时间复杂度为（），删除一个元素的时间复杂度为（）。

• A：O(1)
• B：O(n)
• C：O(${\log }_{2}n$)
• D：O(n${\log }_{2}n$)

解析

在向有n个元素的堆中插入一个新元素时，需要调用一个向上调整的算法，比较次数最多等于树的高度减1，由于树的高度为$\lfloor {\log }_{2}n\rfloor$+1，所以堆的向上调整算法的比较次数最多等于$\lfloor {\log }_{2}n\rfloor$。此处需要注意，调整堆和建初始堆的时间复杂度是不一样的。

答案：C，C

6、构建n个记录的初始堆，其时间复杂度为（）；对n个记录进行堆排序，最坏情况下其时间复杂度为（）。

• A：O(n)
• B：O($n^2$)
• C：O(${\log }_{2}n$)
• D：O(n${\log }_{2}n$)

解析

建堆过程中，向下调整的时间与树高h有关，为O(h)。每次向下调整时，大部分结点的高度都较小。因此，可以证明在元素个数为n的序列上建堆，其时间复杂度为O(n)。无论是在最好情况下还是在最坏情况下，堆排序的时间复杂度均为O($n{\log }_{2}n$)。

答案：A，D

7、对关键码序列{23,17,72,60,25,8,68,71,52}进行堆排序，输出两个最小关键码后的剩余堆是（）。

• A：{23,72,60,25,68,71,52}
• B：{23,25,52,60,71,72,68}
• C：{71,25,23,52,60,72,68}
• D：{23,25,68,52,60,72,71}

解析

筛选法初始建堆为{8,17,23,52,25,72,68,71,60}，输出8后重建的堆为{17,25,23,52,60,72,68,71}，输出17后重建的堆为{23,25,68,52,60,72,71}。

答案：D

8、已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（）。

• A：1
• B：2
• C：4
• D：5

解析

首先18与10比较，交换位置，再与25比较，不交换位置。一共比较了2次。

答案：B

9、在下列4种排序方法中，排序过程中的比较次数与序列初始状态无关的是（）。

• A：选择排序法
• B：插入排序法
• C：快速排序法
• D：冒泡排序法

解析

选择排序算法的比较次数始终为n(n-1)/2，与序列状态无关。

答案：A

10、已知小根堆为8,15,10,21,34,16,12,删除关键字8之后需要重建堆，在此过程中，关键字之间的比较次数是（）。

• A：1
• B：2
• C：3
• D：4

解析

答案：C