欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
单选题
第1题
下列代码中，输出结果是（ ）
#include <iostream>
using namespace std;
int func(int x, int y)
{int a = x, b = y;int t;t = a;a = b;b = t;cout << a << " " << b << " ";
}
int main()
{int c, d;c = 12;d = 24;func(12, 24);cout << c << " " << d << endl;
}
A.12 24 24 12
B.24 12 12 24
C.12 12 24 24
D.24 24 12 12
【答案】：B
【解析】
模拟一下func() 函数的过程， 可以发现它将变量x和y的值进行了交换， 而传入的x、y的分别是12和24， 交换之后便是24和12，因此前两个数输出24和12，后两个数字就是顺序输出的c、d的值，也就是12和24。
第2题
下面函数不能正常执行的是（ ）
A.
#include <iostream>
using namespace std;
int func()
{//...
}
int main()
{//...
}
B.
#include <iostream>
using namespace std;
int main()
{func();
}
int func()
{//...
}
C.
#include <iostream>
using namespace std;
int func()
{//...
}
int main()
{func();
}
D.
#include <iostream>
using namespace std;
int func();
int main()
{func();
}
int func()
{//...
}
【答案】：B
【解析】
在调用函数之前，应该先定义函数。
第3题
下面程序输出的是（ ）
#include <iostream>
using namespace std;
int func();
int main()
{int i = 2;cout << i << endl;for (int x = 0; x < 1; x++){int i = 10;cout << i << endl;}i = i+1;cout << i << endl;{i = i*i;cout << i << endl;}
}
A.2 2 3 9
B.2 10 3 9
C.2 10 11 121
D.2 10 3 100
【答案】：B
【解析】
注意for循环内部的变量i只作用于for循环内部， 因此第二个输出的数应该是10； 而第6行的变量i的作用域则不包含for循环内部的部分， 因此第3、4个数的值取决于第6行变量i的初始值， 模拟计算一下即可。
第4题
假设变量a的地址是0x6ffe14， 下面程序的输出是（ ） 。
#include <iostream>
using namespace std;
int main()
{int *p;int a = 10;p = &a;p++;cout << p << endl;
}
A.10
B.0x6ffe14
C.0x6ffe15
D.0x6ffe18
【答案】：D
【解析】
一个int变量占4字节， 因此当指针p移动到下一个地址时， 应当加上对应的字节数4。
第5题
如果下列程序输出的地址是0x6ffe00则cout<<a+1<<endl； 输出的是（ ）
#include <iostream>
using namespace std;
int main()
{int a[2][3] = {0};cout << a << endl;
}
A.0x6ffe04
B.0x6ffe0C
C.0x6ffe08
D.0x6ffe00
【答案】：B
【解析】
一个int变量占4字节， 而a是一个2*3规模的二维数组， 相当于是2个3长度的一维数组； a 的地址是第0个数组的第0个元素的地址，而a+1的地址是第1个数组的第0个元素的地址；中间间隔了3个int变量， 因此应当加上对应的总字节数12。
第6题
C++中，关于文件路径说法错误的是（ ）
A."GESP.txt"：指定与当前工作目录中的程序文件相同目录中的GESP.txt文件
B."../data/GESP.txt"：指定与当前工作目录中的程序文件上一级目录下的data目录中的GESP.txt文件
C."./data/GESP.txt"：指定与当前工作目录中的程序文件同级目录下的data 目录中的GESP txt文件
D."GESP.txt"是绝对路径
【答案】：D
【解析】
当“GESP.txt”文件前面没有其他前置路径的时候，其表示的意思就是与当前工作目录中的程序文件相同目录中的GESP.txt文件
第7题
关于直接插入排序，下列说法错误的是（ ）
A.插入排序的最好情况是数组已经有序，此时只需要进行n-1次比较，时间复杂度为O(n)
B.最坏情况是数组逆序排序，此时需要进行n(n-1)/2次比较以及n-1次赋值操作（插入）
C.平均来说插入排序算法的复杂度为\(O(n^2)\)
D.空间复杂度上，直接插入法是就地排序，空间复杂度为O(n)
【答案】：D
【解析】
就地排序只需要O(1)的额外空间。
第8题
下列程序横线处，应该输入的是（ ）。
#include <iostream>
using namespace std;
int n, a[10001];
void swap(int &a, int &b)
{int t = a;a = b;b = t;
}
int main()
{cin >> n;for (int i=1; i<=n; i++)cin >> a[i];for (int i=n; i>1; i--)for (int j=1; j<i; j++)if (a[j]>a[j+1])____;for (int i=1; i<=n; i++)cout << a[i] << " ";cout << endl;return 0;
}
A.swap(a[j], a[j+1])
B.swap(a[j-1], a[j])
C.swap(a[j-1], a[j+1])
D.swap(&a[j-1], &a[j+1]);
【答案】：A
【解析】
考察冒泡排序的过程，不断地把较大的值往后放，因此，如果a[j]>a[j+1]成立，说明a[j]是较大的值，应当通过交换操作来将a[j]换到后面去。
第9题
下面关于递推的说法不正确的是（ ）。
A.递推表现为自己调用自己
B.递推是从简单问题出发，一步步的向前发展最终求得问题，最终求得问题。是正向的
C.递推中，问题的n要求是在计算中确定，不要求计算前就知道n
D.斐波那契数列可以用递推实现求解
【答案】：A
【解析】
自己调用自己是递归的表现，而不是递推，注意区分。
第10题
关于几种排序算法的说法，下面说法错误的是（ ）。
A.选择排序不是一个稳定的排序算法
B.冒泡排序算法不是一种稳定的排序算法
C.插入排序是一种稳定的排序算法
D.如果排序前2个相等的数在序列中的前后位置顺序和排序后它们2个的前后位置顺序相同，则称为一种稳定的排序算法
【答案】：B
【解析】
在冒泡排序中，两个元素交换的条件是a[j]>a[j+1]，如果两个元素的值相等，他们并不会发生交换，因此是一种稳定的排序算法。
第11题
数组{45，66，23，1，10，97，52，88，5，33}进行从小到大冒泡排序过程中，第一遍冒泡过后的序列是（ ）。
A.{45，23，1，10，66，52，88，5，33，97}
B.{45，66，1，23，10，97，52，88，5，33}
C.{45，66，23，1，10，52，88，5，33，97}
D.{45，66，23，1，10，97，52，88，33，5}
【答案】：A
【解析】
按照冒泡排序的过程模拟一遍即可，66会被一直交换到97的前面的位置，97会被一直交换到数组末尾的位置。
第12题
下面的排序算法程序中，横线处应该填入的是（ ）。
int a[8] = {2, 3, 4, 5, 6, 2, 3, 1};
for (int i=1; i<8; i++)
{int key = a[i];int j = i - 1;while (a[j]>key && j>=0){____;j -= 1;}a[j+1] = key;
}
A.a[j] = a[j-1];
B.a[j] = a[j+1];
C.a[j+1] = a[j-1];
D.a[j+1] = a[j];
【答案】：D
【解析】
考察插入排序的过程，不断地将a[i]与前面的数字比较，以便找到合适的位置插入进去；因此，在已排好序的部分中，所有比a[i]大的数字都要整体往右移动一个单位；若a[j]比a[i]大，那么它往右移动一个单位之后的位置是j+1，所以应该将a[j]赋值给a[j+1]。
第13题
下面的程序中，如果输入10 0会输出（ ）。
#include <iostream>
using namespace std;
double Division(int a, int b)
{if (b==0)throw "Division by zero condition!";elsereturn ((double)a / (double)b);
}void func()
{int len, time;cin >> len >> time;cout << Division(len, time) << endl;
}int main()
{try {func();}catch (const char* errmsg){cout << errmsg << endl;}catch (const int errmsg){cout << errmsg << endl;}return 0;
}
A.Division by zero condition!
B.0
C.10
D.100
【答案】：A
【解析】
输入len=10与time=0， 分别传入Division() 函数中的a、b， 于是有a=10、b=0， 条件b==0成立。
第14题
10条直线，最多可以把平面分为多少个区域（ ）。
A.55
B.56
C.54
D.58
【答案】：B
【解析】
当第x条直线加入进来的时候，我们总有一种贪心的方法，让这条直线与前面的所有x-1条直线相交，每发生一次相交都会额外产生一个区域，因此会产生x-1个区域，再加上整个平面本身会被分割一次，所以会产生×个区域，于是10条直线能够分割出来的区域数量就是1+2+3+4+5+6+7+8+9+10=55，最后不要忘记整个平面本身最初也有一个区域，所以还要加1，答案是55+1=56。
第15题
下面程序中，如果语句cout<<p<<endl; 输出的是0x6ffe000，则cout<<++p<<endl; 输出的是（ ）
int x[10][10][10] = {{0}};
int *p;
p = &x[0][0][0];
cout << p << endl;
cout << ++p << endl;
A.0x6ffe0c
B.0x6ffe09
C.0x6ffe06
D.0x6ffe04
【答案】：D
【解析】
一个int变量占4字节， p指针指向了x数组的首地址， 因此， 在++p之后， p指针移动到了下一个元素的地址， 需要加上对应的int变量的字节数。
判断题
第16题
int& a 和&a 是一样的，都是取a的地址。
A.正确
B.错误
【答案】：B
【解析】
&a是取a的地址， 而int& a是引用变量， 作用是获取某个变量的“引用”，即给某一个变量起一个别名。
第17题
以下代码不能够正确执行。
#include <iostream>
using namespace std;
int main()
{int a = 20;int& ra;ra = &a;cout << ra << endl;
}
A.正确
B.错误
【答案】：B
【解析】
同上一题， int& ra是引用变量， 需要在定义时设置一个初始值。
第18题
引用是一个指针常量。
A.正确
B.错误
【答案】：A
【解析】
指针常量指向的内存地址无法修改，而指向的内存地址对应的值可以修改。
第19题
下面程序两个输出结果是一样的
#include <iostream>
using namespace std;
int main()
{int a[2][3] = {0};cout << a << endl;cout << &a[0][0] << endl;
}
A.正确
B.错误
【答案】：A
【解析】
输出a即直接输出数组a的首地址，而a[0][0]是数组a的第0个元素，因此&a[0][0]相当于就是去了第0个元素的地址，即首地址。
第20题
函数不可以调用自己。
A.正确
B.错误
【答案】：B
【解析】
递归算法的实现就是“函数调用自己”。
第21题
函数参数传递过程中，如果传常量值、常量引用和常量指针都是不能被修改的，它们可以防止函数对实参的值或地址进行修改。
A.正确
B.错误
【答案】：A
【解析】
常量无法被修改，因此若想要实参的值不被修改，传入常量即可。
第22题
下面代码输出的值等于0。
#include <iostream>
using namespace std;
int main()
{int *p = NULL;cout << p << endl;
}
A.正确
B.错误
【答案】：A
【解析】
空指针指向0地址。
第23题
在下面这个程序里，a[i][j]和一个普通的整型变量一样使用。
#include <iostream>
using namespace std;
int main()
{int a[10][10] = {0};for (int i=0; i<10; i++){for (int j=0; j<10; j++){if (i==j){a[i][j] = 1;}}}
A.正确
B.错误
【答案】：A
【解析】
整型二维数组中的每一个元素都是一个整型变量
第24题
一个一维数组，至少含有一个自然数N，是一个合法的数列。可以在一维数组末尾加入一个自然数M，M不能超过一维数组末尾元素的一半，形成一个新的合法的一维数组，如果N=6，那么可以有6个不同的合法数组。
A.正确
B.错误
【答案】：A
【解析】
合法的6个数组分别是{6}、{6，1}、{6，2}、{6，3}、{6，3，1}、{6，2，1}
第25题
插入排序算法中，平均时间复杂度是\(O(n^2)\)，最坏的情况逆序情况下，达到最大时间复杂度。
A.正确
B.错误
【答案】：A
【解析】
在最坏的逆序情况下，每一个元素都会被插入到已排好序部分的最前面。
编程题
B4005 黑白方块
【题目来源】
洛谷：[B4005 GESP202406 四级] 黑白方块 - 洛谷
【题目描述】
小杨有一个n行m列的网格图，其中每个格子要么是白色，要么是黑色。
对于网格图中的一个子矩形，小杨认为它是平衡的当且仅当其中黑色格子与白色格子数量相同。
小杨想知道最大的平衡子矩形包含了多少个格子。
【输入】
第一行包含两个正整数n，m，含义如题面所示。
之后n行，每行一个长度为m 的01串，代表网格图第i行格子的颜色，如果为0，则对应格子为白色，否则为黑色。
【输出】
输出一个整数，代表最大的平衡子矩形包含格子的数量，如果不存在则输出出0。
【输入样例】
4 5
00000
01111
00011
00011
【输出样例】
16
【算法标签】
《洛谷 B4005 黑白方块》 #枚举# #前缀和# #GESP# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 55; // 定义矩阵的最大尺寸
int w[N][N]; // 存储01矩阵
int n, m; // 矩阵的行数和列数// 检查子矩阵中0和1的数量是否相等
bool check(int xa, int ya, int xb, int yb)
{int a[2] = {0, 0}; // a[0]统计0的数量，a[1]统计1的数量// 遍历子矩阵中的所有元素for (int i = xa; i <= xb; i++) {for (int j = ya; j <= yb; j++) {a[w[i][j]]++; // 根据当前元素的值增加对应计数}}return a[0] == a[1]; // 返回0和1的数量是否相等
}int main()
{// 输入矩阵的行数和列数cin >> n >> m;// 读取矩阵数据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';}}int ans = 0; // 存储最大满足条件的子矩阵面积// 枚举所有可能的子矩阵for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {// 枚举以(i,j)为左上角的所有子矩阵for (int ii = i; ii <= n; ii++) {for (int jj = j; jj <= m; jj++) {// 检查当前子矩阵是否满足条件if (check(i, j, ii, jj)) {// 计算当前子矩阵的面积并更新最大值ans = max(ans, ((ii - i + 1) * (jj - j + 1)));}}}}}// 输出最大面积cout << ans << endl;return 0;
}
【运行结果】
4 5
00000
01111
00011
00011
16
B4006 宝箱
【题目来源】
洛谷：[B4006 GESP202406 四级] 宝箱 - 洛谷
【题目描述】
小杨发现了n个宝箱，其中第i个宝箱的价值是\(a_i\)。
小杨可以选择一些宝箱放入背包并带走，但是小杨的背包比较特殊，假设小杨选择的宝箱中最大价值为x，最小价值为y，小杨需要保证x-y≤k，否则小杨的背包会损坏。
小杨想知道背包不损坏的情况下，自己能够带走宝箱的总价值最大是多少。
【输入】
第一行包含两个正整数n，k，含义如题面所示。
第二行包含n个正整数\(a_1, a_2, \dots, a_n\)，代表宝箱的价值。
【输出】
输出一个整数，代表带走宝箱的最大总价值。
【输入样例】
5 1
1 2 3 1 2
【输出样例】
7
【算法标签】
《洛谷 B4006 宝箱》 #排序# #双指针,two-pointer# #GESP# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int n, k;int main()
{// 输入n和kcin >> n >> k;// 输入数组for (int i = 1; i <= n; i++) {cin >> a[i];}// 对数组进行升序排序sort(a + 1, a + n + 1);int ans = 0; // 存储最大和// 遍历每个元素作为子数组的右端点for (int i = 1; i <= n; i++) {int sum = 0; // 以a[i]为右端点的满足条件的子数组的和// 向左扩展，找到所有满足a[i]-a[j]<=k的元素for (int j = i; j >= 1; j--) {if (a[i] - a[j] <= k) {sum += a[j];} else {break; // 如果不满足条件，后面的元素更小，更不满足}}// 更新最大和ans = max(ans, sum);}cout << ans << endl;return 0;
}
【运行结果】
5 1
1 2 3 1 2
7