欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
单选题
第1题
以下（ ）没有涉及 C++ 语言的面向对象特性支持。
A.C++中构造一个 class 或 struct
B.C++中调用printf 函数
C.C++中调用用户定义的类成员函数
D.C++ 中构造来源于同一基类的多个派生类
【答案】：B
【解析】
选项B 调用的是C语言中的函数printf，这与面向对象特性无关。
第2题
关于以下C++代码，（ ）行代码会引起编译错误。
#include <iostream>
using namespace std;class Base {
private:int a;
protected:int b;
public:int c;Base() : a(1), b(2), c(3) {}
};class Derived : public Base {
public:void show() {cout << a << endl; // Line 1cout << b << endl; // Line 2cout << c << endl; // Line 3}
};
A.Line1
B.Line2
C.Line3
D.没有编译错误
【答案】：A
【解析】
a是 Base 类中的私有成员变量。在派生类 Derived 中无法直接访问基类的私有成员，因此这一行会引发编译错误。
第3题
有6个元素，按照6，5，4，3，2，1的顺序进入栈S，下列（ ）的出栈序列是不能出现的（ ）。
A.5，4，3，6，1，2
B.4，5，3，1，2，6
C.3，4，6，5，2，1
D.2，3，4，1，5，6
【答案】：C
【解析】
C选项，3，4，6，5，2，1
入栈：6
入栈：5
入栈：4
入栈：3
出栈：3
出栈：4
出栈：6（不可能，因为6后面还有5在栈中）
这个序列是不可能的。
第4题
采用如下代码实现检查输入的字符串括号是否匹配。横线处应填入的代码为（ ）。
#include <iostream>
#include <stack>
#include <string>using namespace std;bool is_valid(string s) {stack<char> st;char top;for (char& ch : s) {if (ch == '(' || ch == '{' || ch == '[') {st.push(ch); // 左括号入栈}else{if (st.empty())return false;___________________________ // 在此处填入代码if ((ch==')' && top!='(') ||(ch=='}' && top!='{') ||(ch==']' && top!='[')) {return false;}}}return st.empty(); // 栈为空则说明所有括号匹配成功
}
A.top=st.top(); st.pop();
B.st.pop(); top=st.top();
C.st.pop(); top=st.front();
D.top=st.front(); st.pop();
【答案】：A
【解析】
在处理右括号时，需要从栈中弹出一个元素进行匹配，我们需要先获取栈顶元素，再将其从栈中移除。
第5题
下面代码判断队列的第一个元素是否等于a，并删除该元素，横向上应填写（ ）。
#include <iostream>
#include <queue>
using namespace std;bool is_front_equal(std::queue<int>& q, int a) {bool is_equal = false;if (!q.empty()) {_________________________ // 在此处填入代码}return is_equal;
}
A.is_equal = (q.front() == a);
B.is_equal = (q.front() == a); q.pop();
C.q.pop(); is_equal = (q.front()==a);
D.q.pop(); is_equal = (q.pop()==a);
【答案】：B
【解析】
首先检查队列首元素是否等于a，然后弹出该元素。选项Ｂ正确地执行了这两步操作，保证逻辑完整性和顺序正确性。
第6题
假设字母表 {a，b，c，d，e} 在字符串出现的频率分别为10%，15%，30%，16%，29%。若使用哈夫曼编码方式对字母进行二进制编码，则字符 abcdef 分别对应的一组哈夫曼编码的长度分别为（ ）。
A. 4， 4， 1， 3，2
B. 3， 3， 2， 2，2
C. 3， 3，1，2，1
D. 4， 4， 1， 2，2
【答案】：B
【解析】
画出哈夫曼树：
选项B正确。
第7题
以下C++代码实现n位的格雷码，则横线上应填写（ ）。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 生成 n 位的格雷码
vector<string> generate_graycode(int n) {vector<string> graycode_list;if (n<=0) {return graycode_list;}// 初始1位格雷码graycode_list.push_back("0");graycode_list.push_back("1");// 迭代生成 n 位的格雷码for (int i=2; i<=n; i++) {int current_size = graycode_list.size();for (int j=current_size-1; i>=0; j--) {graycode_list.push_back("1" + graycode_list[j]);}for (int j=0; j<current_size; j++) {__________________ // 在此处填入代码}}return graycode_list;
}
A.graycode_list.push_back("0"+graycode_list[j]);
B.graycode_list[j]="0"+graycode_list[j];
C.graycode_list.push_back("1"+graycode_list[j]);
D.graycode_list[j]="1"+graycode_list[j];
【答案】：B
【解析】
A错误。这个操作会在列表末尾添加带有前缀'0'的新格雷码，但应当是在已有格雷码前面加'0'。
B正确。在已存在的格雷码前面加'0'，这是对称性要求的一部分。
C错误。这段代码重复了之前的操作，应避免。
D错误。这将破坏原有顺序，使得两部分不再对称。
因此，正确答案是B。
第8题
给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG，则这棵树的正确后序遍历结果是（ ）。
A.EDBGFCA
B.EDGBFCA
C.DEBGFCA
D.DBEGFCA
【答案】：A
【解析】
根据先序遍历与中序遍历的结果，可以得到树的结构：
由此得出后序遍历为EDBGFCA，选A。
第9题
一棵有n个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第1个位置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。
A. 8， 18
B. 10，18
C. 8， 19
D. 10， 19
【答案】：C
【解析】
假设根节点存在数组的第1个位置，那么根据完全二叉树的性质：
父节点：
第9个位置的节点的父节点位置为 floor(9 / 2) = 4.
兄弟节点：
若第9个位置的节点有兄弟节点，则其兄弟节点应该在位置8（即9的前一个位置）。
左孩子节点：
第9个位置的节点的左孩子节点位置为2 * 9 = 18。
右孩子节点：
第9个位置的节点的右孩子节点位置为2 * 9 + 1 = 19。
综上所述，第9个位置的节点的兄弟节点位置为8，左孩子节点位置为18，右孩子节点位置为19。
第10题
二叉树的深度定义为从根结点到叶结点的最长路径上的结点数，则以下基于二叉树的深度优先搜索实现的深度计算函数中横线上应填写（ ）。
// 定义二叉树的结点结构
struct tree_node {int val;tree_node* left;tree_node* right;tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
};// 计算二叉树的深度
int max_depth(tree_node* root) {if (root == nullptr) {return 0; // 如果根节点为空，则深度为0}int left_depth = max_depth(root->left);int right_depth = max_depth(root->right);_______________________ // 在此处填入代码
}
A.return left_depth + right_depth;
B.return max(left_depth, right_depth);
C.return max(left_depth, right_depth) + 1;
D.return left_depth + right_depth + 1;
【答案】：C
【解析】
函数 max_depth 递归地计算左右子树的深度，最后返回两者中的较大值加1，选项C正确。
第11题
上一题的二叉树深度计算还可以采用二叉树的广度优先搜索来实现。以下基于二叉树的广度优先搜索实现的深度计算函数中横线上应填写（ ）。
#include <queue>int max_depth_bfs(tree_node* root) {if (root==nullptr) {return 0; // 如果树为空，深度为0}queue <tree_node*> q;q.push(root);int depth = 0;// 使用队列进行层序遍历while (!q.empty()) {_____________________ // 在此处填入代码for (int i=0; i<level_size; ++i) {tree_node* node = q.front();q.pop();if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}}return depth;
}
A.int level_size = q.size(); depth++;
B.int level_size = 2; depth++;
C.int level_size = q.size(); depth += level_size;
D.int level_size = 2; depth += level_size;
【答案】：A
【解析】
题目要求使用广度优先搜索计算二叉树的深度。每遍历一层，深度增加1。level_size 记录当前层节点数，每次循环后深度加1，以反映已完成的一层遍历。选项A正确。
第12题
二叉搜索树中的每个结点，其左子树的所有结点值都小于该结点值，右子树的所有结点值都大于该结点值。以下代码对给定的整数数组（假设数组中没有数值相等的元素），构造一个对应的二叉搜索树，横线上应填写（ ）：
// 定义二叉树的结点结构
struct tree_node {int val;tree_node* left;tree_node* right;tree_node(int x) : val(x), left(nullptr), right(nullptr) {}
};// 插入结点到二叉搜索树中
tree_node* insert(tree_node* root, int val) {if (root == nullptr) {return new tree_node(val);}___________________________ // 在此处填入代码return root;
}// 根据给定数组构造二叉搜索树
tree_node* constructBST(const int arr[], int size) {tree_node* root = nullptr;for (int i=0; i<size; ++i) {root = insert(root, arr[i]);}return root;
}
A.
if (val < root->val)root->left = insert(root->left, val);
else root->right = insert(root->right, val);
B.
if (val > root->val)root->left = insert(root->left, val);
elseroot->right = insert(root->right, val);
C.
if (val < root->val)root->left = insert(root, val);
elseroot->right = insert(root, val);
D.
if (val > root->val)root->left = insert(root, val);
elseroot->right = insert(root, val);
【答案】：A
【解析】
题目要求在 insert 函数中插入代码，以构建二叉搜索树。二叉搜索树的性质决定了，若插入值小于当前节点值，则递归插入左子树，否则递归插入右子树。选项A正确。
第13题
对上题中的二叉搜素树，当输入数组为[5,3,7,2,4,6,8]时，构建二叉搜索树，并采用如下代码实现的遍历方式，得到的输出是（ ）。
#include <iostream>
using namespace std;// 遍历二叉搜索树，输出结点值
void traversal(tree_node* root) {if (root == nullptr) {return ;}traversal(root->left);cout << root->val << " ";traversal(root->right);
}
A.5 3 7 2 4 6 8
B.2 3 4 5 6 7 8
C.2 4 3 6 8 7 5
D.2 4 3 5 6 7 8
【答案】：B
【解析】
题目要求对构建的二叉搜索树进行中序遍历。
插入顺序：[5,3,7,2,4,6,8]
构建的二叉搜索树后进行中序遍历，结果为2 3 4 5 6 7 8
5/ \3 7/ \ / \
2 4 6 8
第14题
动态规划通常用于解决（ ）。
A.无法分解的问题
B.可以分解成相互依赖的子问题的问题
C.可以通过贪心算法解决的问题
D.只能通过递归解决的问题
【答案】：B
【解析】
动态规划用于解决可分解成重叠子问题，并通过保存子问题结果避免重复计算的问题。选项Ｂ正确。
第15题
阅读以下用动态规划解决的0-1背包问题的函数，假设背包的容量W是10kg，假设输入4个物的重量weight 分别为1，3，4，6（单位为kg），每个物品对应的价值values 分别为20，30，50，60，则函数的输出为（ ）。
#include <iostream>
#include <vector>
using namespace std;// 0/1背包问题
int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {vector<vector<int>> dp(n+1, vector<int>(W+1, 0));for (int i=1; i<=n; ++i) {for (int w=0; w<=W; ++w) {if (weight[i-1] <= w) {dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + values[i-1]);}else {dp[i][w] = dp[i-1][w];}}}return dp[n][W];
}
A.90
B.100
C.110
D.140
【答案】：C
【解析】
通过填充dp表，可以得出当背包容量为10时，能够获得的最大价值为110。选项C正确。
判断题
第16题
C++、Python 和JAVA等都是面向对象的编程语言。
A.正确
B.错误
【答案】：A
【解析】
C++、Python 和Java 都是面向对象的编程语言，它们都支持类和对象的概念，允许封装、继承和多态等特性。
第17题
在C++中，类的静态成员变量只能被该类对象的成员函数访问。
A.正确
B.错误
【答案】：B
【解析】
在C++中，类的静态成员变量可以通过类名直接访问，而不仅仅是通过该类对象的成员函数访问。
第18题
栈是一种线性结构，可通过数组或链表来实现。二者相比，数组实现占用的内存较少，链表实现的入队和出队操作的时间复杂度较低。
A.正确
B.错误
【答案】：B
【解析】
数组与链表实现的栈，其入队与出队操作的时间复杂度均为\(O(1)\)。
第19题
运行以下 C++代码，屏幕将输出“derived class”。
#include <iostream>
using namespace std;class base {
public:virtual void show() {cout << "base class" << endl;}
};class derived : public base {
public:void show() override {cout << "derived class" << endl;}
};int main() {base* b;derived d;b = &d;b->show();return 0;
}
A.正确
B.错误
【答案】：A
【解析】
代码中基类 base 的虚函数 show() 被派生类 derived重写。在main函数中，通过基类指针b调用show()，实际会调用派生类的 show() 方法，因此输出“derived class”。
第20题
如下列代码所示的基类（base）及其派生类（derived），则生成一个派生类的对象时，只调用派生类的构造函数。
#include <iostream>
using namespace std;class base {
public:base() {cout << "base constructor" << endl;}~base() {cout << "base destructor" << endl;}
};class derived : public base {
public:derived() {cout << "derived constructor" << endl;}~derived() {cout << "derived destructor" << endl;}
};
A.正确
B.错误
【答案】：B
【解析】
根据代码，当派生类 derived 的对象被创建时，会依次调用基类 base 和派生类derived的构造函数；当对象销毁时，会依次调用派生类和基类的析构函数。因此，输出顺序如下：
1、调用基类构造函数：输出"base constructor"
2、调用派生类构造函数：输出"derived constructor"
3、销毁对象时，先调用派生类析构函数：输出"derived destructor"
4、再调用基类析构函数：输出"base destructor"
第21题
哈夫曼编码本质上是一种贪心策略。
A.正确
B.错误
【答案】：A
【解析】
哈夫曼编码是一种贪心策略，用于构建最优前缀码，以实现数据压缩。通过频率最低的字符分配最长的编码，达到最小化平均编码长度的目的。
第22题
如果根结点的深度记为1，则一棵恰有2024 个叶结点的二叉树的深度最少是12。
A.正确
B.错误
【答案】：A
【解析】
对于一棵包含2024 个叶节点的二叉树，最小深度可以通过计算 log2(2024)得到，其结果约为11.98。因此，向下取整并加1后，最小深度为12。
第23题
在非递归实现的树的广度优先搜索中，通常使用栈来辅助实现。
A.正确
B.错误
【答案】：B
【解析】
在非递归实现的树的广度优先搜索（BFS）中，通常使用队列来辅助实现。
第24题
状态转移方程是动态规划的核心，可以通过递推方式表示问题状态的变化。
A.正确
B.错误
【答案】：A
【解析】
状态转移方程是动态规划的核心，通过递推方式表示问题状态的变化，逐步求解最优解。
第25题
应用动态规划算法时，识别并存储重叠子问题的解是必须的。
A.正确
B.错误
【答案】：A
【解析】
应用动态规划算法时，识别并存储重叠子问题的解是关键步骤。这通过记忆化或表格法来实现，以避免重复计算，提高效率。
编程题
P11246 小杨和整数拆分
【题目来源】
洛谷：[P11246 GESP202409 六级] 小杨和整数拆分 - 洛谷
【题目描述】
小杨有一个正整数\(n\)，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。
小杨请你编写程序计算出总和为\(n\) 的完全平方数的最少数量。
【输入】
第一行包含一个正整数\(n\)，含义如题面所示。
【输出】
输出一个整数，代表总和为\(n\) 的完全平方数的最少数量。
【输入样例】
18
【输出样例】
2
【算法标签】
《洛谷 P11246 小杨和整数拆分》 #动态规划,dp# #GESP# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5; // 定义最大范围
int n; // 输入的数字
int dp[N]; // dp数组int main()
{cin >> n; // 输入n// 动态规划计算for (int i = 1; i <= n; i++) {dp[i] = i; // 初始值：最坏情况，全部用1^2表示for (int j = 1; j <= sqrt(i); j++) { // j从1到√idp[i] = min(dp[i - j*j] + 1, dp[i]);}}cout << dp[n]; // 输出结果return 0;
}
【运行结果】
18
2
P11247 算法学习
【题目来源】
洛谷：[P11247 GESP202409 六级] 算法学习 - 洛谷
【题目描述】
小杨计划学习\(m\) 种算法，为此他找了\(n\) 道题目来帮助自己学习，每道题目至多学习一次。
小杨对于\(m\)种算法的初始掌握程度均为\(0\)。第\(i\) 道题目有对应的知识点\(a_i\) ，即学习第\(i\) 道题目可以令小杨对第\(a_i\) 种算法的掌握程度提高\(b_i\)。小杨的学习目标是对\(m\) 种算法的掌握程度均至少为 \(k\)。
小杨认为连续学习两道相同知识点的题目是不好的，小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。
【输入】
第一行三个正整数\(m\)，\(n\)，\(k\)，代表算法种类数，题目数和目标掌握程度。
第二行\(n\)个正整数\(a_1,a_2,\dots, a_n\)，代表每道题目的知识点。
第二行\(n\)个正整数\(b_1,b_2,\dots, b_n\)，代表每道题目提升的掌握程度。
【输出】
输出一个整数，代表小杨最少需要学习题目的数量，如果不存在满足条件的方案，输出\(-1\)。
【输入样例】
3 5 10
1 1 2 3 3
9 1 10 10 1
【输出样例】
4
【算法标签】
《洛谷 P11247 算法学习》 #贪心# #GESP# #2024#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 5; // 定义最大数量
const int inf = 0x3f3f3f3f; // 定义无穷大值int f[N]; // 辅助数组（未使用）
vector<int> score[N + 2]; // 存储每个类别的分数
vector<int> a, b; // 存储输入的类别和分数// 自定义排序函数：降序排列
bool cmp(int i, int j)
{return i > j;
}int main()
{int n, m, k;// 输入m个类别，n个数据，达标线kcin >> m >> n >> k;// 调整向量大小a.resize(n);b.resize(n);// 输入类别数据for (int i = 0; i < n; i++)cin >> a[i];// 输入分数数据并分类存储for (int i = 0; i < n; i++) {cin >> b[i];score[a[i]].emplace_back(b[i]); // 将分数存入对应类别}vector<int> need(m + 2); // 存储每个类别需要的最少数据量int ans = 0; // 总最少需要的数据量int mx_meed = 0; // 最大需要的数量int mx_need_i = -1; // 需要最多数据的类别索引// 计算每个类别需要的数据量for (int i = 1; i <= m; i++) {// 对该类别分数降序排序sort(score[i].begin(), score[i].end(), cmp);int sum = 0;// 计算达到k分需要的最少数据量for (int j = 0; j < (int)score[i].size(); j++) {sum += score[i][j];if (sum >= k) {need[i] = j + 1; // 记录需要的数据量break;}}// 如果无法达到k分if (sum < k) {puts("-1");return 0;}ans += need[i]; // 累加到总数// 记录需要最多数据的类别if (need[i] > mx_meed){mx_meed = need[i];mx_need_i = i;}}// 如果最大需求类别可以满足条件if (mx_meed - 1 <= ans - mx_meed) {cout << ans << endl;return 0;}// 计算其他类别可以提供的额外数据量int last = 0;for (int i = 1; i <= m; i++){if (i != mx_need_i){last += score[i].size() - need[i];}}// 判断是否可以满足最大需求类别的条件cout << (mx_meed - 1 <= ans - mx_meed + last ? 2 * mx_meed - 1 : -1);return 0;
}
【运行结果】
3 5 10
1 1 2 3 3
9 1 10 10 1
4