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

青少年软件编程（C语言）等级考试试卷（七级） 分数：100 题数：4 一、编程题(共4题，共100分) 1. 重建二叉树 给定一棵二叉树的前序遍历和中序遍历的结果，求其后序遍历。 时间限制：1000 内存限制：65536 输入 输入可能有多组，以EOF结束。 每组输入包含两个字符串，分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。 输出 对于每组输入，用一行来输出它后序遍历结果。 样例输入 DBACEGF ABCDEFG BCAD CBAD 样例输出 ACBFGED CDAB 试题编号：20220618_7_01 试题类型：编程题 标准答案： 试题难度：一般 试题解析： #include<bits/stdc++.h> 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<<root->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<<endl; } 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 试题编号：20220618_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 输入 程序从标准输入设备读入数据。第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 试题编号：20220618_7_03 试题类型：编程题 标准答案： 试题难度：一般 试题解析： #include<bits/stdc++.h> using namespace std; int maze[60][60],M,N; int book[60][60]; int roomnum=0,maxroom=0,room; void dfs(int x,int y){ if(book[x][y])return; room++; book[x][y]=1; if((maze[x][y]&1)==0)dfs(x,y-1); if((maze[x][y]&2)==0)dfs(x-1,y); if((maze[x][y]&4)==0)dfs(x,y+1); if((maze[x][y]&8)==0)dfs(x+1,y); } int main() { cin>>M>>N; memset(book,0,sizeof(book)); for(int i=0;i<M;i++) for(int j=0;j<N;j++) cin>>maze[i][j]; for(int i=0;i<M;i++) for(int j=0;j<N;j++){ if(!book[i][j]){ room=0; roomnum++; dfs(i,j); maxroom=maxroom>room?maxroom:room; } } cout<<roomnum<<endl<<maxroom<<endl; return 0; } 展示地址：点击浏览 考生答案：（此题已作答） 考生得分：25 是否评分：已评分 评价描述： 4. 有多少种二叉树 输入n(1<n<13)，求n个结点的二叉树有多少种形态 时间限制：1000 内存限制：65536 输入 整数n 输出 答案 样例输入 3 样例输出 5 试题编号：20220618_7_04 试题类型：编程题 标准答案： 试题难度：一般 试题解析： #include<bits/stdc++.h> using namespace std; int main() { long long n,h1=1,y=0; cin>>n; for(long long i=1;i<n+1;i++){ y=(4*i-2)*h1/(i+1); h1=y; } cout<<y; return 0; } 展示地址：点击浏览 考生答案：（此题已作答） 考生得分：25 是否评分：已评分 评价描述： 学科网（北京）股份有限公司 $$