首页 › 试卷 › C/C++编程考级 › C/C++编程五级 › 青少年软件编程(C语言五级)等级考试试卷(2020年12月)

青少年软件编程(C语言五级)等级考试试卷(2020年12月) VIP

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

一、简答题

1. 简答题

漫漫回国路

2020年5月,国际航班机票难求。一位在美国华盛顿的中国留学生,因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况,求问他回不回得来(不考虑转机次数和机票价格)。

时间限制:1000

内存限制:65536

输入

第一行为case个数n(n < 10)。 每一个case,第一行为机场个数N,N ≤ 10。 之后的N行,每一行包含N个整数。第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)个整数代表从第i个机场出发到第j个机场的能买到的航班的最低票价t(0 < t < 10000)。如果不幸没有航班,那么用-1表示。第i行第i个整数为0。 起点华盛顿杜勒斯国际机场的编号为1,终点北京首都国际机场的编号为N。

输出

每一个case一行。 能够回国,输出字符串:YES。如果无法回国,输出字符串:NO


样例输入

2
3
0 100 -1
-1 0 200
-1 -1 0
4
0 1 5 -1
3 0 1 -1
2 4 0 -1
4 1 1 0

样例输出

YES
NO
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">// 广搜 #include &lt;bits/stdc++.h&gt; using namespace std; int a[12][12], n; bool v[12][12]; bool bfs(int p) {   queue&lt;int&gt; q;   q.push(p);   v[p][p] = true;   while (!q.empty()) {     int h = q.front();     q.pop();     for (int i = 1; i &lt;= n; i++) {       if (!v[h][i] &amp;&amp; a[h][i] &gt; 0) {         if (i == n)           return true;         else {           q.push(i);           v[h][i] = true;         }       }     }   }   return false; } int main() {   int k;   cin &gt;&gt; k;   while (k--) {     cin &gt;&gt; n;     for (int i = 1; i &lt;= n; i++)       for (int j = 1; j &lt;= n; j++)         cin &gt;&gt; a[i][j];     if (bfs(1))       cout &lt;&lt; "YES" &lt;&lt; endl;     else       cout &lt;&lt; "NO" &lt;&lt; endl;   }   return 0; }</pre><pre class="brush:cpp;toolbar:false">// 参考代码2 // 深度优先搜索 #include &lt;stdbool.h&gt; #include &lt;stdio.h&gt; #define MAX_N 10 #define INF 10000 int airports[MAX_N][MAX_N]; // 存储机场之间的航班票价 bool visited[MAX_N];        // 记录机场是否被访问过 int n;      // 机场个数 bool found; // 是否找到回国路径 void dfs(int start, int end) {   if (start == end) {     found = true; // 找到回国路径     return;   }   visited[start] = true;   for (int i = 1; i &lt;= n; i++) {     if (!visited[i] &amp;&amp; airports[start][i] != -1) {       dfs(i, end);     }   } } bool canReturn() {   found = false;   for (int i = 1; i &lt;= n; i++) {     visited[i] = false;   }   dfs(1, n);   return found; } int main() {   int cases;   scanf("%d", &amp;cases);   while (cases--) {     scanf("%d", &amp;n);     for (int i = 1; i &lt;= n; i++) {       for (int j = 1; j &lt;= n; j++) {         scanf("%d", &amp;airports[i][j]);       }     }     if (canReturn()) {       printf("YES\n");     } else {       printf("NO\n");     }   }   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">#include &lt;cstdio&gt; #include &lt;cstring&gt; using namespace std; int a[7]; int main() {   int x, xx, i, ans;   while (1) {     for (i = 1; i &lt;= 6; i++) {       scanf("%d", &amp;a[i]);     }     if (a[1] == 0 &amp;&amp; a[2] == 0 &amp;&amp; a[3] == 0 &amp;&amp; a[4] == 0 &amp;&amp; a[5] == 0 &amp;&amp;         a[6] == 0)       break;     ans = 0;     ans = a[6];     ans = ans + a[5];     xx = a[5] * 11;     if (xx &lt;= a[1])       a[1] = a[1] - xx;     else       a[1] = 0;     ans = ans + a[4];     x = a[4] * 5;     if (x &lt;= a[2]) {       a[2] = a[2] - x;     } else {       xx = 4 * (x - a[2]);       if (xx &lt;= a[1])         a[1] = a[1] - xx;       else         a[1] = 0;       a[2] = 0;     }     ans = ans + a[3] / 4;     a[3] = a[3] % 4;     if (a[3] &gt; 0) {       if (a[3] == 3) {         ans++;         if (a[2] &gt;= 1) {           a[2]--;           xx = 5;           if (xx &lt;= a[1])             a[1] = a[1] - xx;           else             a[1] = 0;         } else {           xx = 9;           if (xx &lt;= a[1])             a[1] = a[1] - xx;           else             a[1] = 0;         }       } else if (a[3] == 2) {         ans++;         if (a[2] &gt;= 3) {           a[2] -= 3;           xx = 6;           if (xx &lt;= a[1])             a[1] = a[1] - xx;           else             a[1] = 0;         } else {           xx = 6 + (3 - a[2]) * 4;           a[2] = 0;           if (xx &lt;= a[1])             a[1] = a[1] - xx;           else             a[1] = 0;         }       } else if (a[3] == 1) {         ans++;         if (a[2] &gt;= 5) {           a[2] -= 5;           xx = 7;           if (xx &lt;= a[1])             a[1] = a[1] - xx;           else             a[1] = 0;         } else {           xx = 7 + (5 - a[2]) * 4;           a[2] = 0;           if (xx &lt;= a[1])             a[1] = a[1] - xx;           else             a[1] = 0;         }       }     }     ans = ans + a[2] / 9;     a[2] = a[2] % 9;     if (a[2] &gt; 0) {       ans++;       xx = 36 - a[2] * 4;       a[2] = 0;       if (xx &lt;= a[1])         a[1] = a[1] - xx;       else         a[1] = 0;     }     ans = ans + a[1] / 36;     a[1] = a[1] % 36;     if (a[1] &gt; 0) {       ans++;       a[1] = 0;     }     printf("%d\n", ans);   }   return 0; }</pre>
这道题暂未补解析。
3. 简答题

鸣人和佐助

描述

佐助被大蛇丸诱骗走了,鸣人在多少时间内能追上他呢?

已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位置都可以走到,只不过有些位置上有大蛇丸的手下,需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉,每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动,每移动一个距离需要花费1个单位时间,打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了,则只可以走到没有大蛇丸手下的位置,不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动,大蛇丸的手下也不移动。请问,鸣人要追上佐助最少需要花费多少时间?

输入

输入的第一行包含三个整数:M,N,T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200,0 ≤ T < 10

后面是M行N列的地图,其中@代表鸣人,+代表佐助。*代表通路,#代表大蛇丸的手下。

输出

输出包含一个整数R,代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助,则输出-1。

 

样例输入1

4 4 1
#@##
**##
###+
****

样例输入2

4 4 2
#@##
**##
###+
****

 

样例输出1

6

样例输出2

4
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int n, m, t, s2[10][256][256], fx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; char s1[256][256]; struct AAA {   int i;   int j;   int bs;   int st; }; int bfs() {   int i, j, k, ti, tj, ret = -1;   queue&lt;AAA&gt; dl;   AAA tmp, tmp1;   for (i = 0; i &lt; m; i++) {     for (j = 0; j &lt; n; j++)       if (s1[i][j] == '@') {         tmp.i = i;         tmp.j = j;         tmp.bs = 0;         tmp.st = t;         break;       }     if (j &lt; n)       break;   }   dl.push(tmp);   for (i = 0; i &lt; 10; i++)     for (j = 0; j &lt; m; j++)       for (k = 0; k &lt; n; k++)         s2[i][j][k] = 0;   s2[0][tmp.i][tmp.j] = 1;   while (!dl.empty()) {     tmp = dl.front();     dl.pop();     if (s1[tmp.i][tmp.j] == '+') {       ret = tmp.bs;       break;     }     for (i = 0; i &lt; 4; i++) {       ti = tmp.i + fx[i][0];       tj = tmp.j + fx[i][1];       if ((ti &lt; 0) || (ti &gt;= m) || (tj &lt; 0) || (tj &gt;= n))         continue;       if (s2[t - tmp.st][ti][tj] == 1)         continue;       if ((s1[ti][tj] == '#') &amp;&amp; (tmp.st == 0))         continue;       s2[t - tmp.st][ti][tj] = 1;       tmp1.i = ti;       tmp1.j = tj;       tmp1.bs = tmp.bs + 1;       tmp1.st = tmp.st;       if (s1[ti][tj] == '#')         tmp1.st--;       dl.push(tmp1);     }   }   return ret; } int main() {   int i, j, k;   char tmp[16];   gets(tmp);   sscanf(tmp, "%d%d%d", &amp;m, &amp;n, &amp;t);   for (i = 0; i &lt; m; i++)     gets(s1[i]);   printf("%d", bfs());   return 0; }</pre><p><br/></p><pre class="brush:cpp;toolbar:false">//参考代码2 #include&lt;stdio.h&gt; #include&lt;algorithm&gt; #include&lt;string.h&gt; using namespace std; const int inf=0x3f3f3f3f; int n,m,sx,sy,st,minstep=inf; int step[201][201][11],dx[]={0,1,-1,0},dy[]={1,0,0,-1}; char mp[201][201]; bool vis[201][201]; void dfs(int x,int y,int t,int stp) {     if(x&lt;1 || x&gt;n || y&lt;1 || y&gt;m || vis[x][y]) return ;     if(t&lt;0) return ;     if(stp&gt;=minstep) return ;     if(stp&gt;=step[x][y][t]) return ;     step[x][y][t]=stp;          if(mp[x][y]=='#') t--;     else if(mp[x][y]=='+') {         if(stp&lt;minstep) minstep=stp;         return ;     }          vis[x][y]=1;     for(int i=0;i&lt;4;++i){         int nx=x+dx[i];         int ny=y+dy[i];         dfs(nx,ny,t,stp+1);     }     vis[x][y]=0; } int main() {     scanf("%d%d%d",&amp;n,&amp;m,&amp;st);     getchar();     for(int i=1;i&lt;=n;++i){         for(int j=1;j&lt;=m;++j){             scanf("%c",&amp;mp[i][j]);             if(mp[i][j]=='@') {                 sx=i;                 sy=j;             }         }         getchar();     }     memset(step,0x3f,sizeof(step));     dfs(sx,sy,st,0);     if(minstep==inf) printf("-1");     else printf("%d",minstep);     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码3 #include&lt;cstdio&gt; #include&lt;queue&gt; using namespace std; struct POINT {     int x,y,tot,T; } point; queue&lt;POINT&gt; que; int main() {     bool walked[205][205][15]={};     int r,c,T,F[4][2]={{-1,0},{1,0},{0,-1},{0,1}};     scanf("%d%d%d",&amp;r,&amp;c,&amp;T);     char maze[205][205]={};     for(int i=0;i&lt;r;i++)     {         scanf("%s",maze[i]);         for(int j=0;j&lt;c;j++)             if(maze[i][j]=='@')             {                 point.x=i;point.y=j;                 point.tot=0;point.T=T;             }     }     que.push(point);     while(!que.empty())     {         for(int i=0;i&lt;4;i++)         {             point.x=que.front().x+F[i][0];             point.y=que.front().y+F[i][1];             point.tot=que.front().tot+1;             point.T=que.front().T;             if(point.x&lt;0 || point.x&gt;=r || point.y&lt;0 || point.y&gt;=c || walked[point.x][point.y][point.T]) continue;             if(maze[point.x][point.y]=='#')                 if(point.T) point.T--;                 else continue;             if(maze[point.x][point.y]=='+') {printf("%d\n",point.tot);return 0;}             walked[point.x][point.y][point.T]=true;             que.push(point);         }         que.pop();     }     printf("-1\n");     return 0; }</pre>
这道题暂未补解析。
4. 简答题

分成互质组

给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?

时间限制:1000

内存限制:65536

输入

第一行是一个正整数n。1 <= n <= 10。 第二行是n个不大于10000的正整数。

输出

一个正整数,即最少需要的组数。


样例输入

6
14 20 33 117 143 175

样例输出

3
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;bits/stdc++.h&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iomanip&gt; #include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;string&gt; using namespace std; int n, a[12], ans, huzhi[12][12]; int group[12][12], group_size[12]; int hz(int x, int y) {   if (y == 0)     return x;   return hz(y, x % y); } void ss(int x, int group_cnt) {   if (x &gt; n) {     ans = min(group_cnt, ans);     return;   }   for (int i = 1; i &lt;= group_cnt; i++) {     int pd = 0;     for (int j = 1; j &lt;= group_size[i]; j++) {       if (huzhi[x][group[i][j]] == 0) {         pd = 1;         break;       }     }     if (pd == 1)       continue;     group_size[i]++;     group[i][group_size[i]] = x;     ss(x + 1, group_cnt);     group[i][group_size[i]] = 0;     group_size[i]--;   }   group_size[group_cnt + 1] = 1;   group[group_cnt + 1][1] = x;   ss(x + 1, group_cnt + 1);   group[group_cnt + 1][1] = 0;   group_size[group_cnt + 1] = 0; } int main() {   scanf("%d", &amp;n);   for (int i = 1; i &lt;= n; i++)     scanf("%d", &amp;a[i]);   for (int i = 1; i &lt;= n; i++)     for (int j = 1; j &lt;= n; j++) {       if (hz(a[i], a[j]) == 1) {         huzhi[i][j] = 1;       }     }   ans = 10;   ss(1, 0);   printf("%d", ans);   return 0; }</pre>
这道题暂未补解析。