GESP C++ 五级 · 2024 年 9 月认证理论卷

1. 下面关于链表和数组的描述，错误的是（ ）。

2. 通过（ ）操作，能完成在双向循环链表结点p之后插入结点s的功能（其中next域为结点的直接后继，prev域为结点的直接前驱）。

3. 对下面两个函数，说法错误的是（ ）。 ```cpp int sumA(int n) { int res = 0; for (int i = 1; i <= n; i++) { res += i; } return res; } int sumB(int n) { if (n == 1) return 1; int res = n + sumB(n - 1); return res; } ```

4. 有如下函数fun，则fun(20, 12)的返回值为（ ）。 ```cpp int fun(int a, int b) { if (a % b == 0) return b; else return fun(b, a % b); } ```

5. 下述代码实现素数表的埃拉托斯特尼筛法，筛选出所有小于等于n的素数，则横线上应填的最佳代码是( )。 ```cpp void sieve_Eratosthenes(int n) { vector<bool> is_prime(n + 1, true); vector<int> primes; for (int i = 2; i * i <= n; i++) { if (is_prime[i]) { primes.push_back(i); ________________________________ { // 在此处填入代码 is_prime[j] = false; } } } for (int i = sqrt(n) + 1; i <= n; i++) { if (is_prime[i]) { primes.push_back(i); } } return primes; } ```

6. 下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数，则横线上应填的代码是( )。 ```cpp vector<int> sieve_linear(int n) { vector<bool> is_prime(n + 1, true); vector<int> primes; for (int i = 2; i <= n / 2; i++) { if (is_prime[i]) primes.push_back(i); ________________________________ { // 在此处填入代码 is_prime[i * primes[j]] = 0; if (i % primes[j] == 0) break; } } for (int i = n / 2 + 1; i <= n; i++) { if (is_prime[i]) primes.push_back(i); } return primes; } ```

7. 下面函数可以将n的所有质因数找出来，其时间复杂度是（ ）。 ```cpp #include <iostream> #include <vector> vector<int> get_prime_factors(int n) { vector<int> factors; while (n % 2 == 0) { factors.push_back(2); n /= 2; } for (int i = 3; i * i <= n; i += 2) { while (n % i == 0) { factors.push_back(i); n /= i; } } if (n > 2) { factors.push_back(n); } return factors; } ```

8. 现在用如下代码来计算 （ 个 相乘），其时间复杂度为（ ）。 ```cpp double quick_power(double x, unsigned n) { if (n == 0) return 1; if (n == 1) return x; return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1) ? x : 1); } ```

9. 假设快速排序算法的输入是一个长度为 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项（ ）描述的是在这种情况下的快速排序行为。

10. 考虑以下C++代码实现的归并排序算法： ```cpp void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int L[n1], R[n2]; for (int i = 0; i < n1; i++) L[i] = arr[left + i]; for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void merge_sort(int arr[], int left, int right) { if (left < right) { int mid = left + (right - left) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid + 1, right); merge(arr, left, mid, right); } } ``` 对长度为n的数组arr，调用函数merge_sort(a, 0, n-1)，在排序过程中merge函数的递归调用次数大约是（ ）。

11. 现在有n个人要过河，每只船最多载2人，船的承重为100kg。下列代码中，数组weight中保存有n个人的体重（单位为kg），已经按从小到大排好序，代码输出过河所需要的船的数目，采用的思想为（ ）。 ```cpp int i, j; int count = 0; for (i = 0, j = n - 1; i < j; j--) { if (weight[i] + weight[j] <= 100) { i++; } count++; } printf("过河的船数：%d\n", count); ```

12. 关于分治算法，以下哪个说法正确？

13. 根据下述二分查找法，在排好序的数组1，3，6，9，17，31，39，52，61，79中查找数值31，循环while (left <= right)执行的次数为（ ）。 ```cpp int binary_search(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; // 如果找不到目标元素，返回-1 } ```

14. 以下关于高精度运算的说法错误的是( )。

15. 当 时，下面函数的返回值为（ ）。 ```cpp int fun(int n) { if (n == 1) return 1; else if (n >= 5) return n * fun(n - 2); else return n * fun(n - 1); } ```

1. 在操作系统中，需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU将切换到下一个进程。这种循环操作可以通过环形链表来实现。 ( )

2. 找出自然数n以内的所有质数，常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中线性筛法效率更高。 ( )

3. 唯一分解定理表明任何一个大于1的整数都可以唯一地分解为素数之和。 ( )

4. 贪心算法通过每一步选择局部最优解，从而一定能获得最优解。 ( )

5. 快速排序和归并排序的平均时间复杂度均为 $O(n \log n)$，且都是稳定排序。 ( )

6. 插入排序的时间复杂度总是比快速排序低。 ( )

7. 引入分治策略往往可以提升算法效率。一方面，分治策略减少了操作数量；另一方面，分治后有利于系统的并行优化。 ( )

8. 二分查找要求被搜索的序列是有序的，否则无法保证正确性。 ( )

9. 在C++语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。 ( )

10. 对于已经定义好的标准数学函数sin(x)，应用程序中的语句y=sin(sin(x));是一种递归调用。 ( )