选择题共15道

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

判断题共10道

16 17 18 19 20 21 22 23 24 25

编程题共2道

26 27

登录练习

E1031 202606 CCF-GESP C++五级真题-练习

选择题共15道

struct Node {
  int val;
  Node* next;
};

void insertAfterHead(Node* head, int x) {
  Node* newNode = new Node;
  newNode->val = x;
  // 在此处填入代码
}

假设head != nullptr，下面是实现单向循环链表在头节点后插入新节点的代码，横线处应填入（）。 2分

登录后查看选项

struct Node {
  int val;
  Node* next;
};

void printList(Node* head) {
  if (head == nullptr) return;
  Node* p = head;
  // 在此处填入代码
  cout << endl;
}

下面代码遍历并输出一个循环单链表，其中head指向链表的第一个节点，横线处应填入的是（）。 2分

登录后查看选项

struct Node {
  int val;
  Node* prev;
  Node* next;
}

双链表结点定义如下，若要删除双链表中的中间结点（非首尾节点）p，下面写法正确的是（）。 2分

登录后查看选项

int gcd(int a, int b) {
  return b == 0 ? a : gcd(b, a % b);
}

使用如下欧几里得算法求gcd（105，45）时，函数gcd（a，b）的递归调用序列正确的是（）。 2分

登录后查看选项

vector sieve(int n) {
  vector is_prime(n + 1, true);
  vector primes;
  if (n >= 0) is_prime[0] = false;
  if (n >= 1) is_prime[1] = false;
  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 (/* 在此处填入代码 */) break;
    }
  }
  return primes;
}

下面代码实现线性筛（欧拉筛），以筛选出n以内的所有素数。横线处的代码应为（）。 2分

登录后查看选项

06 下面关于埃氏筛法的说法正确的是（）。 2分

登录后查看选项

long long power(long long x, int n) {
  if (n == 0) return 1;
  long long res = power(x, n / 2);
  if (n % 2 == 0) return res * res;
  else return res * res * x;
}

下面代码实现了计算x^n的快速幂算法，该算法体现的编程思想是（）。 2分

登录后查看选项

int n = 40;
int cnt = 0;
while (n % 2 == 0) {
  cnt++;
  n /= 2;
}
cout << cnt;

下面代码用于统计n中因子2出现了多少次。若n=40，输出是（）。 2分

登录后查看选项

int lowerBound(vector& a, int x) {
  int l = 0, r = a.size();
  while (l < r) {
    int mid = l + (r - l) / 2;
    if (a[mid] >= x) /* 在此处填入代码 */;
    else l = mid + 1;
  }
  return l;
}

在一个有序数组中查找第一个大于或等于x的元素位置，横线处应填写（）。 2分

登录后查看选项

int binary_cut(vector& wood, int K) {
  int l = 1;
  int r = 0;
  for (int len : wood) r = max(r, len);
  while (l < r) {
    int mid = l + (r - l) / 2;
    if (check(wood, K, mid))
      /* 在此处填入代码 */;
    else l = mid + 1;
  }
  return l;
}

有若干根木头，长度存于wood。每切一刀可以把一段木头分成两段。函数check（wood，K，x）返回：用不超过K刀，能否使所有木段长度都不超过x。下面代码使用二分答案查找最小可行的x，横线处应填（）。 2分

登录后查看选项

int partition(vector& arr, int low, int high) {
  int pivot = arr[low];
  int i = low, j = high;
  while (i < j) {
    while (i < j && arr[j] >= pivot) j--;
    while (i < j && arr[i] <= pivot) i++;
    if (i < j) swap(arr[i], arr[j]);
  }
  // 在此处填入代码
  return i;
}

下面代码段实现了快速排序的划分操作（以首元素为基准），横线处代码应填入（）。 2分

登录后查看选项

12 下面哪句话最符合归并排序的思想？（） 2分

登录后查看选项

const int MAXN = 100005;
int a[MAXN];
int tempArr[MAXN];

void mergeArray(int left, int mid, int right) {
  int i = left;
  int j = mid + 1;
  int k = left;
  while (i <= mid && j <= right) {
    if (a[i] <= a[j]) {
      tempArr[k++] = a[i++];
    } else {
      tempArr[k++] = a[j++];
    }
  }
  while (i <= mid) {
    tempArr[k++] = a[i++];
  }
  while (j <= right) {
    tempArr[k++] = a[j++];
  }
  for (int p = left; p <= right; p++) {
    a[p] = tempArr[p];
  }
}

void mergeSort(int left, int right) {
  if (left >= right) {
    return;
  }
  int mid = left + (right - left) / 2;
  mergeSort(left, mid);
  mergeSort(mid + 1, right);
  mergeArray(left, mid, right);
}

在对长度为n (n≥1) 的数组进行归并排序的过程中，mergeArray函数（合并两个有序子数组的操作）被调用的次数是（）。 2分

登录后查看选项

int minBoxes(vector& w, int limit) {
  sort(w.begin(), w.end());
  int l = 0, r = w.size() - 1;
  int boxes = 0;
  while (l <= r) {
    if (w[l] + w[r] <= limit) {
      // 在此处填入代码
    } else {
      r--;
    }
    boxes++;
  }
  return boxes;
}

小杨在学校义卖会上负责打包"零食盲盒"。每个盲盒重量不同，快递盒最多承重limit克，每个快递盒最多装两个盲盒。为了尽量少用快递盒，他采用如下策略：（1）每次把最轻的盲盒和最重的盲盒尝试放在一起；（2）如果两者重量之和不超过limit，就一起装；（3）否则，只能让最重的盲盒单独装一盒。下面代码用于计算最少需要多少个快递盒，则横线处应填入的是（）。 2分

登录后查看选项

if (a[i] < b[i]) {
  a[i + 1]--;
  // 在此处填入代码
}
t = a[i] - b[i];

高精度减法中，假设两个高精度数按低位在前存储，且已经保证被减数不小于减数。下面处理借位逻辑代码中横线处应填入（）。 2分

登录后查看选项

判断题共10道

16 数组的存储空间在物理上通常是连续的，而链表的结点可以存储在不连续的内存空间中。 2分

登录后查看选项

17 带哨兵头尾节点的双向循环链表，在表头插入节点p，以下四步操作无论什么顺序执行结果都正确。

p->next = head->next;
p->prev = head;
head->next->prev = p;
head->next = p;

2分

登录后查看选项

18 对任意正整数a、b，以下两种写法的gcd函数返回值完全相同。

int gcd1(int a, int b) {
  return b ? gcd1(b, a % b) : a;
}

int gcd2(int a, int b) {
  while (b) {
    int t = b;
    b = a % b;
    a = t;
  }
  return a;
}

2分

登录后查看选项

19 在归并排序的合并操作中，如下代码片段可以正确地将两个已排序的子数组L和R合并回原数组arr中。

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++];
    else arr[k++] = R[j++];
  }
  while (i < n1) arr[k++] = L[i++];
  while (j < n2) arr[k++] = R[j++];
}

2分

登录后查看选项

20 分治法通常将一个规模较大的问题拆分为若干个规模较小、结构相似的子问题，分别求解后再合并子问题的结果。 2分

登录后查看选项

21 贪心算法只要每一步选择当前最优解，就一定能得到全局最优解。 2分

登录后查看选项

22 二分查找不仅可以应用于有序数组，也可以在不增加时间复杂度的情况下应用于有序的单链表，因为链表也支持O(1)时间内的随机访问。 2分

登录后查看选项

23 以下函数 f1 的时间复杂度比函数 f2 的更高。

void f1(int n) {
	for (int i = 1; i < n; i *= 2);
}
void f2(int n) {
	if (n <= 1) return;
	f2(n - 1);
	f2(n - 1);
}

2分

登录后查看选项

24 唯一分解定理表明，任何一个大于 1 的自然数都可以唯一地分解为若干个质数的乘积，如果不考虑质因数的顺序，这种分解方式是唯一的。 2分

登录后查看选项

25 归并排序和快速排序在平均情况下的时间复杂度均为O(nlogn)。但在稳定性方面，归并排序通常是不稳定的，而快速排序是稳定的。 2分

登录后查看选项

编程题共2道

试题名称：排排坐

时间限制：1.0s

内存限制：512.0MB

题目描述

老师正在和小朋友们分糖果。

小朋友们先在自己的手上写一个数字，然后坐成一排。

老师分发糖果的规则是：每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。

现在小朋友们都已经在自己手上写上了数字。

请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。

输入格式

输入2行，

第一行为一个正整数 n，表示小朋友的个数；

第二行为 n 个正整数 a₁, a₂, ..., a_n，表示小朋友们手上的数字，整数之间以空格分隔。

输出格式

输出一个整数，表示小朋友们可能分到的最大糖果总数量。

样例

输入样例1

5
7 5 8 9 3

输出样例1

样例解释

小朋友安排座位后从左向右每人手上数字依次是：9，8，7，5，3。

这时可以得到最多的糖果：(9) + (9+8) + (9+8+7) + (9+8+7+5) + (9+8+7+5+3) = 111。

数据范围

1 ≤ n ≤ 1000，1 ≤ a_i ≤ 1000。

25分

登录后作答

试题名称：晚宴

时间限制：1.0s

内存限制：512.0MB

题目描述

小明去参加晚宴。晚宴中有 n 个菜肴，每个菜肴都有一个美味度，第 i 个菜肴的美味度为 v_i。晚宴规定小明只能恰好选取两道菜肴，并且这两道菜肴的美味度必须要互质（即最大公约数为1）。请帮助小明选取两道菜肴，使得两道菜肴美味度之和最大。

输入格式

输入2行，

第一行为一个正整数 n，表示菜肴的个数；

第二行为 n 个整数 v₁, v₂, ..., v_n，表示菜肴的美味度，整数之间以空格分隔。

输出格式

输出一个整数，表示两道互质菜肴美味度之和的最大值。

样例

输入样例1

5
3 5 7 35 105

输出样例1

样例解释1

最优选择是3和35。

注意到，105与其他任意菜肴的最大公约数都大于1，因此无法参与合法选择。

数据范围

2 ≤ n ≤ 1000，1 ≤ v_i ≤ 1000000

数据保证不存在相同美味度的菜肴。

数据保证至少存在一种选取两道菜肴的方案。

25分

登录后作答

登录练习

E1031 202606 CCF-GESP C++五级真题-练习

选择题 共15道

01 struct Node { int val; Node* next; }; void insertAfterHead(Node* head, int x) { Node* newNode = new Node; newNode->val = x; // 在此处填入代码 }假设head != nullptr，下面是实现单向循环链表在头节点后插入新节点的代码，横线处应填入（）。 2分

02 struct Node { int val; Node* next; }; void printList(Node* head) { if (head == nullptr) return; Node* p = head; // 在此处填入代码 cout << endl; }下面代码遍历并输出一个循环单链表，其中head指向链表的第一个节点，横线处应填入的是（）。 2分

03 struct Node { int val; Node* prev; Node* next; }双链表结点定义如下，若要删除双链表中的中间结点（非首尾节点）p，下面写法正确的是（）。 2分

04 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }使用如下欧几里得算法求gcd（105，45）时，函数gcd（a，b）的递归调用序列正确的是（）。 2分

06 下面关于埃氏筛法的说法正确的是（）。 2分

07 long long power(long long x, int n) { if (n == 0) return 1; long long res = power(x, n / 2); if (n % 2 == 0) return res * res; else return res * res * x; }下面代码实现了计算x^n的快速幂算法，该算法体现的编程思想是（）。 2分

08 int n = 40; int cnt = 0; while (n % 2 == 0) { cnt++; n /= 2; } cout << cnt;下面代码用于统计n中因子2出现了多少次。若n=40，输出是（）。 2分

09 int lowerBound(vector& a, int x) { int l = 0, r = a.size(); while (l < r) { int mid = l + (r - l) / 2; if (a[mid] >= x) /* 在此处填入代码 */; else l = mid + 1; } return l; }在一个有序数组中查找第一个大于或等于x的元素位置，横线处应填写（）。 2分

12 下面哪句话最符合归并排序的思想？（） 2分

15 if (a[i] < b[i]) { a[i + 1]--; // 在此处填入代码 } t = a[i] - b[i];高精度减法中，假设两个高精度数按低位在前存储，且已经保证被减数不小于减数。下面处理借位逻辑代码中横线处应填入（）。 2分

判断题 共10道

16 数组的存储空间在物理上通常是连续的，而链表的结点可以存储在不连续的内存空间中。 2分

17 带哨兵头尾节点的双向循环链表，在表头插入节点p，以下四步操作无论什么顺序执行结果都正确。 p->next = head->next; p->prev = head; head->next->prev = p; head->next = p; 2分

18 对任意正整数a、b，以下两种写法的gcd函数返回值完全相同。 int gcd1(int a, int b) { return b ? gcd1(b, a % b) : a; } int gcd2(int a, int b) { while (b) { int t = b; b = a % b; a = t; } return a; } 2分

20 分治法通常将一个规模较大的问题拆分为若干个规模较小、结构相似的子问题，分别求解后再合并子问题的 结果。 2分

21 贪心算法只要每一步选择当前最优解，就一定能得到全局最优解。 2分

22 二分查找不仅可以应用于有序数组，也可以在不增加时间复杂度的情况下应用于有序的单链表，因为链表也支持O(1)时间内的随机访问。 2分

23 以下函数 f1 的时间复杂度比函数 f2 的更高。 void f1(int n) { for (int i = 1; i < n; i *= 2); } void f2(int n) { if (n <= 1) return; f2(n - 1); f2(n - 1); } 2分

24 唯一分解定理表明，任何一个大于 1 的自然数都可以唯一地分解为若干个质数的乘积，如果不考虑质因数的顺序，这种分解方式是唯一的。 2分

25 归并排序和快速排序在平均情况下的时间复杂度均为O(nlogn)。但在稳定性方面，归并排序通常是不稳定的，而快速排序是稳定的。 2分

编程题 共2道

试题名称：排排坐

题目描述

输入格式

输出格式

样例

输入样例1

输出样例1

样例解释

数据范围

试题名称：晚宴

题目描述

输入格式

输出格式

样例

输入样例1

输出样例1

样例解释1

数据范围

选择题共15道

01
`struct Node { int val; Node* next; }; void insertAfterHead(Node* head, int x) { Node* newNode = new Node; newNode->val = x; // 在此处填入代码 }`
假设head != nullptr，下面是实现单向循环链表在头节点后插入新节点的代码，横线处应填入（）。 2分

02
`struct Node { int val; Node* next; }; void printList(Node* head) { if (head == nullptr) return; Node* p = head; // 在此处填入代码 cout << endl; }`
下面代码遍历并输出一个循环单链表，其中head指向链表的第一个节点，横线处应填入的是（）。 2分

03
`struct Node { int val; Node* prev; Node* next; }`
双链表结点定义如下，若要删除双链表中的中间结点（非首尾节点）p，下面写法正确的是（）。 2分

04
`int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }`
使用如下欧几里得算法求gcd（105，45）时，函数gcd（a，b）的递归调用序列正确的是（）。 2分

07
`long long power(long long x, int n) { if (n == 0) return 1; long long res = power(x, n / 2); if (n % 2 == 0) return res * res; else return res * res * x; }`
下面代码实现了计算x^n的快速幂算法，该算法体现的编程思想是（）。 2分

08
`int n = 40; int cnt = 0; while (n % 2 == 0) { cnt++; n /= 2; } cout << cnt;`
下面代码用于统计n中因子2出现了多少次。若n=40，输出是（）。 2分

09
`int lowerBound(vector& a, int x) { int l = 0, r = a.size(); while (l < r) { int mid = l + (r - l) / 2; if (a[mid] >= x) /* 在此处填入代码 */; else l = mid + 1; } return l; }`
在一个有序数组中查找第一个大于或等于x的元素位置，横线处应填写（）。 2分

15
`if (a[i] < b[i]) { a[i + 1]--; // 在此处填入代码 } t = a[i] - b[i];`
高精度减法中，假设两个高精度数按低位在前存储，且已经保证被减数不小于减数。下面处理借位逻辑代码中横线处应填入（）。 2分

判断题共10道

17 带哨兵头尾节点的双向循环链表，在表头插入节点p，以下四步操作无论什么顺序执行结果都正确。
`p->next = head->next; p->prev = head; head->next->prev = p; head->next = p;`
2分

18 对任意正整数a、b，以下两种写法的gcd函数返回值完全相同。
`int gcd1(int a, int b) { return b ? gcd1(b, a % b) : a; } int gcd2(int a, int b) { while (b) { int t = b; b = a % b; a = t; } return a; }`
2分

20 分治法通常将一个规模较大的问题拆分为若干个规模较小、结构相似的子问题，分别求解后再合并子问题的结果。 2分

23 以下函数 f1 的时间复杂度比函数 f2 的更高。
`void f1(int n) { for (int i = 1; i < n; i *= 2); } void f2(int n) { if (n <= 1) return; f2(n - 1); f2(n - 1); }`
2分

编程题共2道