程序一：插入排序与逆序对

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

int a[6] = {5, 2, 4, 6, 1, 3};
int cnt = 0;
for (int i = 1; i < 6; ++i) {
    int x = a[i], j = i - 1;
    while (j >= 0 && a[j] > x) {
        a[j + 1] = a[j];
        j--;
        cnt++;
    }
    a[j + 1] = x;
}

第 1 题

当 i=1 的一轮结束后，数组内容是什么？

{{ input(1) }}

---

第 2 题

当 i=2 的一轮结束后，数组内容是什么？

{{ input(2) }}

---

第 3 题

程序全部结束后，数组内容是什么？

{{ input(3) }}

---

第 4 题

程序全部结束时 cnt 的值是多少？

{{ input(4) }}

---

第 5 题

条件使用 a[j] > x 而不是 a[j] >= x，有助于保证（ ）。

{{ select(5) }}

• 相等元素的相对次序不变
• 程序只处理奇数
• 空间复杂度为 $O(n)$
• 数组必须严格递增

---

第 6 题

输入已经有序时，该实现的时间复杂度是（ ）。

{{ select(6) }}

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

---

程序二：快速排序中的一次划分

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

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

第 7 题

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

{{ input(7) }}

---

第 8 题

程序结束后 p 的值是多少？

{{ input(8) }}

---

第 9 题

程序结束后一定成立的性质是（ ）。

{{ select(9) }}

• pivot 左侧都小于 pivot，右侧都大于等于 pivot
• 整个数组已经有序
• pivot 一定是数组中位数
• 右侧元素都小于 pivot

---

第 10 题

执行完这一次划分后，整个数组是否已经完成排序？

{{ select(10) }}

• 是
• 否

---

第 11 题

循环中一共执行多少次 a[j] < pivot 的比较？

{{ input(11) }}

---

第 12 题

若数组中存在多个等于 pivot 的元素，当前 < pivot 条件会把它们放在（ ）。

{{ select(12) }}

• pivot 左侧区域
• 不小于 pivot 的右侧区域
• 全部删除
• 随机区域且无任何约束

---

程序三：重复元素的二分边界

阅读程序并完成第 13～18 题。

int a[8] = {1, 2, 2, 2, 4, 7, 7, 9};
// lower_pos(x)：返回第一个 >= x 的位置
// upper_pos(x)：返回第一个 > x 的位置

第 13 题

lower_pos(2) 的返回值是多少？

{{ input(13) }}

---

第 14 题

upper_pos(2) 的返回值是多少？

{{ input(14) }}

---

第 15 题

数组中 2 的出现次数是多少？

{{ input(15) }}

---

第 16 题

lower_pos(8) 的返回值是多少？

{{ input(16) }}

---

第 17 题

upper_pos(9) 的返回值是多少？

{{ input(17) }}

---

第 18 题

实现两个函数时，核心分支的区别是（ ）。

{{ select(18) }}

• lower 排除 <x，upper 排除 <=x
• lower 使用栈，upper 使用队列
• lower 必须递归，upper 禁止循环
• 二者没有区别

---

程序四：二分最小可行容量

货物必须按原顺序装运，每天总重量不超过 cap。阅读程序并完成第 19～24 题。

int w[5] = {4, 2, 3, 5, 1};
bool ok(int cap) {
    int days = 1, sum = 0;
    for (int x : w) {
        if (sum + x > cap) {
            days++;
            sum = 0;
        }
        sum += x;
    }
    return days <= 3;
}

第 19 题

满足 ok(cap)==true 的最小 cap 是多少？

{{ input(19) }}

---

第 20 题

当 cap=5 时共需要多少天？

{{ input(20) }}

---

第 21 题

当 cap=7 时共需要多少天？

{{ input(21) }}

---

第 22 题

随着 cap 增大，ok(cap) 的真假变化具有哪种形式？

{{ select(22) }}

• 先真后假
• 先假后真
• 真假交替
• 没有规律

---

第 23 题

对最小可行容量进行二分时，左边界至少应设为（ ）。

{{ select(23) }}

• 0
• 最轻货物重量
• 最重货物重量
• 所有货物总重量

---

第 24 题

若总重量记为 $S$，每次 ok 扫描全部 $n$ 件货物，总时间复杂度可写为（ ）。

{{ select(24) }}

• $O(1)$
• $O(\log S)$
• $O(n\log S)$
• $O(nS)$

---