当前位置：首页 > article >正文

GESP CCF C++五级编程等级考试认证真题 2024年12月

article 2024/12/25 20:19:39

GESP CCF C++五级编程等级考试认证真题 202412

1 单选题（每题 2 分，共 30 分）
第 1 题下面关于链表和数组的描述，错误的是（）。
A. 当数据数量不确定时，为了应对各种可能的情况，需要申请一个较大的数组，可能浪费空间；此时用链表比较合适，大小可动态调整。
B. 在链表中访问节点的效率较低，时间复杂度为 O(n)。
C. 链表插入和删除元素效率较低，时间复杂度为 O(n)。
D. 链表的节点在内存中是分散存储的，通过指针连在一起。

第 2 题在循环单链表中，节点的 next 指针指向下一个节点，最后一个节点的 next 指针指向（）。
A. 当前节点
B. nullptr
C. 第一个节点
D. 上一个节点

第 3 题为了方便链表的增删操作，一些算法生成一个虚拟头节点，方便统一删除头节点和其他节点。下面代码实现了删除链表中值为 val 的节点，横线上应填的最佳代码是( )。
struct LinkedNode {
   int val;
   LinkedNode* next;
   LinkedNode(int val):val(val), next(nullptr) {
   }
}
;
void removeElements(LinkedNode* head, int val) {
   if (head == nullptr) {
       return;
   }
   LinkedNode* cur;
   LinkedNode* dummyHead = new LinkedNode(0);
   //虚拟头节点
   ________________________________ // 在此处填入代码
   while(cur ->next ！= nullptr) {
       if(cur->next->val == val) {
           LinkedNode* tmp = cur->next;
           cur->next = cur->next->next;
           delete tmp;
           tmp = nullptr;
       } else {
           cur = cur ->next;
       }
   }
   head = dummyHead->next;
   delete dummyHead;
   dummyHead = nullptr;
}
A. dummyHead->next = head; cur = dummyHead;
B. dummyHead->next = head->next; cur = dummyHead;
C. dummyHead->next = head; cur = dummyHead->next;
D. dummyHead->next = head->next; cur = dummyHead->next;

第 4 题对下面两个函数，说法错误的是（）。
int fibA(int n) {
   if (n <= 1) return n;
   int f1 = 0, f2 = 1;
   for (int i = 2; i <= n; ++i) {
       int temp = f2;
       f2 = f1 + f2;
       f1 = temp;
   }
   return f2;
}
int fibB(int n) {
   if (n <= 1) return n;
   return fibB(n - 1) + fibB(n - 2);
}
A. 两个函数的实现的功能相同。
B. fibA采用递推方式。
C. fibB采用的是递归方式。
D. fibA时间复杂度为O(n)，fibB的时间复杂度为O(n^2)。

第 5 题两块长方形土地的长宽分别为和米，要将它们分成正方形的小块，使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24, 36) 来求正方形分块的边长，则函数 gcd 调用顺序为（）。
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. gcd(24, 36)、gcd(24, 12)、gcd(12, 0)
B. gcd(24, 36)、gcd(12, 24)、gcd(0, 12)
C. gcd(24, 36)、gcd(24, 12)
D. gcd(24, 36)、gcd(12, 24)

第 6 题唯一分解定理表明，每个大于1的自然数可以唯一地写成若干个质数的乘积。下面函数将自然数的所有质因素找出来，横线上能填写的最佳代码是（）。
#include <vector>
vector<int> get_prime_factors(int n) {
   vector<int> factors;
   if (n <= 1) {
       cout << "输入的数必须是大于1的正整数" << endl;
       return;
   }
   while (n % 2 == 0) {
       factors.push_back(2);
       n /= 2;
   }
   ________________________________ {
       // 在此处填入代码
       while (n % i == 0) {
           factors.push_back(i);
           n /= i;
       }
   }
   if (n > 2) {
       factors.push_back(n);
   }
   return factors;
}
A. for (int i = 3; i <= n; i ++)
B. for (int i = 3; i * i <= n; i ++)
C. for (int i = 3; i <= n; i += 2)
D. for (int i = 3; i * i <= n; i += 2)

第 7 题下述代码实现素数表的埃拉托色尼(埃氏)筛法，筛选出所有小于等于n的素数。
vector<int> 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);
           for (int j = i * i; j <= n; j += i) {
               is_prime[j] = false;
           }
       }
   }
   for (int i = sqrt(n) + 1; i <= n; i++) {
       if (is_prime[i]) {
           primes.push_back(i);
       }
   }
   return primes;
}
下面说法，正确的是（）。

A. 代码的时间复杂度是O(n√n) 。
B. 在标记非素数时，代码从i^2开始，可以减少重复标记。
C. 代码会输出所有小于等于n的奇数。
D. 调用函数 sieve_Eratosthenes(10) ，函数返回值的数组中包含的元素有： 2, 3, 5, 7, 9 。

第 8 题下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数。下面说法正确的是( )。
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);
       for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
           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;
}
A. 线性筛的时间复杂度是O(n)。
B. 每个合数会被其所有的质因子标记一次。
C. 线性筛和埃拉托色尼筛的实现思路完全相同。
D. 以上都不对

第 9 题考虑以下C++代码实现的快速排序算法：
int partition(vector<int>& arr, int left, int right) {
   int pivot = arr[right];
   // 基准值
   int i = left - 1;
   for (int j = left; j < right; j++) {
       if (arr[j] < pivot) {
           i++;
           swap(arr[i], arr[j]);
       }
   }
   swap(arr[i + 1], arr[right]);
   return i + 1;
}
// 快速排序
void quickSort(vector<int>& arr, int left, int right) {
   if (left < right) {
       int pi = partition(arr, left, right);
       quickSort(arr, left, pi - 1);
       quickSort(arr, pi + 1, right);
   }
}
以下关于快速排序的说法，正确的是（）。
A. 快速排序通过递归对子问题进行求解。
B. 快速排序的最坏时间复杂度是O(n log n)。
C. 快速排序是一个稳定的排序算法。
D. 在最优情况下，快速排序的时间复杂度是 O(n)。

第 10 题下面关于归并排序，描述正确的是（）。
A. 归并排序是一个不稳定的排序算法。
B. 归并排序的时间复杂度在最优、最差和平均情况下都是 O(n log n)。
C. 归并排序需要额外的O(1)空间。
D. 对于输入数组 {12, 11, 13, 5, 6, 7}，代码输出结果为：7 6 5 13 12 11。

第 11 题给定一个长度为n的有序数组 nums ，其中所有元素都是唯一的。下面的函数返回数组中元素 target 的索
引。
int binarySearch(vector<int> &nums, int target, int left, int right) {
   if (left > right) {
       return -1;
   }
   int middle = left + ((right - left) / 2);
   if (nums[middle] == target) {
       return middle;
   } else if (nums[middle] < target) {
       return binarySearch(nums, target, middle + 1, right);
   } else
   return binarySearch(nums, target, left, middle - 1);
}
}
int Find(vector<int> &nums, int target) {
int n = nums.size();
return binarySearch(nums, target, 0, n - 1);
}
关于上述函数，描述不正确的是（）。
A. 函数采用二分查找，每次计算搜索当前搜索区间的中点，然后根据中点的元素值排除一半搜索区间。
B. 函数采用递归求解，每次问题的规模减小一半。
C. 递归的终止条件是中间元素的值等于 target ，若数组中不包含该元素，递归不会终止。
D. 算法的复杂度为O(log n).