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

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

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

一、简答题

1. 简答题

迷宫(2023.12)

一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。

时间限制:3000

内存限制:65536

输入

第1行是测试数据的组数k,后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100),表示迷宫的规模是n * n的。接下来是一个n * n的矩阵,矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb,描述A处在第ha行, 第la列,B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。

输出

k行,每行输出对应一个输入。能办到则输出“YES”,否则输出“NO”。


样例输入

2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0

样例输出

YES
NO
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">// 参考答案1 #include &lt;queue&gt; #include &lt;stdio.h&gt; #include &lt;string.h&gt; int m; char c[100][100]; int xa, ya, xb, yb; bool vis[100][100]; int dir[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; struct node {   int x;   int y;   int step; } q[10000]; void bfs(int xa, int ya, int xb, int yb) {   int head = 1, tail = 1;   memset(vis, 0, sizeof(vis));   q[tail].x = xa;   q[tail].y = ya;   q[tail].step = 0;   tail++;   vis[xa][ya] = 1;   int flag = 1;   while (head &lt; tail) {     int x = q[head].x;     int y = q[head].y;     int step = q[head].step;     if (x == xb &amp;&amp; y == yb) {       flag = 0;       printf("YES\n");       break;     }     for (int i = 0; i &lt; 4; i++) {       int nx = x + dir[i][0];       int ny = y + dir[i][1];       if (nx &gt;= 0 &amp;&amp; nx &lt; m &amp;&amp; ny &gt;= 0 &amp;&amp; ny &lt; m &amp;&amp; c[nx][ny] == '.' &amp;&amp;           vis[nx][ny] == 0) {         vis[nx][ny] = 1;         q[tail].x = nx;         q[tail].y = ny;         q[tail].step = step + 1;         tail++;       }     }     head++;   }   if (flag == 1) {     printf("NO\n");   } } int main() {   int n;   scanf("%d", &amp;n);   while (n--) {     scanf("%d", &amp;m);     for (int i = 0; i &lt; m; i++) {       scanf("%s", c[i]);     }     scanf("%d%d%d%d", &amp;xa, &amp;ya, &amp;xb, &amp;yb);     bfs(xa, ya, xb, yb);   }   return 0; }</pre><pre class="brush:cpp;toolbar:false">// 参考答案1 #include &lt;bits/stdc++.h&gt; using namespace std; const int N = 1e4 + 10; int k, n, v[102][102]; char a[102][102]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; bool bfs(int x1, int y1, int x2, int y2) {   if (a[x1][y1] == '#' || a[x2][y2] == '#')     return false;   if (a[x1][y1] != '#' &amp;&amp; x1 == x2 &amp;&amp; y1 == y2)     return true;   queue&lt;pair&lt;int, int&gt;&gt; q;   pair&lt;int, int&gt; pa;   pa.first = x1;   pa.second = y1;   v[x1][y1] = 1;   q.push(pa);   while (!q.empty()) {     int x = q.front().first;     int y = q.front().second;     q.pop();     for (int i = 0; i &lt; 4; i++) {       int xx = x + dx[i];       int yy = y + dy[i];       if (xx &lt; 0 || xx &gt;= n || yy &lt; 0 || yy &gt;= n)         continue;       if (a[xx][yy] == '.' &amp;&amp; v[xx][yy] == 0) {         if (xx == x2 &amp;&amp; yy == y2)           return true;         v[xx][yy] = 1;         pa.first = xx;         pa.second = yy;         q.push(pa);       }     }   }   return false; } int main() {   cin &gt;&gt; k;   int x1, y1, x2, y2;   while (k--) {     cin &gt;&gt; n;     for (int i = 0; i &lt; n; i++)       for (int j = 0; j &lt; n; j++)         cin &gt;&gt; a[i][j];     cin &gt;&gt; x1 &gt;&gt; y1 &gt;&gt; x2 &gt;&gt; y2;     memset(v, 0, sizeof(v));     if (bfs(x1, y1, x2, y2))       cout &lt;&lt; "YES" &lt;&lt; endl;     else       cout &lt;&lt; "NO" &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。
2. 简答题

拯救公主(2023.12)

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

    身为超级厉害的术士,同时也是阿福的好伙伴,你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图,上面标记了阿福和公主所在的位置,以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门,通过一个传送门可以瞬间转移到任意一个传送门,当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外,你还查探到公主所在的地方被设下了结界,需要集齐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><pre class="brush:cpp;toolbar:false">// 参考答案3 #include &lt;bits/stdc++.h&gt; using namespace std; struct Point {   int x, y, step;     // 坐标 步长   bool germ[7], ench; // 找到的宝石  结界 } point, door; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int k; int main() {   cin &gt;&gt; k;   while (k--) {     // 准备工作     queue&lt;Point&gt; q;     int r, c, needk; // 边界 需要宝石种类     cin &gt;&gt; r &gt;&gt; c &gt;&gt; needk;     int door_c[15][2]{}, door_n = 0; // 传送门坐标 数量     char ma[205][205]{};             // 地图     bool walked[205][205][35]{}, finish = false;     // 标记路是否走过及取得的宝石种类   是否完成     for (int i = 0; i &lt; r; i++) {       cin &gt;&gt; ma[i];       for (int j = 0; j &lt; c; j++) {         if (ma[i][j] == 'S') { // 起点           memset(point.germ, false, sizeof(point.germ));           point.x = i;           point.y = j;           point.step = 0;           point.ench = true;         }         if (ma[i][j] == '$') { // 传送门           door_c[door_n][0] = i;           door_c[door_n][1] = j;           door_n++;         }       }     }     // 广搜     q.push(point);     while (!q.empty()) {       for (int i = 0; i &lt; 4; i++) {         point = q.front();         point.step++;         point.x += dx[i];         point.y += dy[i];         if (point.x &lt; 0 || point.x &gt;= r || point.y &lt; 0 || point.y &gt;= c ||             (ma[point.x][point.y] == '#'))           continue;         if (ma[point.x][point.y] &gt;= '0' &amp;&amp;             ma[point.x][point.y] &lt;= '4') // 找到宝石           point.germ[ma[point.x][point.y] - '0'] = true;         int get_v = 0, s = 0;         for (int i = 0; i &lt;= 4; i++) // 统计宝石           if (point.germ[i]) {             get_v += (int)pow(2, i);             s++;           }         if (walked[point.x][point.y][get_v])           continue;                             // 之前到达过         walked[point.x][point.y][get_v] = true; // 标记         if (s &gt;= needk)           point.ench = false;              // 结界消失         if (ma[point.x][point.y] == '$') { // 找到传送门           door = point;           for (int i = 0; i &lt; door_n; i++) // 遍历所有的传送门             if ((door_c[i][0] != point.x) ||                 (door_c[i][1] != point.y)) { // 可传送               door.x = door_c[i][0];               door.y = door_c[i][1];               q.push(door);             }         }         if (ma[point.x][point.y] == 'E' &amp;&amp; !point.ench) { // 找到终点且无结界           cout &lt;&lt; point.step &lt;&lt; endl;           finish = true;         }         if (finish)           break;         q.push(point);       }       if (finish)         break;       q.pop();     }     if (!finish)       cout &lt;&lt; "oop!" &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。
3. 简答题

二叉树的深度(2023.12)

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

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

时间限制: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><pre class="brush:cpp;toolbar:false">//题解3 #include &lt;bits/stdc++.h&gt; using namespace std; struct node {   int left;   int right; } tree[25]; int depth(int root) {   if (root == -1)     return 0;   int a = depth(tree[root].left);   int b = depth(tree[root].right);   return max(a, b) + 1; } int main() {   int n;   cin &gt;&gt; n;   for (int i = 1; i &lt;= n; i++) {     cin &gt;&gt; tree[i].left &gt;&gt; tree[i].right;   }   cout &lt;&lt; depth(1);   return 0; }</pre>
这道题暂未补解析。
4. 简答题

Sequence(2023.12)

给定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">// 参考答案1 #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><pre class="brush:cpp;toolbar:false">// 参考答案2 #include &lt;bits/stdc++.h&gt; using namespace std; typedef pair&lt;int, int&gt; pii; int m, n; vector&lt;int&gt; a[105]; struct Plan {   pii ptr;   bool last; // 记录本方案是否是由ptr2++得到的   int sum;   Plan() {}   Plan(int i, int j, pii _ptr, bool _last) {     ptr = _ptr;     last = _last;     sum = a[i][ptr.first] + a[j][ptr.second];   }   bool operator&lt;(const Plan &amp;oth) const { return sum &gt; oth.sum; } } init; priority_queue&lt;Plan&gt; Q; int main() {   int T;   cin &gt;&gt; T;   while (T--) {     scanf("%d%d", &amp;m, &amp;n);     for (int i = 1; i &lt;= m; i++) {       a[i].clear();       for (int j = 1, x; j &lt;= n; j++) {         scanf("%d", &amp;x);         a[i].push_back(x);       }       sort(a[i].begin(), a[i].end());     }     int i = 1;     for (int j = 2; j &lt;= m; j++, i ^= 1) {       init = Plan(i, j, make_pair(0, 0), 0);       while (!Q.empty())         Q.pop();       Q.push(init);       a[i ^ 1].clear();       while (!Q.empty()) {         Plan now = Q.top();         Q.pop();         a[i ^ 1].push_back(now.sum);         if (a[i ^ 1].size() &gt;= n)           break;         if (!now.last &amp;&amp; now.ptr.first &lt; n - 1)           Q.push(Plan(i, j, make_pair(now.ptr.first + 1, now.ptr.second), 0));         if (now.ptr.second &lt; n - 1)           Q.push(Plan(i, j, make_pair(now.ptr.first, now.ptr.second + 1), 1));       }     }     for (int k = 0; k &lt; a[i].size(); k++)       printf("%d ", a[i][k]);     printf("\n");   } }</pre>
这道题暂未补解析。