欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
单选题
第1题
下面C++代码用于求斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。函数fibo() 属于（ ）。
int fibo(int n) {if (n<=0)return 0;if (n==1 || n==2)return 1;int a = 1, b = 1, next;for (int i=3; i<=n; i++) {next = a + b;a = b;b = next;}return next;
}
A.枚举算法
B.贪心算法
C.迭代算法
D.递归算法
【答案】：C
【解析】
枚举算法：通过穷尽所有可能的解来找到问题的最优解
贪心算法：在每一步选择中都做出当前最优的选择，以期望最终得到全局最优解。
迭代算法：使用循环结构反复执行一系列操作，直到满足特定条件为止
递归算法：通过函数自身调用自身来解决问题，每次调用时缩小问题规模，直至达到基准情况。
本题代码使用的是迭代算法，通过循环结构计算斐波那契数列的值。
第2题
下面C++代码用于将输入金额换成最少币种组合方案，其实现算法是（ ）。
#include <iostream>
using namespace std;#define N_COINS 7
int coins[N_COINS] = {100, 50, 20, 10, 5, 2, 1}; // 货币面值，单位相同
int coins_used[N_COINS];void find_coins(int money) {for (int i=0; i<N_COINS; i++) {coins_used[i] = money / coins[i];money = money % coins[i];}return;
}
int main() {int money;cin >> money; // 输入要换算的金额find_coins(money);for (int i=0; i<N_COINS; i++)cout << coins_used[i] << endl;return 0;
}
A.枚举算法
B.贪心算法
C.迭代算法
D.递归算法
【答案】：B
【解析】
本题代码在每一步都选择当前面值最大的硬币来减少剩余金额，这是一种典型的贪心策略。因此，该算法属于贪心算法。
第3题
小杨采用如下双链表结构保存他喜欢的歌曲列表：
struct dl_node {string song;dl_node* next;dl_node* prev;
};
小杨想在头指针为head 的双链表中查找他喜欢的某首歌曲，采用如下查询函数，该操作的时间复杂度为（ ）。
dl_node* search(dl_node* head, string my_song) {dl_node* temp = head;while (temp != nullptr) {if (temp->song == my_song) return temp;temp = temp->next;}return nullptr;
}
A.O(1)
B.O(n)
C.O(logn)
D.\(O(n^2)\)
【答案】：B
【解析】
这段代码是一个在双链表中查找特定歌曲的函数。它从头节点开始，逐个遍历每个节点，直到找到匹配的歌曲或到达链表末尾。由于最坏情况下需要遍历整个链表，所以复杂度为O(n)。
第4题
小杨想在如上题所述的双向链表中加入一首新歌曲。为了能快速找到该歌曲，他将其作为链表的第一首歌曲，则下面横线上应填入的代码为（ ）。
void insert(dl_node *head, string my_song) {p = new dl_node;p->song = my_song;p->prev = nullptr;p->next = head;if (head != nullptr) {____ // 在此处填入代码}head = p;
}
A.head->next->prev = p;
B.head->next = p;
C.head->prev = p;
D.触发异常，不能对空指针进行操作。
【答案】：C
【解析】
这道题目要求在双向链表的头部插入一个新节点p。为了保证链表结构正确，需要更新原头节点的prev指针。
第5题
下面是根据欧几里得算法编写的函数，它计算的是a与b的（ ）。
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}
A.最小公倍数
B.最大公共质因子
C.最大公约数
D.最小公共质因子
【答案】：C
【解析】
这段代码实现了欧几里得算法，用于计算两个整数的最力大公约数（GCD）。函数通过不断取余和交换值，直到第二个数为0时返回第一个数。正确答案是最大公约数。
第6题
欧几里得算法还可以写成如下形式：
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}
下面有关说法，错误的是（ ）
A.本题的gcd()实现为递归方式。
B.本题的gcd()代码量少，更容易理解其辗转相除的思想。
C.当较大时， 本题的gcd()实现会多次调用自身，需要较多额外的辅助空间。
D.当较大时， 相比上题中的gcd()的实现，本题的gcd()执行效率更高。
【答案】D
【解析】
当a较大时，递归法会多次调用自身，递归过程中需要不断压入和弹出栈，这导致递归相比于迭代通常来说效率较低。
第7题
下述代码实现素数表的线性筛法，筛选出所有小于等于的素数，则横线上应填的代码是（ ）。
vector<int> linear_sieve(int n) {vector<bool> is_prime(n+1, true);vector<int> primes;is_prime[0] = is_prime[1] = 0; // 0和1两个数特殊处理for (int i=2; i<=n; ++i) {if (is_prime[i]) {primes.push_back(i);}____ { // 在此填入代码is_prime[i * primes[j]] = 0;if (i % primes[j] == 0)break;}}return primes;
}
A.for (int j=0; j<primes.size() && i * primes[j]<=n; j++)
B.for (int j=0; j<=sqrt(n) && i * primes[j]<=n; j++)
C.for (int j=0; j<=n; j++)
D.for (int j=1; j<=sqrt(n); j++)
【答案】A
【解析】
线性筛法的原理是让每个合数都被其最小的质因数筛掉。A正确，遍历已找到的素数，并确保i * primes[j] 不超过n。
第8题
上题代码的时间复杂度是（ ）。
A.\(O(n^2)\)
B.O(nlogn)
C.O(nloglogn)
D.O(n)
【答案】：D
【解析】
线性筛的时间复杂度为O(n)
第9题
为了正确实现快速排序，下面横线上的代码应为（ ）。
void qsort(vector<int>& arr, int left, int right) {int i, j, mid;int pivot;i = left;j = right;mid = (left + right) / 2; // 计算中间元素的索引pivot = arr[mid]; // 选择中间元素作为基准值do {while (arr[i] < pivot) i++;while (arr[j] > pivot) j--;if (i<=j) {swap(arr[i], arr[j]); // 交换两个元素i++; j--;}} ____; // 在此处填入代码if (left < j) qsort(arr, left, j); // 对左子数组进行快速排序if (i < right) qsort(arr, i, right); // 对右子数组进行快速排序
}
A.while (i<=mid)
B.while (i<mid)
C.while (i<j)
D.while (i<=j)
【答案】：D
【解析】
快速排序的原理是将数组划分为两部分，然后保证前一个子数列中的数都小于后一个子数列中的数， 递归到两个子序列中分别进行快速排序。while循环的条件应为(i <=j) ， 将数组划分成[left, j] 和[i, right] 区间， 两个区间不重叠。倘若条件为(i<j)，循环结束后可能i=j，区间发生了重叠，特殊情况下无法变小，就会无限递归。因此选D。
第10题
关于分治算法，以下哪个说法正确？
A.分治算法将问题分成子问题，然后分别解决子问题，最后合并结果。
B.归并排序不是分治算法的应用。
C.分治算法通常用于解决小规模问题。
D.分治算法的时间复杂度总是优于O(nlog(n)) 。
【答案】：A
【解析】
分治算法的核心思想就是将一个复杂的问题分解为较小的子问题，递归地解决这些子问题，最后再合并它们的结果。例如，快速排序和归并排序都是典型的分治算法。分治算法实际上通常用于解决大规模问题。分治算法的时间复杂度取决于具体的实现和问题类型。例如， 快速排序的平均时间复杂度是O(nlog(n)) ， 但最坏情况下可以达到\(O(n^2)\)。
第11题
根据下述二分查找法，在排好序的数组1，3，6，9，17，31，39，52，61，79，81，90，96中查找数值82，和82比较的数组元素分别是（ ）。
int binary_search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;while (left<=right) {int mid = (left + right) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1; // 如果找不到目标元素，返回-1
}
A.52, 61, 81, 90
B.52, 79, 90, 81
C.39, 79, 90, 81
D.39, 79, 90
【答案】：C
【解析】
这道题目要求根据给定的二分查找算法，在排序好的数组中查找值82，并列出与82比较的元素。
初始范围：left=0， right=12。
第一次比较：mid=(0+12)/2=6， nums[6]=39<82，更新left=mid + 1=7。
第二次比较：mid=(7+12)/2=9， nums[9]=79<82， 更新left=mid + 1=10。
第三次比较：mid=(10+12)/2=11， nums[11]=90>82， 更新right=mid - 1=10。
第四次比较：mid=(10+10)/2=10， nums[10]=81<82，更新left=mid + 1=11。
比较过的元素依次是：39，79，90，81。答案选C。
第12题
要实现一个高精度减法函数，则下面代码中加划线应该填写的代码为（ ）
//假设a和b均为正数，且a表示的数比b大
vector<int> minus(vector<int> a, vector<int> b) {vector<int> c;int len1 = a.size();int len2 = b.size();int i, t;for (i=0; i<len2; i++) {if (a[i]<b[i]) { // 错位____ // 在此处填入代码a[i] += 10;}t = a[i] - b[i];c.push_back(t);}for (; i<len1; i++)c.push_back(a[i]);len3 = c.size();while (c[len3-1]==0) { // 去除前导0c.pop_back();len3--;}return c;
}
A.a[i+1]--;
B.a[i]--;
C.b[i+1]--;
D.b[i]--;
【答案】：A
【解析】
如果a[i]<b[i]，则需要借位处理，即从更高位a[i+1]借1（相当于10），并将当前位加上10，同时下一位减去1。因此，答案为a[i+1]--；
第13题
设和是两个长度为的有序数组，现将和合并成一个有序数组，归并排序算法在最坏情况下至少要做（ ）次比较。
A.\(n^2\)
B.nlogn
C.2n-1
D.n
【答案】：C
【解析】
归并排序中，将两个长度为n的有序数组合并，需要逐个元素进行比较。在最坏情况下，每个元素都需要与另一个数组中的所有剩余元素进行比较。总共需要进行2n-1次比较，因为每次比较后都会减少一个待比较的元素，总共有2n个元素。
第14题
给定如下函数：
int fun(int n) {if (n==1) return 1;if (n==2) return 2;return fun(n-2) - fun(n-1);
}
则当n=7时，函数返回值为（ ）。
A.0
B.1
C.21
D.-11
【答案】：D
【解析】
根据递归关系式fun(n) =fun(n-2) -fun(n-1) ， 我们可以逐步展开计算：
fun(1)=1
fun(2)=2
fun(3) =fun(1) -fun(2) =1-2=-1
fun(4) =fun(2) -fun(3) =2-(-1) = 3
fun(5) =fun(3) -fun(4) =-1-3=-4
fun(6) =fun(4) -fun(5) =3-(-4) = 7
fun(7) =fun(5) -fun(6) =-4-7=-11
因此，当n=7时，函数返回值为-11。
第15题
给定如下函数（函数功能同上题，增加输出打印）：
int fun(int n) {cout << n << " ";if (n==1) return 1;if (n==2) return 2;return fun(n-2) - fun(n-1);
}
则当时，屏幕上输出序列为（ ）。
A.4 3 2 1
B.1 2 3 4
C.4 2 3 1 2
D.4 2 3 2 1
【答案】：C
【解析】
当调用fun(4) 时， 按照递归展开过程和打印顺序进行分析：
fun(4) ：首先打印4， 然后计算fun(2) -fun(3)
fun(2) ：打印2，返回2
fun(3) ：打印3， 然后计算fun(1) -fun(2)
fun(1) ：打印1， 返回1
fun(2) ：再次打印2， 返回2
fun(3) 结果为1-2=-1
最终， fun(4) 的计算结果是2-(-1)=3。但我们关注的是打印顺序，打印顺序依次是：4 2 3 1 2。
判断题
第16题
如果将双向链表的最后一个结点的下一项指针指向第一个结点，第一个结点的前一项指针指向最后一个结点，则该双向链表构成循环链表。
A.正确
B.错误
【答案】：A
【解析】
双向链表首尾相连，形成闭环，即为循环链表。
第17题
第2题数组和链表都是线性表，链表的优点是插入删除不需要移动元素，并且能随机查找。
A.正确
B.错误
【答案】：B
【解析】
链表插入删除确实不需移动元素，但链表不能随机访问，需要遍历找到指定位置。
第18题
链表的存储空间物理上可以连续，也可以不连续。
A.正确
B.错误
【答案】：B
【解析】
链表节点在内存中可以分散存储，通过指针链接，不要求物理地址连续。
第19题
找出自然数n以内的所有质数，常常用算法有埃拉托斯特尼（埃氏）筛法和线性筛法，其中埃氏筛法效率更高。
A.正确
B.错误
【答案】：B
【解析】
埃氏筛法时间复杂度为O(nloglogn) ， 而线性筛法为O(n) ， 因此线性筛法效率更高。
第20题
唯一分解定理表明任何一个大于1的整数都可以唯一地表示为一系列质数的乘积，即质因数分解是唯一的。
A.正确
B.错误
【答案】：B
【解析】
唯一分解定理（算术基本定理）指出每个正整数都有且只有一种方式分解成质数的乘积，顺序除外。
第21题
贪心算法通过每一步选择局部最优解来获得全局最优解，但并不一定能找到最优解。
A.正确
B.错误
【答案】：A
【解析】
贪心算法在某些问题中可以得到全局最优解，但并非所有情况都适用，可能无法保证全局最优。
第22题
归并排序和快速排序都采用递归实现，也都是不稳定排序。
A.正确
B.错误
【答案】：B
【解析】
归并排序是稳定排序，保持相同元素的相对顺序，而快速排序是不稳定排序。两者均可用递归实现。
第23题
插入排序有时比快速排序时间复杂度更低。
A.正确
B.错误
【答案】：A
【解析】
在小规模数据或近乎有序的数据集上，插入排序的实际运行时间可能优于快速排序。
第24题
在进行全国人口普查时，将其分解为对每个省市县乡来进行普查和统计。这是典型的分治策略。
A.正确
B.错误
【答案】：A
【解析】
这是典型的分治策略。分治策略是一种将一个复杂问题分解成若干个较小且相互独立的子问题，分别解决这些子问题，然后将它们的结果合并以得到原问题的解的方法。在全国人口普查中，将整个国家的人口统计任务分解为各省、市、县、乡等不同层级进行普查和统计，就是应用了这种策略。
第25题
在下面C++代码中， 由于删除了变量ptr， 因此ptr所对应的数据也随之删除，故执行下述代码时，将报错。
int* ptr = new int(10);
cout << *ptr << endl;
delete ptr;
cout << ptr <<endl;
A.正确
B.错误
【答案】：B
【解析】
delete ptr释放内存， 但指针ptr仍然存在并指向已释放的地址。访问该地址是未定义行为，不一定会立即报错，但可能导致程序崩溃或其他不可预测的问题。
编程题
P10719 黑白格
【题目来源】
洛谷：[P10719 GESP202406 五级] 黑白格 - 洛谷
【题目描述】
小杨有一个 \(n\) 行 \(m\) 列的网格图，其中每个格子要么是白色，要么是黑色。
小杨想知道至少包含 \(k\) 个黑色格子的最小子矩形包含了多少个格子。
【输入】
第一行包含三个正整数 \(n,m,k\)，含义如题面所示。
之后 \(n\) 行，每行一个长度为 \(m\) 的 \(01\) 串，代表网格图第 \(i\) 行格子的颜色，如果为 \(0\)，则对应格子为白色，否则为黑色。
【输出】
输出一个整数，代表至少包含 \(k\) 个黑色格子的最小子矩形包含格子的数量，如果不存在则输出 \(0\)。
【输入样例】
4 5 5
00000
01111
00011
00011
【输出样例】
6
【算法标签】
《洛谷 P10719 [GESP202406 五级] 黑白格》 #数学# #二分# #前缀和# #GESP# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 110;
int w[N][N]; // 存储原始矩阵
int sum[N][N]; // 前缀和数组
int n, m; // 矩阵的行数和列数int main() {int k;cin >> n >> m >> k; // 输入矩阵大小和阈值k// 读取矩阵数据并计算每行的前缀和for (int i = 1; i <= n; i++) {string s;cin >> s;for (int j = 1; j <= m; j++) {w[i][j] = s[j-1] - '0'; // 字符转数字sum[i][j] = sum[i][j-1] + w[i][j]; // 计算行前缀和}}int ans = 0; // 存储最小面积// 枚举所有可能的列区间[i,j]for (int i = 1; i <= m; i++) {for (int j = i; j <= m; j++) {vector<int> num; // 存储当前列区间的累计和int now = 0; // 当前累计和// 遍历每一行for (int l = 1; l <= n; l++) {// 计算当前行在[i,j]列区间内的和int tmp = sum[l][j] - sum[l][i-1];now += tmp;num.push_back(now);// 如果累计和达到k，尝试更新最小面积if (now >= k) {// 整个[1,l]行区间的面积if (ans == 0) ans = (j-i+1) * l;else ans = min(ans, (j-i+1) * l);// 使用二分查找寻找更小的行区间int L = 1, R = l;while (L < R) {int mid = (L + R + 1) >> 1;if (now - num[mid-1] >= k) L = mid;else R = mid - 1;}// 检查是否找到符合条件的子矩阵if (now - num[L-1] >= k) {if (ans == 0) ans = (j-i+1) * (l-L);else ans = min(ans, (j-i+1) * (l-L));}}}}}cout << ans << endl; // 输出最小面积return 0;
}
【运行结果】
4 5 5
00000
01111
00011
00011
6
P10720 小杨的幸运数字
【题目来源】
洛谷：[P10720 GESP202406 五级] 小杨的幸运数字 - 洛谷
【题目描述】
小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，\(12=2×2×3\) 的质因子有 \(2,3\)，恰好为两种不同的质因子，因此 \(12\) 是幸运数字，而 \(30\) 的质因子有 \(2,3,5\)，不符合要求，不为幸运数字。
小杨现在有 \(n\) 个正整数，他想知道每个正整数是否是他的幸运数字。
【输入】
第一行包含一个正整数\(n\) ，代表正整数个数。
之后 \(n\) 行，每行一个正整数。
【输出】
输出 \(n\) 行，对于每个正整数，如果是幸运数字，输出 \(1\) ，否则输出 \(0\)。
【输入样例】
3
7
12
30
【输出样例】
0
1
0
【算法标签】
《洛谷 P10720 [GESP202406 五级] 小杨的幸运数字》 #数论# #GESP# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 计算一个数的不同质因数个数
int calc(int x) {set<int> prime_factors; // 使用集合存储不同的质因数// 分解质因数for (int i = 2; i * i <= x; i++) {if (x % i == 0) {prime_factors.insert(i); // 插入质因数while (x % i == 0) {x /= i; // 除去所有该因数}}}// 处理剩余的大于1的质因数if (x > 1) {prime_factors.insert(x);}return prime_factors.size(); // 返回不同质因数的个数
}int main() {int n;cin >> n; // 输入数字个数for (int i = 1; i <= n; i++) {int num;cin >> num; // 输入每个数字// 计算并判断质因数个数是否为2if (calc(num) == 2) {cout << "1\n"; // 恰好两个不同质因数} else {cout << "0\n"; // 其他情况}}return 0;
}
【运行结果】
3
7
0
12
1
30
0