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

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

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

一、简答题

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><p><br/></p>
这道题暂未补解析。
2. 简答题

装箱问题

一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。

时间限制:1000

内存限制:65536

输入

输入文件包括几行,每一行代表一个订单。每个订单里的一行包括六个整数,中间用空格隔开,分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。

输出

除了输入的最后一行6个0以外,输入文件里每一行对应着输出文件的一行,每一行输出一个整数代表对应的订单所需的最小包裹数。

样例输入

0 0 4 0 0 1 
7 5 1 0 0 0 
0 0 0 0 0 0

样例输出

2 
1
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//解法1:贪心 #include &lt;bits/stdc++.h&gt; using namespace std; int status[8][4];//status[i][j]:包裹中已有1个大小为i*i的产品,此时可以最多放入多少个j*j的产品  void initStatus() {//status[0]:包裹中没有产品时,各种产品最多可以放多少个      status[2][2] = 8;     status[3][2] = 5, status[3][3] = 3;     status[4][2] = 5;     for(int i = 1; i &lt;= 6; ++i)         status[i][1] = 36 - i*i; } int pro[8];//pro[i]:i*i产品的数量 int main()  {     initStatus();      while(true)     {         int sum = 0, bag = 0, rem[8];//sum:总产品数量  bag:包裹数 rem[i]:当前剩余空间能放几个i*i          for(int i = 1; i &lt;= 6; ++i)         {             cin &gt;&gt; pro[i];             sum += pro[i];         }         if(sum == 0)//如果6个数都是0,那么加和为0,要跳出循环              break;         for(int i = 6; i &gt;= 1; --i)         {             while(pro[i] &gt; 0)             {                 bag++;//用一个新包裹放i*i                 pro[i]--;                 for(int j = 1; j &lt;= 3; ++j)//获取当前剩余空间情况                      rem[j] = status[i][j];                 int j = 3;                 while(j &gt;= 1)                 {                     if(rem[j] &gt; 0 &amp;&amp; pro[j] &gt; 0)//如果可以放j*j的产品                      {                         pro[j]--;//放一个产品                          if(j == 3)                         {                             rem[3]--;                             rem[2] -= 2;                             rem[1] -= 9;                         }                         else if(j == 2)                         {                             rem[2]--;                             rem[1] -= 4;                         }                         else//j == 1                             rem[1]--;                     }                     else                         --j;                 }             }            }         cout &lt;&lt; bag &lt;&lt; endl;     }       return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2:手动完成贪心过程 #include&lt;bits/stdc++.h&gt; using namespace std; int bag;//总包裹数  int k[4] = {0, 5, 3, 1};//k[i]表示3*3的产品有i个时(k[0]表示有4个时)剩余空间可以放2*2产品的个数    int pro[8], p2, p1;//p2:2*2空位数 p1:1*1空位数  int main() {      while(true)     {         for(int i = 1; i &lt;= 6; ++i)             cin &gt;&gt; pro[i];       if(pro[1] == 0 &amp;&amp; pro[2] == 0 &amp;&amp; pro[3] == 0 &amp;&amp; pro[4] == 0 &amp;&amp; pro[5] == 0 &amp;&amp; pro[6] == 0)              break;       bag = pro[6] + pro[5] + pro[4] + ceil(pro[3]/4.0);//6*6和5*5和4*4一定是一个占一个箱子,而3*3 4个占一个箱子         p2 = 5*pro[4]+k[pro[3]%4];//k[pro[3]%4]:有pro[3]%4个3*3在一个包裹中时,剩下的位置可以放2*2的数目         if(pro[2] &gt; p2)//2*2的个数比我们留出来为2*2的空间个数多,就需要为2*2另开箱子             bag += ceil((pro[2]-p2)/9.0);//多出来的2*2箱子应该占用的新箱子数        p1 = 36*bag-36*pro[6]-25*pro[5]-16*pro[4]-9*pro[3]-4*pro[2];//求出当前包裹中所有剩下的可以放1*1的位置数          if(pro[1] &gt; p1)//如果1*1的个数,比我们留出的空间多就需要另开空间         bag += ceil((pro[1]-p1)/36.0);//将多出来的另开箱子      cout &lt;&lt; bag &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; #include&lt;algorithm&gt; #define INF 999999999 #define N 101 using namespace std;   int main() {     int a,b,c,d,e,f;     int g[4]={0,5,3,1};     int x,y;       while(cin&gt;&gt;a&gt;&gt;b&gt;&gt;c&gt;&gt;d&gt;&gt;e&gt;&gt;f)     {         if(a+b+c+d+e+f==0)             break;         int n=f+e+d+(c+3)/4;         x=5*d+g[c%4];         if(b&gt;x)             n+=(b-x+8)/9;         y=36*n-36*f-25*e-16*d-9*c-4*b;         if(a&gt;y)             n+=(a-y+35)/36;         cout&lt;&lt;n&lt;&lt;endl;     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。
3. 简答题

课程表

现在你总共有n门课需要选,记为0到n-1。在选修某些课程之前需要一些先修课程。例如,想要学习课程0,你需要先完成课程1,我们用一个匹配来表示他们:[0, 1]。给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?

时间限制:1000

内存限制:65536

输入

多组数据。每组数据第一行是n和m,n表示有n门课程,m表示有m组依赖关系,接下来的m行是依赖关系的具体信息a b,表示第a门课程依赖第b门课程。 0<=n <=1000,0 <= m <= 4000 两组数据之间可能有空行

输出

对每组数据,能完成输出 True,不能完成输出 False

样例输入

2 1
1 0
2 2
1 0 
0 1

样例输出

True
False
提示

示例2解释: 总共有2门课程。学习课程1之前,你需要先完成课程0;并且学习课程0之前,你还应先完成课程1。这是不可能的。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//拓扑排序:Kahn算法+邻接表+栈 #include &lt;bits/stdc++.h&gt; using namespace std; int n,m; int a[1005][1005];//邻接点 int rd[1005],cd[1005];//入度 出度 int main() {  int r,c,num,i,j,k;  stack&lt;int&gt; st;  while(cin&gt;&gt;n&gt;&gt;m){   memset(a,0,sizeof(a));   memset(rd,0,sizeof(rd));   memset(cd,0,sizeof(cd));   while(!st.empty()) st.pop();   for(i=1;i&lt;=m;i++){    cin&gt;&gt;r&gt;&gt;c;    rd[c]++;    cd[r]++;    a[r][cd[r]]=c;   }   for(i=0;i&lt;=n-1;i++)    if(rd[i]==0){     st.push(i);    }   num=0;   while(!st.empty()){    i=st.top();    st.pop();    num++;    for(j=1;j&lt;=cd[i];j++){     k=a[i][j];     rd[k]--;     if(rd[k]==0)st.push(k);    }   }    if(num==n) cout&lt;&lt;"True"&lt;&lt;endl;   else cout&lt;&lt;"False"&lt;&lt;endl;  }     return 0; }</pre>
这道题暂未补解析。
4. 简答题

最小新整数

给定一个十进制正整数n(0 < n < 1000000000),每个数位上数字均不为0。n的位数为m。 现在从m位中删除k位(0<k < m),求生成的新整数最小为多少? 例如: n = 9128456, k = 2, 则生成的新整数最小为12456

时间限制:1000

内存限制:65536

输入

第一行t, 表示有t组数据; 接下来t行,每一行表示一组测试数据,每组测试数据包含两个数字n, k。

输出

t行,每行一个数字,表示从n中删除k位后得到的最小整数。

样例输入

2
9128456 2
1444 3

样例输出

12456
1
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//解法1:每次找k+1个数中的最小值 #include&lt;bits/stdc++.h&gt; using namespace std; #define N 15 int main() {     int k, t;      char s[N], a[N];     cin &gt;&gt; t;     while(t--)     {         cin &gt;&gt; s &gt;&gt; k;         int an = 0, len = strlen(s), i = 0;         while(i &lt; len)         {             if(k == len-i)//如果剩下的元素个数只有k个,那么都删掉                  break;             int mi = i;//求i~i+k的最小值下标              for(int j = i; j &lt;= i+k; ++j)             {                 if(s[j] &lt; s[mi])                     mi = j;             }             a[++an] = s[mi];             k -= mi - i;//s[i]~s[mi-1]都删掉,删掉了mi-i个元素             i = mi + 1;         }             for(i = 1; i &lt;= an; ++i)             cout &lt;&lt; a[i];         cout &lt;&lt; endl;     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2:删掉比后面数字大的数字 #include&lt;bits/stdc++.h&gt; using namespace std; #define N 15 int main() {     int k, t;      char s[N], a[N];     cin &gt;&gt; t;     while(t--)     {         cin &gt;&gt; s &gt;&gt; k;         int an = 0, len = strlen(s), ct = 0;         for(int i = 0; i &lt; len; ++i)         {             while(an &gt; 0 &amp;&amp; a[an] &gt; s[i] &amp;&amp; ct &lt; k)//a[an]为前一个数 s[i]为后一个数,当a[an]&gt;s[i]时,删除a[an]             {                 an--;                 ct++;//删除数字个数加1             }             a[++an] = s[i];//无论如何s[i]都会填充进数组a         }         while(ct &lt; k)//删除末尾的k-ct个元素         {             an--;             ct++;         }             for(int i = 1; i &lt;= an; ++i)             cout &lt;&lt; a[i];         cout &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; #include&lt;algorithm&gt; #define INF 999999999 #define N 101 using namespace std; char str[N]; int main() {     int t,n;     cin&gt;&gt;t;     while(t--)     {         cin&gt;&gt;str&gt;&gt;n;         int len=strlen(str);         while(n--)         {             for(int i=0;i&lt;len-1;i++)                 if(str[i]&gt;str[i+1])                 {                     for(int j=i;j&lt;len-1;j++)                         str[j]=str[j+1];                     break;                 }             len--;         }         str[len]='\0';         cout&lt;&lt;str&lt;&lt;endl;     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。