学习C++从娃娃抓起！记录下CCF-GESP备考学习过程中的题目，记录每一个瞬间。
附上汇总贴：GESP编程能力等级认证C++编程真题解析 | 汇总
单选题
第1题
唯一分解定理描述的内容是（ ）？
A. 任意整数都可以分解为素数的乘积
B. 每个合数都可以唯一分解为一系列素数的乘积
C. 两个不同的整数可以分解为相同的素数乘积
D. 以上都不对
【答案】：B
【解析】
唯一分解定理：任一个素数可以分解为若干个素数的乘积，任一个合数可以唯一分解为一系列素数的乘积
第2题
贪心算法的核心思想是（ ）？
A. 在每一步选择中都做当前状态下的最优选择
B. 在每一步选择中都选择局部最优解
C. 在每一步选择中都选择全局最优解
D. 以上都对
【答案】：B
【解析】
贪心只能选择局部最优解
第3题
下面的 C++ 代码片段用于计算阶乘。请在横线处填入（ ），实现正确的阶乘计算。
int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
_________________________________ // 在此处填入代码
}
}
A. return n * factorial(n - 1);
B. return factorial(n - 1) / n;
C. return n * factorial(n);
D. return factorial(n / 2) * factorial(n / 2);
【答案】：A
【解析】
阶乘=1 * 2 * 3 * … * (n-1) * n
第4题
下面的代码片段用于在双向链表中删除一个节点。请在横线处填入（ ），使其能正确实现相应功能。
void deleteNode(DoublyListNode*& head, int value) {
DoublyListNode* current = head;
while (current != nullptr && current->val != value) {
current = current->next;
}
if (current != nullptr) {
if (current->prev != nullptr) {
____________________________________ // 在此处填入代码
} else {
head = current->next;
}
if (current->next != nullptr) {
current->next->prev = current->prev;
}
delete current;
}
}
A. if (current->next != nullptr) current->next->prev = current->prev;
B. current->prev->next = current->next;
C. delete current->next;
D. current->prev = current->next;
【答案】：B
【解析】
理解 current = current->next; 等式的左边表示指向右侧的地址。第9行else表示current为头指针。
第5题
辗转相除法也被称为（ ）
A. 高斯消元法
B. 费马定理
C. 欧几里德算法
D. 牛顿迭代法
【答案】：C
【解析】
高斯消元用来解线性方程组，费马小定理，a与p互质， a p − 1 % p = 1 a^{p-1}\ \%\ p = 1 ap−1 % p=1，牛顿迭代法也是用来求方程的解
第6题
下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是（ ）？
int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
A.O(1)
B.O(n)
C. O ( 2 n ) O(2^n) O(2n)
D.O(logn)
【答案】：C
【解析】
每一个数都变为了2个，可以画成二叉树，结论就是 O ( 2 n ) O(2^n) O(2n)
第7题
下面的代码片段用于将两个高精度整数进行相加。请在横线处填入（ ），使其能正确实现相应功能。
string add(string num1, string num2) {
string result;
int carry = 0;
int i = num1.size() - 1, j = num2.size() - 1;
while (i >= 0 || j >= 0 || carry) {
int x = (i >= 0) ? num1[i--] - '0' : 0;
int y = (j >= 0) ? num2[j--] - '0' : 0;
int sum = x + y + carry;
carry = sum / 10;
_______________________________________
}
return result;
}
A. result = to_string(sum % 10) + result;
B. result = to_string(carry % 10) + result;
C. result = to_string(sum / 10) + result;
D. result = to_string(sum % 10 + carry) + result;
【答案】：A
【解析】
从右向左计算，result是从左至右拼接字符串的，sum%10表示剩余的数
第8题
给定序列：1，3，6，9，17，31，39，52，61，79，81，90，96。使用以下代码进行二分查找查找元素 82 时，需要循环多少次，即最后输出的 times 值为（ ）。
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
int times = 0;
while (left <= right) {
times ++;
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
cout << times << endl;
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
cout << times << endl;
return -1;
}
A. 2
B. 5
C. 3
D. 4
【答案】：D
【解析】
二分搜索，查到第4次仍没有找到，最后left>right结束循环，times留在4
第9题
下面的代码片段用于判断一个正整数是否为素数。请对以下代码进行修改，使其能正确实现相应功能。（ ）
bool isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i * i < num; ++i) {
if (num % i == 0) {
return false;
}
}
return true;
}
A. num < 2 应该改为 num <= 2
B. 循环条件 i * i < num 应该改为 i * i <= num
C. 循环条件应该是 i <= num
D. 循环体中应该是 if (num % i != 0)
【答案】：B
【解析】
如果不改为i * i <= num，传入9后计算结果错误
第10题
在埃拉托斯特尼筛法中，要筛选出不大于 n 的所有素数，最外层循环应该遍历什么范围（ ）？
vector<int> sieveOfEratosthenes(int n) {
std::vector<bool> isPrime(n + 1, true);
std::vector<int> primes;
_______________________ {
if (isPrime[i]) {
primes.push_back(i);
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
for (int i = sqrt(n) + 1; i <= n; ++i) {
if (isPrime[i]) {
primes.push_back(i);
}
}
return primes;
}
A. for (int i = 2; i <= n; ++i)
B. for (int i = 1; i < n; ++i)
C. for (int i = 2; i <= sqrt(n); ++i)
D. for (int i = 1; i <= sqrt(n); ++i)
【答案】：C
【解析】
如果到n，第6行会将所有质数都放到primes向量中，第12统计的就多余了
第11题
素数的线性筛法时间复杂度为（ ）。
A.O(n)
B.O(nloglogn)
C.O(nlogn)
D. O ( n 2 ) O(n^2) O(n2)
【答案】：A
【解析】
概念题，背下来。埃氏筛法的时间复杂度就是O(nloglogn)
第12题
归并排序的基本思想是（ ）。
A. 动态规划
B. 分治
C. 贪心算法
D. 回溯算法
【答案】：B
【解析】
基本概念
第13题
在快速排序中，选择的主元素（pivot）会影响算法的（ ）。
A. 不影响
B. 时间复杂度
C. 空间复杂度
D. 时间复杂度和空间复杂度
【答案】：B
【解析】
如果主元素是中间元素，时间复杂度约为O(nlogn)，同二分。但如果选择极端，时间复杂度会变为 O ( n 2 ) O(n^2) O(n2)（快排会变坏，希尔会窜稀）
第14题
递归函数在调用自身时，必须满足（ ），以避免无限递归？
A. 有终止条件
B. 函数参数递减（或递增）
C. 函数返回值固定
D. 以上都对
【答案】：A
【解析】
基本概念
第15题
假设给定链表为: 1->3->5->7->nullptr ，若调用 searchValue(head, 5) ，函数返回值为（ ）。
int searchValue(ListNode* head, int target) {
while (head != nullptr) {
if (head->val == target) {
return 1;
}
head = head->next;
}
return 0;
}
A. 返回 1
B. 返回 0
C. 死循环，无法返回
D. 返回 -1
【答案】：A
【解析】
第3行，如果在链表中可以找到target，就返回1。5是在链表中，所以返回1
判断题
第16题
辗转相除法用于求两个整数的最大公约数。
A.正确
B.错误
【答案】：A
【解析】
基本概念
第17题
插入排序的时间复杂度是 O(NlogN)。
A.正确
B.错误
【答案】：B
【解析】
基于比较的排序，插入、冒泡、选择的时间复杂度都是 O ( n 2 ) O(n^2) O(n2)
第18题
二分查找要求被搜索的序列是有序的，否则无法保证正确性。
A.正确
B.错误
【答案】：A
【解析】
基本概念，只有有序了才能二分查找
第19题
使用贪心算法解决问题时，每一步的局部最优解一定会导致全局最优解。
A.正确
B.错误
【答案】：B
【解析】
如01背包问题，局部最优解不一定导致全局最优
第20题
分治算法的核心思想是将一个大问题分解成多个相同或相似的子问题进行解决，最后合并得到原问题的解。
A.正确
B.错误
【答案】：A
【解析】
基本概念，归并算法就是典型的分治算法
第21题
分治算法的典型应用之一是归并排序，其时间复杂度为 O(NlogN)。
A.正确
B.错误
【答案】：A
【解析】
如归并算法，层数是logN，每层都要需要遍历所有元素N，所以是NlogN
第22题
素数表的埃氏筛法和线性筛法的时间复杂度都是O(NloglogN)。
A.正确
B.错误
【答案】：B
【解析】
线性筛时间复杂度为O(N)
第23题
贪心算法是一种可以应用于所有问题的通用解决方案。
A.正确
B.错误
【答案】：B
【解析】
动态规划问题是无法用贪心求解的
第24题
单链表和双链表都可以在常数时间内实现在链表头部插入或删除节点的操作。
A.正确
B.错误
【答案】：A
【解析】
使用O(1)的时间复杂度在头部插入或删除，如果是任意位置就不是O(1)了
第25题
在C语言中，递归的实现方式通常会占用更多的栈空间，可能导致栈溢出。
A.正确
B.错误
【答案】：A
【解析】
递归每次调用自己，都会开辟一个新的栈空间。
编程题
第26题 成绩排序
【题目描述】
有 名同学，每名同学有语文、数学、英语三科成绩。你需要按如下规则对所有同学的成绩从高到低排序：
- 比较总分，高者靠前；
- 如果总分相同，则比较语文和数学两科总分，高者靠前；
- 如果仍相同，则比较语文和数学两科的最高分，高者靠前；
- 如果仍相同，则二人并列。
你需要输出每位同学的排名，如遇 x 人并列，则他们排名相同，并留空后面的 x-1 个名次。例如，有 3 名同学并列第 1，则后一名同学自动成为第 4 名。
【输入】
第一行一个整数 N，表示同学的人数。
接下来 N 行，每行三个非负整数 c i , m i , e i c_i,m_i,e_i ci,mi,ei 分别表示该名同学的语文、数学、英语成绩。
【输出】
输出 N 行，按输入同学的顺序，输出他们的排名。
注意：请不要按排名输出同学的序号，而是按同学的顺序输出他们各自的排名
【输入样例】
6
140 140 150
140 149 140
148 141 140
141 148 140
145 145 139
0 0 0
【输出样例】
1
3
4
4
2
6
【代码详解】
#include <bits/stdc++.h>
using namespace std;
int n;
struct Stu {
int yw, sx, yy, tot, ys, max_ys, id, rk;
};
Stu stu[10005];
bool cmp(Stu x, Stu y)
{
if (x.tot != y.tot) return x.tot>y.tot; //比较总分，高者靠前
else if (x.ys != y.ys) return x.ys > y.ys; //比较语文和数学两科的总分，高者靠前
else if (x.max_ys != y.max_ys) return x.max_ys > y.max_ys; //比较语文和数学两科的最高分，高者靠前
else return x.id < y.id; //如果仍相同，按id排（排名并列的事情在main中做）
}
bool cmp2(Stu x, Stu y) //最后输出按同学的顺序输出，所以要再按id进行排序
{
return x.id < y.id;
}
int main()
{
cin >> n;
for (int i=1; i<=n; i++) { //处理每个学生的成绩
int ci, mi, ei;
cin >> ci >> mi >> ei;
stu[i].id = i;
stu[i].yw = ci, stu[i].sx = mi, stu[i].yy = ei;
stu[i].ys = ci + mi;
stu[i].max_ys = max(ci, mi);
stu[i].tot = ci + mi + ei;
}
sort(stu+1, stu+n+1, cmp); //按照规则1-4进行排序
int cnt = 1; // 定义排名
for (int i=1; i<=n; i++) {
if ((stu[i].tot==stu[i-1].tot) && (stu[i].ys==stu[i-1].ys) && (stu[i].max_ys==stu[i-1].max_ys)) { //对于并列的同学
stu[i].rk = stu[i-1].rk; //排名去前一个孩子的排名相同
}
else { // 否则赋值排名
stu[i].rk = cnt;
}
cnt++; // 不管怎样排名都在递增
}
sort(stu+1, stu+n+1, cmp2); //按同学的顺序进行排序
for (int i=1; i<=n; i++) { // 输出各自的排名
cout << stu[i].rk << endl;
}
return 0;
}
【运行结果】
6
140 140 150
140 149 140
148 141 140
141 148 140
145 145 139
0 0 0
1
3
4
4
2
6
第27题 B-smooth数
【题目描述】
小杨同学想寻找一种名为 B-smooth 数的正整数。
如果一个正整数的最大质因子不超过 B，则该正整数为 B-smooth 数。
小杨同学想知道，对于给定的 n 和 B，有多少个不超过 n 的 B-smooth 数。
【输入】
第一行包含两个正整数 ，含义如题面所示。
【输出】
输出一个非负整数，表示不超过 n 的 B-smooth 数的数量。
【输入样例】
10 3
【输出样例】
7
【代码详解】
#include <bits/stdc++.h>
using namespace std;
int n, B, ans, cnt;
int maxPrime[1000005], prime[1000005], notPrime[1000005];
void getPrime() // 使用欧拉筛
{
prime[1] = 1; // 1不是质数
maxPrime[1] = 1; // 1的最大质因子是1
for (int i=2; i<1000000; i++) { // 欧拉筛求每个质数和合数的最大质因子
if (!notPrime[i]) { // 如果是质数
prime[cnt++] = i; // 存储质数至primes数组中
maxPrime[i] = i; // 最大质因子就是质数本身
}
for (int j=0; j<cnt && i * prime[j]<1000000; j++) { // 用小于i的所有质数筛去其倍数（合数）
notPrime[i*prime[j]] = 1; // 标记其倍数为合数
maxPrime[i*prime[j]] = max(prime[j], maxPrime[i]); // 用最小质因子prime[j] 和 已经求得的i的最大质因子做比较，取最大值作为i*prime[j]的最大质因子
if (i % prime[j]==0) { // 如果prime[j]是i的因数，则停止筛，防止被后面的数字重复筛去
break;
}
}
}
}
int main()
{
cin >> n >> B;
getPrime(); // 预处理所有数据
for (int i=1; i<=n; i++) { // 统计所有最大质因子不超过B的数的数量
if (maxPrime[i]<=B) ans++;
}
cout << ans << endl; // 输出结果
return 0;
}
【运行结果】
10 3
7