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

1. 与数组相比，链表在（ ）操作上通常具有更高的效率？ {{ select(1) }}

• 随机访问元素
• 查找指定元素
• 在已知位置插入或删除节点
• 遍历所有元素

2. 双向链表的is_empty()函数判断链表是否为空，横线处不能填写（ ）？ {{ select(2) }}

• return head == nullptr;
• return tail == nullptr;
• return head.data == 0;
• return size == 0;

3. 完善双向链表的append()函数（在尾部增加新节点），横线上应填写（ ）？ {{ select(3) }}

• tail->next = newNode;
• newNode->prev = tail; tail = newNode;
• tail = newNode; newNode->prev = tail; tail->next = newNode;
• tail->next = newNode; newNode->prev = tail; tail = newNode;

4. 用循环链表解决约瑟夫问题的findLastSurvival()函数，横线上应填写（ ）？ {{ select(4) }}

• p = prev->next; delete p; prev->next = p->next;
• prev->next = p->next; delete p; p = prev->next;
• p = prev->next; delete p; prev->next = p->next;
• prev->next = p->next; p = prev->next; delete p;

5. 关于判断正整数是否为质数的代码，说法正确的是（ ）？ {{ select(5) }}

• 代码存在错误，比如5是质数，但因为5%5余数是0返回了false
• finish_number的值应该是n/2，当前写法将导致错误
• 当前while循环正确的前提是：所有大于3的质数都符合6k±1形式
• 将while循环改为普通for循环，执行效果和执行时间相同

6. 关于两种求解最大公约数的gcd0和gcd1函数，说法错误的是（ ）？ {{ select(6) }}

• gcd0()函数的时间复杂度为 (O(log n))
• gcd1()函数的时间复杂度为 (O(n))
• 一般说来，gcd0()的效率高于gcd1()
• gcd1()中的循环应修改为for (int i = small; i > 1; --i)

7. 关于判断整数是否为质数的代码，错误的说法是（ ）？ {{ select(7) }}

• 埃氏筛算法相对于该代码效率更高
• 线性筛算法相对于该代码效率更高
• 该代码筛选连续数中质数时存在重复计算，效率不高
• 埃氏筛算法比该代码及线性筛算法效率都高

8. 唯一分解定理描述了正整数的什么性质？（ ） {{ select(8) }}

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

9. 关于递归求数组最大值的find_max_recursive函数，算法说法错误的是（ ）？ {{ select(9) }}

• 该算法采用分治算法
• 该算法是递归实现
• 该算法采用贪心算法
• 该算法不是递推算法

10. 关于迭代求数组最大值的find_max函数，说法错误的是（ ）？ {{ select(10) }}

• 该函数采用迭代算法
• 该函数的时间复杂度为 (O(n))
• 和上题递归版本相比，无栈的创建和销毁开销
• 本题函数和上题递归版本的空间复杂度相同

11. 关于在升序数组中查找目标值最后一次出现位置的binary_search_last_occurrence函数，说法正确的是（ ）？ {{ select(11) }}

• 当数组存在重复target时，总能返回最后一个target的位置
• 当target小于所有元素时，函数会返回0
• 循环条件改为while (low <= high) 执行效果相同且准确性更高
• 将mid计算改为(low + high) / 2 效果相同

12. 关于二分法求平方根的代码，说法错误的是（ ）？ {{ select(12) }}

• 阶段1用于寻找正整数n的正完全平方根
• 阶段2用于寻找非完全平方根的小数形式
• 代码中check_int用于处理浮点误差导致的完全平方根判断
• 阶段2中浮点数比较条件会导致死循环

13. 关于硬币找零的代码，相关说法正确的是（ ）？ {{ select(13) }}

• 上述代码采用贪心算法实现
• 针对本题要求，该代码总能找到最优解
• 上述代码采用枚举算法
• 上述代码采用分治算法

14. 关于随机选择基准值的快速排序算法，说法错误的是（ ）？ {{ select(14) }}

• 变量i用于记录大于基准值的元素边界
• 随机选择基准值可避免最坏时间复杂度 (O(n^2))
• 快速排序平均时间复杂度是 (O(n log n))
• 快速排序是稳定排序算法

15. 关于高精度除法函数div，横线上应填写的代码为（ ）？ {{ select(15) }}

• r.d[0] = a.d[i]; r.len++;
• r.d[i] = a.d[i]; r.len++;
• r.d[i] = a.d[i]; r.len = 1;
• r.d[0] = a.d[i]; r.len = 1;