C++练手题系列一

第 1 题 【 问答题 】
• 有多少种二叉树
输入n(1<n<13)，求n个结点的二叉树有多少种形态
时间限制：1000
内存限制：65536
输入
整数n
输出答案
样例输入
3
样例输出
5
第 2 题 【 问答题 】
• 城堡问题
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####—#####—#—#####—#
2 # # | # # # # #
#—#####—#####—#####—#
3 # | | # # # # #
#—#########—#####—#—#
4 # # | | | | # #
#############################
(图 1)

= Wall

| = No wall

• = No wall
  图1是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成m×n(m≤50，n≤50)个方块，每个方块可以有0~4面墙。
  时间限制：1000
  内存限制：65536
  输入
  程序从标准输入设备读入数据。第1、2行每行1个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。
  输出
  输出2行，每行一个数，表示城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。
  样例输入
  4
  7
  11 6 11 6 3 10 6
  7 9 6 13 5 15 5
  1 10 12 7 13 7 5
  13 11 10 8 10 12 13
  样例输出
  5
  9
  第 3 题 【 问答题 】
  • 快速堆猪
  小明有很多猪，他喜欢玩叠猪游戏，就是将猪一头头叠起来。猪叠上去后，还可以把顶上的猪拿下来。小明知道每头猪的重量，而且他还随时想知道叠在那里的猪最轻的是多少斤。
  时间限制：1000
  内存限制：65536
  输入
  有三种输入 1)push n n是整数(0<=0 <=20000)，表示叠上一头重量是n斤的新猪 2)pop 表示将猪堆顶的猪赶走。如果猪堆没猪，就啥也不干 3)min 表示问现在猪堆里最轻的猪多重。如果猪堆没猪，就啥也不干 输入总数不超过100000条
  输出
  对每个min输入，输出答案。如果猪堆没猪，就啥也不干

样例输入
pop
min
push 5
push 2
push 3
min
push 4
min
样例输出
2
2
第 4 题 【 问答题 】
• 重建二叉树
给定一棵二叉树的前序遍历和中序遍历的结果，求其后序遍历。
时间限制：1000
内存限制：65536
输入
输入可能有多组，以EOF结束。 每组输入包含两个字符串，分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。
输出
对于每组输入，用一行来输出它后序遍历结果。

样例输入
DBACEGF ABCDEFG
BCAD CBAD
样例输出
ACBFGED
CDAB