1. 下面代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数 N 是否素数，有关其时间复杂度的正确说法是（ ）

{{ select(1) }}

• isPrimeA() 的最坏时间复杂度是O(N)，isPrimeB() 的最坏时间复杂度是O(logN)，isPrimeB() 优isPrimeA() 。
• isPrimeA() 的最坏时间复杂度是O(N),isPrimeB() 的最坏时间复杂度是O($N^\frac{1}{2}$),isPrimeB() 优于isPrimeA() 。
• isPrimeA() 的最坏时间复杂度是O($N^\frac{1}{2}$),isPrimeB() 的最坏时间复杂度是O(N),isPrimeA() 优于isPrimeB() 。
• isPrimeA() 的最坏时间复杂度是O(logN)，isPrimeB() 的最坏时间复杂度是O(N)，isPrimeA() 优isPrimeB()

2. 下面代码用于归并排序，其中 merge() 函数被调用次数为（ ） {{ select(2) }}

• 0
• 1
• 6
• 7

3. 近年来，线上授课变得普遍，很多有助于改善教学效果的设备也逐渐流行，其中包括比较常用的手写板，那么它属于哪类设备？（）。{{ select(3) }}

• 输入
• 输出
• 控制
• 记录

4. 下面C++代码以递归方式实现字符串反序，横线处应填上代码是（ ）。

   {{ select(4) }}

• sIn[sIn.length() - 1] + sReverse(sIn.substr(0, sIn.length() - 1));
• sIn[0] + sReverse(sIn.substr(1, sIn.length() - 1));
• sReverse(sIn.substr(0, sIn.length() - 1)) + sIn[sIn.length() - 1];
• sReverse(sIn.substr(1, sIn.length() - 1)) + sIn[sIn.length() - 1];

5. 印度古老的汉诺塔传说：创世时有三根金刚柱，其中一柱从下往上按照大小顺序摞着64片黄金圆盘，当圆盘逐一从一柱借助另外一柱全部移动到另外一柱时，宇宙毁灭。移动规则：在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。下面的C++代码以递归方式实现汉诺塔，横线处应填入代码是（ ）。

{{ select(5) }}

• Hanoi(B, C, A, N - 2)
• Hanoi(B, A, C, N - 1)
• Hanoi(A, B, C, N - 2)
• Hanoi(C, B, A, N - 1)

6. 根据下面C++代码的注释，两个横线处应分别填入（ ）

   {{ select(6) }}

• compare 和 isOdd(lstA[i])
• compare(x1,y1) 和 isOdd
• compare 和 isOdd
• compare(x1,y1) 和 isOdd(lstA[i])

7. 找出自然数 N 以内的所有质数，常用算法有埃氏筛法和线性筛法，其中埃氏筛法效率更高。（ ） {{ select(7) }}

• 正确
• 错误

8. 在C++中，可以使用二分法查找链表中的元素。（ ） {{ select(8) }}

• 正确
• 错误

9. 质数的判定和筛法的目的并不相同，质数判定旨在判断特定的正整数是否为质数，而质数筛法意在筛选出范围内的所有质数。（ ） {{ select(9) }}

• 正确
• 错误

10. 下面 C++代码用于求斐波那契数列，该数列第 1 、2 项为 1，以后各项均是前两项之和。下面有关说法错误的是( )。

{{ select(10) }}

• fiboA( ) 用递归方式，fiboB( ) 循环方式
• fiboA( ) 更加符合斐波那契数列的数学定义，直观易于理解，而fiboB() 需要将数学定义转换为计算机程序实现
• fiboA( ) 不仅仅更加符合数学定义，直观易于理解，且因代码量较少执行效率更高
• fiboB( ) 虽然代码量有所增加，但其执行效率更高

11. 下面C++代码以递归方式实现合并排序 ，并假设 merge (int T[], int R[], int s, int m, int t) 函数将有序（同样排序规则） 的 T[s..m]和 T[m+1..t]归并到 R[s..t]中。横线处应填上代码是( )。

{{ select(11) }}

• mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m,t,len)
• mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m+1,t,len)
• mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m+1,t,len)
• mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m-1,t,len)

12. 下⾯C++代码中的 isPrimeA( ) 和 isPrimeB( ) 都用于判断参数 N 是否素数 ，有关其时间复杂度的正确说法是（ ）。

{{ select(12) }}

• isPrimeA( ) 的最坏时间复杂度是$O({N\over2})$，isPrimeB( ) 的最坏时间复杂度是$O(logN)$，isPrimeA( ) 优于isPrimeB( )
• isPrimeA( ) 的最坏时间复杂度是 $O({N\over2})$，isPrimeB( ) 的最坏时间复杂度是$O(N{1\over2})$，isPrimeB( ) 绝⼤多数情况下优于isPrimeA( )
• isPrimeA( ) 的最坏时间复杂度是 $O(N{1\over2})$ ，isPrimeB( ) 的最坏时间复杂度是$O(N)$，isPrimeA( ) 优于isPrimeB( )
• isPrimeA( ) 的最坏时间复杂度是 $O(logN)$ ，isPrimeB( ) 的最坏时间复杂度是 $O(N)$，isPrimeA( ) 优于isPrimeB( )

13. 下⾯C++代码用于有序 list 的⼆分查找 ，有关说法错误的是（ ）。

    

    {{ select(13) }}

• 代码采用二分法实现有序 list 的查找
• 代码采用分治算法实现有序 list 的查找
• 代码采用递归⽅式实现有序 list 的查找
• 代码采用动态规划算法实现有序 list 的查找

14. 在上题的_binarySearch 算法中，如果 lst 中有 N 个元素，其时间复杂度是（ ）。 {{ select(14) }}

• $O(N)$
• $O(logN)$
• $O(NlogN)$
• $O({N^2})$

15. 小杨想编写⼀个判断任意输入的整数 N 是否为素数的程序 ，下面哪个方法不合适？ ( ) {{ select(15) }}

• 埃氏筛法
• 线性筛法
• 二分答案
• 枚举法

16. 小杨在生日聚会时拿⼀块 $H*W$ 的巧克力招待来的 K 个小朋友，保证每位小朋友至少能获得⼀块相同大小的巧克力 。那么小杨想分出来最大边长的巧克力可以使用二分法。 ( ) {{ select(16) }}

• 正确
• 错误

17. 以下 C++代码能以递归方式实现斐波那契数列 ，该数列第 1 、2 项为 1， 以后各项均是前两项之和 。( )

{{ select(17) }}

• 正确
• 错误

18. 小杨设计了一个拆数程序，它能够将任意的非质数自然数 N 转换成若干个质数的乘积，这个程序是可以设计出来的。( )

{{ select(18) }}

• 正确
• 错误

19. 唯一分解定理描述的内容是（ ）？

{{ select(19) }}

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

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

    

    {{ select(20) }}

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

21. 辗转相除法也被称为（ ） {{ select(21) }}

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

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

{{ select(22) }}

• 2
• 5
• 3
• 4

23. 下面的代码片段用于判断⼀个正整数是否为素数。请对以下代码进行修改，使其能正确实现相应功能。（ ）{{ select(23) }}

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

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

    {{ select(24) }}

• 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)

25. 素数的线性筛法时间复杂度为（ ）。 {{ select(25) }}

• 𝑂(𝑛)
• 𝑂(𝑛 𝑙𝑜𝑔 𝑙𝑜𝑔 𝑛)
• 𝑂(𝑛 𝑙𝑜𝑔 𝑛)
• 𝑂($n^2$ )

26. 辗转相除法用于求两个整数的最大公约数。 {{ select(26) }}

• 正确
• 错误

27. 二分查找要求被搜索的序列是有序的，否则无法保证正确性。

{{ select(27) }}

• 正确
• 错误

28. 素数表的埃氏筛法和线性筛法的时间复杂度都是𝑂(N 𝑙𝑜𝑔 𝑙𝑜𝑔 N) ​。

{{ select(28) }}

• 正确
• 错误

29. 下面是根据欧几里得算法编写的函数，它计算的是a与 b的（ ）。

{{ select(29) }}

• 最小公倍数
• 最大公共质因子
• 最大公约数
• 最小公共质因子

30. 欧几里得算法还可以写成如下形式:

下面有关说法，错误的是（ ）。 {{ select(30) }}

• 本题的 gcd() 实现为递归方式。
• 本题的 gcd() 代码量少，更容易理解其辗转相除的思想。
• 当a较大时，本题的 gcd() 实现会多次调用自身，需要较多额外的辅助空间。
• 当a较大时，相比上题中的 gcd() 的实现，本题的 gcd() 执行效率更高。

31. 根据下述二分查找法，在排好序的数组 1，3，6，9，17，31，39，52，61，79，81，90，96 中查找数值 82，和82比较的数组元素分别是（ ）

{{ select(31) }}

• 52, 61, 81, 90
• 52, 79, 90, 81
• 39, 79, 90, 81
• 39, 79, 90

32. 找出自然数n以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中埃氏筛法效率更高。（ ）

    {{ select(32) }}

• 正确
• 错误

33. 唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积，即质因数分解是唯一的。（） {{ select(33) }}

• 正确
• 错误