测验 · 佛大附属信奥 OJ

1. 与数组相比，链表在（）操作上通常具有更高的效率。

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

2. 下面C++代码实现双向链表。函数is_empty()判断链表是否为空，如链表为空返回true，否则返回false。横线处不能填写（）。 ```cpp // 节点结构体 struct Node { int data; Node* prev; Node* next; }; // 双向链表结构体 struct DoubleLink { Node* head; Node* tail; int size; DoubleLink() { head = nullptr; tail = nullptr; size = 0; } ~DoubleLink() { Node* curr = head; while (curr) { Node* next = curr->next; delete curr; curr = next; } } // 判断链表是否为空 bool is_empty() const { _______________________ } }; ```

A. `return head == nullptr;` B. `return tail == nullptr;` C. `return head.data == 0;` D. `return size == 0;`

3. 基于上题代码正确的前提下，填入相应代码完善append()，用于在双向链表尾部增加新节点，横线上应填写（）。 ```cpp void append(int data) { Node* newNode = new Node{data, nullptr, nullptr}; if (is_empty()) { head = tail = newNode; } else { _______________________ } ++size; } ```

A. ```cpp tail->next = newNode; ``` B. ```cpp newNode->prev = tail; tail = newNode; ``` C. ```cpp tail = newNode; newNode->prev = tail; tail->next = newNode; ``` D. ```cpp tail->next = newNode; newNode->prev = tail; tail = newNode; ```

4. 下列C++代码用循环链表解决约瑟夫问题，即假设n个人围成一圈，从第一个人开始数，每次数到第k 个人就出圈，输出最后留下的那个人的编号。横线上应填写（）。 ```cpp struct Node { int data; Node* next; }; Node* createCircularList(int n) { Node* head = new Node{1, nullptr}; Node* prev = head; for (int i = 2; i <= n; ++i) { Node* node = new Node{i, nullptr}; prev->next = node; prev = node; } prev->next = head; return head; } int fingLastSurvival(int n, int k) { Node* head = createCircularList(n); Node* p = head; Node* prev = nullptr; while (p->next != p) { for (int count = 1; count < k; ++count) { prev = p; p = p->next; } _______________________ } cout << "最后留下的人编号是: " << p->data << endl; delete p; return 0; } ```

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

5. 下列C++代码判断一个正整数是否是质数，说法正确的是( )。 ```cpp bool is_prime(int n) { if (n <= 1) return false; if (n == 2 || n == 3 || n == 5) return true; if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false; int i = 7; int step = 4; int finish_number = sqrt(n) + 1; while (i <= finish_number) { if (n % i == 0) return false; i += step; step = 6 - step; } return true; } ```

A. 代码存在错误，比如5是质数，但因为5 % 5余数是0返回了false B. finish_number的值应该是n / 2，当前写法将导致错误 C. 当前while循环正确的前提是：所有大于3的质数都符合6k±1形式 D. while循环修改如下，其执行效果和执行时间相同。 ```cpp for (int i = 2; i < finish_number; i++) { if (n % i == 0) return false; } return true; ```

6. 下列C++代码用两种方式求解两个正整数的最大公约数，说法错误的是( )。 ```cpp int gcd0(int big, int small) { if (big < small) { swap(big, small); } if (big % small == 0) { return small; } return gcd0(small, big % small); } int gcd1(int big, int small) { if (big < small) { swap(big, small); } for (int i = small; i >= 1; --i) { if (big % i == 0 && small % i == 0) return i; } return 1; } ```

A. gcd0()函数的时间复杂度为 $O(\log n)$ B. gcd1()函数的时间复杂度为 $O(n)$ C. 一般说来，gcd0()的效率高于gcd1() D. gcd1()中的代码`for (int i = small; i >= 1; --i)`应该修改为`for (int i = small; i > 1; --i)`

7. 下面的代码用于判断整数是否是质数，错误的说法是（）。 ```cpp bool is_prime(int n) { if (n <= 1) return false; int finish_number = static_cast<int>(sqrt(n)) + 1; for (int i = 2; i < finish_number; ++i) { if (n % i == 0) return false; } return true; } ```

A. 埃氏筛算法相对于上面的代码效率更高 B. 线性筛算法相对于上面的代码效率更高 C. 上面的代码有很多重复计算，因为不是判断单个数是否为质数，故而导致筛选出连续数中质数的效率不高 D. 相对而言，埃氏筛算法比上面代码以及线性筛算法效率都高

8. 唯一分解定理描述了关于正整数的什么性质？

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

9. 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（）。 ```cpp int find_max_recursive(const vector<int>& nums, int left, int right) { if (left == right) return nums[left]; int mid = left + (right - left) / 2; int left_max = find_max_recursive(nums, left, mid); int right_max = find_max_recursive(nums, mid + 1, right); return max(left_max, right_max); } int find_max(const vector<int>& nums) { if (nums.empty()) { throw invalid_argument("输入数组不能为空"); } return find_max_recursive(nums, 0, nums.size() - 1); } ```

A. 该算法采用分治算法 B. 该算法是递归实现 C. 该算法采用贪心算法 D. 该算法不是递推算法

10. 下面的C++代码，用于求一系列数据中的最大值。有关其算法说法错误的是（）。 ```cpp int find_max(const vector<int>& nums) { if (nums.empty()) { throw invalid_argument("输入数组不能为空"); } int max_value = nums[0]; for (int num : nums) { if (num > max_value) { max_value = num; } } return max_value; } ```

A. 本题find_max()函数采用的是迭代算法 B. 本题find_max()函数的时间复杂度为 $O(n)$ C. 和上一题的find_max()相比，因为没有递归，所以没有栈的创建和销毁开销 D. 本题find_max()函数和上一题的find_max()空间复杂度相同

11. 下面的 C++ 代码用于在升序数组lst中查找目标值target最后一次出现的位置。相关说法，正确的是（）。 ```cpp int binary_search_last_occurrence(const vector<int>& lst, int target) { if (lst.empty()) return -1; int low = 0, high = lst.size() - 1; while (low < high) { int mid = (low + high + 1) / 2; if (lst[mid] <= target) { low = mid; } else { high = mid - 1; } } if (lst[low] == target) return low; else return -1; } ```

A. 当lst中存在重复的target时，该函数总能返回最后一个target的位置，即便lst全由相同元素组成 B. 当target小于lst中所有元素时，该函数会返回0 C. 循环条件改为while (low <= high)程序执行效果相同，且能提高准确性 D. 将代码中`(low + high + 1) / 2`修改为`(low + high) / 2`效果相同

12. 有关下面C++代码的说法，错误的是（）。 ```cpp double sqrt_binary(long long n, double epsilon = 1e-10) { if (n < 0) { throw invalid_argument("输入必须为非负整数"); } if (n == 0 || n == 1) return n; // 阶段 1 long long low = 1, high = n; long long k = 0; while (low <= high) { long long mid = (low + high) / 2; long long mid_sq = mid * mid; if (mid_sq == n) { return mid; } else if (mid_sq < n) { k = mid; low = mid + 1; } else { high = mid - 1; } } long long next_k = k + 1; if (next_k * next_k == n) { return next_k; } // 阶段 2 double low_d = (double)k; double high_d = (double)(k + 1); double mid; while (high_d - low_d >= epsilon) { mid = (low_d + high_d) / 2; double mid_sq = mid * mid; if (mid_sq < n) { low_d = mid; } else { high_d = mid; } } double result = (low_d + high_d) / 2; long long check_int = (long long)(result + 0.5); if (check_int * check_int == n) { return check_int; } return result; } ```

A. "阶段1"的目标是寻找正整数n可能的正完全平方根 B. "阶段2"的目标是如果正整数n没有正完全平方根，则在可能产生完全平方根附近寻找带小数点的平方根 C. 代码`check_int = (long long)(result + 0.5)`是检查因浮点误差是否为正完全平方根 D. 阶段2的二分法中 `high_d - low_d >= epsilon` 不能用于浮点数比较，会进入死循环

13. 13.硬币找零问题中要求找给客户最少的硬币。coins存储可用硬币规格，单位为角，假设规格都小于10角，且一定有1角规格。amount为要找零的金额，约定必须为1角的整数倍。输出为每种规格及其数量，按规格从大到小输出，如果某种规格不必要，则输出为0。下面是其实现代码，相关说法正确的是（）。 ```cpp const int MAX_COINS = 10; int result[MAX_COINS] = {0}; // 假设最多10种面额 int find_coins(const vector<int>& coins, int amount) { sort(coins.begin(), coins.end(), greater<int>()); int n = coins.size(); for (int i = 0; i < n; ++i) { int coin = coins[i]; int num = amount / coin; result[i] = num; amount -= num * coin; if (amount == 0) break; } cout << "找零方案如下：" << endl; for (int i = 0; i < n; ++i) { cout << sorted_coins[i] << "角需要" << result[i] << "枚" << endl; } return 0; } ```

A. 上述代码采用贪心算法实现 B. 针对本题具体要求，上述代码总能找到最优解 C. 上述代码采用枚举算法 D. 上述代码采用分治算法

14. 关于下述C++代码的快速排序算法，说法错误的是（）。 ```cpp int randomPartition(std::vector<int>& arr, int low, int high) { int random = low + rand() % (high - low + 1); std::swap(arr[random], arr[high]); int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(std::vector<int>& arr, int low, int high) { if (low < high) { int pi = randomPartition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } ```

A. 在randomPartition函数中，变量i的作用是记录大于基准值的元素的边界 B. randomPartition函数随机选择基准值，可以避免输入数据特定模式导致的最坏情况下时间复杂度 $O(n^2)$ C. 快速排序平均时间复杂度是 $O(n \log n)$ D. 快速排序是稳定排序算法

15. 小杨编写了一个如下的高精度除法函数，则横线上应填写的代码为（）。 ```cpp const int MAXN = 1005; // 最大位数 struct BigInt { int d[MAXN]; // 存储数字，d[0]是个位，d[1]是十位，... int len; // 数字长度 BigInt() { memset(d, 0, sizeof(d)); len = 0; } }; // 比较两个高精度数的大小 int compare(BigInt a, BigInt b) { if(a.len != b.len) return a.len > b.len ? 1 : -1; for(int i = a.len - 1; i >= 0; i--) { if(a.d[i] != b.d[i]) return a.d[i] > b.d[i] ? 1 : -1; } return 0; } // 高精度减法 BigInt sub(BigInt a, BigInt b) { BigInt c; for(int i = 0; i < a.len; i++) { c.d[i] += a.d[i] - b.d[i]; if(c.d[i] < 0) { c.d[i] += 10; c.d[i+1]--; } } c.len = a.len; while(c.len > 1 && c.d[c.len-1] == 0) c.len--; return c; } // 高精度除法（a/b，返回商和余数） pair<BigInt, BigInt> div(BigInt a, BigInt b) { BigInt q, r; // q是商，r是余数 if(compare(a, b) < 0) { // 如果a<b，商为0，余数为a q.len = 1; q.d[0] = 0; r = a; return make_pair(q, r); } // 初始化余数r为a的前b.len位 r.len = b.len; for(int i = a.len - 1; i >= a.len - b.len; i--) { r.d[i - (a.len - b.len)] = a.d[i]; } // 逐位计算商 for(int i = a.len - b.len; i >= 0; i--) { // 把下一位加入余数 if(r.len > 1 || r.d[0] != 0) { for(int j = r.len; j > 0; j--) { r.d[j] = r.d[j-1]; } _______________________ } else { r.d[0] = a.d[i]; r.len = 1; } // 计算当前位的商 while(compare(r, b) >= 0) { r = sub(r, b); q.d[i]++; } } // 确定商的长度 q.len = a.len - b.len + 1; while(q.len > 1 && q.d[q.len-1] == 0) q.len--; // 处理余数前导零 while(r.len > 1 && r.d[r.len-1] == 0) r.len--; return make_pair(q, r); } ```

A. ```cpp r.d[0] = a.d[i]; r.len++; ``` B. ```cpp r.d[i] = a.d[i]; r.len++; ``` C. ```cpp r.d[i] = a.d[i]; r.len = 1; ``` D. ```cpp r.d[0] = a.d[i]; r.len = 1; ```

1. 下面C++代码是用欧几里得算法（辗转相除法）求两个正整数的最大公约数，a大于b还是小于b都适用。 ```cpp int gcd(int a, int b) { while (b) { int temp = b; b = a % b; a = temp; } return a; } ``` ( )

对错

2. 假设函数gcd()函数能正确求两个正整数的最大公约数，则下面的lcm()函数能求相应两数的最小公倍数。 ```cpp int lcm(int a, int b) { return a * b / gcd(a, b); } ``` ( )

对错

3. 下面的C++代码用于输出每个数对应的质因数列表，输出形如：{5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]}。 ```cpp int main() { int n, m; cin >> n >> m; if (n > m) swap(n, m); map<int, vector<int>> prime_factor; for (int i = n; i <= m; ++i) { int j = 2, k = i; while (k != 1) { if (k % j == 0) { prime_factor[i] = prime_factor[i] + j; k /= j; } else { ++j; } } } for (auto& p : prime_factor) { cout << p.first << ": "; for (int v : p.second) cout << v << " "; cout << endl; } return 0; } ``` ( )

对错

4. 下面的C++代码实现归并排序。代码在执行时，将输出一次HERE字符串，因为merge()函数仅被调用一次。 ```cpp void merge(std::vector<int>& arr, int left, int mid, int right) { std::vector<int> temp(right - left + 1); int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } for (int p = 0; p < k; ++p) { arr[left + p] = temp[p]; } } void mergeSort(std::vector<int>& arr, int left, int right) { if (left >= right) { return; } int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); std::cout << "HERE"; merge(arr, left, mid, right); } ``` ( )

对错

5. 归并排序的最好、最坏和平均时间复杂度均为 $O(n \log n)$。 ( )

对错

6. 查字典这个小学生必备技能，可以把字典视为一个已排序的数组。假设小杨要查找一个音首字母为g的单词，他首先翻到字典约一半的页数，发现该页的首字母是m，由于字母表中g位于m之前，所以排除字典后半部分，查找范围缩小到前半部分；不断重复上述步骤，直至找到首字母为g的页码。这种查字典的一系列操作可看作二分查找。 ( )

对错

7. 求解下图中A点到D点最短路径，其中A到B之间的12可以理解为距离。求解这样的问题常用Dijkstra算法，其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图（如距离不能为负值）单源最短路径的算法。从该算法的描述可以看出，Dijkstra算法是贪心算法。 ( )

对错

8. 分治算法将原问题可以分解成规模更小的子问题，使得求解问题的难度降低。但由于分治算法需要将问题进行分解，并且需要将多个子问题的解合并为原问题的解，所以分治算法的效率通常比直接求解原问题的效率低。 ( )

对错

9. 函数puzzle定义如下，则调用puzzle(7)程序会无限递归。 ```cpp int puzzle(int n) { if (n == 1) return 1; if (n % 2 == 0) return puzzle(n / 2); return puzzle(3 * n + 1); } ``` ( )

对错

10. 如下为线性筛法，用于高效生成素数表，其核心思想是每个合数只被它的最小质因数筛掉一次，时间复杂度为 $O(n)$。 ```cpp vector<int> linearSieve(int n) { vector<bool> is_prime(n + 1, true); vector<int> primes; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { primes.push_back(i); } for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) { is_prime[i * primes[j]] = false; if (i % primes[j] == 0) { break; } } } return primes; } ``` ( )

对错

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

一、单选题(每题 2 分)

二、判断题(每题 2 分)