一、选择题。(15题，每题2分，共30分)

1. 唯一分解定理描述的内容是？ {{ select(1) }}

• 任意整数都可以分解为素数的乘积
• 每个合数都可以唯一分解为一系列素数的乘积
• 两个不同的整数可以分解为相同的素数乘积
• 以上都不对
  
  

2. 贪心算法的核心思想是？ {{ select(2) }}

• 在每一步选择中都做当前状态下的最优选择
• 在每一步选择中都选择局部最优解
• 在每一步选择中都选择全局最优解
• 以上都对
  
  

3. 下面的 C++ 代码片段用于计算阶乘。请在横线处填入（ ），实现正确的阶乘计算？

{{ select(3) }}

• return n * factorial(n - 1);
• return factorial(n - 1) / n;
• return n * factorial(n);
• return factorial(n / 2) * factorial(n / 2);
  
  

4. 下面的代码片段用于在双向链表中删除一个节点。请在横线处填入（ ），使其能正确实现相应功能？

{{ select(4) }}

• if (current->next != nullptr) current->next->prev = current->prev;
• current->prev->next = current->next;
• delete current->next;
• current->prev = current->next;
  
  

5. 辗转相除法也被称为？ {{ select(5) }}

• 高斯消元法
• 费马定理
• 欧几里德算法
• 牛顿迭代法
  
  

6. 下⾯的代码⽚段⽤于计算斐波那契数列。该代码的时间复杂度是？

{{ select(6) }}

• $O(1)$
• $O(n)$
• $O(2^n)$
• $O(logn)$
  
  

7. 下⾯的代码⽚段⽤于将两个⾼精度整数进⾏相加。请在横线处填⼊（ ），使其能正确实现相应功能？

{{ select(7) }}

• result = to_string(sum % 10) + result;
• result = to_string(carry % 10) + result;
• result = to_string(sum / 10) + result;
• result = to_string(sum % 10 + carry) + result;
  
  

8. 给定序列：1，3，6，9，17，31，39，52，61，79，81，90，96。使⽤以下代码进⾏⼆分查找查找元素 82时，需要循环多少次，即最后输出的 times 值为？

{{ select(8) }}

• 2
• 5
• 3
• 4
  
  

9. 下⾯的代码⽚段⽤于判断⼀个正整数是否为素数。请对以下代码进⾏修改，使其能正确实现相应功能？

{{ select(9) }}

• num < 2 应该改为 num <= 2
• 循环条件 i * i < num 应该改为 i * i <= num
• 循环条件应该是 i <= num
• 循环体中应该是 if (num % i != 0)
  
  

10. 在埃拉托斯特尼筛法中，要筛选出不⼤于 n 的所有素数，最外层循环应该遍历什么范围？

{{ select(10) }}

• for (int i = 2; i <= n; ++i)
• for (int i = 1; i < n; ++i)
• for (int i = 2; i <= sqrt(n); ++i)
• for (int i = 1; i <= sqrt(n); ++i)
  
  

11. 素数的线性筛法时间复杂度为？ {{ select(11) }}

• $O(n)$
• $O(nloglogn)$
• $O(nlogn)$
• $O(n^2)$
  
  

12. 归并排序的基本思想是？ {{ select(12) }}

• 动态规划
• 分治
• 贪⼼算法
• 回溯算法
  
  

13. 在快速排序中，选择的主元素（pivot）会影响算法的？ {{ select(13) }}

• 不影响
• 时间复杂度
• 空间复杂度
• 时间复杂度和空间复杂度
  
  

14. 递归函数在调⽤⾃⾝时，必须满⾜（ ），以避免⽆限递归？ {{ select(14) }}

• 有终⽌条件
• 函数参数递减（或递增）
• 函数返回值固定
• 以上都对
  
  

15. 假设给定链表为:$1->3->5->7->nullptr$，若调⽤searchValue(head, 5)，函数返回值为？

{{ select(15) }}

• 返回 1
• 返回 0
• 死循环，⽆法返回
• 返回 -1
  
  

二、判断题​。(10题，每题2分，共20分)

16. 辗转相除法⽤于求两个整数的最⼤公约数。 {{ select(16) }}

• 对
• 错
  
  

17. 插⼊排序的时间复杂度是$O(NlogN)$。 {{ select(17) }}

• 对
• 错
  
  

18. ⼆分查找要求被搜索的序列是有序的，否则⽆法保证正确性。 {{ select(18) }}

• 对
• 错
  
  

19. 使⽤贪⼼算法解决问题时，每⼀步的局部最优解⼀定会导致全局最优解。 {{ select(19) }}

• 对
• 错
  
  

20. 分治算法的核⼼思想是将⼀个⼤问题分解成多个相同或相似的⼦问题进⾏解决，最后合并得到原问题的解。 {{ select(20) }}

• 对
• 错
  
  

21. 分治算法的典型应⽤之⼀是归并排序，其时间复杂度为$O(NlogN)$。 {{ select(21) }}

• 对
• 错
  
  

22. 素数表的埃⽒筛法和线性筛法的时间复杂度都是$O(NloglogN)$。 {{ select(22) }}

• 对
• 错
  
  

23. 贪⼼算法是⼀种可以应⽤于所有问题的通⽤解决⽅案。 {{ select(23) }}

• 对
• 错
  
  

24. 单链表和双链表都可以在常数时间内实现在链表头部插⼊或删除节点的操。 {{ select(24) }}

• 对
• 错
  
  

25. 在C语⾔中，递归的实现⽅式通常会占⽤更多的栈空间，可能导致栈溢出。 {{ select(25) }}

• 对
• 错
  
  

​三、​编程题。(2题，每题25分，共50分)

26. 【成绩排序】

27. 【B-smooth 数】