DS的一些Questions
DS的一些Questions
关于B+树的插入
问题2：
给定以下阶为 3 的 B+ 树，其中叶子节点最多可以存储 3 条记录。按顺序插入键值 13 和 50。分别画出每次插入后的更新后的 B+ 树。
关于改进的prim算法
假设对 Prim 算法进行了修订，以寻找最大生成树（MaxST）。修订后的算法是：最大生成树通过反复选择从当前生成树中某个顶点到不在生成树中的顶点的最大边来扩展。
请在以下图形上运行修订版的 Prim 算法，开始于顶点 2，绘制最终的最大生成树。
解答和解释：
最大生成树（MaxST）：
最大生成树（MaxST）是连接图中所有顶点的树，且所有边的总权重最大。与传统的
Prim
算法（通常用于最小生成树）不同，在修订后的算法中，我们每次选择最大权重的边。
Prim 算法的修订步骤：
- 从给定的起始顶点开始。
- 选择从当前生成树中的顶点到图中未包含在生成树中的顶点的最大权重边。
- 将选中的边和它连接的顶点加入生成树中。
- 重复步骤 2 和 3，直到所有顶点都被包含在生成树中。
排序
一、填空题
评价排序算法好坏的标准主要是（执行时间）和（所需的辅助空间）。
若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变。则这种排序方法是（稳定）的排序方法。
大多数排序算法都有两个基本的操作：（比较（两个关键字的大小））和（交换（记录或改变指向记录的指针））。
在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较（3）次。（可约定为，从后向前比较）
在插入和选择排序中，若初始数据基本正序，则选用（插入排序）；若初始数据基本反序，则选用（选择排序）。
直接选择排序的总的关键字比较次数与（文件的初始状态）无关。
在堆排序和快速排序中，若初始记录接近正序或反序，则选用（堆排序）；若初始记录基本无序，则最好选用（快速排序）。
在堆排序、快速排序和归并排序中，若只从排序结果的稳定性考虑，则应选取（归并排序）方法；若只从平均情况下最快考虑，则应选取（快速排序）方法；若只从最坏情况下最快并且要节省内存考虑，则应选取（堆排序）方法。
分配排序的两个基本过程是（分配）和（收集）。
二、单项选择题
(C) 1. 内部排序和外部排序的区别不在于：
- A、待排序文件的大小
- B、有无内外存的交换
- C、是否在内存中排序
- D、可采用的排序策略
答案：C
解释：
内部排序是指待排序的所有数据能够完全加载到内存中进行排序；外部排序则是指数据量较大，不能完全装入内存，需采用外部存储器（如磁盘）来进行排序。因此，内部排序和外部排序的主要区别在于是否能将所有数据装入内存，而不在于排序是否发生在内存中。选项
C 不是正确的区别。
(C) 2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上方法，称为：
- A. 希尔排序
- B. 冒泡排序
- C. 插入排序
- D. 选择排序
答案：C
解释：
插入排序的基本思想是每次从未排序的序列中取出一个元素，插入到已排序序列的适当位置。选项
C 正确。
(D) 3．排序方法中，从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为：
- A. 希尔排序
- B. 归并排序
- C. 插入排序
- D. 选择排序
答案：D
解释：
选择排序的基本思想是从未排序序列中选择最小（或最大）元素，交换到已排序序列的一端。因此，选项
D 正确。
(C) 4．快速排序在下列哪种情况下最易发挥其长处：
- A. 被排序的数据中含有多个相同排序码
- B. 被排序的数据已基本有序
- C. 被排序的数据完全无序
- D. 被排序的数据中的最大值和最小值相差悬殊
答案：C
解释：
快速排序最适合的情况是数据完全无序，能充分发挥其分治思想和分割的优势。快速排序的时间复杂度为
O(n log n)，但在最佳情况下更为高效。
(B) 5．对有 n 个记录的表作快速排序，在最坏情况下，算法的时间复杂度是：
- A．O(n)
- B．O(n²)
- C．O(n log₂n)
- D．O(n³)
答案：B
解释： 在最坏情况下，快速排序的时间复杂度为
O(n²)，例如当选择的基准元素总是数组的最大值或最小值时，无法有效分割数据。
（D）6. 在最好情况下，下列排序算法中排序算法所需比较关键字次数最少的是：
- A．冒泡
- B．归并
- C．快速
- D．直接插入
答案：D
解释：
在最好情况下，直接插入排序的比较次数最少。当输入数据已经是有序的，插入排序只需要进行一次比较就能确认每个元素的位置。因此，它在最好情况下的时间复杂度是
O(n)，相比其他排序算法所需的比较次数较少。
（D）7. 下列关键字序列中，______ 是堆。
- A. 16, 72, 31, 23, 94, 53
- B. 94, 23, 31, 72, 16, 53
- C. 16, 53, 23, 94, 31, 72
- D. 16, 23, 53, 31, 94, 72
答案：D
解释：
堆是一种完全二叉树，其中父节点的值要么大于等于子节点的值（大根堆），要么小于等于子节点的值（小根堆）。对于给定的序列，D
选项符合大根堆的性质。它符合完全二叉树的结构，并且父节点大于子节点。
（B）8. 堆是一种______排序。
- A. 插入
- B. 选择
- C. 交换
- D. 归并
答案：B
解释：
堆排序是一种选择排序。堆排序通过构建堆数据结构（大根堆或小根堆），每次选择最大（或最小）元素放到序列的末尾。它基于选择的思想，不断选择最大元素来排序。
（C）9. 堆的形状是一棵______。
- A. 二叉排序树
- B. 满二叉树
- C. 完全二叉树
- D. 平衡二叉树
答案：C
解释：
堆是一棵完全二叉树。完全二叉树要求除了最后一层外，所有层的节点都必须满，而且最后一层的节点必须从左到右排列。
（B）10. 若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始最大值堆为______。
- A. 79, 46, 56, 38, 40, 84
- B. 84, 79, 56, 38, 40, 46
- C. 84, 79, 56, 46, 40, 38
- D. 84, 56, 79, 40, 46, 38
本题无答案。
（D）11. 下列四种排序方法中，不稳定的方法是______。
- A. 直接插入排序
- B. 冒泡排序
- C. 归并排序
- D. 直接选择排序
答案：D
解释：
直接选择排序是一个不稳定的排序算法。因为在排序过程中，如果遇到相同的元素，它们的相对顺序可能会发生变化。相比之下，直接插入排序、冒泡排序和归并排序都是稳定的排序算法。
（D）12. 下面排序方法中，关键字比较次数与记录的初始排序无关的是______。
- A、希尔排序
- B、冒泡排序
- C、直接插入排序
- D、直接选择排序
答案：D
解释：
直接选择排序的关键字比较次数与记录的初始排序状态无关。无论数据是否有序，选择排序每次都在未排序部分寻找最小（或最大）元素。因此，其比较次数是固定的，与初始数据的顺序无关。
（A）13. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是______。
- A、直接插入排序
- B、冒泡排序
- C、直接选择排序
- D、归并排序
答案：A
解释：
当文件“局部有序”或文件长度较小时，直接插入排序表现最好。因为直接插入排序在数据已经接近有序的情况下，能够快速完成排序，且时间复杂度接近
O(n)。其他排序方法在此情况下效率较低。
（C）14. 在下列算法中，______算法可能出现下列情况：在最后一趟开始之前，所有元素都不在其最终位置上。
- A、堆排序
- B、冒泡排序
- C、直接插入排序
- D、快速排序
答案：C
解释：
直接插入排序可能会出现这种情况。在排序的过程中，只有一个元素会被逐步插入到正确位置，而其他元素可能会在“最后一趟”才完全排序完成。这种情况通常发生在元素初始位置非常不理想时（例如，逆序排列）。
（A）15. 快速排序在最坏情况下时间复杂度是 O(n²)，比______的性能差。
- A、堆排序
- B、冒泡排序
- C、选择排序
答案：A
解释： 快速排序的最坏时间复杂度为
O(n²)，而堆排序的最坏时间复杂度为 O(n log
n)。因此，在最坏情况下，堆排序的性能优于快速排序。
（A）16. 就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是_______。
- A、堆排序<快速排序<归并排序
- B、堆排序<归并排序<快速排序
- C、堆排序>归并排序>快速排序
- D、堆排序>快速排序>归并排序
- E、以上答案都不对
答案：A
解释：
- 堆排序是原地排序算法，不需要额外的辅助空间。
- 快速排序虽然在分割过程中使用栈空间，但其空间复杂度仍为 O(log
n)，属于较小的空间消耗。
- 归并排序需要 O(n)
的辅助空间来存储临时数据，因此其空间复杂度较大。
因此，堆排序的空间消耗最小，归并排序的空间消耗最大。
（D）17. 在下列排序算法中，关键字比较次数与记录的初始排列无关的是______。
- A、希尔排序
- B、冒泡排序
- C、直接插入排序
- D、直接选择排序
答案：D
解释：
直接选择排序的关键字比较次数与记录的初始排列无关。它始终会扫描整个未排序部分，选择最小的元素放到已排序部分，因此比较次数是固定的，不受初始排序状态影响。
（C）18. 对记录的关键字集合 key={50, 26, 38, 80, 70, 90, 8, 30, 40, 20} 进行排序，各趟排序结束时的结果为：
- 初始：50 26 38 80 70 90 8 30 40 20
- 第一趟：50 8 30 40 20 90 26 38 80 70
- 第二趟：26 8 30 40 20 80 50 38 90 70
- 第三趟：8 20 26 30 38 40 50 70 80 90
其使用的排序方法是______。
- A、快速排序
- B、基数排序
- C、希尔排序
- D、归并排序
答案：C
（C）19. 用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下：
- 初始：25 84 21 47 15 27 68 35 20
- 第一趟：15 20 21 25 47 27 68 35 84
- 第二趟：15 20 21 25 35 27 47 68 84
- 第三趟：15 20 21 25 27 35 47 68 84
则采取的排序方法是 _________。
- A. 直接选择排序
- B. 冒泡排序
- C. 快速排序
- D. 归并排序
答案：C
问题1：
- 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好采用哪种排序方法？
答案：
堆排序最合适。因为堆排序可以在不需要排序全部元素的情况下，直接通过构建一个大小为10的最大堆来快速找到前10个最大的元素。时间效率为O(n log n)，相比于排序所有元素（时间复杂度为O(n log n)），堆排序可以在较短时间内得到所需结果。
解释：
- 堆排序：通过构建一个最大堆或最小堆，可以很快找到最大元素或最小元素。在这道题中，我们需要找到前10个最大元素，采用最大堆可以有效地解决这个问题。
- 首先，构建一个大小为10的最大堆，然后遍历剩余的990个元素，每次判断新元素是否大于堆顶元素。如果是，则将堆顶元素替换为新元素，并重新调整堆。通过这种方式，我们可以在O(n log k)的时间内找到前k个最大元素（其中k=10）。
- 由于k远小于n，因此相较于直接排序所有元素，堆排序能更高效地挑选出最大的10个元素。
问题2：
以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态？
① 直接插入排序 ② 希尔排序 ③冒泡排序 ④快速排序
⑤直接选择排序 ⑥ 堆排序 ⑦ 归并排序 ⑧ 基数排序
以下是对您提供的排序算法过程的排版，使其更加清晰和美观：
1. 直接插入排序
(方括号表示无序区)
初始态:
265 [301 751 129 937 863 742 694 076 438]
- 第一趟:
265 301 [751 129 937 863 742 694 076 438] - 第二趟:
265 301 751 [129 937 863 742 694 076 438] - 第三趟:
129 265 301 751 [937 863 742 694 076 438] - 第四趟:
129 265 301 751 937 [863 742 694 076 438] - 第五趟:
129 265 301 751 863 937 [742 694 076 438] - 第六趟:
129 265 301 742 751 863 937 [694 076 438] - 第七趟:
129 265 301 694 742 751 863 937 [076 438] - 第八趟:
076 129 265 301 694 742 751 863 937 [438] - 第九趟:
076 129 265 301 438 694 742 751 863 937
2. 希尔排序 (增量为 5, 3, 1)
初始态:
265 301 751 129 937 863 742 694 076 438
- 第一趟:
265 301 694 076 438 863 742 751 129 937 - 第二趟:
076 301 129 265 438 694 742 751 863 937 - 第三趟:
076 129 265 301 438 694 742 751 863 937
3. 冒泡排序
(方括号表示无序区)
初始态:
[265 301 751 129 937 863 742 694 076 438]
- 第一趟:
076 [265 301 751 129 937 863 742 694 438] - 第二趟:
076 129 [265 301 751 438 937 863 742 694] - 第三趟:
076 129 265 [301 438 694 751 937 863 742] - 第四趟:
076 129 265 301 [438 694 742 751 937 863] - 第五趟:
076 129 265 301 438 [694 742 751 863 937] - 第六趟:
076 129 265 301 438 694 742 751 863 937
4. 快速排序
(方括号表示无序区，层表示递归层数)
初始态:
[265 301 751 129 937 863 742 694 076 438]
- 第二层:
[076 129] 265 [751 937 863 742 694 301 438] - 第三层:
076 [129] 265 [438 301 694 742] 751 [863 937] - 第四层:
076 129 265 [301] 438 [694 742] 751 863 [937] - 第五层:
076 129 265 301 438 694 [742] 751 863 937 - 第六层:
076 129 265 301 438 694 742 751 863 937
5. 直接选择排序
(方括号表示无序区)
初始态:
[265 301 751 129 937 863 742 694 076 438]
- 第一趟:
076 [301 751 129 937 863 742 694 265 438] - 第二趟:
076 129 [751 301 937 863 742 694 265 438] - 第三趟:
076 129 265 [301 937 863 742 694 751 438] - 第四趟:
076 129 265 301 [937 863 742 694 751 438] - 第五趟:
076 129 265 301 438 [863 742 694 751 937] - 第六趟:
076 129 265 301 438 694 [742 751 863 937] - 第七趟:
076 129 265 301 438 694 742 [751 863 937] - 第八趟:
076 129 265 301 438 694 742 751 [937 863] - 第九趟:
076 129 265 301 438 694 742 751 863 937
6. 堆排序
(通过画二叉树可以一步步得出排序结果)
初始态:
[265 301 751 129 937 863 742 694 076 438]
- 建立初始堆:
[937 694 863 265 438 751 742 129 075 301] - 第一次排序重建堆:
[863 694 751 765 438 301 742 129 075] 937 - 第二次排序重建堆:
[751 694 742 265 438 301 075 129] 863 937 - 第三次排序重建堆:
[742 694 301 265 438 129 075] 751 863 937 - 第四次排序重建堆:
[694 438 301 265 075 129] 742 751 863 937 - 第五次排序重建堆:
[438 265 301 129 075] 694 742 751 863 937 - 第六次排序重建堆:
[301 265 075 129] 438 694 742 751 863 937 - 第七次排序重建堆:
[265 129 075] 301 438 694 742 751 863 937 - 第八次排序重建堆:
[129 075] 265 301 438 694 742 751 863 937 - 第九次排序重建堆:
075 129 265 301 438 694 742 751 863 937
7. 归并排序
(为了表示方便，采用自底向上的归并，方括号为有序区，当 n
为奇数时，mid=n/2 取上限)
初始态:
[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]
- 第一趟:
[265 301] [751] [129 937] [742 863] [694] [076 438] - 第二趟:
[265 301 751] [129 937] [694 742 863] [076 438] - 第三趟:
[129 265 301 751 937] [076 438 694 742 863] - 第四趟:
[076 129 265 301 438 694 742 751 863 937]
8. 基数排序
(方括号内表示一个箱子，共有 10 个箱子，箱号从 0 到 9)
初始态:
265 301 751 129 937 863 742 694 076 438
- 第一趟:
[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129] - 第二趟:
[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694] - 第三趟:
[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937]
在上面的排序方法中，直接插入排序、冒泡排序、归并排序和基数排序是稳定的，其他排序算法均是不稳定的
