1 单选题（每题 2 分，共 30 分）

1. 双向链表中，若要在结点 p 之后插入新结点 s，正确的指针操作为（ ）。 {{ select(1) }}

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

2. 下面代码用于读入由 $n$ 个数字组成的序列 $A$，并计算 $\sum_{1\leq i\leq n}\left(\sum_{1\leq j< i} A_j\right)\cdot A_i$ 的值，该代码使用的是（ ）。

int main() {  
    int n, x, pre = 0, ans = 0;  
    cin >> n;  
    for (int i = 1; i <= n; i++) {  
        cin >> x;  
        ans += x * pre;  
        pre += x;  
    }  
    cout << ans;  
}  

{{ select(2) }}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

3. 下面代码实现单链表（头节点非空）的逆序，横线上应填的代码是（ ）。

struct ListNode {  
    int val;  
    ListNode* next;  
};  
ListNode* reverseList(ListNode* head) {  
    ListNode* prev = nullptr;  
    ListNode* curr = head;  
    while (curr != nullptr) {  
        ListNode* nextTemp = curr->next;  
        curr->next = prev;  
        prev = curr;  
        curr = nextTemp;  
    }  
    return ______; // 填入代码  
}  

{{ select(3) }}

• head
• prev
• curr
• nextTemp

4. 以下代码说法正确的是（ ）。

int func(int n) {  
    if (n <= 1)  
        return 1;  
    return func(n - 1) + func(n / 2);  
}  

{{ select(4) }}

• 该算法的时间复杂度为 $O(n)$
• 递归深度为 $O(\log n)$
• 空间复杂度主要由递归调用栈决定
• 该算法比迭代实现更高效

5. 以下代码实现了辗转相除法（欧几里得算法）求最大公约数，则调用 gcd(48, 18) 的返回值是（ ）。

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

{{ select(5) }}

• 6
• 8
• 12
• 18

6. 小杨有 n 个活动，每个活动需要他在从 start[i] 到 end[i] 的整个时间段（包括端点）内一直在现场。他想知道，最多能举办多少活动。若前一个活动结束时刻与下一个活动开始时刻相同，也视为时间冲突。以下代码实现了解决此问题的贪心算法，横线处应填入的代码是（ ）。

struct Activity {  
    int start, end;  
};  
bool cmp(Activity a, Activity b) {  
    return a.end < b.end;  
}  
int activitySelection(Activity arr[], int n) {  
    if (n == 0) return 0;  
    sort(arr, arr + n, cmp);  
    int count = 1;  
    int lastEnd = arr[0].end;  
    for (int i = 1; i < n; i++) {  
        if (__________) {  
            count++;  
            lastEnd = arr[i].end;  
        }  
    }  
    return count;  
}  

{{ select(6) }}

• arr[i].start > lastEnd
• arr[i].end > lastEnd
• arr[i].start < lastEnd
• arr[i].end < lastEnd

7. 二分查找在查找失败时，最多比较次数为（ ）。 {{ select(7) }}

• $n / 2$
• $\log_2 n - 1$
• $\log_2 n$
• $\log_2 n + 1$

8. 线性筛法的时间复杂度是 $O(n)$，它比时间复杂度为 $O(n \log \log n)$ 的埃氏筛法更快的关键点在于（ ）。{{ select(8) }}

• 每个合数仅被其最大质因子筛去
• 通过标记最小质因子避免重复筛去
• 利用空间换时间，空间复杂度增加
• 仅筛奇数以减少计算量

9. 唯一分解定理表明，每个大于 1 的自然数可唯一分解为（ ）。 {{ select(9) }}

• 素数的乘积
• 素数的和
• 奇数的乘积
• 奇数的和

10. 高精度减法中，若被减数小于减数，正确的处理方式是（ ）。

#include <iostream>  
#include <algorithm>  
#include <string>
using namespace std;  

string subtract(string a, string b) {  
    if (a.length() < b.length() || (a.length() == b.length() && a < b)) {  
        ______________; // 横线中应填入  
    }  

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    
    string res = "";  
    int carry = 0;  
    for (int i = 0; i < b.length(); i++) {  
        int diff = (a[i] - '0') - (b[i] - '0') - carry;  
        if (diff < 0) {  
            diff += 10;  
            carry = 1;  
        } else {  
            carry = 0;  
        }  
        res.push_back(diff + '0');  
    }  
    
    for (int i = b.length(); i < a.length(); i++) {  
        int diff = (a[i] - '0') - carry;  
        if (diff < 0) {  
            diff += 10;  
            carry = 1;  
        } else {  
            carry = 0;  
        }  
        res.push_back(diff + '0');  
    }  
    
    while (res.length() > 1 && res.back() == '0') {  
        res.pop_back();  
    }  
    reverse(res.begin(), res.end());  
    return res;  
}  

int main() {  
    string a, b;  
    cin >> a >> b;  
    cout << subtract(a, b);  
    return 0;  
}  

{{ select(10) }}

• return "-" + subtract(b, a);
• return "-" + subtract(a, b);
• swap(a, b);
• return "";

11. 高精度整数存储时，通常采用逆序存储（低位在前），目的是（ ）。 {{ select(11) }}

• 提高访问速度
• 避免前导零的处理
• 节省存储空间
• 方便逐位处理进位和借位

12. 高精度乘法中，若两个 n 位整数相乘，结果最多有（ ）位。 {{ select(12) }}

• $n+1$
• $2n-1$
• $2n$
• $2n+1$

13. 在左闭右闭的区间[left, right]中进行归并排序，递归终止条件是（ ）。

void mergeSort(vector<int>& arr, int left, int right) {  
    if (__________) {  // 横线处应填入  
        return;  
    }  
    int mid = left + (right - left) / 2;  
    mergeSort(arr, left, mid);  
    mergeSort(arr, mid + 1, right);  
    merge(arr, left, mid, right);  
}  

{{ select(13) }}

• right - left == 1
• left < right
• left > right
• left >= right

14. 计算中间索引 mid 时使用 left + (right - left) / 2 而非 (left + right) / 2，是为了（ ）。 {{ select(14) }}

• 确保中间索引偏向左侧
• 兼容负数索引
• 提高计算速度
• 避免整数溢出

15. 快速排序函数的核心逻辑如下，横线处应填入的代码是（ ）。

int partition(vector<int>& arr, int low, int high) {  
    int pivot = arr[high];  
    int i = low - 1;  
    for (int j = low; j < high; j++) {  
        if (arr[j] < pivot) {  
            i++;  
            swap(arr[i], arr[j]);  
        }  
    }  
    swap(arr[_______], arr[high]);  
    return i + 1;  
}  
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
 
        quickSort(arr, low, pi - 1);  
        quickSort(arr, pi + 1, high);
    }
}

{{ select(15) }}

• i
• i + 1
• j
• low

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

1. 循环链表是一种首尾相连的链表，其最后一个结点的后继指针指向头结点。（ ） {{ select(16) }}

• 正确
• 错误

2. 快速排序是稳定排序，归并排序不是稳定排序。（ ） {{ select(17) }}

• 正确
• 错误

3. 贪心算法总能找到局部最优解。（ ） {{ select(18) }}

• 正确
• 错误

4. 如果整数 a 除以 m 的余数等于 b 除以 m 的余数，则称 a 与 b 对模 m 同余。（ ） {{ select(19) }}

• 正确
• 错误

5. 在有序链表中是可以进行二分查找的，不过它不会比直接遍历查找更快。（ ） {{ select(20) }}

• 正确
• 错误

6. 快速排序的基准元素选择中间值可以避免最坏情况。（ ） {{ select(21) }}

• 正确
• 错误

7. 判断一个整数 n 是否为素数时，只需检查 2 到 √n 之间的所有整数是否能整除 n 即可。（ ） {{ select(22) }}

• 正确
• 错误

8. 递归算法必须有明确的递归终止条件（边界条件），否则会导致无限递归。（ ） {{ select(23) }}

• 正确
• 错误

9. 分治算法将问题分解为规模更小的子问题。（ ） {{ select(24) }}

• 正确
• 错误

10. 链表的空间利用率一定高于数组。（） {{ select(25) }}

• 正确
• 错误