GESP C++ 五 级 2023年12月真题（180 分钟，总分 100 分）

单选题（共 15 题，每题 2 分，共 30 分）

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

{{ select(1) }}

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

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

{{ select(2) }}

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

3. 阅读下面的C++代码，执行后其输出是()。

{{ select(3) }}

• 1->120<===>2->120
• 1->120<===>1->120
• 1->120<===>1->2->3->4->5->120
• 1->120<===>2->3->4->5->6->120

4. 下面的C++用于对lstA排序，使得偶数在前奇数在后，横线处应填入()。

{{ select(4) }}

• !isEven(lstA[j]) && isEven(lstA[j+1])
• isEven(lstA[j]) && !isEven(lstA[j+1])
• lstA[j]>lstA[j+1]
• lstA[j] < lstA[j+1]

5. 下面的C++代码用于将字符串保存到带头节点的双向链表中，并对重复的串计数，然后将最新访问的串的节点放在链头便于查找。横线处应填入代码是（）。

{{ select(5) }}

• if(pHead) {p->next=pHead->next, pHead->next->prev=p;}
• if(pHead->next) {p->next=pHead->next, pHead->next->prev=p;}
• p->next=pHead->next, pHead->next->prev=p;
• 触发异常，不能对空指针进行操作。

6. 有关下面C++代码说法正确的是（）。

{{ select(6) }}

• 如果x小于10，rc值也不会超过20
• foo可能无限递归
• foo可以求出x和y的最大公共质因子
• foo能够求出x和y的最小公倍数

7. 下面的C++代码实现对list的快速排序，有关说法，错误的是（）。

{{ select(7) }}

• qSort(less) + qSort(greater) + (vector<int>)pivot
• (vector<int>)pivot + (qSort(less) + qSort(greater))
• (qSort(less) + (vector<int>)pivot + qSort(greater))
• qSort(less) + pivot + qSort(greater)

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

{{ select(8) }}

• isPrimeA()的最坏时间复杂度是$O(\frac{N}{2})$，isPrimeB()的最坏时间复杂度是O(logN)，isPrimeA()优于isPrimeB()
• isPrimeA()的最坏时间复杂度是$O(\frac{N}{2})$，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()

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

{{ select(9) }}

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

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

{{ select(10) }}

• O(N)
• O(logN)
• O(N log N)
• O(N²)

11. 下面的C++代码使用数组模拟整数加法，可以处理超出大整数范围的加法运算。横线处应填入代码是()。

{{ select(11) }}

• c.push_back(t%10), t=t%10;
• c.push_back(t/10), t=t%10;
• c.push_back(t/10), t=t/10;
• c.push_back(t%10), t=t/10;

12. 有关下面C++代码的说法正确的是（）。

{{ select(12) }}

• 上述代码构成单向链表
• 上述代码构成双向链表
• 上述代码构成循环链表
• 上述代码构成指针链表

13. 通讯卫星在通信网络系统中主要起到（）的作用。

{{ select(13) }}

• 信息过滤
• 信号中继
• 避免攻击
• 数据加密

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

{{ select(14) }}

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

15. 下面的排序算法都要处理多趟数据，哪种排序算法不能保证在下一趟处理时从待处理数据中选出最大或最小的数据？()

{{ select(15) }}

• 选择排序
• 快速排序
• 堆排序
• 冒泡排序