一、单项选择题（每题 2 分，共 15 题）

1. 对如下定义的循环单链表，横线处填写（ ）。

{{ select(1) }}

• 
• 
• 
• 

2. 区块链技术是比特币的基础。在区块链中，每个区块指向前一个区块，构成链式列表，新区块只能接在链尾，不允许在中间插入或删除。下面代码实现插入区块添加函数，则横线处填写（ ）。

{{ select(2) }}

• 
• 
• 
• 

3. 下面关于单链表和双链表的描述中，正确的是（ ）。

{{ select(3) }}

• 双链表删除指定节点是 $O(1)$，单链表是$O(1)$
• 双链表删除指定节点是 $O(n)$，单链表是 $O(1)$
• 双链表删除指定节点是 $O(1)$，单链表是 $O(n)$
• 双链表删除指定节点是 $O(n)$，单链表是 $O(n)$

4. 假设我们有两个数 $a = 38$ 和 $b = 14$，它们对模 $m$ 同余，即 $a \equiv b \ (\text{mod} \ m)$。以下哪个值不可能是 $m$？

{{ select(4) }}

• 3
• 4
• 6
• 9

5. 下面代码实现了欧几里得算法。下面有关说法，错误的是（ ）。

{{ select(5) }}

• gcd1() 实现为递归方式
• gcd2() 实现为迭代方式
• 当 $a,b$ 较大时，gcd1() 会多次调用自身，占用较多辅助空间
• 当 $a,b$ 较大时，gcd1() 比 gcd2() 执行效率更高

6. 唯一分解定理描述的内容是（ ）。

{{ select(6) }}

• 任何正整数都可以表示为两个素数的和
• 任何大于 $1$ 的合数都可以唯一分解为有限个质数的乘积
• 两个正整数的最大公约数等于最小公倍数除以它们的乘积
• 所有素数都是奇数

7. 下述代码实现素数表的线性筛法，筛选出所有小于等于 $n$ 的素数，则横线上应填的代码是（ ）。

{{ select(7) }}

• for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
• for (int j = sqrt(n); j <= n && i * primes[j] <= n; j++)
• for (int j = 1; j <= sqrt(n); j++)
• for (int j = 1; j < n && i * primes[j] <= n; j++)

8. 下列关于排序的说法，正确的是（ ）。

{{ select(8) }}

• 快速排序是稳定排序
• 归并排序通常是稳定的
• 插入排序是不稳定排序
• 冒泡排序不是原地排序

9. 下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ）。

{{ select(9) }}

• 平均时间复杂度是 $O(n\log n)$
• 需要 $O(n)$ 的额外空间
• 最坏时间复杂度是 $O(n^2)$
• 适合大规模数据

10. 下述 C++ 代码实现了快速排序算法，最坏情况的时间复杂度是（ ）。

{{ select(10) }}

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

11. 在有序数组中查找第一个大于等于 $x$ 的元素位置，若不存在返回 $arr.size()$。以下说法正确的是（ ）。

{{ select(11) }}

• 代码逻辑正确
• while 条件应为 $l \le r$
• mid 计算错误
• 边界条件不对

12. 第 $12$ 题 小杨要把一根长度为 $L$ 的木头切成 $K$ 段，使得每段长度小于等于 $x$。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小 $x$（$x$ 为整数），则横线处填写（ ）。

{{ select(12) }}

• 
• 
• 
• 

13. 关于阶乘的两种实现方式，以下说法正确的是（ ）。

{{ select(13) }}

• 上面两种实现方式的时间复杂度相同，都为 $O(n)$。
• 上面两种实现方式的空间复杂度相同，都为 $O(n)$。
• 上面两种实现方式的空间复杂度相同，都为 $O(1)$。
• 函数 $factorial1()$ 的时间复杂度为 $O(2^n)$，函数 $factorial2()$ 的时间复杂度为 $O(n)$。

14. 给定有 $n$ 个任务，每个任务有截止时间和利润，每个任务耗时 1 个时间单位，必须在截止时间前完成，且每个时间槽最多做 1 个任务。为了在规定时间内获得最大利润，可以采用贪心策略，即按照利润从高到低排序，尽量安排，横线处应填写（ ）。

{{ select(14) }}

• 
• 
• 
• 

15. 两个数组表示的正整数进行高精度加法（低位在前），横线处应填写（ ）。

{{ select(15) }}

• 
• 
• 
• 

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

16. 数组和链表都是线性表，链表的优点是插入删除不需要移动元素，并且能随机查找。 {{ select(16) }}

• 正确
• 错误

17. 假设函数 $gcd()$ 能正确求两个正整数的最大公约数，则下面的 $lcm(a,b)$ 函数能正确求两个正整数 $a$ 和 $b$ 的最小公倍数。

{{ select(17) }}

• 正确
• 错误

18. 在单链表中，已知指针 $p$ 指向要删除的节点（非尾节点），想在 $O(1)$ 删除 $p$，可以做法是用 p->next 替换 $p$ 的值，然后删除 p->next。 {{ select(18) }}

• 正确
• 错误

19. 在求解所有不大于 $n$ 的素数时，线性筛法（欧拉筛法）都应当优于埃拉托斯特尼筛法，因为线性筛法的时间复杂度为 $O(n)$，低于埃拉托斯特尼的 $O(n \log \log n)$。

    {{ select(19) }}

• 正确
• 错误

20. 二分查找仅适用于排序数据。若输入数据无序，则仅进行一次查找，为了使用二分排序而排序通常不划算。 {{ select(20) }}

• 正确
• 错误

21. 通过在数组的第一个、最中间和最后一个这三个元素之间选择中间值作为枢轴（比较基准），快速排序算法可降低最坏情况下的概率。 {{ select(21) }}

• 正确
• 错误

22. 贪心计算在每一步都做出当前最优的局部选择，并且一旦做出选择就不再回溯；而分治算法将问题分解为若干子问题，再将子问题的解合并得到原问题的解。

    {{ select(22) }}

• 正确
• 错误

23. 以下 $fib$ 函数计算第 $n$ 项斐波那契数（$fib(0)=0$，$fib(1)=1$），其时间复杂度为 $O(n)$。

{{ select(23) }}

• 正确
• 错误

24. 递归函数一定要有终止条件，否则可能会造成栈溢出。 {{ select(24) }}

• 正确
• 错误

25. 使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。 {{ select(25) }}

• 正确
• 错误