1. 对序列 3, 2, 5, 1, 4 进行升序冒泡排序，第一趟排序后的结果是
   {{ select(1) }}

• 2, 3, 1, 4, 5
• 2, 3, 5, 1, 4
• 3, 2, 1, 4, 5
• 2, 1, 3, 4, 5

2. 关于冒泡排序，下列说法正确的是
   {{ select(2) }}

• 每一趟都可以确定多个元素的最终位置
• 冒泡排序和选择排序的交换次数相同
• 冒泡排序在数据基本有序时效率较高
• 冒泡排序属于不稳定排序

3. 下列排序算法中，在大多数情况下，当序列已经基本有序时效率最高的简易排序算法是
   {{ select(3) }}

• 选择排序
• 插入排序
• 冒泡排序
• 三者效率相同

4. 以下是插入排序的代码片段，其中哪一行是核心的交换或插入操作

for (int i = 1; i < n; i++) {
    int key = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > key) {
        a[j+1] = a[j];
        j--;
    }
    a[j+1] = key;
}

{{ select(4) }}

• int key = a[i];
• a[j+1] = a[j];
• j--;
• a[j+1] = key;

5. 以下是模拟冒泡排序的代码，输入为 4 3 2 1，问第一次外层循环结束后数组状态是

for (int i = 0; i < n-1; i++) {
    for (int j = 0; j < n-1-i; j++) {
        if (a[j] > a[j+1]) swap(a[j], a[j+1]);
    }
}

{{ select(5) }}

• 1 2 3 4
• 3 2 1 4
• 2 3 1 4
• 3 2 4 1

6. 下列排序算法中，平均时间复杂度为O(n²)且稳定的是
   {{ select(6) }}

• 冒泡排序
• 选择排序
• 希尔排序
• 快速排序

7. 下列排序算法中，在每一趟结束后都能确定一个元素的最终位置的是
   ① 冒泡排序 ② 选择排序 ③ 插入排序
   {{ select(7) }}

• ①③
• ②③
• ①②
• ①②③

8. 以下哪种情况适合使用插入排序
   {{ select(8) }}

• 数据量非常大，且乱序严重
• 希望获得稳定排序，但不要求实时性
• 数据几乎有序，只需少量调整
• 想在交换次数最少的前提下排好大数组

9. 以下代码是哪种排序算法的核心部分

for (int i = 1; i < n; i++) {
    for (int j = i; j > 0 && a[j] < a[j-1]; j--) {
        swap(a[j], a[j-1]);
    }
}

{{ select(9) }}

• 冒泡排序
• 选择排序
• 插入排序
• 快速排序

10. 下面代码试图实现选择排序，使其能对数组 nums 排序为升序，则横线上应分别填写

void selectionSort(int nums[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (_________(1)_________) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            swap(_________(2)_________);
        }
    }
}

{{ select(10) }}

• (1) nums[j] < nums[minIdx] (2) nums[i], nums[minIdx]
• (1) nums[j] > nums[minIdx] (2) nums[i], nums[minIdx]
• (1) nums[j] < nums[i] (2) nums[i], nums[minIdx]
• (1) nums[j] < nums[minIdx] (2) nums[i], nums[j]

11. 小杨老师让同学把作业本按学号排序。学号几乎已经排好了，只是 5 和 4 反了。如果用插入排序，只需要调整几次
    {{ select(11) }}

• 1次
• 2次
• 3次
• 4次

12. 用冒泡排序算法对数列 2, 1, 6, 3, 4, 5 进行从大到小排序，每一趟排序都把未排序元素中最小的数放到未排序位置的最后面，第三趟排序后的状态为
    {{ select(12) }}

• 4 5 6 3 2 1
• 6 4 5 3 2 1
• 6 3 4 5 2 1
• 6 5 4 3 2 1

13. 插入排序在以下哪种输入情况下，需要移动的元素次数最多
    {{ select(13) }}

• [1, 2, 3, 4, 5]
• [5, 4, 3, 2, 1]
• [2, 3, 4, 5, 1]
• [1, 3, 5, 2, 4]

14. 执行以下代码，输入 4 2 3 1，输出结果是

int a[4], n = 4;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n-1; i++) {
    int minIdx = i;
    for (int j = i+1; j < n; j++) {
        if (a[j] < a[minIdx]) minIdx = j;
    }
    if (minIdx != i) {
        int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t;
    }
    cout << a[i] << " ";
}

{{ select(14) }}

• 1 2 3 4
• 1 2 3
• 1 2

15. 阅读以下代码，输出结果是

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n = 5;
    int a[5] = {3, 5, 2, 4, 1};
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (a[j] > a[j + 1])
                swap(a[j], a[j + 1]);
        }
    }
    cout << a[2];
    return 0;
}

{{ select(15) }}

• 1
• 2
• 3
• 4

---

阅读程序题（程序如下）

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int a[1005];
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 2; i <= n; i++) {
        int t = a[i];
        int j = i - 1;
        while (j >= 1 && a[j] > t) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = t;
    }
    cout << a[1] << " " << a[n];
    return 0;
}

16. 该程序实现的是选择排序算法。
    {{ select(16) }}

• 正确
• 错误

17. 若输入为 3 2 1，程序输出为 1 3。
    {{ select(17) }}

• 正确
• 错误

18. 若输入为 4 3 1 4 2，输出结果为：
    {{ select(18) }}

• 1 2
• 1 4
• 3 4
• 2 4

---

完善程序题

题目描述：选择排序过程模拟

给定一个长度为 $n$（$1 \leq n \leq 10^5$）的整数序列 $a[]$。
要求模拟选择排序的过程，但只进行 前 k 步（每步选择未排序部分的最小元素与未排序部分的第一个元素交换）。

请输出 前 k 步中参与交换的元素对的数量（即实际发生交换的次数，若某一步中未排序部分的最小值已经在正确位置，则该步不计入交换次数）。

输入：

• 第一行：$n \quad k$
• 第二行：$n$ 个整数，表示 $a[]$

输出：

• 一个整数，表示前 k 步中实际交换的次数。

示例：

输入：

6 3
5 2 8 1 4 3

输出：

2

#include <iostream>
using namespace std;

const int MAXN = 100005;
int a[MAXN];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int swap_count = 0;

    for (int i = 0; i < k; i++) {
        int min_pos = i;
        for (int j = i + 1; j < n; j++) {
            if (_____(1)_____) {
                min_pos = j;
            }
        }
        if (_____(2)_____) {
            int temp = a[i];
            a[i] = a[min_pos];
            a[min_pos] = temp;
            _____(3)_____;
        }
    }

    cout << _____(4)_____ << endl;

    return 0;
}

19. 第(1)处应填入？
    {{ select(19) }}

• a[j] < a[min_pos]
• a[j] > a[min_pos]
• a[j] == a[min_pos]
• j < min_pos

20. 第(2)处应填入？
    {{ select(20) }}

• min_pos != i
• min_pos == i
• min_pos > i
• a[min_pos] < a[i]

21. 第(3)处应填入？
    {{ select(21) }}

• swap_count++
• swap_count--
• swap_count = 0
• swap_count += i

22. 第(4)处应填入？
    {{ select(22) }}

• swap_count
• k
• n
• swap_count + k