青少年软件编程（C语言）等级考试试卷（七级）
1、
模拟树遍历
二叉树的中序遍历可以借助一个堆栈来用非递归的方式实现。例如，对一棵有 6 个结点的二叉树（结点键值从 1 到 6）进行遍历，堆栈操作为：push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop() —— 其中 push 为入栈，pop 为出栈。则这套操作对应了一棵唯一的二叉树，如下图所示。
你的任务是输出这棵树的后序遍历序列。
时间限制：1000
内存限制：262144
输入
输入第一行给出一个正整数 N（≤ 30），是二叉树中结点的个数（结点键值从 1 到 N）。随后 2N 行，每行给出一个堆栈操作：`Push X` 表示将键值为 `X` 的结点入栈，`Pop` 表示将一个结点出栈。
输出
在一行中输出该树后序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。裁判保证输入数据一定对应了一棵树。
样例输入
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
样例输出
3 4 2 6 5 1
参考程序：
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
void postorderTraversal(vector<int>& inorder, int start, int end) {
if (start > end) return;
int root = inorder[end];
int index = end;
for (int i = end - 1; i >= start; i--) {
if (inorder[i] < root) {
index = i;
break;
}
}
postorderTraversal(inorder, start, index);
postorderTraversal(inorder, index + 1, end - 1);
cout << root << " ";
}
int main() {
int n;
cin >> n;
stack<int> s;
vector<int> inorder;
for (int i = 0; i < 2 * n; i++) {
string operation;
int value;
cin >> operation;
if (operation == "Push") {
cin >> value;
s.push(value);
} else {
value = s.top();
s.pop();
inorder.push_back(value);
}
}
postorderTraversal(inorder, 0, n - 1);
cout << endl;
return 0;
}
2、
寻宝图
给定一幅地图，其中有水域，有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏有宝藏，这些有宝藏的点也被标记出来了。本题就请你统计一下，给定的地图上一共有多少岛屿，其中有多少是有宝藏的岛屿。
202409 C语言七级