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

1. 下面关于链表和数组的描述，错误的是（ ）？ {{ select(1) }}

• 当数据数量不确定时，为了应对各种可能的情况，需要申请一个较大的数组，可能浪费空间；此时用链表比较合适，大小可动态调整
• 在链表中访问节点的效率较低，时间复杂度为 (O(n))
• 链表插入和删除元素效率较低，时间复杂度为 (O(n))
• 链表的节点在内存中是分散存储的，通过指针连在一起

2. 在循环单链表中，节点的next指针指向下一个节点，最后一个节点的next指针指向（ ）？ {{ select(2) }}

• 当前节点
• nullptr
• 第一个节点
• 上一个节点

3. 实现删除链表中值为val的节点（含虚拟头节点），横线处应填的最佳代码是（ ）？ {{ select(3) }}

• dummyHead->next = head; cur = dummyHead;
• dummyHead->next = head->next; cur = dummyHead;
• dummyHead->next = head; cur = dummyHead->next;
• dummyHead->next = head->next; cur = dummyHead->next;

4. 对fibA和fibB两个求斐波那契数列的函数，说法错误的是（ ）？ {{ select(4) }}

• 两个函数实现的功能相同
• fibA采用递推方式
• fibB采用递归方式
• fibA时间复杂度为 (O(n))，fibB的时间复杂度为 (O(n^2))

5. 用辗转相除函数gcd(24, 36)求正方形分块的边长，函数gcd的调用顺序为（ ）？ {{ select(5) }}

• gcd(24, 36)、gcd(24,12)、gcd(12,0)
• gcd(24, 36)、gcd(12, 24)、gcd(0, 12)
• gcd(24, 36)、gcd(24, 12)
• gcd(24, 36)、gcd(12, 24)

6. 找出自然数n所有质因子的函数，横线处能填写的最佳代码是（ ）？ {{ select(6) }}

• for(int i=3;i<=n;i++)
• for (int i=3;i*i<=n;i++)
• for(int i=3;i<=n;i+=2)
• for(int i=3;i*i<=n;i+=2)

7. 关于埃拉托斯特尼（埃氏）筛法的代码，说法正确的是（ ）？ {{ select(7) }}

• 代码的时间复杂度是 (O(n\sqrt{n}))
• 在标记非素数时，代码从 (i^2) 开始，可以减少重复标记
• 代码会输出所有小于等于n的奇数
• 调用函数sieve_Eratosthenes(10)，函数返回值的数组中包含的元素有：2, 3, 5, 7, 9

8. 关于线性筛法的代码，说法正确的是（ ）？ {{ select(8) }}

• 线性筛的时间复杂度是 (O(n))
• 每个合数会被其所有的质因子标记一次
• 线性筛和埃拉托斯特尼筛的实现思路完全相同
• 以上都不对

9. 关于快速排序算法，说法正确的是（ ）？ {{ select(9) }}

• 快速排序通过递归对子问题进行求解
• 快速排序的最坏时间复杂度是 (O(n log n))
• 快速排序是一个稳定的排序算法
• 在最优情况下，快速排序的时间复杂度是 (O(n))

10. 下面关于归并排序，描述正确的是（ ）？ {{ select(10) }}

• 归并排序是一个不稳定的排序算法
• 归并排序的时间复杂度在最优、最差和平均情况下都是 (O(n log n))
• 归并排序需要额外的 (O(1)) 空间
• 对于输入数组 {12, 11, 13, 5, 6, 7}，代码输出结果为：7 6 5 13 12 11

11. 关于递归实现的二分查找函数，描述不正确的是（ ）？ {{ select(11) }}

• 函数采用二分查找，每次计算当前搜索区间的中点，然后根据中点的元素值排除一半搜索区间
• 函数采用递归求解，每次问题的规模减小一半
• 递归的终止条件是中间元素的值等于target，若数组中不包含该元素，递归不会终止
• 算法的时间复杂度为 (O(log n))

12. 查找有序数组中target左边界的函数，横线处应填写的代码为（ ）？ {{ select(12) }}

• right = middle - 1;
• right = middle;
• right = middle + 1;
• 以上都不对

13. 用贪心算法计算能满足孩子的最多数目，横线处应填写的代码为（ ）？ {{ select(13) }}

• result++; index--;
• result--; index--;
• result--; index++;
• result++; index++;

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

• 分治算法将问题分成子问题，然后分别解决子问题，最后合并结果
• 归并排序采用了分治思想
• 快速排序采用了分治思想
• 冒泡排序采用了分治思想

15. 关于高精度减法函数，说法正确的是（ ）？ {{ select(15) }}

• 如果数组a表示的整数小于数组b表示的整数，代码会正确返回二者的差为负数
• 代码假设输入数字是以倒序存储的，例如 500 存储为 {0, 0, 5}
• 代码的时间复杂度为 (O(a.size() + b.size()))
• 当减法结果为0时，结果数组仍然会存储很多个元素