数据结构之选择排序题解

选择题

1. 在以下排序算法中，每次从未排序的记录中选取最小关键字的记录，加入已排序记录的末尾，该排序方法是()

A. 简单选择排序
B. 冒泡排序
C. 堆排序
D. 直接插入排序
答案: A. 简单选择排序
解释: 简单选择排序每次从未排序的部分中找到最小的元素，并将其放到已排序部分的末尾。

2. 简单选择排序算法的比较次数和移动次数分别为()

A. $O(n)，O(log n) $
B.$ O(log n)，O(n²) $
C. $O(n^2)，O(n) $
D. $O(n log n)，O(n) $ 答案: $C. O(n^2)，O(n) $ 解释: 简单选择排序在最坏情况下需要进行 $O(n^2)$ 次比较，但由于在每次选择后只进行少量的移动，所以其移动次数也为 $O(n)$。

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

A. 先按 $k_1$ 进行直接插入排序，再按 $k_2$ 进行简单选择排序
B. 先按 $k_2$ 进行直接插入排序
C. 先按 $k_1$ 进行简单选择排序，再按 $k_2$ 进行直接插入排序
D. 先按 $k_2$ 进行简单选择排序，再按 $k_1$ 进行直接插入排序
答案: D. 先按 $k_2$ 进行简单选择排序，再按 $k_1$ 进行直接插入排序
解释: 由于 $k_1$ 的排序会影响到 $k_2$ 的相对位置，因此需要在保证 $k_1$ 排序的情况下，使用稳定的排序算法（直接插入排序）对 $k_2$ 进行排序。

4. 若只想得到 1000 个元素组成的序列中第 10 个最小元素之前的部分排序的序列，用( )方法最快。

A. 冒泡排序
B. 快速排序
C. 希尔排序
D. 堆排序
答案: D. 堆排序
解释: 堆排序可以在不完全排序的情况下快速找到前 10 个最小元素，通过建立小根堆可以有效调整，只需进行少量的调整即可得到所需元素。

5. 通常，取一大堆数据中的 $k$ 个最大(最小)的元素时，都优先采用堆排序。

A. 冒泡排序
B. 快速排序
C. 希尔排序
D. 堆排序
答案: D. 堆排序
解释: 堆排序特别适合用于选择最大或最小元素，因为它可以通过堆的性质快速找到所需的元素。

6. 下列( )是一个堆。

A. 19, 75, 34, 26, 97, 56
B. 97, 26, 34, 75, 19, 56
C. 19, 56, 26, 97, 34, 75
D. 19, 34, 26, 97, 56, 75
答案: D. 19, 34, 26, 97, 56, 75
解释: 将每个选项中的序列表示成完全二叉树，检查父结点与子结点的关系是否满足堆的定义。选项 D 中的序列符合小根堆的定义，即每个父节点的值都小于等于其子节点的值。

7. 有一组数据 (15, 9, 7, 8, 20, -1, 7, 4)，用堆排序的筛选方法建立的初始小根堆为:

A. -1, 4, 8, 9, 20, 7, 15, 7
B. -1, 7, 15, 7, 4, 8, 20, 9
C. -1, 4, 7, 8, 20, 15, 7, 9
D. A、B、C 均不对
答案: C. -1, 4, 7, 8, 20, 15, 7, 9
解释: 筛选堆的过程是从最后一个非叶子节点开始逐层向上调整，最终形成小根堆。

8. 在含有 n 个关键字的小根堆中，关键字最大的记录有可能存储在()位置。

A. n/2
B. n/2 + 2
C. n/2 - 1
D. n
答案: B. n/2 + 2
解释: 小根堆的最大元素一定存储在叶子节点中。叶子节点从 $\lfloor n/2 \rfloor + 1$ 到 $n$ 的范围内，因此最大记录的存储位置为 $\lfloor n/2 \rfloor + 1$ 到 $n$。

9. 向具有 n 个结点的堆中插入一个新元素的时间复杂度为()。

A. $O(n)$
B. $O(log n)$
C. $O(n log n)$
D. $O(n^2)$
答案: B. $O(log n) $ 解释: 在堆中插入一个新元素时，需要进行向上调整，最多需要调整的次数等于堆的高度，而堆的高度为 $O(\log n)$。

10. 构建 n 个记录的初始堆，其时间复杂度为();对 n 个记录进行堆排序，最坏情况下其时间复杂度为()。

A. $O(n)，O(n log n) $
B. $O(n log n)，O(n) $
C. $O(log n)，O(n log n) $
D. $O(n log n)，O(n log n) $ 答案: A. $O(n)，O(n log n) $ 解释: 构建初始堆的时间复杂度为 $O(n)$，这是因为通过向下调整的过程在最坏情况下是线性的。而堆排序的最坏情况下时间复杂度为 $O(n \log n)$，因为每次取出最小（或最大）元素后都需要进行堆的重建。

11. 对关键码序列 {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}
答案: 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}。

12. 【2009 统考真题】已知关键字序列 5, 8, 12, 19, 28, 20, 15, 22 是小根堆，插入关键字 3，调整好后得到的小根堆是()。

A. {23, 72, 60, 25, 68, 71, 52}
B. {3, 5, 12, 19, 20, 15, 22, 8, 28}
C. {71, 25, 23, 52, 60, 72, 68}
D. {3, 12, 5, 8, 28, 20, 15, 22, 19}
答案: B. {3, 5, 12, 19, 20, 15, 22, 8, 28}
解释: 插入关键字 3 后，首先将 3 放入堆的末尾，然后与父节点比较并向上调整，最终形成的小根堆为 {3, 5, 12, 19, 20, 15, 22, 8, 28}。

13. 【2011 统考真题】已知序列 25, 13, 10, 12, 9 是大根堆，在序列尾部插入新元素 18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是()。

A. 1
B. 2
C. 4
D. 5
答案: B. 2
解释: 插入元素 18 后，首先与 10 进行比较并交换位置，然后再与 25 比较而不交换位置。共进行了 2 次比较，因此答案为 B。

14. 下列 4 种排序方法中，排序过程中的比较次数与序列初始状态无关的是( )。

A. 选择排序法
B. 插入排序法
C. 快速排序法
D. 冒泡排序法
答案: A. 选择排序法
解释: 选择排序的比较次数始终为 $ $，与初始序列的状态无关。而插入排序、快速排序和冒泡排序的比较次数则会受到初始状态的影响。

15. 【2015 统考真题】已知小根堆为 {8, 15, 10, 21, 34, 16, 12}，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是()。

A. 1
B. 2
C. 3
D. 4
答案: C. 3
解释: 删除根节点 8 后，将最后一个元素 12 放到根节点，进行调整。过程中需要与 10 和 15 比较，最多需要进行 3 次比较，因此答案为 C。

16. 【2018 统考真题】在将序列 {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
答案: 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
解释: 正确的构建大根堆的过程是从序列开始，依次调整，最终得到的序列为 {9, 8, 7, 1, 6, 4, 5}。

17. 【2020 统考真题】下列关于大根堆（至少含 2 个元素）的叙述中，正确的是( )。

I. 可以将堆视为一棵完全二叉树
1. 可以采用顺序存储方式保存堆
1. 可以将堆视为一棵二叉排序树
1. 堆中的次大值一定在根的下一层
A. 仅 I、II
B. 仅 II、III
C. 仅 I、II 和 IV
D. I、II 和 IV
答案: D. I、II 和 IV
解释:
I 正确：堆是完全二叉树。
II 正确：堆可以用数组（顺序存储）存储。
III 错误：堆并不是二叉排序树，堆只保证父节点大于或小于子节点，并不要求左右子树有序。
IV 正确：在大根堆中，次大值在根的下一层。

18. 【2021 统考真题】将关键字 {6, 9, 1, 5, 8, 4, 7} 依次插入到初始为空的大根堆 H 中，得到的 H 是()。

A. 9, 8, 7, 6, 5, 4, 1
B. 9, 8, 7, 5, 6, 1, 4
C. 9, 8, 7, 5, 6, 4, 1
D. 9, 6, 7, 5, 8, 4, 1
答案: B.
解释: 插入的过程如下：

插入 6 → {6}
插入 9 → {9, 6}
插入 1 → {9, 6, 1}
插入 5 → {9, 6, 1, 5}
插入 8 → {9, 8, 6, 5, 1}
插入 4 → {9, 8, 6, 5, 1, 4}
插入 7 → {9, 8, 7, 6, 5, 4, 1}

最终形成的大根堆是 {9, 8, 7, 6, 5, 4, 1}。

程序题

01. 堆与二叉排序树的区别

解答
堆（以小根堆为例）和二叉排序树的主要区别如下：

结构性质：
- 堆：堆是一种完全二叉树，满足父节点的关键字小于等于任何子节点的关键字（小根堆）或大于等于任何子节点的关键字（大根堆）。但堆中的子节点之间没有特定的顺序关系。
- 二叉排序树：每个父节点的关键字均大于其左子树的所有节点的关键字，并且小于其右子树的所有节点的关键字。因而，二叉排序树的中序遍历将得到一个有序的序列。
遍历结果：
- 堆：中序遍历堆的节点不会得到有序序列。
- 二叉排序树：中序遍历二叉排序树能得到一个升序排列的序列。

02. 获取序列中第k个最小元素之前的部分排序序列

解答
如果只想得到一个序列中第 $ k $ 个最小元素之前的部分排序序列，最佳排序方法是堆排序。

原因：

在基于比较的排序方法中，插入排序、快速排序和归并排序都必须将所有元素完全排好序才能得到前 $ k $ 小的元素，效率较低。
而堆排序可以在每一趟中确定一个最小的元素。建立初始堆的时间复杂度为 $ O(n) $，而取得第 $ k $ 个最小元素之前的排序序列的时间复杂度为 $ O(k n) $。因此，总时间复杂度为 $ O(n + k n) $。
相比之下，冒泡排序和简单选择排序的时间复杂度为 $ O(k^2) $，当 $ k > 5 $ 时，这两种方法效率较低。

综上所述，堆排序最适合用于获得前 $ k $ 小元素的部分排序序列。注意，如果只需得到前 $ k $ 小元素的顺序排列，其他排序算法如冒泡排序和简单选择排序也可以使用。

03. 在小根堆中增加一个元素 K 的调整方法

问题
有 $ n $ 个元素已构成一个小根堆，现在要增加一个元素 K，请用文字简要说明如何在 $ O(n) $ 的时间内将其重新调整为一个堆。

解答

插入位置：首先，将新元素 $ K $ 插入到数组的第 $ n + 1 $ 个位置，意味着 $ K $ 作为一个新的叶节点添加到小根堆中。
比较与调整：接下来，进行调整以维护小根堆的性质：
- 与其双亲节点比较。根据小根堆的性质，如果 $ K $ 小于其双亲节点，则交换 $ K $ 和双亲节点的值。
- 如果交换后，新的位置仍然小于其新的双亲节点，则继续进行比较与交换。
- 该过程将持续进行，直到以下任一条件满足：
  - $ K $ 大于等于其双亲节点，停止调整。
  - $ K $ 成为堆的根节点（即到达数组的第 1 个位置）。
时间复杂度：此调整过程的时间复杂度为 $ O(n) $，因为在最坏情况下，元素 $ K $ 可能需要上升到堆的根节点，而小根堆的高度为 $ n $。

解释

小根堆性质：在小根堆中，任一节点的值都小于或等于其子节点的值，因此，插入新元素后，需通过调整保持这一性质。
调整过程：通过与双亲节点的比较和可能的交换，确保新插入的元素不会破坏小根堆的结构。该方法有效且高效，适合处理大多数场景中的元素插入。

04. 单链表的简单选择排序算法

问题
编写一个算法，在基于单链表表示的待排序关键字序列上进行简单选择排序。

解答
算法的思想是：每趟在原始链表中摘下关键字最大的节点，把它插入结果链表的最前端。由于在原始链表中摘下的关键字越来越小，在结果链表前端插入的关键字也越来越小，因此最后形成的结果链表中的节点将按关键字非递减的顺序有序链接。

下面是实现简单选择排序的算法示例，假设单链表的定义如第2章所述，不带表头节点：

struct LinkNode {
    int data;
    LinkNode* link;
};

void selectSort(LinkNode*& head) {
    LinkNode *result = nullptr; // 新的结果链表
    LinkNode *current = head;   // 原链表的工作指针

    while (current != nullptr) {
        LinkNode *p = current; // 用于扫描原链表
        LinkNode *maxNode = current; // 记录当前最大节点
        LinkNode *prevMax = nullptr;  // 记录当前最大节点的前驱
        LinkNode *prev = nullptr;      // prev用于跟踪当前节点的前驱

        // 寻找原链表中的最大节点
        while (p != nullptr) {
            if (p->data > maxNode->data) {
                maxNode = p; // 更新最大节点
                prevMax = prev; // 更新最大节点的前驱
            }
            prev = p; // 移动到下一个节点
            p = p->link;
        }

        // 从原链表中摘下最大节点
        if (maxNode == head) {
            // 最大节点在原链表的前端
            head = head->link;
        } else {
            // 最大节点在原链表的中间
            prevMax->link = maxNode->link;
        }

        // 将最大节点插入结果链表的前端
        maxNode->link = result;
        result = maxNode;
    }

    // 更新原链表为结果链表
    head = result;
}

解释

算法思想：每一轮从原链表中找到最大的节点并将其插入到新链表的前端，最终新链表的顺序是按关键字非递减排序的。
节点操作：
- 使用两个指针 p 和 prev 来遍历原链表，寻找最大节点及其前驱。
- 通过比较，确定最大节点并进行摘除，同时保持原链表的连接完整。
- 最后，将找到的最大节点插入到结果链表的前端。
时间复杂度：算法的时间复杂度为 $ O(n^2) $，这是因为每次都要遍历一次原链表来找最大节点。

05. 判断数据序列是否构成小根堆的算法

问题
设计一个算法，判断一个数据序列是否构成一个小根堆。

解答
算法的思想是将顺序表 $A[1..n]$ 视为一个完全二叉树，扫描所有的非叶子节点（即父节点），检查每个父节点与其子节点的关键字关系。如果遇到任何一个子节点的关键字小于其父节点的关键字，则返回 false；如果所有父节点都符合小根堆的特性，则返回 true。

下面是实现该算法的代码示例：

#include <iostream>
using namespace std;

typedef int ElemType;

bool IsMinHeap(ElemType A[], int len) {
    // 判断边界条件
    if (len < 1) return false; // 空堆情况

    // 扫描所有非叶子节点
    for (int i = len / 2; i >= 1; i--) {
        // 判断当前节点与左子节点的关系
        if (2 * i <= len && A[i] > A[2 * i]) {
            return false; // 当前节点大于左子节点，不满足小根堆性质
        }
        // 判断当前节点与右子节点的关系
        if (2 * i + 1 <= len && A[i] > A[2 * i + 1]) {
            return false; // 当前节点大于右子节点，不满足小根堆性质
        }
    }
    
    return true; // 所有父节点均满足小根堆性质
}

int main() {
    ElemType A[] = {0, 1, 3, 5, 7, 9}; // 假设 A[0] 为无效，实际使用从 A[1] 开始
    int len = sizeof(A) / sizeof(A[0]) - 1; // 计算有效长度

    if (IsMinHeap(A, len)) {
        cout << "该序列构成一个小根堆。" << endl;
    } else {
        cout << "该序列不构成小根堆。" << endl;
    }

    return 0;
}

解释

算法逻辑：
- 通过从最后一个非叶子节点开始遍历（即 $len/2$ 到 1），检查每个父节点与其左右子节点的关系。
- 对于每个父节点 $A[i]$，检查是否满足以下条件：
  - $A[i] \leq A[2*i]$（如果存在左子节点）
  - $A[i] \leq A[2*i + 1]$（如果存在右子节点）
- 如果任何一个条件不满足，则返回 false，说明不是小根堆；否则返回 true。
时间复杂度：算法的时间复杂度为 $O(n)$，因为每个非叶子节点只需常数时间进行比较。
边界条件：
- 如果序列为空或长度小于1，则返回 false。
- 本实现假设输入数组索引从1开始，故A[0]不使用。