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

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

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

一、简答题

1. 简答题

走出迷宫

当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。

假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。

时间限制:1000

内存限制:65536

输入

第一行是两个整数n和m(1<=n,m<=100),表示迷宫的行数和列数。 接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符'.'表示空地,'#'表示墙,'S'表示起点,'T'表示出口。

输出

输出从起点到出口最少需要走的步数。

样例输入

3 3
S#T
.#.
...

样例输出

6
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int n, m, p[10008], q[10008], ans[108][108], qx, qy, zx, zy; char a[108][108]; int xx[5] = {0, 1, -1, 0, 0}; int yy[5] = {0, 0, 0, 1, -1}; void bfs() {   a[qx][qy] = '#';   ans[qx][qy] = 0;   int head = 1;   int tail = 1;   p[1] = qx;   q[1] = qy;   while (head &lt;= tail) {     for (int i = 1; i &lt;= 4; i++) {       int h = p[head] + xx[i];       int l = q[head] + yy[i];       if (a[h][l] != '#' &amp;&amp; h &gt;= 1 &amp;&amp; l &gt;= 1 &amp;&amp; h &lt;= n &amp;&amp; l &lt;= m) {         a[h][l] = '#';         tail++;         p[tail] = h;         q[tail] = l;         ans[h][l] = ans[p[head]][q[head]] + 1;         if (h == zx &amp;&amp; l == zy) {           cout &lt;&lt; ans[h][l] &lt;&lt; endl;           return;         }       }     }     head++;   } } int main() {   cin &gt;&gt; n &gt;&gt; m;   for (int i = 1; i &lt;= n; i++) {     for (int j = 1; j &lt;= m; j++) {       cin &gt;&gt; a[i][j];       if (a[i][j] == 'S') {         qx = i;         qy = j;       }       if (a[i][j] == 'T') {         zx = i;         zy = j;       }     }   }   bfs();   return 0; }</pre>
这道题暂未补解析。
2. 简答题

拯救公主

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

    身为超级厉害的术士,同时也是阿福的好伙伴,你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图,上面标记了阿福和公主所在的位置,以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门,通过一个传送门可以瞬间转移到任意一个传送门,当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外,你还查探到公主所在的地方被设下了结界,需要集齐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;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;queue&gt; using namespace std; struct POINT {   int x, y, tot;   bool get_jewel[7], enchantment; } point, door; int main() {   int k, F[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};   scanf("%d", &amp;k);   for (int kk = 1; kk &lt;= k; kk++) {     queue&lt;POINT&gt; que;     int r, c, needkind, door_coord[15][2] = {}, sdoor_coord = 0;     char maze[205][205] = {};     bool walked[205][205][35] = {}, finish = false;     scanf("%d%d%d", &amp;r, &amp;c, &amp;needkind);     for (int i = 0; i &lt; r; i++) {       scanf("%s", maze[i]);       for (int j = 0; j &lt; c; j++) {         if (maze[i][j] == 'S') {           memset(point.get_jewel, false, sizeof(point.get_jewel));           point.x = i;           point.y = j;           point.tot = 0;           point.enchantment = true;         }         if (maze[i][j] == '$') {           door_coord[sdoor_coord][0] = i;           door_coord[sdoor_coord++][1] = j;         }       }     }     que.push(point);     while (!que.empty()) {       for (int i = 0; i &lt; 4; i++) {         point = que.front();         point.tot++;         point.x += F[i][0];         point.y += F[i][1];         if (point.x &lt; 0 || point.x &gt;= r || point.y &lt; 0 || point.y &gt;= c ||             maze[point.x][point.y] == '#')           continue;         if ('0' &lt;= maze[point.x][point.y] &amp;&amp; maze[point.x][point.y] &lt;= '4')           point.get_jewel[maze[point.x][point.y] - '0'] = true;         int sget_jewel = 0, ss = 0;         for (int i = 0; i &lt; 5; i++)           if (point.get_jewel[i])             sget_jewel += pow(2, i), ss++;         if (walked[point.x][point.y][sget_jewel])           continue;         walked[point.x][point.y][sget_jewel] = true;         if (ss &gt;= needkind)           point.enchantment = false;         if (maze[point.x][point.y] == '$') {           door = point;           for (int i = 0; i &lt; sdoor_coord; i++)             if (door_coord[i][0] != point.x || door_coord[i][1] != point.y) {               door.x = door_coord[i][0];               door.y = door_coord[i][1];               que.push(door);             }         }         if (maze[point.x][point.y] == 'E' &amp;&amp; !point.enchantment) {           printf("%d\n", point.tot);           finish = true;         }         if (finish)           break;         que.push(point);       }       if (finish)         break;       que.pop();     }     if (!finish)       printf("oop!\n");   }   return 0; }</pre><pre class="brush:cpp;toolbar:false">// 参考答案2 #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>
这道题暂未补解析。
3. 简答题

有多少种二叉树(2023.3)

输入n(1<n<13),求n个结点的二叉树有多少种形态

时间限制:1000

内存限制:65536

输入

整数n

输出

答案

样例输入

3

样例输出

5
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; long long cat(int n) {   if (n == 0)     return 1;   long long sum(0);   for (int i = 0; i &lt; n; i++)     sum += cat(i) * cat(n - 1 - i);   return sum; } int main() {   int n;   cin &gt;&gt; n;   cout &lt;&lt; cat(n);   return 0; }</pre>
这道题暂未补解析。
4. 简答题

Sequence

给定m个数字序列,每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列,显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和,一共会得到n^m个和,请找出最小的n个和

时间限制:3000

内存限制:65536

输入

输入的第一行是一个整数T,表示测试用例的数量,接下来是T个测试用例的输入 每个测试用例输入的第一行是两个正整数m(0 < m <= 100)和n(0 < n <= 2000),然后有m行,每行有n个数,数字之间用空格分开,表示这m个序列 序列中的数字不会大于10000

输出

对每组测试用例,输出一行用空格隔开的数,表示最小的n个和

样例输入

1
2 3
1 2 3
2 2 3

样例输出

3 3 4
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;iostream&gt; #include &lt;queue&gt; using namespace std; priority_queue&lt;int&gt; que; int a[2005]; int b[2005]; // 用作中间数组 int main() {   int T;   cin &gt;&gt; T;   int m, n;   while (T--) {     cin &gt;&gt; m &gt;&gt; n;     for (int i = 0; i &lt; n; i++) {       scanf("%d", &amp;a[i]);     }     sort(a, a + n);             // 用a做总的和数组     for (int i = 1; i &lt; m; i++) // 轮接下来的序列     {       for (int j = 0; j &lt; n; j++) {         scanf("%d", &amp;b[j]);         que.push(a[0] + b[j]);       }       for (int j = 1; j &lt; n; j++) {         for (int k = 0; k &lt; n; k++) {           if (a[j] + b[k] &lt; que.top()) {             que.pop();             que.push(a[j] +                      b[k]); // 比最大值小就顶了它,想要得到ab两个里面最小的n个数           }         }       }       for (int i = 0; i &lt; n; i++) {         a[n - i - 1] = que.top(); // 由于是最大值堆,要反过来让a有序         que.pop();                // 队列已经被清空了,轮下一次       }     }     for (int i = 0; i &lt; n - 1; i++)       printf("%d ", a[i]);     printf("%d\n", a[n - 1]);   }   return 0; }</pre>
这道题暂未补解析。