测验 · 佛大附属信奥 OJ

1. 链表不具备的特点是( )。

A. 可随机访问任何一个元素 B. 插入、删除操作不需要移动元素 C. 无需事先估计存储空间大小 D. 所需存储空间与存储元素个数成正比

2. 双向链表中每个结点有两个指针域prev和next，分别指向该结点的前驱及后继结点。设p指向链表中的一个结点，它的前驱结点和后继结点均非空。要删除结点p，则下述语句中错误的是（）。

A. ```cpp p->next->prev = p->next; p->prev->next = p->prev; delete p; ``` B. ```cpp p->prev->next = p->next; p->next->prev = p->prev; delete p; ``` C. ```cpp p->next->prev = p->prev; p->next->prev->next = p->next; delete p; ``` D. ```cpp p->prev->next = p->next; p->prev->next->prev = p->prev; delete p; ```

3. 假设双向循环链表包含头尾哨兵结点(不存储实际内容)，分别为head和tail，链表中每个结点有两个指针域prev和next，分别指向该结点的前驱及后继结点。下面代码实现了一个空的双向循环链表，横线上应填的最佳代码是( )。 ```cpp // 链表结点 template <typename T> struct ListNode { T data; ListNode* prev; ListNode* next; // 构造函数 explicit ListNode(const T& val = T()) : data(val), prev(nullptr), next(nullptr) {} }; struct LinkedList { ListNode<T>* head; ListNode<T>* tail; }; void InitLinkedList(LinkedList* list) { list->head = new ListNode<T>; list->tail = new ListNode<T>; ________________________________ // 在此处填入代码 }; ```

A. ```cpp list->head->prev = list->head; list->tail->prev = list->head; ``` B. ```cpp list->head->next = list->tail; list->tail->prev = list->head; ``` C. ```cpp list->head->next = list->tail; list->tail->next = list->head; ``` D. ```cpp list->head->next = list->tail; list->tail->next = nullptr; ```

4. 用以下辗转相除法（欧几里得算法）求gcd(84, 60)的步骤中，第二步计算的数是（）。 ```cpp int gcd(int a, int b) { int big = a > b ? a : b; int small = a < b ? a : b; if (big % small == 0) { return small; } return gcd(small, big % small); } ```

A. 84和60 B. 60和24 C. 24和12 D. 12和0

5. 根据唯一分解定理，下面整数的唯一分解是正确的（）。

A. 18 = 3 × 6 B. 28 = 4 × 7 C. 36 = 2 × 3 × 6 D. 30 = 2 × 3 × 5

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

A. `j < primes.size()` B. `i * primes[j] <= n` C. `j < primes.size() && i * primes[j] <= n` D. `j <= n`

7. 在程序运行过程中，如果递归调用的层数过多，会因为（）引发错误。

A. 系统分配的栈空间溢出 B. 系统分配的堆空间溢出 C. 系统分配的队列空间溢出 D. 系统分配的链表空间溢出

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

A. 两个函数的实现的功能相同。 B. 两个函数的时间复杂度均为 $O(n)$。 C. factorialA采用递归方式。 D. factorialB采用递归方式。

9. 下算法中，（）是不稳定的排序。

A. 选择排序 B. 插入排序 C. 归并排序 D. 冒泡排序

10. 考虑以下C++代码实现的快速排序算法，将数据从小到大排序，则横线上应填的最佳代码是( )。 ```cpp int partition(vector<int>& arr, int low, int high) { int pivot = arr[high]; // 基准值 int i = low - 1; for (int j = low; j < high; j++) { ________________________________ // 在此处填入代码 } swap(arr[i + 1], arr[high]); return i + 1; } // 快速排序 void quickSort(vector<int>& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } ```

A. ```cpp if (arr[j] > pivot) { i++; swap(arr[i], arr[j]); } ``` B. ```cpp if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); } ``` C. ```cpp if (arr[j] < pivot) { swap(arr[i], arr[j]); i++; } ``` D. ```cpp if (arr[j] == pivot) { i++; swap(arr[i], arr[j]); } ```

11. 若用二分法在[1, 100]内猜数，最多需要猜（）次。

A. 100 B. 10 C. 7 D. 5

12. 下面代码实现了二分查找算法，在数组 arr 找到目标元素 target 的位置，则横线上能填写的最佳代码是（）。 ```cpp int binarySearch(int arr[], int left, int right, int target) { while (left <= right) { ________________________________ // 在此处填入代码 if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } ```

A. `int mid = left + (right - left) / 2;` B. `int mid = left;` C. `int mid = (left + right) / 2;` D. `int mid = right;`

13. 贪心算法的核心特征是（）。

A. 总是选择当前最优解 B. 回溯尝试所有可能 C. 分阶段解决子问题 D. 总能找到最优解

14. 函数int findMax(int arr[], int low, int high) 计算数组中最大元素，其中数组arr从索引low到high，（）正确实现了分治逻辑。

A. ```cpp if (low == high) return arr[low]; int mid = (low + high) / 2; return arr[mid]; ``` B. ```cpp if (low >= high) return arr[low]; int mid = (low + high) / 2; int leftMax = findMax(arr, low, mid - 1); int rightMax = findMax(arr, mid, high); return leftMax + rightMax; ``` C. ```cpp if (low > high) return 0; int mid = low + (high - low) / 2; int leftMax = findMax(arr, low, mid); int rightMax = findMax(arr, mid + 1, high); return leftMax * rightMax; ``` D. ```cpp if (low == high) return arr[low]; int mid = low + (high - low) / 2; int leftMax = findMax(arr, low, mid); int rightMax = findMax(arr, mid + 1, high); return (leftMax > rightMax) ? leftMax : rightMax; ```

15. 小杨编写了一个如下的高精度乘法函数，则横线上应填写的代码为（）。 ```cpp vector<int> multiply(vector<int>& a, vector<int>& b) { int m = a.size(), n = b.size(); vector<int> c(m + n, 0); // 逐位相乘，逆序存储 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { c[i + j] += a[i] * b[j]; } } // 处理进位 int carry = 0; for (int k = 0; k < c.size(); ++k) { ________________________________ // 在此处填入代码 c[k] = temp % 10; carry = temp / 10; } while (c.size() > 1 && c.back() == 0) c.pop_back(); return c; } ```

A. `int temp = c[k];` B. `int temp = c[k] + carry;` C. `int temp = c[k] - carry;` D. `int temp = c[k] * carry;`

1. 要删除单链表中某个结点`p`(非尾结点)，但不知道头结点，可行的操作是将`p->next`的数据拷贝到`p`的数据部分，将`p->next`设置为`p->next->next`，然后删除`p->next`。 ( )

对错

2. 链表存储线性表时要求内存中可用存储单元地址是连续的。 ( )

对错

3. 线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最小质因数筛去一次，因此效率更高。 ( )

对错

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

对错

5. 递归函数必须具有一个终止条件，以防止无限递归。 ( )

对错

6. 快速排序算法的时间复杂度与输入是否有序无关，始终稳定为 $O(n \log n)$。 ( )

对错

7. 归并排序算法的时间复杂度与输入是否有序无关，始终稳定为 $O(n \log n)$。 ( )

对错

8. 二分查找适用于对无序数组和有序数组的查找。 ( )

对错

9. 小杨有100元去超市买东西，每个商品有各自的价格，每种商品只能买1个，小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买，这体现了分治思想。 ( )

对错

10. 归并排序算法体现了分治算法，每次将大的待排序数组分成大小大致相等的两个小数组，然后分别对两个小数组进行排序，最后对排好序的两个小数组合并成有序数组。 ( )

对错

GESP C++ 五级 · 2025 年 3 月认证理论卷

一、单选题(每题 2 分)

二、判断题(每题 2 分)