1. 假设 head != nullptr ，下面是实现单向循环链表在头节点后插入新节点的代码，横线处应填入（ ）。

struct Node {
    int val;
    Node* next;
};

void insertAfterHead(Node* head, int x) {
    Node* newNode = new Node;
    newNode->val = x;
    _______________________ // 在此处填入代码
}

{{ select(1) }}

• A.

newNode->next = head;
head->next = newNode;

• B.

newNode->next = head->next;
head->next = newNode;

• C.

head->next = newNode;
newNode->next = head->next;

• D.

newNode->next = head->next;
head = newNode;

2. 下面代码遍历并输出一个循环单链表，其中 head 指向链表的第一个节点，横线处应填入的是（ ）。

struct Node {
    int val;
    Node* next;
};

void printList(Node* head) {
    if (head == nullptr) return;
    Node* p = head;
    _______________________ // 在此处填入代码
    cout << endl;
}

{{ select(2) }}

• A.

while (p != nullptr) {
    cout << p->val << " ";
    p = p->next;
}

• B.

while (p->next != nullptr) {
    cout << p->val << " ";
    p = p->next;
}

• C.

do {
    cout << p->val << " ";
    p = p->next;
} while (p != head);

• D.

for (; p; p = p->next) {
    cout << p->val << " ";
}

3. 双链表结点定义如下，若要删除双链表中的中间结点（非首尾节点） p ，下面写法正确的是（ ）。

struct Node {
    int val;
    Node* prev;
    Node* next;
};

{{ select(3) }}

• A.

p->prev->next = p->next;
p->next->prev = p->prev;
delete p;

• B.

p->next->prev = p->next;
p->prev->next = p->prev;
delete p;

• C.

p->prev = p->next;
p->next = p->prev;
delete p;

• D.

p->next->next = p->prev;
p->prev->next = p->prev;
delete p;

4. 使用短除法先求质因数来求 gcd(300, 45) 和 gcd(a, b) 的递归调用过程正确的是（ ）。

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

{{ select(4) }}

• A. gcd(300, 45) -> gcd(45, 300) -> gcd(300, 45) -> gcd(25, 0)
• B. gcd(300, 45) -> gcd(45, 30) -> gcd(30, 15) -> gcd(15, 0)
• C. gcd(300, 45) -> gcd(45, 30) -> gcd(15, 0)
• D. gcd(300, 45) -> gcd(45, 300) -> gcd(300, 45) -> gcd(15, 45)

5. 下面的代码实现了线性筛法，已知边界 n 内的所有质数，横线处的代码是（ ）。

vector<int> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;

    if (n == 0) is_prime[0] = false;
    if (n >= 1) is_prime[1] = false;

    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) primes.push_back(i);
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            is_prime[i * primes[j]] = false;
            if (_________________) break; // 在此填入代码
        }
    }
    return primes;
}

{{ select(5) }}

• A. i % primes[j] == 0
• B. primes[j] % i == 0
• C. primes[0] % primes[i] == 0
• D. i % primes[0] == 0

6. 下面关于埃氏筛法的说法正确的是（ ）。

{{ select(6) }}

• A. 每个合数只会被筛除一次
• B. 从每个素数的2倍开始，将它的倍数标记为合数
• C. 可以用来判断一个数是否是素数，但无法求出所有素数
• D. 时间复杂度为 O(n)

7. 下面代码实现了计算 $x^n$ 的快速幂算法，该算法体现的编程思想是（ ）。

long long power(long long x, int n) {
    if (n == 0) return 1;
    long long res = power(x, n / 2);
    if (n % 2 == 0) return res * res;
    else return res * res * x;
}

{{ select(7) }}

• A. 枚举
• B. 贪心
• C. 分治
• D. 模拟

8. 下面代码用于统计 n 中因子 2 出现了多少次。若 n = 40 ，输出是（ ）。

int n = 40;
int cnt = 0;
while (n % 2 == 0) {
    cnt++;
    n /= 2;
}
cout << cnt;

{{ select(8) }}

• A. 1
• B. 2
• C. 3
• D. 4

9. 在一个有序数组中查找第一个大于或等于 x 的元素位置，横线处应填写（ ）。

int lowerBound(vector<int>& a, int x) {
    int l = 0, r = a.size();
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) ________________; // 在此处填入代码
        else l = mid + 1;
    }
    return l;
}

{{ select(9) }}

• A. r = mid + 1
• B. r = mid - 1
• C. r = mid
• D. l = mid

10. 有若干根木头，长度存于 wood 。每切一刀可以把一段木头分成两段。函数 check(wood, K, x) 返回：用不超过 K 刀，能否使所有木段长度都不超过 x 。下面代码使用二分答案查找最小可行的 x ，横线处应填（ ）。

int binary_cut(vector<int>& wood, int K) {
    int l = 1;
    int r = 0;

    for (int len : wood) r = max(r, len);
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(wood, K, mid))
            ________________; // 在此处填入代码
        else l = mid + 1;
    }
    return l;
}

{{ select(10) }}

• A. r = mid + 1
• B. r = mid
• C. l = mid
• D. r = mid - 1

11. 下面代码段实现了快速排序的划分操作（以首元素为基准），横线处代码应填入（ ）。

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    int i = low, j = high;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        while (i < j && arr[i] <= pivot) i++;
        if (i < j) swap(arr[i], arr[j]);
    }
    ________________; // 在此处填入代码
    return i;
}

{{ select(11) }}

• A. swap(arr[low], arr[high])
• B. swap(arr[low], arr[i])
• C. swap(arr[i], arr[high])
• D. arr[i] = pivot

12. 下面哪句话最符合归并排序的思想？（ ）

{{ select(12) }}

• A. 每次选择最小元素放到前面
• B. 将数组分成两半分别排序，再合并两个有序部分
• C. 相邻元素两两交换
• D. 从左到右把元素插入有序区

13. 在对长度为 n（$n \ge 1$）的数组进行归并排序的过程中， mergeArray 函数（合并两个有序子数组的操作）被调用的次数是（ ）。

const int MAXN = 100005;

int a[MAXN];
int tempArr[MAXN];

void mergeArray(int left, int mid, int right) {
    int i = left;       // 左半部分起点
    int j = mid + 1;    // 右半部分起点
    int k = left;       // 临时数组下标

    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            tempArr[k++] = a[i++];
        } else {
            tempArr[k++] = a[j++];
        }
    }

    while (i <= mid) {
        tempArr[k++] = a[i++];
    }

    while (j <= right) {
        tempArr[k++] = a[j++];
    }

    for (int p = left; p <= right; p++) {
        a[p] = tempArr[p];
    }
}

void mergeSort(int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = left + (right - left) / 2;

    mergeSort(left, mid);
    mergeSort(mid + 1, right);
    mergeArray(left, mid, right);
}

{{ select(13) }}

• A. $n - 1$
• B. $\log n$
• C. $n \log n$
• D. $2n$

14. 小杨在学校义卖会上负责打包"零食盲盒"，每个盲盒重量不同，快递盒最多承重 limit 克，每个快递盒最多装两个盲盒。为了尽量少用快递盒，他采用如下策略：

（1）每次把最轻的盲盒和最重的盲盒尝试放在一起；

（2）如果两者重量之和不超过 limit ，就一起装；

（3）否则，只能让最重的盲盒单独装一盒。

下面代码用于计算最少需要多少个快递盒，则横线处应填入的是（ ）。

int minBoxes(vector<int>& w, int limit) {
    sort(w.begin(), w.end());

    int l = 0, r = w.size() - 1;
    int boxes = 0;

    while (l <= r) {
        if (w[l] + w[r] <= limit) {
            __________; // 在此处填入代码
        } else {
            r--;
        }
        boxes++;
    }

    return boxes;
}

{{ select(14) }}

• A. l++
• B. r--
• C.

l++;
r--;

• D. boxes--

15. 高精度减法中，假设两个高精度数按低位在前存储，且已经保证被减数不小于减数。下面处理借位逻辑代码中横线处应填入（ ）。

if (a[i] < b[i]) {
    a[i + 1]--;
    ________________;
}
t = a[i] - b[i];

{{ select(15) }}

• A. a[i] += 10
• B. a[i] -= 10
• C. b[i] += 10
• D. a[i] = a[i+1] + 10