首页 › 试卷 › C/C++编程考级 › C/C++编程七级 › 青少年软件编程(C/C++)7级等级考试真题试卷(2023年9月)

青少年软件编程(C/C++)7级等级考试真题试卷(2023年9月) VIP

C/C++编程七级 共 4 题 2023 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

1. 简答题

红与黑(2023.9)

有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。

时间限制:1000

内存限制:65536

输入

包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下 1)‘.’:黑色的瓷砖; 2)‘#’:白色的瓷砖; 3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时,表示输入结束。

输出

对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

样例输入

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

样例输出

45
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//解法1:深搜 #include &lt;bits/stdc++.h&gt; using namespace std; #define N 25 char mp[N][N];//地图 int w, h, ct;//h:行数,w:ct:结果计数 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组 bool vis[N][N]; void dfs(int sx, int sy) { for(int i = 0; i &lt; 4; ++i) { int x = sx + dir[i][0], y = sy + dir[i][1]; if(x &gt;= 1 &amp;&amp; x &lt;= h &amp;&amp; y &gt;= 1 &amp;&amp; y &lt;= w &amp;&amp; vis[x][y] == false &amp;&amp; mp[x][y] != '#') { ct++; vis[x][y] = true; dfs(x, y); } } } int main() { int stx, sty;//起始位置     while(true)     {      cin &gt;&gt; w &gt;&gt; h;      if(w == 0 &amp;&amp; h == 0)      return 0;      for(int i = 1; i &lt;= h; ++i)      for(int j = 1; j &lt;= w; ++j)      {      cin &gt;&gt; mp[i][j];      if(mp[i][j] == '@')      stx = i, sty = j;      }      memset(vis, 0, sizeof(vis));//多组数据,注意状态还原      ct = 1;      vis[stx][sty] = true; dfs(stx, sty);      cout &lt;&lt; ct &lt;&lt; endl; }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2:广搜 #include &lt;bits/stdc++.h&gt; using namespace std; #define N 25 struct Node { int x, y; Node(){} Node(int a, int b):x(a),y(b){} }; char mp[N][N];//地图 int w, h;//w:列数 h:行数 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组 bool vis[N][N]; int bfs(int sx, int sy)//传入起始位置 { queue&lt;Node&gt; que; vis[sx][sy] = true; que.push(Node(sx, sy)); int ct = 1;//计数,看可以到达几个黑色格子 while(que.empty() == false) { Node u = que.front(); que.pop(); for(int i = 0; i &lt; 4; ++i) { int x = u.x + dir[i][0], y = u.y + dir[i][1]; if(x &gt;= 1 &amp;&amp; x &lt;= h &amp;&amp; y &gt;= 1 &amp;&amp; y &lt;= w &amp;&amp; vis[x][y] == false &amp;&amp; mp[x][y] != '#') { vis[x][y] = true; que.push(Node(x, y)); ct++; } } } return ct; } int main() { int stx, sty;     while(true)     {      cin &gt;&gt; w &gt;&gt; h;      if(w == 0 &amp;&amp; h == 0)      return 0;      for(int i = 1; i &lt;= h; ++i)      for(int j = 1; j &lt;= w; ++j)      {      cin &gt;&gt; mp[i][j];      if(mp[i][j] == '@')      stx = i, sty = j;      }      memset(vis, 0, sizeof(vis));      cout &lt;&lt; bfs(stx, sty) &lt;&lt; endl; }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法3: #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;cstdlib&gt; #include&lt;cstring&gt; #define N 1001 using namespace std; int m,n; char ch; int maps[N][N]; int vis[N][N]; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int cnt; void dfs(int x,int y) {     for(int i=0;i&lt;4;i++)     {         int nx=x+dir[i][0];         int ny=y+dir[i][1];         if(nx&gt;=1&amp;&amp;ny&gt;=1&amp;&amp;nx&lt;=n&amp;&amp;ny&lt;=m&amp;&amp;vis[nx][ny]==0&amp;&amp;maps[nx][ny]==1)         {             vis[nx][ny]=1;             cnt++;             dfs(nx,ny);         }     } } int main() {     while(scanf("%d%d",&amp;m,&amp;n)!=EOF&amp;&amp;m&amp;&amp;n)     {         int x,y;         cnt=1;         memset(vis,0,sizeof(vis));         memset(maps,0,sizeof(maps));           for(int i=1;i&lt;=n;i++)             for(int j=1;j&lt;=m;j++)             {                 cin&gt;&gt;ch;                 if(ch=='@')                 {                     x=i;                     y=j;                     maps[i][j]=1;                 }                 if(ch=='.')                     maps[i][j]=1;                 if(ch=='#')                     maps[i][j]=0;             }         vis[x][y]=1;         dfs(x,y);         cout&lt;&lt;cnt&lt;&lt;endl;     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。
2. 简答题

重建二叉树

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

时间限制:1000

内存限制:65536

输入

输入可能有多组,以EOF结束。 每组输入包含两个字符串,分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。

输出

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

样例输入

DBACEGF ABCDEFG
BCAD CBAD

样例输出

ACBFGED
CDAB
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码! #include&lt;stdio.h&gt; #include&lt;string.h&gt; void bulid(int n,char s1[],char s2[])//n是树的节点数,s1是记录先序遍历,s2中序遍历  {      if(n&lt;=0)  return;//没有节点了,找到边界return       int p=strchr(s2,s1[0])-s2;      // strchr(s2,s1[0])是s2的地址+s1[0]第一次出现的位置i。s2是s2的地址       //所以p是 s1[0]第一次出现在s2中的位置      bulid(p,s1+1,s2);      //数的节点数为s1[0]在s2中之前的所有节点。s1+1是把s1数组整体向前移动一位(s1[0]是以前的s1[1],s1[1]改为以前s1[2]...      //以前s1[0]是根,现在不需要,所以删除。要它左子树的根节点       //s2不变(假设中序遍历中根节点的位置是a,那么后序遍历中0~a个点是树的左子树节点)      bulid(n-p-1,s1+p+1,s2+p+1);      //数的节点数为s1[0]在s2中之后的所有节点(因为数组从0开始,所以-1)      //以前s1[0]是根,现在不需要,左子树也不需要,所以都删除。要它右子树的根节点      //s2+p+1(假设中序遍历中根节点的位置是a,a~n-2(数组从0开始)个点是树的右子树节点 )       printf("%c",s1[0]);//输出  } int main() {      char s1[10007],s2[10007];//s1是树的前序遍历,s2是树的中序遍历      while(scanf("%s %s",s1,s2)!=EOF)//多组数据       {          bulid(strlen(s1),s1,s2);           printf("\n");//记得输出\n       }      return 0; } /* 先序遍历第一个节点一定是根节点。 中序遍历根节点左侧就是树的左子树,右侧就是树的右子树。 后序遍历最后一个节点一定是根节点,而假设中序序列里根节点位置是m,那么后序序列里0至m-1个节点是树的左子树节点,m至倒数第二个点是树的右子树节点。 */</pre><p><br/></p>
这道题暂未补解析。
3. 简答题

快速堆猪(2023.9)

小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。

时间限制: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
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; typedef long long LL; int h[2005]; int size_; void up(int u){ while(u/2&amp;&amp;h[u/2]&gt;h[u]){ swap(h[u/2],h[u]); u/=2; } } void down(int u){ int t=u; if(u*2&lt;=size_&amp;&amp;h[u*2]&lt;h[u]) t=u*2; if(u*2+1&lt;=size_&amp;&amp;h[u*2+1]&lt;h[u]) t=u*2+1; if(u!=t){ swap(h[u],h[t]);down(t); } } int main() { char t[10]; string s; int n; while(scanf("%s",t)!=EOF){ s=string(t); if(s=="pop"){ if(size_==0) continue; h[1]=h[size_]; size_--; down(1); } else if(s=="min"){ if(size_==0) continue; cout&lt;&lt;h[1]&lt;&lt;endl; } else if(s=="push"){ cin&gt;&gt;n; size_++; h[size_]=n; up(size_); } } return 0; }</pre><p><br/></p>
这道题暂未补解析。
4. 简答题

表达式·表达式树·表达式求值

众所周知,任何一个表达式,都可以用一棵表达式树来表示。例如,表达式a+b*c,可以表示为如下的表达式树:

   +

  / \

 a   *

    / \

    b c

现在,给你一个中缀表达式,这个中缀表达式用变量来表示(不含数字),请你将这个中缀表达式用表达式二叉树的形式输出出来。

时间限制:1000

内存限制:65535

输入

输入分为三个部分。 第一部分为一行,即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量(a-z),也可能含有运算符(+、-、*、/、小括号),不含有数字,也不含有空格。 第二部分为一个整数n(n < 10),表示中缀表达式的变量数。 第三部分有n行,每行格式为C x,C为变量的字符,x为该变量的值。

输出

输出分为三个部分,第一个部分为该表达式的逆波兰式,即该表达式树的后根遍历结果。占一行。 第二部分为表达式树的显示,如样例输出所示。如果该二叉树是一棵满二叉树,则最底部的叶子结点,分别占据横坐标的第1、3、5、7……个位置(最左边的坐标是1),然后它们的父结点的横坐标,在两个子结点的中间。如果不是满二叉树,则没有结点的地方,用空格填充(但请略去所有的行末空格)。每一行父结点与子结点中隔开一行,用斜杠(/)与反斜杠(\)来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格,\出现的横坐标位置为父结点的横坐标偏右一格。也就是说,如果树高为m,则输出就有2m-1行。 第三部分为一个整数,表示将值代入变量之后,该中缀表达式的值。需要注意的一点是,除法代表整除运算,即舍弃小数点后的部分。同时,测试数据保证不会出现除以0的现象。

样例输入

a+b*c
3
a 2
b 7
c 5

样例输出

abc*+
   +
  / \
 a   *
    / \
    b c
37
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码! #include&lt;iostream&gt; #include&lt;string&gt; #include &lt;cstring&gt; #include&lt;cmath&gt; #include&lt;stack&gt; #define OK 1 #define ERROR 0 #define MAXSIZE 50 using namespace std; struct number {     char ch;     int value; }; number a[10];   //定义二叉树类型 typedef struct BiNode{     char date;     struct BiNode* lchild, * rchild; }BiNode;   //定义栈类型 typedef struct SqStack {     char* base;     char* top;     int stacksize; }SqStack;   //初始化栈 int InitStack(SqStack&amp; S) {     S.base = new char[MAXSIZE];     if (!S.base) exit(ERROR);     S.top = S.base;     S.stacksize = MAXSIZE;     return OK; }   //出栈 char Pop(SqStack&amp; S) {     if (S.top == S.base)         return ERROR;     char e = *(--S.top);     return e; }   //入栈 int Push(SqStack&amp; S, char e) {     if (S.top - S.base==S.stacksize)         return ERROR;     *(S.top++) = e;     return OK; } //将中缀表达式转化为后缀表达式 string Change(string str) {     //str为中缀表达式,str2为后缀表达式     string str2="";     char ch,e;//e用于保存栈中弹出的元素     SqStack S1;//S1用于存放操作符(为辅助栈),S用于存放后续表达式     InitStack(S1);     for (int i = 0; i &lt; str.size(); i++)     {         ch = str[i];         if (ch &gt;= 'a' &amp;&amp; ch &lt;= 'z')         {             str2 += ch;         }         if (ch == '(')             Push(S1, ch);         if (ch == ')')         {             while (*(S1.top - 1) != '(')             {                 e=Pop(S1);                 str2 += e;             }             Pop(S1);//左括号出栈但不入S2栈中         }         //遇到+或-时         //栈空/栈顶为左括号:直接入栈         //否则一直出栈,直到栈空/栈顶为左括号,再入栈         if (ch == '+' || ch == '-')         {             while (*(S1.top - 1) != '(' &amp;&amp; S1.base != S1.top)             {                 e = Pop(S1);                 str2 += e;             }             Push(S1, ch);         }         //遇到*或/时         //栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈         //否则一直出栈,直到满足上述条件,再入栈         if (ch == '*' || ch == '/')         {             while (S1.base != S1.top &amp;&amp; *(S1.top - 1) != '(' &amp;&amp; *(S1.top - 1) != '-' &amp;&amp; *(S1.top - 1) != '+')             {                 e = Pop(S1);                 str2 += e;             }             Push(S1, ch);         }     }     //中缀表达式遍历完成,还需检查栈中是否有未输出字符        //判断栈空,非空则直接出栈     while (S1.base != S1.top)     {         e = Pop(S1);         if (e != '(')             str2 +=e;     }     return str2; } struct BiNode* s[MAXSIZE];//定义栈,该栈用于存放树 int top = -1;   //建立二叉树 BiNode* CreatTree(string str) {     //str为后缀表达式     BiNode* T,* T2;     SqStack S;     BiNode* e1, * e2;     int i;     InitStack(S);     for (i = 0; i &lt; str.size()-1; i++)     {         if (str[i] &gt;= 'a' &amp;&amp; str[i] &lt;= 'z')         {             T = new BiNode;             T-&gt;date = str[i];             T-&gt;lchild = T-&gt;rchild = NULL;             s[++top] = T;         }         else         {             T = new BiNode;             T-&gt;date = str[i];             e1 = s[top--];             e2 = s[top--];             T-&gt;lchild = e2; T-&gt;rchild = e1;             s[++top] = T;         }     }     T = new BiNode;     T-&gt;date = str[i];T-&gt;rchild = s[top--];T-&gt;lchild = s[top--];     s[++top] = T;     T2 = new BiNode;     T2 = s[top];     return T2; }   int Seek(char e,int n) {     for (int i = 0; i &lt; n; i++)     {         if (a[i].ch == e)             return a[i].value;     } }   int Count(string str,int n) {     //str为后缀表达式数组,n变量个数     int sum = 0;     stack&lt;int&gt;S;     int x,x1, x2;     for (int i = 0; i &lt; n; i++)     {         cin &gt;&gt; a[i].ch &gt;&gt; a[i].value;     }     for (int i = 0; i &lt; str.size(); i++)     {         if (str[i] &gt;= 'a' &amp;&amp; str[i] &lt;= 'z')         {             x = Seek(str[i], n);             S.push(x);         }         else         {             x2 = S.top(); S.pop();//左操作数             x1 = S.top(); S.pop();//右操作数             switch (str[i])             {             case'+':sum = x1 + x2; break;             case'-':sum = x1 - x2; break;             case'*':sum = x1 * x2; break;             case'/':sum = x1 / x2; break;             }             S.push(sum);         }     }     sum = S.top();     return sum; } char arr[1000][1000]; //打印二叉树 void PrintTree(int tag,BiNode* T,int x,int m,int y) {     arr[2 * tag - 1][(x + m) / 2] = T-&gt;date;     if (tag != 1)     {         if (y == 1)             arr[2 * tag - 2][m] = '/';         else             arr[2 * tag - 2][x] = '\\';     }     if (T-&gt;lchild != NULL)         PrintTree(tag + 1, T-&gt;lchild, x, (x + m) / 2 - 1, 1);     if (T-&gt;rchild != NULL)         PrintTree(tag + 1, T-&gt;rchild, (x + m) / 2 + 1, m, 0); }   //计算二叉树的深度 int Depth(BiNode* T)  {     int m, n;     if (T == NULL) return 0;     else {         m = Depth(T-&gt;lchild);         n = Depth(T-&gt;rchild);         if (m &gt; n) return (m + 1);         else             return(n + 1);     } }   bool Judge(int i, int j, int n) {     for (int k = j + 1; k &lt;= n; k++)     {         if (arr[i][k] != ' ')             return 1;     }     return 0; }   int main() {     string str1;//中序表达式     cin &gt;&gt; str1;     int n;//变量个数     cin &gt;&gt; n;     string str2 = Change(str1);//str2为后序表达式     BiNode* T = CreatTree(str2);     int sum = Count(str2, n);     int dp = Depth(T);     cout &lt;&lt; str2 &lt;&lt; endl;     memset(arr, ' ', sizeof(arr));     PrintTree(1, T, 1, pow(2.0, dp) - 1, 0);     for (int i = 1; i &lt;= 2 * dp - 1; i++)     {         for (int j = 1; j &lt;= pow(2.0, dp) - 1; j++)         {             cout &lt;&lt; arr[i][j];             if (arr[i][j] != ' ')             {                 if(Judge(i,j,pow(2.0,dp)-1))                     continue;                 else                     break;             }         }         cout &lt;&lt; endl;     }     cout &lt;&lt; sum &lt;&lt; endl;     return 0; }</pre><p><br/></p>
这道题暂未补解析。