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

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

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

一、简答题

1. 简答题

书架

John最近买了一个书架用来存放奶牛养殖书籍,但书架很快被存满了,只剩最顶层有空余。

John共有N头奶牛(1 ≤ N ≤ 20,000),每头奶牛有自己的高度Hi(1 ≤ Hi ≤ 10,000),N头奶牛的总高度为S。书架高度为B(1 ≤ B ≤ S < 2,000,000,007).

为了到达书架顶层,奶牛可以踩着其他奶牛的背,像叠罗汉一样,直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助John到达书架顶层,找出使用奶牛数目最少的解决方案吧。

时间限制:10000

内存限制:65536

输入

第1行:空格隔开的整数N和B 第2~N+1行:第i+1行为整数Hi

输出

能达到书架高度所使用奶牛的最少数目

样例输入

6 40
6
18
11
13
19
11

样例输出

3
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #define INF 999999999 #define N 20001 using namespace std; int a[N]; void qsort(int x, int y) {   int i = x, j = y, mid = a[(x + y) / 2];   while (i &lt;= j) {     while (a[i] &gt; mid)       i++;     while (a[j] &lt; mid)       j--;     if (i &lt;= j) {       swap(a[i], a[j]);       i++;       j--;     }   }   if (x &lt; j)     qsort(x, j);   if (i &lt; y)     qsort(i, y); } int main() {   int n, b;   int sum = 0;   int i;   cin &gt;&gt; n &gt;&gt; b;   for (i = 1; i &lt;= n; i++)     cin &gt;&gt; a[i];   qsort(1, n);   for (i = 1; i &lt;= n; i++) {     sum += a[i];     if (sum &gt;= b)       break;   }   cout &lt;&lt; i &lt;&lt; endl;   ;   return 0; }</pre>
这道题暂未补解析。
2. 简答题

棋盘问题

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。

时间限制:1000

内存限制:65536

输入

输入含有多组测试数据。 每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。

输出

对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。

样例输入

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

样例输出

2
1
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;vector&gt; using namespace std; int vis[20]; char G[20][20]; int ans, n, k; int dfs(int x, int total) {   if (total == k) {     ans++;     return 0;   }   for (int i = x; i &lt; n; i++)     for (int j = 0; j &lt; n; j++)       if (!vis[j] &amp;&amp; G[i][j] == '#') {         vis[j] = 1;         dfs(i + 1, total + 1);         vis[j] = 0;       }   return 0; } int main() {   while (cin &gt;&gt; n &gt;&gt; k) {     if (n == -1 &amp;&amp; k == -1)       break;     memset(vis, 0, sizeof(vis));     memset(G, 0, sizeof(G));     for (int i = 0; i &lt; n; i++)       cin &gt;&gt; G[i];     ans = 0;     dfs(0, 0);     cout &lt;&lt; ans &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。
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. 简答题

拯救公主

多灾多难的公主又被大魔王抓走啦!国王派遣了第一勇士阿福去拯救她。

身为超级厉害的术士,同时也是阿福的好伙伴,你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图,上面标记了阿福和公主所在的位置,以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门,通过一个传送门可以瞬间转移到任意一个传送门,当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外,你还查探到公主所在的地方被设下了结界,需要集齐K种宝石才能打开。当然,你在地图上也标记出了不同宝石所在的位置。

你希望阿福能够带着公主早日凯旋。于是在阿福出发之前,你还需要为阿福计算出他最快救出公主的时间。

地图用一个R×C的字符矩阵来表示。字符S表示阿福所在的位置,字符E表示公主所在的位置,字符#表示不能踏入的禁区,字符$表示传送门,字符.表示该位置安全,数字字符0至4表示了宝石的类型。阿福每次可以从当前的位置走到他上下左右四个方向上的任意一个位置,但不能走出地图边界。阿福每走一步需要花费1个单位时间,从一个传送门到达另一个传送门不需要花费时间。当阿福走到宝石所在的位置时,就视为得到了该宝石,不需要花费额外时间。

时间限制:1000

内存限制:65536

输入

第一行是一个正整数T(1 <= T <= 10),表示一共有T组数据。 每一组数据的第一行包含了三个用空格分开的正整数R、C(2 <= R, C <= 200)和K,表示地图是一个R×C的矩阵,而阿福需要集齐K种宝石才能够打开拘禁公主的结界。 接下来的R行描述了地图的具体内容,每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。$的数量不超过10个。宝石的类型在数字0至4范围内,即不会超过5种宝石。

输出

对于每一组数据,输出阿福救出公主所花费的最少单位时间。若阿福无法救出公主,则输出“oop!”(只输出引号里面的内容,不输出引号)。每组数据的输出结果占一行。

样例输入

1
7 8 2
........
..S..#0.
.##..1..
.0#.....
...1#...
...##E..
...1....

样例输出

11
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;queue&gt; #define N 210 using namespace std; int dir[2][4] = {{1, 0, 0, -1}, {0, 1, -1, 0}}; int dp[N][N][1 &lt;&lt; 5 - 1], trans[20][2], n, m, k, tot, num, T, x, y, ans; char map[N][N]; struct node {   int x, y, step, key;   node(int xx, int yy, int ss, int kk) : x(xx), y(yy), step(ss), key(kk){}; }; bool check(int key) {   int cnt = 0;   for (int i = 0; i &lt;= 5; i++)     if ((key &gt;&gt; i) &amp; 1)       cnt++; // 位运算 统计这条路上可获不同种类的宝石数量   if (cnt &gt;= k)     return 1;   return 0; } int bfs(int x, int y) {   queue&lt;node&gt; que; // 根据结构体 定义队列que   dp[x][y][0] = 1;   node now(x, y, 0, 0); // 相当于 定义了now这个结构体变量   que.push(now);        // 进队   while (!que.empty()) // 当队列不为空时  .empty()--&gt;若队列为空返回1;   {     now = que.front();          // 把队头的值赋给now这个结构体上     que.pop();                  // 弹出队首     for (int i = 0; i &lt; 4; i++) // 上下左右四个执行方案     {       int xx = now.x + dir[0][i]; // 具体变动       int yy = now.y + dir[1][i];       int step = now.step; // 步数       int key = now.key;   //       if (xx &lt; 0 || xx &gt;= n || yy &lt; 0 || yy &gt;= m)         continue; // 判断边界       if (dp[xx][yy][key])         continue; // 若在队中 不走       if (map[xx][yy] == '#')         continue;                           // 禁区 不走       if (map[xx][yy] == 'E' &amp;&amp; check(key)) // 既到达营救点 且 宝石够数       {         return step + 1; // 返回步数 //结束遍历       }       if (isdigit(map[xx][yy])) //       {         dp[xx][yy][key] = 1;                    // 标记 相当于vis         key = key | (1 &lt;&lt; (map[xx][yy] - '0')); // 记录宝石         que.push(node(xx, yy, step + 1, key));  // 进队       }       if (map[xx][yy] == '.') // 普通地带       {         dp[xx][yy][key] = 1; // 标记         que.push(node(xx, yy, step + 1, key));       }       if (map[xx][yy] == '$') // 传送门       {         dp[xx][yy][key] = 1;                   // 标记         que.push(node(xx, yy, step + 1, key)); // 进队         for (int j = 1; j &lt;= tot; j++)         // 遍历 方案         {           xx = trans[j][0], yy = trans[j][1];           if (!dp[xx][yy][key]) {             dp[xx][yy][key] = 1;                   // 标记             que.push(node(xx, yy, step + 1, key)); // 进队           }         }       }     }   }   return -1; // 若遍历完还没返回 就说明没有可行方案 } main() {   cin &gt;&gt; T; // 组数   while (T--) {     memset(dp, 0, sizeof(dp));     tot = 0;     num = 0; // 初始化     scanf("%d%d%d", &amp;n, &amp;m, &amp;k);     // cin&gt;&gt;n&gt;&gt;m&gt;&gt;k;     for (int i = 0; i &lt; n; i++)       for (int j = 0; j &lt; m; j++) {         cin &gt;&gt; map[i][j];         // scanf("%c",&amp;map[i][j]);还是没搞明白为什么不能用scanf和getchar         // map[i][j]=getchar();         if (map[i][j] == 'S')           x = i, y = j, map[i][j] = '.'; // 标记起点         if (map[i][j] == '$')           trans[++tot][0] = i, trans[tot][1] = j; // 记录传送门         if (isdigit(map[i][j]))           num++; // 判断是否是宝石(数字)       }     if (k &gt; num) {       printf("oop!\n");       continue;     } // 没有足够的宝石     ans = bfs(x, y);     if (ans == -1)       printf("oop!\n");     else       printf("%d\n", ans);   } }</pre>
这道题暂未补解析。