2024年5月4日发(作者：)

青少年软件编程（C语言）等级考试试卷（七级）

分数：100 题数：4

一、编程题(共4题，共100分)

1. 重建二叉树

给定一棵二叉树的前序遍历和中序遍历的结果，求其后序遍历。

时间限制：1000

内存限制：65536

输入

输入可能有多组，以EOF结束。 每组输入包含两个字符串，分别为树的前序遍历和中

序遍历。每个字符串中只包含大写字母且互不重复。

输出

对于每组输入，用一行来输出它后序遍历结果。

样例输入

DBACEGF ABCDEFG

BCAD CBAD

样例输出

ACBFGED

CDAB

试题编号：_7_01

试题类型：编程题

标准答案：

试题难度：一般

试题解析：

#include

using namespace std;

struct Node{

char c;

Node *lchild;

Node *rchild;

}tree [200];

int loc;

char str1[100],str2[100];

Node *create(){

tree[loc].lchild=tree[loc].rchild=NULL;

return &tree[loc++];

}

Node *build(Node *root,int q1,int q2,int z1,int z2){

root=create();

char cr=str1[q1];

root->c=cr;

int idx=z1;

for(;idx<=z2;idx++){

if(str2[idx]==cr)

break;

}

if(idx!=z1){

root->lchild=build(root->lchild,q1+1,q1+(idx-z1),z1,idx-1);

}

if(idx!=z2){

root->rchild=build(root->rchild,q1+(idx-z1)+1,q2,idx+1,z2);

}

return root;

}

void PostOrder(Node *root) {

if(root->lchild!=NULL){

PostOrder(root->lchild);

}

if(root->rchild!=NULL){

PostOrder(root->rchild);

}

cout<c;

}

int main() {

while(cin>>str1){

cin>>str2;

loc=0;

Node *root=NULL;

int len1=strlen(str1);

int len2=strlen(str2);

root=build(root,0,len1-1,0,len2-1);

PostOrder(root);

cout<

}

return 0;

}

展示地址：点击浏览

考生答案：（此题已作答）

考生得分：25

是否评分：已评分

评价描述：

2. 快速堆猪

小明有很多猪，他喜欢玩叠猪游戏，就是将猪一头头叠起来。猪叠上去后，还可以把

顶上的猪拿下来。小明知道每头猪的重量，而且他还随时想知道叠在那里的猪最轻的是

多少斤。

时间限制：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

试题编号：_7_02

试题类型：编程题

标准答案：

试题难度：一般

试题解析：

展示地址：点击浏览

考生答案：（此题已作答）

考生得分：0

是否评分：已评分

评价描述：

3. 城堡问题

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