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

1. 在单链表中，要删除结点 p 的后继结点，正确的操作是（ ）{{ select(1) }}

• 直接 delete p->next;
• 执行 p = p->next;
• 执行 p->next = p;
• 把 p 的后继指向其后继的后继，并释放原后继结点

2. 用辗转相除法计算 gcd(36, 24)，结果是（ ）{{ select(2) }}

• 6
• 8
• 12
• 24

3. 以下代码实现在单链表表头插入一个新结点，横线处应填入的代码是（ ）

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

void insertHead(Node*& head, int x)
{
    Node* t = new Node;
    t->val = x;
    t->next = head;
    head = ______; // 填入代码
}

{{ select(3) }}

• head
• t
• t->next
• nullptr

4. 埃氏筛法筛素数的主要思想是（ ）{{ select(4) }}

• 从小到大把每个数都删除
• 只筛除偶数
• 随机标记一些数为合数
• 从 $2$ 开始，把每个质数的倍数标记为合数

5. 高精度加法逐位相加时，设当前位两个数字与进位之和为 sum，正确的处理方式是（ ）{{ select(5) }}

• 当前位存 sum % 10，进位为 sum / 10
• 当前位存 sum，不进位
• 当前位存 sum / 10，进位为 sum % 10
• 直接丢弃进位

6. 关于贪心算法，下列说法正确的是（ ）{{ select(6) }}

• 每一步都直接计算出全局最优解
• 每一步都做出当前看来最优的选择
• 需要大量回溯来修正错误的决策
• 与动态规划完全一样

7. 使用二分查找的前提条件是（ ）{{ select(7) }}

• 数组必须是无序的
• 数组长度必须是偶数
• 数组必须是有序的
• 数组元素必须互不相同

8. 表达式 (2024 % 7 + 1) % 7 的值是（ ）{{ select(8) }}

• 0
• 1
• 2
• 3

9. 比较两个高精度正整数 a 和 b 的大小，正确的做法是（ ）{{ select(9) }}

• 从低位到高位逐位比较
• 先比较位数，位数相同时再从高位到低位逐位比较
• 直接比较字符串长度即可
• 随机抽取若干位比较

10. 归并排序的时间复杂度是（ ）{{ select(10) }}

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

11. 以下递归函数的调用结果 f(5) 是（ ）

int f(int n)
{
    if (n <= 1)
        return 1;
    return n * f(n - 1);
}

{{ select(11) }}

• 15
• 720
• 24
• 120

12. 在有序数组 {1, 3, 5, 7, 9, 11} 中用二分查找查找数字 $7$。每次比较当前区间中间位置的元素（设 $mid = \lfloor (l+r)/2 \rfloor$，$l, r$ 为当前区间左右端下标，初始区间为整个数组），需要进行（ ）次比较才能找到 {{ select(12) }}

• 1
• 2
• 3
• 4

13. 高精度除法（大整数除以整数）通常采用的做法是（ ）{{ select(13) }}

• 用 long long 直接计算
• 先转换为浮点数再计算
• 用位运算代替除法
• 模拟竖式除法，逐位试商

14. 快速排序中，一次分区（partition）操作结束后，基准元素会被放到（ ）{{ select(14) }}

• 数组的开头
• 它最终排序后的正确位置
• 数组的正中间
• 随机位置

15. 下列关于枚举法的说法，正确的是（ ）{{ select(15) }}

• 逐一列举所有候选解并逐一检验
• 枚举法只能解决数学计算问题
• 枚举法的时间复杂度一定是最优的
• 枚举法不能与模拟法结合使用

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

1. 单链表的每个结点只有一个指向后继结点的指针。{{ select(16) }}

• 正确
• 错误

2. 两个互质的正整数的最小公倍数是它们的乘积。{{ select(17) }}

• 正确
• 错误

3. 归并排序是一种不稳定的排序算法。{{ select(18) }}

• 正确
• 错误

4. 贪心算法一定能得到问题的全局最优解。{{ select(19) }}

• 正确
• 错误

5. 在单链表中删除一个结点，只需要知道该结点本身的指针，不需要知道它的前驱结点。{{ select(20) }}

• 正确
• 错误

6. 任何一个大于 $1$ 的合数，都至少有一个不超过 $\sqrt n$ 的质因子。{{ select(21) }}

• 正确
• 错误

7. 快速排序的最坏时间复杂度为 $O(n^2)$。{{ select(22) }}

• 正确
• 错误

8. 递归算法可以不设置递归终止条件（边界条件）。{{ select(23) }}

• 正确
• 错误

9. 在循环链表中，从任意一个结点出发都可以遍历到所有结点。{{ select(24) }}

• 正确
• 错误

10. 分治算法的基本步骤是：分解、求解子问题、合并。{{ select(25) }}

• 正确
• 错误