GESP C++ 五级 · 2023 年 12 月认证理论卷

1. 下面C++代码用于求斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。下面有关说法错误的是( )。 ```cpp int fiboA(int n) { if (n <= 2) return 1; return fiboA(n - 1) + fiboA(n - 2); } int fiboB(int n) { if (n <= 2) return 1; int a = 1, b = 1, c; for (int i = 3; i <= n; i++) { c = a + b; a = b; b = c; } return c; } ```

2. 下面C++代码以递归方式实现合并排序，并假设merge(int T[], int R[], int s, int m, int t)函数将有序（同样排序规则）的T[s..m]和T[m+1..t]归并到R[s..t]中。横线处应填上代码是( )。 ```cpp void mergeSort(int SList[], int T2[], int s, int t, int len) { if (s == t) { T2[s] = SList[s]; return; } int m = (s + t) / 2; int T1[len]; ________________________; merge(T1, T2, s, m, t); } ```

3. 阅读下面的C++代码，执行后其输出是( )。 ```cpp #include <iostream> using namespace std; struct Node { int data; Node* next; }; int main() { Node* head1 = new Node{1, nullptr}; Node* p = new Node{120, nullptr}; head1->next = p; Node* head2 = new Node{2, nullptr}; Node* q = head2; for (int i = 3; i <= 6; i++) { q->next = new Node{i, nullptr}; q = q->next; } q->next = p; Node* t1 = head1; while (t1) { cout << t1->data; if (t1->next) cout << "->"; t1 = t1->next; } cout << "<===>"; Node* t2 = head2; while (t2) { cout << t2->data; if (t2->next) cout << "->"; t2 = t2->next; } return 0; } ```

4. 下面的C++用于对lstA排序，使得偶数在前奇数在后，横线处应填入( )。 ```cpp bool isEven(int x) { return x % 2 == 0; } void sortEvenOdd(int lstA[], int len) { for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len - 1 - i; j++) { if (________________________) { swap(lstA[j], lstA[j + 1]); } } } } ```

5. 下面的C++代码用于将字符串保存到带头节点的双向链表中，并对重复的串计数，然后将最新访问的串的节点放在链头便于查找。横线处应填入代码是（ ）。 ```cpp struct Node { string data; int count; Node* prev; Node* next; Node(string s) : data(s), count(1), prev(nullptr), next(nullptr) {} }; void insert(Node* pHead, string s) { Node* p = pHead->next; while (p) { if (p->data == s) { p->count++; // 将p移到链头 if (p->prev != pHead) { p->prev->next = p->next; if (p->next) p->next->prev = p->prev; ______________________; pHead->next = p; } return; } p = p->next; } // 新节点 p = new Node(s); p->next = pHead->next; if (pHead->next) pHead->next->prev = p; pHead->next = p; } ```

6. 有关下面C++代码说法正确的是（ ）。 ```cpp int foo(int x, int y) { if (x == 0) return y; return foo(x - 1, x + y); } ```

7. 下面的C++代码实现对list的快速排序，有关说法，错误的是（ ）。 ```cpp vector<int> qSort(vector<int> list) { if (list.size() <= 1) return list; int pivot = list[0]; vector<int> less, greater; for (int i = 1; i < list.size(); i++) { if (list[i] <= pivot) less.push_back(list[i]); else greater.push_back(list[i]); } vector<int> result; vector<int> sortedLess = qSort(less); vector<int> sortedGreater = qSort(greater); result.insert(result.end(), sortedLess.begin(), sortedLess.end()); result.push_back(pivot); result.insert(result.end(), sortedGreater.begin(), sortedGreater.end()); return result; } ```

8. 下面C++代码中的 isPrimeA() 和 isPrimeB() 都用于判断参数N是否素数，有关其时间复杂度的正确说法是（ ）。 ```cpp bool isPrimeA(int N) { if (N < 2) return false; for (int i = 2; i < N; i++) { if (N % i == 0) return false; } return true; } bool isPrimeB(int N) { if (N < 2) return false; for (int i = 2; i * i <= N; i++) { if (N % i == 0) return false; } return true; } ```

9. 下面C++代码用于有序list的二分查找，有关说法错误的是（ ）。 ```cpp int _binarySearch(int lst[], int left, int right, int x) { if (left > right) return -1; int mid = left + (right - left) / 2; if (lst[mid] == x) return mid; else if (lst[mid] < x) return _binarySearch(lst, mid + 1, right, x); else return _binarySearch(lst, left, mid - 1, x); } ```

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

11. 下面的C++代码使用数组模拟整数加法，可以处理超出大整数范围的加法运算。横线处应填入代码是（ ）。 ```cpp vector<int> add(vector<int> &a, vector<int> &b) { vector<int> c; int t = 0; for (int i = 0; i < a.size() || i < b.size(); i++) { if (i < a.size()) t += a[i]; if (i < b.size()) t += b[i]; ______________________; } if (t) c.push_back(1); return c; } ```

12. 有关下面C++代码的说法正确的是（ ）。 ```cpp struct Node { int data; Node* prev; Node* next; }; int main() { Node* head = new Node{0, nullptr, nullptr}; Node* p1 = new Node{1, nullptr, nullptr}; Node* p2 = new Node{2, nullptr, nullptr}; head->next = p1; p1->prev = head; p1->next = p2; p2->prev = p1; return 0; } ```

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

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

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

1. 归并排序的时间复杂度是 $O(n \log n)$。 ( )

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

3. 以下C++代码能以递归方式实现斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。( ) ```cpp int fib(int n) { if (n <= 2) return 1; return fib(n - 1) + fib(n - 2); } ```

4. 贪心算法可以达到局部最优，但可能不是全局最优解。( )

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

6. 插入排序有时比快速排序时间复杂度更低。（ ）

7. 下面的C++代码能实现十进制正整数N转换为八进制并输出。（ ） ```cpp #include <iostream> #include <stack> using namespace std; int main() { int N; cin >> N; stack<int> s; while (N > 0) { s.push(N % 8); N /= 8; } while (!s.empty()) { cout << s.top(); s.pop(); } return 0; } ```

8. 对数组int arr[] = {2, 6, 3, 5, 4, 8, 1, 0, 9, 10}执行sort(arr, arr+10)，则执行后arr中的数据调整为{0, 1, 2, 3, 4, 5, 6, 8, 9, 10}。（ ）

9. 小杨想写一个程序来算出正整数N有多少个因数，经过思考他写出了一个重复没有超过N/2次的循环就能够算出来了。（ ）

10. 同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。（ ）