首页 › 试卷 › C/C++编程考级 › C/C++编程七级 › 青少年软件编程(C语言七级)等级考试真题试卷(2022年3月)

青少年软件编程(C语言七级)等级考试真题试卷(2022年3月) VIP

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

一、简答题

1. 简答题

红与黑

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

时间限制: 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>
这道题暂未补解析。
2. 简答题

迷宫问题

定义一个二维数组:

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫, 其中的 1 表示墙壁, 0 表示可以走的路, 只能横着走或竖着走, 不能斜着走, 要求编程序找出从左上角到右下角的最短路线。

时间限制: 1000

内存限制: 65536

输入

一个 5 × 5 的二维数组, 表示一个迷宫。 数据保证有唯一解。

输出

左上角到右下角的最短路径, 格式如样例所示。

样例输入

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

样例输出

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">/*#include &lt;iostream&gt;*/ #include &lt;bits/stdc++.h&gt; using namespace std; const int idata = 50 + 5; int maps[idata][idata]; bool judge[idata][idata]; int change[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int nx, ny; int x[idata], y[idata]; int show[30]; bool flag; void print(int tail) {   if (show[tail])     print(show[tail]);   cout &lt;&lt; "(" &lt;&lt; x[tail] &lt;&lt; ", " &lt;&lt; y[tail] &lt;&lt; ")" &lt;&lt; endl; } int main() {   int head, tail;   register int i, j;   for (i = 0; i &lt; 5; i++) {     for (j = 0; j &lt; 5; j++) {       cin &gt;&gt; maps[i][j];       if (maps[i][j] == 1)         judge[i][j] = 1;     }   }   head = 0;   tail = 1;   judge[0][0] = 1;   show[tail] = head;   while (tail &gt; head) {     head++;     for (i = 0; i &lt; 4; i++) {       nx = x[head] + change[i][0];       ny = y[head] + change[i][1];       if (nx &gt;= 0 &amp;&amp; nx &lt; 5 &amp;&amp; ny &gt;= 0 &amp;&amp; ny &lt; 5 &amp;&amp; !judge[nx][ny]) {         tail++;         x[tail] = nx;         y[tail] = ny;         judge[nx][ny] = 1;         show[tail] = head;         if (nx == 4 &amp;&amp; ny == 4) {           flag = 1;           print(tail);           break;         }       }     }     if (flag)       break;   }   return 0; }</pre><p><a href="http://oj.scratchor.com/problem/CD202203_7_2 " target="_blank">&gt;&gt;试试在线提交?季卡以上会员请联系客服,<span><strong>免费</strong></span>开通OJ账号</a><span></span></p>
这道题暂未补解析。
3. 简答题

二叉树的深度

给定一棵二叉树,求该二叉树的深度

二叉树深度定义:从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的节点个数为树的深度

时间限制:1000

内存限制:65535

输入

第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n <= 10 接下来有n行,依次对应二叉树的n个节点。 每行有两个整数,分别表示该节点的左儿子和右儿子的节点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子

输出

输出一个整型数,表示树的深度


样例输入

3
2 3
-1 -1
-1 -1

样例输出

2
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int MAXN = 2e5 + 7; struct node {   int left, right; } t[MAXN]; int n; void build() {   for (int i = 1; i &lt;= n; i++) {     cin &gt;&gt; t[i].left &gt;&gt; t[i].right;   } } #define rep1(i, n) for (int i = 1; i &lt;= n; i++) inline int dfs(int x) {   if (x == -1)     return 0;   return max(dfs(t[x].left), dfs(t[x].right)) + 1; } signed main() {   ios::sync_with_stdio(0);   cin.tie(0);   cout.tie(0);   cin &gt;&gt; n;   build();   cout &lt;&lt; dfs(1);   return 0; }</pre><pre class="brush:cpp;toolbar:false">//题解2 #include &lt;algorithm&gt; #include &lt;iostream&gt; using namespace std; int meng[102][30]; /*a[i][0]表示节点i的左孩子节点编号, a[i][1]表示节点i的右孩子节点编号,a[i][2]表示i节点的父节点编号。*/ int a, b; int dfs(int root) {   if (meng[root][0] == -1 &amp;&amp; meng[root][1] == -1)     return 1;   else {     int left = 0, right = 0;     if (meng[root][0] &gt;= 0)       left = dfs(meng[root][0]);     /*如果该节点满足不为-1证明它有父节点,     递归回去去证明它的父节点上面是否也有父节点*/     if (meng[root][1] &gt;= 0) {       right = dfs(meng[root][1]);     }     return max(right, left) + 1;   } } int main() {   int n;   cin &gt;&gt; n;   for (int i = 1; i &lt;= n; i++) {     cin &gt;&gt; a &gt;&gt; b;     // 二维是为了更好的判断左孩子还是右孩子,父节点     meng[i][0] = a; // i的左孩子是a     meng[i][1] = b; // i的右孩子是b   }   cout &lt;&lt; dfs(1) &lt;&lt; endl;   return 0; }</pre>
这道题暂未补解析。
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">#include &lt;cmath&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;stack&gt; #include &lt;string&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>
这道题暂未补解析。