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

1、排序趟数与序列的原始状态无关的排序方法是（）。

Ⅰ、直接插入排序
Ⅱ、简单选择排序
Ⅲ、冒泡排序
Ⅳ、基数排序

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

解析

交换类的排序，其趟数和原始序列状态有关，故冒泡排序与初始序列有关。

• 直接插入排序：每趟排序都插入一个元素，所以排序趟数固定为n-1躺；
• 简单选择排序：每趟排序都选出一个最小（或最大）的元素，所以排序趟数固定为n-1；
• 技术排序：每趟排序都要进行“分配”和“收集”，排序趟数固定为d。

答案：B

2、若序列的原始状态为{1,2,3,4,5,10,6,7,8,9}，要想使得排序过程中的元素比较次数最少，则应该采用（）方法。

• A：插入排序
• B：选择排序
• C：希尔排序
• D：冒泡排序

解析

选择排序和序列初态无关，直接排除。

初始序列基本有序时，插入排序比较次数较少。本题中，插入排序仅需比较n+4次，而希尔排序和冒泡排序的比较次数均远大于此。

答案：A

3、下列排序方法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是（）。

Ⅰ、插入排序
Ⅱ、选择排序
Ⅲ、起泡排序
Ⅳ、希尔排序
Ⅴ、堆排序

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

解析

插入排序、选择排序、起泡排序的原本时间复杂度是O($n^2$)，更换为链式存储后的时间复杂度还是o($n^2$)。希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加，因此选D。

答案：D

4、对大部分元素已有序的数组排序时，直接插入排序比简单选择排序效率更高，其原因是（）。

Ⅰ、直接插入排序过程中元素之间的比较次数更少
Ⅱ、直接插入排序过程中所需的辅助空间更少
Ⅲ、直接插入排序过程中元素的移动次数更少

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

解析

考虑较极端的情况，对于有序数组，直接插入排序的比较次数为n-1，简单选择排序的比较次数始终为1+2+…+n-1=n(n-1)/2，Ⅰ正确。

两种排序方法的辅助空间都是O(1)，无差别，Ⅱ错误。

初始有序时，移动次数均为0；对于通常情况，直接插入排序每趟插入都需要依次向后挪位，而简单选择排序只需与找到的最小元素交换位置，后者的移动次数少很多，Ⅲ错误。

答案：A

5、设在磁盘上存放有375000个记录，做5路平衡归并排序，内存工作区能容纳600个记录，为把所有记录排好序，需要做（）趟归并排序。

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

解析

初始归并段的个数r=375000/600=625，因此，归并趟数S=$\lceil {\log }_{m}r\rceil$=$\lceil {\log }_{5}625\rceil$=4。

第一趟把625个归并段归并成625/5=125个；

第二趟把125个归并段归并成125/5=25个；

第三趟把25个归并段归并成15/5=5个；

第四趟把5个归并段归并成5/5=1个。

答案：B

6、设有5个初始归并段，每个归并段有20个记录，采用5路平衡归并排序，若不采用败者树，使用传统的顺序选出最小记录（简单选择排序）的方法，总的比较次数为（①）；若采用败者树最小的方法，总的比较次数约为（②）。

• A：20
• B：300
• C：396
• D：500

解析

不采用败者树时，在5个记录中选出最小的需要做4次比较，共有100个记录，需要做99次选择最小记录的操作，所以需要的比较次数为4 $\times$ 99=396，故选C。

采用败者树时，5路归并意味着败者树的外结点有5个，败者树的高度h=$\lceil {\log }_{2}5\rceil$=3。每次在参加比较的记录中选择一个关键字最小的记录，比较次数不超过h，共100个记录，需要的比较次数不超过100 $\times$ 3 =300，故选B。

答案：C，B

7、置换-选择排序的作用是（）。

• A：用于生成外部排序的初始归并段
• B：完成将一个磁盘文件排序成有序文件的有效的外部排序算法
• C：生成的初始归并段的长度是内存工作区的2倍
• D：对外部排序中输入、归并、输出的并行处理

解析

置换-选择排序是外部排序中生成初始归并段的方法，用此方法得到的初始归并段的长度是不等长的，其长度平均是传统等长初始归并段的2倍，从而使得初始归并段数减少到原来的近二分之一。但是，置换-选择排序不是一种完整的生成有序文件的外部排序算法。

答案：A

8、在做m路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置（①）个输入缓冲区和（②）个输出缓冲区。

• A：2

• B：m

• C：2m-1

• D：2m

• A：2

• B：m

• C：2m-1

• D：2m

解析

在做m路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置2m个输入缓冲区和2个输出缓冲区，以便在执行内部归并时，能同时进行输入/输出操作。若仅设置m个输入缓冲区，则仅能进行串行操作，无法并行处理。

答案：D，A

9、已知三叉树T中6个叶结点的权分别是2,3,4,5,6,7,T的带权（外部）路径长度最小是（）。

• A：27
• B：46
• C：54
• D：56

解析

将哈夫曼树的思路推广到三叉树的情形。

为了构成严格的三叉树，需添加权为0的虚叶结点，对于严格的三叉树，（$n_0$-1）%（3-1）=u=1$\ne$ 0，需要添加m-u-1=3-1-1=1个叶结点，说明7个叶结点刚好可以构成一棵严格的三叉树。按照哈夫曼树的原则，权为0的叶结点应离树根最远，构造的最小带权生成树如下图所示。

最下带权路径长度为（2+3）$\times$ 3+（4+5）$\times$ 2+（6+7）$\times$ 1=46。

答案：B

10、设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是（）。

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

解析

在12路归并树中只存在度为0和度为12的结点，设度为0的结点数、度为12的结点数和要补充的结点数分别为$n_0$、$n_{1}2$和$n_{补}$，则有$n_0$=120+$n_{补}$，$n_0$=(12-1)$n_{1}2$+1，可得$n_{1}2$=（120-1+$n_{补}$）/（12-1）。

由于结点数$n_{1}2$为整数，所以$n_{补}$是使上式整除的最小整数，求得$n_{补}$=2，所以答案选B。

答案：B