程序一：带提前结束的冒泡排序

阅读程序并完成第 1～5 题。

int a[6] = {5, 1, 4, 2, 8, 3};
int cnt = 0;
for (int i = 0; i < 5; ++i) {
    bool swapped = false;
    for (int j = 0; j < 5 - i; ++j) {
        if (a[j] > a[j + 1]) {
            swap(a[j], a[j + 1]);
            cnt++;
            swapped = true;
        }
    }
    if (!swapped) break;
}

第 1 题

第一趟外层循环结束后，数组内容是什么？（数字间用一个空格）

{{ input(1) }}

---

第 2 题

程序结束时 cnt 的值是多少？（只填数字）

{{ input(2) }}

---

第 3 题

变量 swapped 的主要作用是（ ）。

{{ select(3) }}

• 记录本趟是否发生交换，从而在数组已有序时提前结束
• 统计数组中不同元素个数
• 保证选择排序稳定
• 记录当前最小值下标

---

第 4 题

若输入数组原本已经升序，外层循环实际执行几次？（只填数字）

{{ input(4) }}

---

第 5 题

该程序最坏情况下的时间复杂度是（ ）。

{{ select(5) }}

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n^2)$

---

程序二：选择排序

阅读程序并完成第 6～9 题。

int a[5] = {4, 2, 4, 1, 3};
for (int i = 0; i < 4; ++i) {
    int p = i;
    for (int j = i + 1; j < 5; ++j)
        if (a[j] < a[p]) p = j;
    swap(a[i], a[p]);
}

第 6 题

第一轮选择并交换后，数组内容是什么？

{{ input(6) }}

---

第 7 题

前两轮结束后，数组内容是什么？

{{ input(7) }}

---

第 8 题

整个程序一共执行多少次数值大小比较 a[j] < a[p]？

{{ input(8) }}

---

第 9 题

若相等元素带有原始编号，该排序是否一定保持相等元素的原相对次序？

{{ select(9) }}

• 一定保持
• 不一定保持
• 只在逆序数组中保持
• 由整数范围决定

---

程序三：合并两个有序序列

阅读程序并完成第 10～12 题。

int a[4] = {1, 3, 5, 7};
int b[3] = {2, 3, 6};
int c[7], i = 0, j = 0, k = 0;
while (i < 4 && j < 3) {
    if (a[i] <= b[j]) c[k++] = a[i++];
    else c[k++] = b[j++];
}
while (i < 4) c[k++] = a[i++];
while (j < 3) c[k++] = b[j++];

第 10 题

程序结束后，数组 c 的内容是什么？

{{ input(10) }}

---

第 11 题

把 a[i] <= b[j] 改为 a[i] < b[j]，对这组数值结果和相等元素来源顺序的影响是（ ）。

{{ select(11) }}

• 数值顺序错误
• 数值顺序不变，但两个 3 的来源顺序改变
• 程序死循环
• 时间复杂度变为平方级

---

第 12 题

若两个输入序列长度分别为 $n,m$，合并过程的时间复杂度是（ ）。

{{ select(12) }}

• $O(1)$
• $O(\log(n+m))$
• $O(n+m)$
• $O(nm)$

---