2024年6月CCF GESP C++五级单选题（共15题，每题2分，满分30分）

1. 用于求斐波那契数列（第1、2项为1，以后各项均是前两项之和）的C++函数fibo()属于（ ）？ {{ select(1) }}

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

2. 用于将输入金额换成最少币种组合方案的C++代码，其实现的算法是（ ）？ {{ select(2) }}

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

3. 在双链表中查找指定歌曲的查询函数，该操作的时间复杂度为（ ）？ {{ select(3) }}

• A. (O(1))
• B. (O(n))
• C. (O(log n))
• D. (O(n^2))

4. 在双向链表中加入新歌曲并作为链表第一首歌曲，横线处应填入的代码为（ ）？ {{ select(4) }}

• head->next->prev = p;
• head->next = p;
• head->prev = p;
• 触发异常，不能对空指针进行操作

5. 根据欧几里得算法编写的gcd函数，计算的是两个数的（ ）？ {{ select(5) }}

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

6. 关于递归形式的欧几里得算法gcd函数，说法错误的是（ ）？ {{ select(6) }}

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

7. 实现素数表线性筛法的代码，横线处应填入的代码是（ ）？ {{ select(7) }}

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

8. 素数线性筛法代码的时间复杂度是（ ）？ {{ select(8) }}

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

9. 为正确实现快速排序，横线处的代码应为（ ）？ {{ select(9) }}

• while (i <= mid)
• while (i < mid)
• while (i < j)
• while (i <= j)

10. 关于分治算法，以下说法正确的是（ ）？ {{ select(10) }}

• 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果
• 归并排序不是分治算法的应用
• 分治算法通常用于解决小规模问题
• 分治算法的时间复杂度总是优于 (O(n log n))

11. 使用二分查找法在有序数组1,3,6,9,17,31,39,52,61,79,81,90,96中查找数值82，与82比较的数组元素分别是（ ）？ {{ select(11) }}

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

12. 要实现高精度减法函数（假设a和b均为正数，且a表示的数比b大），代码中横线处应填写的代码为（ ）？ {{ select(12) }}

• a[i + 1]--;
• a[i]--;
• b[i + 1]--;
• b[i]--;

13. 设A和B是两个长度为n的有序数组，将其合并成一个有序数组，归并排序算法在最坏情况下至少要做（ ）次比较？ {{ select(13) }}

• n^2
• n log n
• 2n - 1
• n

14. 给定函数fun(int n)，当n=7时，函数返回值为（ ）？ {{ select(14) }}

• 0
• 1
• 21
• -11

15. 给定增加输出打印的fun函数，当n=4时，屏幕上输出的序列为（ ）？ {{ select(15) }}

• 4 3 2 1
• 1 2 3 4
• 4 2 3 1 2
• 4 2 3 2 1