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

1、在将序列(6,1,5,9,8,4,7)建成大根堆时，正确的序列变化过程是（）。

• A：6,1,7,9,8,4,5->6,9,7,1,8,4,5->9,6,7,1,8,4,5->9,8,7,1,6,4,5
• B：6,9,5,1,8,4,7->6,9,7,1,8,4,5->9,6,7,1,8,4,5->9,8,7,1,6,4,5
• C：6,9,5,1,8,4,7->9,6,5,1,8,4,7->9,6,7,1,8,4,5->9,8,7,1,6,4,5
• D：6,1,7,9,8,4,5->7,1,6,9,8,4,5->7,9,6,1,8,4,5->9,7,6,1,8,4,5->9,8,6,1,7,4,5

解析

要熟练掌握建堆和调整堆的方法，从序列末尾开始向前遍历，变换过程如下图所示。

答案：A

2、下列关于大根堆（至少含2个元素）的叙述中，正确的是（）。

Ⅰ、可以将堆视为一棵完全二叉树
Ⅱ、可以采用顺序存储方式保存堆
Ⅲ、可以将堆视为一棵二叉排序树
Ⅳ、堆中的次大值一定在根的下一层

• A：仅Ⅰ、Ⅱ
• B：仅Ⅱ、Ⅲ
• C：仅Ⅰ、Ⅱ和Ⅳ
• D：Ⅰ、Ⅲ和Ⅳ

解析

堆是一棵完全树，采用一位数组存储，故Ⅰ、Ⅱ正确。大根堆只要求根结点值大于左右孩子值，并不要求左右孩子值有序，Ⅲ错误。堆的定义是递归的，所以其左右子树也是大根堆，所以堆的次大值一定是其左孩子或右孩子，Ⅳ正确。

答案：C

3、以下排序方法中，（）在一趟结束后不一定能选出一个元素放在其最终位置上。

• A：简单选择排序
• B：冒泡排序
• C：归并排序
• D：堆排序

解析

插入排序不能保证在一趟结束后一定有元素放在最终位置上。事实上，归并排序也不能保证。

例如，序列{6,5,7,8,2,1,4,3}进行一趟2路归并排序（从小到大）后为{5,6,7,8,1,2,3,4}，显然它们都未被放在最终位置上。

答案：C

4、在下列排序算法中，平均情况下空间复杂度为O(n)的是（）；最坏情况下空间复杂度为O(n)的是（）。

Ⅰ、希尔排序
Ⅱ、堆排序
Ⅲ、冒泡排序
Ⅳ、归并排序
Ⅴ、快速排序
Ⅵ、基数排序

• A：Ⅰ、Ⅳ、Ⅵ
• B：Ⅱ、Ⅴ
• C：Ⅳ、Ⅴ
• D：Ⅳ

解析

归并排序算法在平均情况下和最坏情况下的空间复杂度都会达到O(n)，快速排序只在最坏情况下才会达到O(n)，平均情况下为O(${\log }_{2}n$)。

答案：D，C

5、若对27个元素只进行三趟多路归并排序，则选取的归并路数最少为（）。

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

解析

对于N个元素进行k路归并排序时，排序的趟数m满足$k^m$=N，所以求得k=3。

答案：B

6、2路归并排序中，归并趟数的数量级是（）。

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

解析

对于N个元素进行k路归并排序时，排序的趟数m满足$k^m$=N，所以m=$\lceil {\log }_{k}N\rceil$。

所以本题中为$\lceil {\log }_{2}n\rceil$。

答案：B

7、在内部排序时，若选择了归并排序而未选择插入排序，则可能的理由是（）。

Ⅰ、归并排序的代码更短
Ⅱ、归并排序的占用空间更少
Ⅲ、归并排序的运行效率更高

• A：仅Ⅱ
• B：仅Ⅲ
• C：仅Ⅰ、Ⅱ
• D：仅Ⅰ、Ⅲ

解析

归并排序代码比选择插入排序更复杂，前者的空间复杂度是O(n)，后者的是O(1)。前者的时间复杂度是O(n$\log$n)，后者的是O($n^2$)。所以B正确。

答案：B

8、若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）。

• A：直接插入排序
• B：选择排序
• C：基数排序
• D：快速排序

解析

采用排除法。
由于题目要求是稳定排序，排除选项B和D，又由于基数排序不能对float和double类型的实数进行排序，故排除选项C。

答案：A

9、设被排序的结点序列共有N个结点，在该序列中的结点已十分接近有序的情况下，用直接插入排序、归并排序和快速排序对其进行排序，这些算法的时间复杂度应为（）。

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

解析

熟练掌握各种排序算法的时间和空间复杂度、稳定性等。

答案：C

10、下列排序算法中属于稳定排序的是（①），平均时间复杂度为O(n${\log }_2$n)的是（②），在最好的情况下，时间复杂度可以达到线性时间的有（③）。堆排序和归并排序在最坏情况下的时间复杂度与最好情况下的时间复杂度是同一数量级的，都是O(n${\log }_2$n)。

Ⅰ、冒泡排序
Ⅱ、堆排序
Ⅲ、选择排序
Ⅳ、直接插入排序
Ⅴ、希尔排序
Ⅵ、归并排序
Ⅶ、快速排序

解析

答案：

①：Ⅰ、Ⅳ、Ⅵ
②：Ⅱ、Ⅵ、Ⅶ
③：Ⅰ、Ⅳ