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

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

news 2024/10/23 3:14:56

2024.09 GESP CCF C++五级编程能力等级考试认证真题

1 单选题（每题 2 分，共 30 分）
第 1 题下面关于链表和数组的描述，错误的是（）。
A. 数组大小固定，链表大小可动态调整。
B. 数组支持随机访问，链表只能顺序访问。
C. 存储相同数目的整数，数组比链表所需的内存多。
D. 数组插入和删除元素效率低，链表插入和删除元素效率高。

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

第 3 题对下面两个函数，说法错误的是（）。
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;
}
A. sumA体现了迭代的思想。
B. SumB采用的是递归方式。
C. SumB函数比SumA的时间效率更高。
D. 两个函数的实现的功能相同。

第 4 题有如下函数 fun ，则 fun(20, 12) 的返回值为（）。
int fun(int a, int b) {
if (a % b == 0)
return b;
else
return fun(b, a % b);
}
A. 20
B. 12
C. 4
D. 2

第 5 题下述代码实现素数表的埃拉托斯特尼筛法，筛选出所有小于等于 n 的素数，则横线上应填的最佳代码是( )。
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;
}
A. for (int j = i; j <= n; j++)
B. for (int j = i * i; j <= n; j++)
C. for (int j = i * i; j <= n; j += i)
D. for (int j = i; j <= n; j += i)

第 6 题下述代码实现素数表的线性筛法，筛选出所有小于等于 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);
________________________________ { // 在此处填入代码
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. for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)
B. for (int j = 1; j < primes.size() && i * j <= n; j++)
C. for (int j = 2; j < primes.size() && i * primes[j] <= n; j++)
D. 以上都不对

第 7 题下面函数可以将 n 的所有质因数找出来，其时间复杂度是（）。
#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;

}
A.O(n^2)

B.O(n log n)
C.O(√n log n)
D.O(n)

第 8 题现在用如下代码来计算（个相乘），其时间复杂度为（）。
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);
}
A.O(n)
B.O(n^2)
C.O(n log n)
D.O(n log n)

第 9 题假设快速排序算法的输入是一个长度为的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项（）描述的是在这种情况下的快速排序行为。
A. 快速排序对于此类输入的表现最好，因为数组已经排序。
B. 快速排序对于此类输入的时间复杂度是O(n log n)。
C. 快速排序对于此类输入的时间复杂度是O(n^2)。
D. 快速排序无法对此类数组进行排序，因为数组已经排序。

第 10 题考虑以下C++代码实现的归并排序算法：

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 函数的递归调用次数大约是（）。
A.O(1)
B.O(n)
C.O(log n)
D.O(n log n)