E1032 CCF-GESP编程能力等级认证-C++ -202603 CCF-GESP C++六级真题-考试

下列代码中， s1->draw(); 和 s2->draw(); 输出不同结果的主要原因是（ ）。

class Shape {
	public:
		virtual void draw() {
			cout << "绘制图形" << endl;
		}
		virtual ~Shape() {}
};
class Circle : public Shape {
	public:
		void draw() override {
			cout << "绘制圆形" << endl;
		}
};
class Rectangle : public Shape {
	public:
		void draw() override {
			cout << "绘制矩形" << endl;
		}
};
int main() {
	Shape* s1 = new Circle();
	Shape* s2 = new Rectangle();
	s1->draw();
	s2->draw();
	delete s1;
	delete s2;
	return 0;
}

下面的代码在 main() 中有一行会导致编译错误，请找出来。

Class Pet {
public:
	Pet(string n, int a) : name(n), age(a) {}
	string getName()  { return name; }
	void birthday() { age++; }       
private:
	string name;
	int age;
};
int main() {
	Pet cat("奶茶", 2);
	cout << cat.getName();  //第1行
	cat.birthday();         //第2行
	cat.name = "大橘";	    //第3行
	cout << cat.getName();  //第4行
}

游乐园的过山车每次限坐 4 人，用循环队列管理排队（容量 MAX=5 ，空一格判满）。下面代码执行后，循环队列是否已满？ rear 的值是多少？

const int MAX = 5;
int queue[MAX];
int front = 0, rear = 0;
// 入队
void enqueue(int x) {
	queue[rear] = x;
	rear = (rear + 1) % MAX;
}
// 出队
void dequeue() {
	front = (front + 1) % MAX;
}
int main() {
	enqueue(1);
	enqueue(2);
	enqueue(3);
	enqueue(4);
	dequeue();
	dequeue();
	enqueue(5);
	enqueue(6);
}

给定一棵二叉树，采用广度优先搜索 (BFS) 算法，返回右视图所有节点的值。其中右视图定义为：二叉树的右视图是从树的右侧看过去时可见的节点集合，即右视图中的每个节点都是某一层中最右侧的节点。

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
vector<int> rightSideView(TreeNode* root) {
	unordered_map<int, int> rightmostValueAtDepth;
	int max_depth = -1;
	queue<TreeNode*> nodeQueue;
	queue<int> depthQueue;
	nodeQueue.push(root);
	depthQueue.push(0);
	while (!nodeQueue.empty()) {
		TreeNode* node = nodeQueue.front();
		nodeQueue.pop();
		int depth = depthQueue.front();
		depthQueue.pop();
		if (node != NULL) {
			max_depth = max(max_depth, depth);
			rightmostValueAtDepth[depth] = node->val;
			nodeQueue.push(node->left);
			nodeQueue.push(node->right);
			depthQueue.push(________);
			depthQueue.push(________);
		}
	}
	vector<int> rightView;
	for (int depth = 0; ________; ++depth) {
		rightView.push_back(rightmostValueAtDepth[depth]);
	}
	return rightView;
};

小朋友们去邻里拜年，每个家里有不同数量的糖果。规则是：不能连续进入两个相邻的房子（即不能同时取相邻两家的糖果）。目标是拿到最多糖果。以下是代码实现，请补全横线。

int visit(vector<int>& nums) {
	if (nums.empty()) {
		return 0;
	}
	int size = nums.size();
	if (size == 1) {
		return nums[0];
	}
	vector<int> dp = vector<int>(size, 0);
	dp[0] = nums[0];
	dp[1] = max(nums[0], nums[1]);
	for (int i = 2; i < size; i++) {
		dp[i] = ______; // 在此处填写代码
	}
	return dp[size - 1];
}

下面定义了一个表示二维坐标点的类 Point ， 并提供了一个带参数的构造函数，但第 ② 行 Point b; 会调用编译器自动生成的默认构造函数，将 b.x 和 b.y 初始化为 0.0，程序可以正常编译运⾏。

class Point {
	public:
		double x, y;
		Point(double px, double py) : x(px), y(py) {}
		void print() {
			cout << "(" << x << ", " << y << ")";
		}
};
int main() {
	Point a(3.0, 4.0); // ①
	Point b; // ②
	a.print();
}

对如下结构的树，执行 travel 函数，输出结果是 1 2 3 4 5 。

    1
   / \
  2   3
 / \
4   5

struct Node {
	int val;
	Node *left, *right;
	Node(int v) : val(v), left(nullptr), right(nullptr) {}
};
void travel(Node* root) {
	if (!root) return;
	stack<Node*> s;
	s.push(root);
	while (!s.empty()) {
		Node* cur = s.top();
		s.pop();
		cout << cur->val << " ";
		if (cur->right) s.push(cur->right);
		if (cur->left) s.push(cur->left);
	}
}

设二叉树共有n个结点，函数 preorderTraversal 以下代码的时间复杂度为O(n)，空间复杂度为O(n)。

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};
void preorder(TreeNode *root, vector<int> &res) {
	if (root == nullptr) {
		return;
	}
	res.push_back(root->val);
	preorder(root->left, res);
	preorder(root->right, res);
}
vector<int> preorderTraversal(TreeNode *root) {
	vector<int> res;
	preorder(root, res);
	return res;
};

下列代码实现了一个0-1背包的一维动态规划代码，内层循环是经典的逆序写法。若将内层循环改成正序遍历（即 for (int j = w[i]; j <= W; j++) ），仍能得到正确答案。

int main() {
	int W = 5;
	int w[] = {2, 3, 4};
	int v[] = {10, 1, 1};
	int n = 3;
	int dp[6] = {0};
	for (int i = 0; i < n; i++) {
		for (int j = W; j >= w[i]; j--) { // ← 逆序！
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		}
	}
	cout << dp[W];
}