当前位置：首页 > article >正文

2024年9月青少年软件编程（C语言/C++）等级考试试卷（七级）

article 2024/11/13 17:38:17

青少年软件编程（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 为出栈。则这套操作对应了一棵唯一的二叉树，如下图所示。
你的任务是输出这棵树的后序遍历序列。
时间限制： 1 000
内存限制： 2621 44
输入
输入第一行给出一个正整数 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
2、寻宝图
给定一幅地图，其中有水域，有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏
有宝藏，这些有宝藏的点也被标记出来了。本题就请你统计一下，给定的地图上一共有
多少岛屿，其中有多少是有宝藏的岛屿。
时间限制： 1 000
内存限制： 2621 44
输入
输入第一行给出 2 个正整数 N 和 M（1 < N × M ≤ 1 0 5 ），是地图的尺寸，表示地图
由 N 行 M 列格子构成。随后 N 行，每行给出 M 位个位数，其中 `0` 表示水域，`1 `
表示陆地，`2`-`9` 表示宝藏。注意：两个格子共享一条边时，才是“相邻”的。默认地
图外围全是水域。
输出
在一行中输出 2 个整数，分别是岛屿的总数量和有宝藏的岛屿的数量。
样例输入
10 11
01000000151
11000000111
00110000811
00110100010
00000000000
00000111000
00114111000
00110010000
00019000010
00120000001