欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
单选题
第1题
下列代码中，输出结果是（ ）
#include<iostream>usingnamespacestd;intfunc(intx,inty){inta=x,b=y;intt;t=a;a=b;b=t;cout<<a<<" "<<b<<" ";}intmain(){intc,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>usingnamespacestd;intfunc(){//...}intmain(){//...}B.
#include<iostream>usingnamespacestd;intmain(){func();}intfunc(){//...}C.
#include<iostream>usingnamespacestd;intfunc(){//...}intmain(){func();}D.
#include<iostream>usingnamespacestd;intfunc();intmain(){func();}intfunc(){//...}【答案】：B
【解析】
在调用函数之前，应该先定义函数。
第3题
下面程序输出的是（ ）
#include<iostream>usingnamespacestd;intfunc();intmain(){inti=2;cout<<i<<endl;for(intx=0;x<1;x++){inti=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>usingnamespacestd;intmain(){int*p;inta=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>usingnamespacestd;intmain(){inta[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 ) O(n^2)O(n2)
D.空间复杂度上，直接插入法是就地排序，空间复杂度为O(n)
【答案】：D
【解析】
就地排序只需要O(1)的额外空间。
第8题
下列程序横线处，应该输入的是（ ）。
#include<iostream>usingnamespacestd;intn,a[10001];voidswap(int&a,int&b){intt=a;a=b;b=t;}intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];for(inti=n;i>1;i--)for(intj=1;j<i;j++)if(a[j]>a[j+1])____;for(inti=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;return0;}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题
下面的排序算法程序中，横线处应该填入的是（ ）。
inta[8]={2,3,4,5,6,2,3,1};for(inti=1;i<8;i++){intkey=a[i];intj=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>usingnamespacestd;doubleDivision(inta,intb){if(b==0)throw"Division by zero condition!";elsereturn((double)a/(double)b);}voidfunc(){intlen,time;cin>>len>>time;cout<<Division(len,time)<<endl;}intmain(){try{func();}catch(constchar*errmsg){cout<<errmsg<<endl;}catch(constinterrmsg){cout<<errmsg<<endl;}return0;}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; 输出的是（ ）
intx[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>usingnamespacestd;intmain(){inta=20;int&ra;ra=&a;cout<<ra<<endl;}A.正确
B.错误
【答案】：B
【解析】
同上一题， int& ra是引用变量， 需要在定义时设置一个初始值。
第18题
引用是一个指针常量。
A.正确
B.错误
【答案】：A
【解析】
指针常量指向的内存地址无法修改，而指向的内存地址对应的值可以修改。
第19题
下面程序两个输出结果是一样的
#include<iostream>usingnamespacestd;intmain(){inta[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>usingnamespacestd;intmain(){int*p=NULL;cout<<p<<endl;}A.正确
B.错误
【答案】：A
【解析】
空指针指向0地址。
第23题
在下面这个程序里，a[i][j]和一个普通的整型变量一样使用。
#include<iostream>usingnamespacestd;intmain(){inta[10][10]={0};for(inti=0;i<10;i++){for(intj=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 ) O(n^2)O(n2)，最坏的情况逆序情况下，达到最大时间复杂度。
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>usingnamespacestd;constintN=55;// 定义矩阵的最大尺寸intw[N][N];// 存储01矩阵intn,m;// 矩阵的行数和列数// 检查子矩阵中0和1的数量是否相等boolcheck(intxa,intya,intxb,intyb){inta[2]={0,0};// a[0]统计0的数量，a[1]统计1的数量// 遍历子矩阵中的所有元素for(inti=xa;i<=xb;i++){for(intj=ya;j<=yb;j++){a[w[i][j]]++;// 根据当前元素的值增加对应计数}}returna[0]==a[1];// 返回0和1的数量是否相等}intmain(){// 输入矩阵的行数和列数cin>>n>>m;// 读取矩阵数据for(inti=1;i<=n;i++){string s;cin>>s;for(intj=1;j<=m;j++){// 将字符转换为数字存入矩阵w[i][j]=s[j-1]-'0';}}intans=0;// 存储最大满足条件的子矩阵面积// 枚举所有可能的子矩阵for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){// 枚举以(i,j)为左上角的所有子矩阵for(intii=i;ii<=n;ii++){for(intjj=j;jj<=m;jj++){// 检查当前子矩阵是否满足条件if(check(i,j,ii,jj)){// 计算当前子矩阵的面积并更新最大值ans=max(ans,((ii-i+1)*(jj-j+1)));}}}}}// 输出最大面积cout<<ans<<endl;return0;}【运行结果】
4 5 00000 01111 00011 00011 16B4006 宝箱
【题目来源】
洛谷：[B4006 GESP202406 四级] 宝箱 - 洛谷
【题目描述】
小杨发现了n个宝箱，其中第i个宝箱的价值是a i a_iai。
小杨可以选择一些宝箱放入背包并带走，但是小杨的背包比较特殊，假设小杨选择的宝箱中最大价值为x，最小价值为y，小杨需要保证x-y≤k，否则小杨的背包会损坏。
小杨想知道背包不损坏的情况下，自己能够带走宝箱的总价值最大是多少。
【输入】
第一行包含两个正整数n，k，含义如题面所示。
第二行包含n个正整数a 1 , a 2 , … , a n a_1, a_2, \dots, a_na1,a2,…,an，代表宝箱的价值。
【输出】
输出一个整数，代表带走宝箱的最大总价值。
【输入样例】
5 1 1 2 3 1 2【输出样例】
7【算法标签】
《洛谷 B4006 宝箱》 #排序# #双指针,two-pointer# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=1010;inta[N];intn,k;intmain(){// 输入n和kcin>>n>>k;// 输入数组for(inti=1;i<=n;i++){cin>>a[i];}// 对数组进行升序排序sort(a+1,a+n+1);intans=0;// 存储最大和// 遍历每个元素作为子数组的右端点for(inti=1;i<=n;i++){intsum=0;// 以a[i]为右端点的满足条件的子数组的和// 向左扩展，找到所有满足a[i]-a[j]<=k的元素for(intj=i;j>=1;j--){if(a[i]-a[j]<=k){sum+=a[j];}else{break;// 如果不满足条件，后面的元素更小，更不满足}}// 更新最大和ans=max(ans,sum);}cout<<ans<<endl;return0;}【运行结果】
5 1 1 2 3 1 2 7
