二叉树的深度定义为从根结点到叶结点的最长路径上的结点数，则以下基于二叉树的深度优先搜索实现的深度计算函数中横线上应填写（ ）。

// 定义二叉树的结点结构
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,b,c,d,e} 在字符串出现的频率分别为 10%，15%，30%，16%，29%。若使用哈夫曼编码方式对字母进行二进制编码，则字符 abcdef 分别对应的一组哈夫曼编码的长度分别为（ ）。（2024.9-6）

上一题的二叉树深度计算还可以采用二叉树的广度优先搜索来实现。以下基于二叉树的广度优先搜索实现的深度计算函数中横线上应填写（ ）。

#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;
}

阅读以下用动态规划解决的0-1背包问题的函数，假设背包的容量 W 是10kg，假设输入4个物品的重量weights 分别为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 (weights[i - 1] <= w) {
				dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
			}
			else
			{
				dp[i][w] = dp[i - 1][w];
			}
		}
	}
	
	return dp[n][W];
}

动态规划通常用于解决（ ）。（2024.9-6）

关于以下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 1
		cout << b << endl; // Line 2
		cout << c << endl; // Line 3
	}
};

给定一棵二叉树，其前序遍历结果为：ABDECFG,中序遍历结果为：DEBACFG，则这棵树的正确后序遍历结果是（ ）。（2024.9-6）

二叉搜索树中的每个结点，其左子树的所有结点值都小于该结点值，右子树的所有结点值都大于该结点值。以下代码对给定的整数数组(假设数组中没有数值相等的元素)，构造一个对应的二叉搜索树，横线上应填写（）:

// 定义二叉树的结点结构
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;
}

if (val < root->val)
	root->left = insert(root->left, val);
else
	root->right = insert(root->right, val);

if (val > root->val)
	root->left = insert(root->left, val);
else
	root->right = insert(root->right, val);

if (val < root->val)
	root->left = insert(root, val);
else
	root->right = insert(root, val);

if (val > root->val)
	root->left = insert(root, val);
else
	root->right = insert(root, val);

一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。（2024.9-6）

对上题中的二叉搜素树，当输入数组为[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);
}

以下（ ）没有涉及 C++ 语言的面向对象特性支持。

下面代码判断队列的第一个元素是否等于a，并删除该元素，横向上应填写（ ）。

采用如下代码实现检查输入的字符串括号是否匹配，横线上应填入的代码为（ ）。

#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(); // 栈为空则说明所有括号匹配成功
}

有6个元素，按照 6,5,4,3,2,1 的顺序进入栈S，下列（ ）的出栈序列是不能出现的（ ）。（2024.9-6）

以下C++代码实现 n nn 位的格雷码，则横线上应填写（ ）。

#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; j >= 0; j--) {
			graycode_list.push_back("1" + graycode_list[j]);
		}
		
		for (int j = 0; j < current_size; j++) {
			———————————————————————— // 在此处填入代码
		}
	}
	return graycode_list;
}

在C++中，类的静态成员变量只能被该类对象的成员函数访问。

哈夫曼编码本质上是一种贪心策略。（2024.9-6）

在非递归实现的树的广度优先搜索中，通常使用栈来辅助实现。（2024.9-6）

如下列代码所示的基类（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;
	}
};

应用动态规划算法时，识别并存储重叠子问题的解是必须的。（2024.9-6）

如果根结点的深度记为1，则一棵恰有2024 个叶结点的二叉树的深度最少是12。

状态转移方程是动态规划的核心，可以通过递推方式表示问题状态的变化。（2024.9-6）

栈是一种线性结构，可通过数组或链表来实现。二者相比，数组实现占用的内存较少，链表实现的入队和出队操作的时间复杂度较低。

C++、Python和JAVA等都是面向对象的编程语言。（2024.9-6）

运行以下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;
}

小杨和整数拆分

时间限制：1.0 s

内存限制：512.0 MB

题面描述

小杨有一个正整数n，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。

小杨请你编写程序计算出总和为n 的完全平方数的最少数量。

输入格式

第一行包含一个正整数n，含义如题面所示。

输出格式

输出一个整数，代表总和为n 的完全平方数的最少数量。

输入样例

18

输出样例

2

18=9+9=16+1+1，其中最少需要2 个完全平方数。

对于全部数据，保证有1≤n≤105。

算法学习

时间限制：1.0 s

内存限制：512.0 MB

题面描述

小杨计划学习 m 种算法，为此他找了 n 道题目来帮助自己学习，每道题目至多学习一次。

小杨对于 m 种算法的初始掌握程度均为 0 。第 i 道题目有对应的知识点ai，即学习第 i 道题目可以令小杨对第ai种算法的掌握程度提高bi。小杨的学习目标是对 m 种算法的掌握程度均至少为 k 。

小杨认为连续学习两道相同知识点的题目是不好的，小杨想请你编写程序帮他计算出他最少需要学习多少道题目才能使得他在完成学习目标的同时避免连续学习两道相同知识点的题目。

输入格式

第一行三个正整数m,n,k，代表算法种类数，题目数和目标掌握程度。

第二行n个正整数a1,a2,a3,...,an，代表每道题目的知识点。

第二行n个正整数b1,b2,b3,...,bn，代表每道题目提升的掌握程度。

输出格式

输出一个整数，代表小杨最少需要学习题目的数量，如果不存在满足条件的方案，输出 -1。

输入样例1

3 5 10
1 1 2 3 3
9 1 10 10 1

输出样例1

1

输入样例2

2 4 10
1 1 1 2
1 2 7 10

输出样例2

-1

对于样例1，一种最优学习顺序为第一道题，第三道题，第四道题，第二道题。

对于全部数据，保证有1≤m,n≤105,1≤bi,k≤105,1≤ai≤m。