一、单选题（每题 2 分，共 30 分）

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

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

{{ select(1) }}

• newNode->next = head; head->next = newNode;
• newNode->next = head->next; head->next = newNode;
• head->next = newNode; newNode->next = head->next;
• 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) }}

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

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

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

{{ select(3) }}

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

第 4 题：使用如下欧几里得算法求 gcd(105, 45) 时，函数 gcd(a, b) 的递归调用序列正确的是（ ）

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

{{ select(4) }}

• gcd(105, 45) -> gcd(45, 60) -> gcd(60, 15) -> gcd(15, 0)
• gcd(105, 45) -> gcd(45, 15) -> gcd(15, 0)
• gcd(105, 45) -> gcd(60, 45) -> gcd(15, 45)
• gcd(105, 45) -> gcd(15, 45) -> gcd(15, 0)

第 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) }}

• i % primes[j] == 0
• primes[j] % i == 0
• i % primes[j] != 0
• i == primes[j]

第 6 题：下面关于埃氏筛法的说法正确的是（ ）

{{ select(6) }}

• 每个合数只会被筛掉一次
• 从每个素数出发，把它的倍数标记为合数
• 只能判断一个数是不是偶数
• 不能求出素数表

第 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) }}

• 枚举
• 贪心
• 分治
• 模拟

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

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

{{ select(8) }}

• 1
• 2
• 3
• 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) }}

• r = mid + 1
• r = mid - 1
• r = mid
• 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) }}

• r = mid + 1
• r = mid
• l = mid
• 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) }}

• swap(arr[low], arr[high])
• swap(arr[low], arr[i])
• swap(arr[i], arr[high])
• arr[i] = pivot

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

{{ select(12) }}

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

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

{{ select(13) }}

• $n - 1$
• $\log n$
• $n \log n$
• $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) }}

• l++;
• r--;
• l++; r--;
• boxes--;

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

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

{{ select(15) }}

• a[i] += 10
• a[i] -= 10
• b[i] += 10
• a[i] = a[i+1] + 10

---

二、判断题（每题 2 分，共 20 分）

第 16 题：数组的存储空间在物理上通常是连续的，而链表的结点可以存储在不连续的内存空间中。（ ）

{{ select(16) }}

• 正确
• 错误

第 17 题：带哨兵头尾节点的双向循环链表，在表头插入节点 p ，以下四步操作无论什么顺序执行结果都正确。 ① p->next = head->next; ② p->prev = head; ③ head->next->prev = p; ④ head->next = p;（ ）

{{ select(17) }}

• 正确
• 错误

第 18 题：对任意正整数 a 、 b ，以下两种写法的 gcd 函数返回值完全相同。（ ）

int gcd1(int a, int b) {
    return b ? gcd1(b, a % b) : a;
}

int gcd2(int a, int b) {
    while (b) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

{{ select(18) }}

• 正确
• 错误

第 19 题：在归并排序的合并操作中，如下代码片段可以正确地将两个已排序的子数组 L 和 R 合并回原数组 arr 中。（ ）

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

{{ select(19) }}

• 正确
• 错误

第 20 题：分治法通常将一个规模较大的问题拆分为若干个规模较小、结构相似的子问题，分别求解后再合并子问题的结果。（ ）

{{ select(20) }}

• 正确
• 错误

第 21 题：贪心算法只要每一步选择当前最优解，就一定能得到全局最优解。（ ）

{{ select(21) }}

• 正确
• 错误

第 22 题：二分查找不仅可以应用于有序数组，也可以在不增加时间复杂度的情况下应用于有序的单链表，因为链表也支持 $O(1)$ 时间内的随机访问。（ ）

{{ select(22) }}

• 正确
• 错误

第 23 题：以下函数 f1 的时间复杂度比函数 f2 的更高。（ ）

void f1(int n) {
    for (int i = 1; i < n; i *= 2);
}
void f2(int n) {
    if (n <= 1) return;
    f2(n - 1);
    f2(n - 1);
}

{{ select(23) }}

• 正确
• 错误

第 24 题：唯一分解定理表明，任何一个大于 $1$ 的自然数都可以唯一地分解为若干个质数的乘积，如果不考虑质因数的顺序，这种分解方式是唯一的。（ ）

{{ select(24) }}

• 正确
• 错误

第 25 题：归并排序和快速排序在平均情况下的时间复杂度均为 $O(n \log n)$。但在稳定性方面，归并排序通常是不稳定的，而快速排序是稳定的。（ ）

{{ select(25) }}

• 正确
• 错误