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

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

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

一、简答题

1. 简答题

走迷宫

一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。

时间限制:1000

内存限制:65536

输入

第一行是两个整数,R和C,代表迷宫的长和宽。(1<= R,C <= 40) 接下来是R行,每行C个字符,代表整个迷宫。 空地格子用'.'表示,有障碍物的格子用'#'表示。 迷宫左上角和右下角都是'.'。

输出

输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。

样例输入

5 5
..###
#....
#.#.#
#.#.#
#.#..

样例输出

9
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;bits/stdc++.h&gt; #include &lt;cstdio&gt; using namespace std; const int idata = 1000 + 5; char maps[idata][idata]; int judge[idata][idata]; int change[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int nx, ny; int x[idata], y[idata]; int Count[idata][idata]; int soux, souy; int exitx, exity; bool flag; int m, n; int main() {   int i, j;   int tail = 1, head = 0;   cin &gt;&gt; m &gt;&gt; n;   for (i = 1; i &lt;= m; i++) {     for (j = 1; j &lt;= n; j++) {       cin &gt;&gt; maps[i][j];       if (maps[i][j] == '#')         judge[i][j] = 1;     }   }   judge[1][1] = 1;   Count[1][1] = 1;   x[1] = 1, y[1] = 1;   while (head &lt; tail) {     head++;     for (i = 0; i &lt; 4; i++) {       nx = x[head] + change[i][0];       ny = y[head] + change[i][1];       if (nx &gt;= 1 &amp;&amp; nx &lt;= m &amp;&amp; ny &gt;= 1 &amp;&amp; ny &lt;= n &amp;&amp; !judge[nx][ny]) {         judge[nx][ny] = 1;         tail++;         x[tail] = nx;         y[tail] = ny;         Count[x[tail]][y[tail]] = Count[x[head]][y[head]] + 1;         if (nx == m &amp;&amp; ny == n) {           flag = 1;           break;         }       }     }     if (flag)       break;   }   cout &lt;&lt; Count[m][n] &lt;&lt; endl;   return 0; }</pre>
这道题暂未补解析。
2. 简答题

重建二叉树

给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历。

时间限制:1000

内存限制:65536

输入

输入可能有多组,以EOF结束。 每组输入包含两个字符串,分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。

输出

对于每组输入,用一行来输出它后序遍历结果。

样例输入

DBACEGF ABCDEFG
BCAD CBAD

样例输出

ACBFGED
CDAB
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;stdio.h&gt; #include &lt;string.h&gt; void bulid(int n, char s1[],            char s2[]) // n是树的节点数,s1是记录先序遍历,s2中序遍历 {   if (n &lt;= 0)     return; // 没有节点了,找到边界return   int p = strchr(s2, s1[0]) - s2;   // strchr(s2,s1[0])是s2的地址+s1[0]第一次出现的位置i。s2是s2的地址   // 所以p是 s1[0]第一次出现在s2中的位置   bulid(p, s1 + 1, s2);   // 数的节点数为s1[0]在s2中之前的所有节点。s1+1是把s1数组整体向前移动一位(s1[0]是以前的s1[1],s1[1]改为以前s1[2]...   // 以前s1[0]是根,现在不需要,所以删除。要它左子树的根节点   // s2不变(假设中序遍历中根节点的位置是a,那么后序遍历中0~a个点是树的左子树节点)   bulid(n - p - 1, s1 + p + 1, s2 + p + 1);   // 数的节点数为s1[0]在s2中之后的所有节点(因为数组从0开始,所以-1)   // 以前s1[0]是根,现在不需要,左子树也不需要,所以都删除。要它右子树的根节点   // s2+p+1(假设中序遍历中根节点的位置是a,a~n-2(数组从0开始)个点是树的右子树节点   // )   printf("%c", s1[0]); // 输出 } int main() {   char s1[10007], s2[10007]; // s1是树的前序遍历,s2是树的中序遍历   while (scanf("%s %s", s1, s2) != EOF) // 多组数据   {     bulid(strlen(s1), s1, s2);     printf("\n"); // 记得输出\n   }   return 0; } /* 先序遍历第一个节点一定是根节点。 中序遍历根节点左侧就是树的左子树,右侧就是树的右子树。 后序遍历最后一个节点一定是根节点,而假设中序序列里根节点位置是m,那么后序序列里0至m-1个节点是树的左子树节点,m至倒数第二个点是树的右子树节点。 */</pre>
这道题暂未补解析。
3. 简答题

快速堆猪

小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。

时间限制:1000

内存限制:65536

输入

有三种输入 1)push n n是整数(0<=0 <=20000),表示叠上一头重量是n斤的新猪 2)pop 表示将猪堆顶的猪赶走。如果猪堆没猪,就啥也不干 3)min 表示问现在猪堆里最轻的猪多重。如果猪堆没猪,就啥也不干 输入总数不超过100000条

输出

对每个min输入,输出答案。如果猪堆没猪,就啥也不干


样例输入

pop
min
push 5
push 2
push 3
min
push 4
min

样例输出

2
2
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; typedef long long LL; int h[2005]; int size_; void up(int u) {   while (u / 2 &amp;&amp; h[u / 2] &gt; h[u]) {     swap(h[u / 2], h[u]);     u /= 2;   } } void down(int u) {   int t = u;   if (u * 2 &lt;= size_ &amp;&amp; h[u * 2] &lt; h[u])     t = u * 2;   if (u * 2 + 1 &lt;= size_ &amp;&amp; h[u * 2 + 1] &lt; h[u])     t = u * 2 + 1;   if (u != t) {     swap(h[u], h[t]);     down(t);   } } int main() {   char t[10];   string s;   int n;   while (scanf("%s", t) != EOF) {     s = string(t);     if (s == "pop") {       if (size_ == 0)         continue;       h[1] = h[size_];       size_--;       down(1);     } else if (s == "min") {       if (size_ == 0)         continue;       cout &lt;&lt; h[1] &lt;&lt; endl;     } else if (s == "push") {       cin &gt;&gt; n;       size_++;       h[size_] = n;       up(size_);     }   }   return 0; }</pre>
这道题暂未补解析。
4. 简答题

表达式· 表达式树· 表达式求值

众所周知, 任何一个表达式, 都可以用一棵表达式树来表示。 例如,

表达式 a+b*c, 可以表示为如下的表达式树:

+

/ \

a *

/ \

 b c

现在, 给你一个中缀表达式, 这个中缀表达式用变量来表示(不含数字), 请你将这个中缀表达式用表达式二叉树的形式输出出来。

时间限制: 1000

内存限制: 65535

输入

输入分为三个部分。 第一部分为一行,即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量(a-z),也可能含有运算符(+、-、*、/、小括号),不含有数字,也不含有空格。 第二部分为一个整数n(n < 10),表示中缀表达式的变量数。 第三部分有n行,每行格式为C x,C为变量的字符,x为该变量的值。

输出

输出分为三个部分,第一个部分为该表达式的逆波兰式,即该表达式树的后根遍历结果。占一行。 第二部分为表达式树的显示,如样例输出所示。如果该二叉树是一棵满二叉树,则最底部的叶子结点,分别占据横坐标的第1、3、5、7……个位置(最左边的坐标是1),然后它们的父结点的横坐标,在两个子结点的中间。如果不是满二叉树,则没有结点的地方,用空格填充(但请略去所有的行末空格)。每一行父结点与子结点中隔开一行,用斜杠(/)与反斜杠(\)来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格,\出现的横坐标位置为父结点的横坐标偏右一格。也就是说,如果树高为m,则输出就有2m-1行。 第三部分为一个整数,表示将值代入变量之后,该中缀表达式的值。需要注意的一点是,除法代表整除运算,即舍弃小数点后的部分。同时,测试数据保证不会出现除以0的现象。


样例输入

a+b*c
3
a 2
b 7
c 5

样例输出

abc*+
   +
  / \
 a   *
    / \
    b c
37
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cmath&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;stack&gt; #include &lt;string&gt; #define OK 1 #define ERROR 0 #define MAXSIZE 50 using namespace std; struct number {   char ch;   int value; }; number a[10]; // 定义二叉树类型 typedef struct BiNode {   char date;   struct BiNode *lchild, *rchild; } BiNode; // 定义栈类型 typedef struct SqStack {   char *base;   char *top;   int stacksize; } SqStack; // 初始化栈 int InitStack(SqStack &amp;S) {   S.base = new char[MAXSIZE];   if (!S.base)     exit(ERROR);   S.top = S.base;   S.stacksize = MAXSIZE;   return OK; } // 出栈 char Pop(SqStack &amp;S) {   if (S.top == S.base)     return ERROR;   char e = *(--S.top);   return e; } // 入栈 int Push(SqStack &amp;S, char e) {   if (S.top - S.base == S.stacksize)     return ERROR;   *(S.top++) = e;   return OK; } // 将中缀表达式转化为后缀表达式 string Change(string str) {   // str为中缀表达式,str2为后缀表达式   string str2 = "";   char ch, e; // e用于保存栈中弹出的元素   SqStack S1; // S1用于存放操作符(为辅助栈),S用于存放后续表达式   InitStack(S1);   for (int i = 0; i &lt; str.size(); i++) {     ch = str[i];     if (ch &gt;= 'a' &amp;&amp; ch &lt;= 'z') {       str2 += ch;     }     if (ch == '(')       Push(S1, ch);     if (ch == ')') {       while (*(S1.top - 1) != '(') {         e = Pop(S1);         str2 += e;       }       Pop(S1); // 左括号出栈但不入S2栈中     }     // 遇到+或-时     // 栈空/栈顶为左括号:直接入栈     // 否则一直出栈,直到栈空/栈顶为左括号,再入栈     if (ch == '+' || ch == '-') {       while (*(S1.top - 1) != '(' &amp;&amp; S1.base != S1.top) {         e = Pop(S1);         str2 += e;       }       Push(S1, ch);     }     // 遇到*或/时     // 栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈     // 否则一直出栈,直到满足上述条件,再入栈     if (ch == '*' || ch == '/') {       while (S1.base != S1.top &amp;&amp; *(S1.top - 1) != '(' &amp;&amp;              *(S1.top - 1) != '-' &amp;&amp; *(S1.top - 1) != '+') {         e = Pop(S1);         str2 += e;       }       Push(S1, ch);     }   }   // 中缀表达式遍历完成,还需检查栈中是否有未输出字符   // 判断栈空,非空则直接出栈   while (S1.base != S1.top) {     e = Pop(S1);     if (e != '(')       str2 += e;   }   return str2; } struct BiNode *s[MAXSIZE]; // 定义栈,该栈用于存放树 int top = -1; // 建立二叉树 BiNode *CreatTree(string str) {   // str为后缀表达式   BiNode *T, *T2;   SqStack S;   BiNode *e1, *e2;   int i;   InitStack(S);   for (i = 0; i &lt; str.size() - 1; i++) {     if (str[i] &gt;= 'a' &amp;&amp; str[i] &lt;= 'z') {       T = new BiNode;       T-&gt;date = str[i];       T-&gt;lchild = T-&gt;rchild = NULL;       s[++top] = T;     } else {       T = new BiNode;       T-&gt;date = str[i];       e1 = s[top--];       e2 = s[top--];       T-&gt;lchild = e2;       T-&gt;rchild = e1;       s[++top] = T;     }   }   T = new BiNode;   T-&gt;date = str[i];   T-&gt;rchild = s[top--];   T-&gt;lchild = s[top--];   s[++top] = T;   T2 = new BiNode;   T2 = s[top];   return T2; } int Seek(char e, int n) {   for (int i = 0; i &lt; n; i++) {     if (a[i].ch == e)       return a[i].value;   } } int Count(string str, int n) {   // str为后缀表达式数组,n变量个数   int sum = 0;   stack&lt;int&gt; S;   int x, x1, x2;   for (int i = 0; i &lt; n; i++) {     cin &gt;&gt; a[i].ch &gt;&gt; a[i].value;   }   for (int i = 0; i &lt; str.size(); i++) {     if (str[i] &gt;= 'a' &amp;&amp; str[i] &lt;= 'z') {       x = Seek(str[i], n);       S.push(x);     } else {       x2 = S.top();       S.pop(); // 左操作数       x1 = S.top();       S.pop(); // 右操作数       switch (str[i]) {       case '+':         sum = x1 + x2;         break;       case '-':         sum = x1 - x2;         break;       case '*':         sum = x1 * x2;         break;       case '/':         sum = x1 / x2;         break;       }       S.push(sum);     }   }   sum = S.top();   return sum; } char arr[1000][1000]; // 打印二叉树 void PrintTree(int tag, BiNode *T, int x, int m, int y) {   arr[2 * tag - 1][(x + m) / 2] = T-&gt;date;   if (tag != 1) {     if (y == 1)       arr[2 * tag - 2][m] = '/';     else       arr[2 * tag - 2][x] = '\\';   }   if (T-&gt;lchild != NULL)     PrintTree(tag + 1, T-&gt;lchild, x, (x + m) / 2 - 1, 1);   if (T-&gt;rchild != NULL)     PrintTree(tag + 1, T-&gt;rchild, (x + m) / 2 + 1, m, 0); } // 计算二叉树的深度 int Depth(BiNode *T) {   int m, n;   if (T == NULL)     return 0;   else {     m = Depth(T-&gt;lchild);     n = Depth(T-&gt;rchild);     if (m &gt; n)       return (m + 1);     else       return (n + 1);   } } bool Judge(int i, int j, int n) {   for (int k = j + 1; k &lt;= n; k++) {     if (arr[i][k] != ' ')       return 1;   }   return 0; } int main() {   string str1; // 中序表达式   cin &gt;&gt; str1;   int n; // 变量个数   cin &gt;&gt; n;   string str2 = Change(str1); // str2为后序表达式   BiNode *T = CreatTree(str2);   int sum = Count(str2, n);   int dp = Depth(T);   cout &lt;&lt; str2 &lt;&lt; endl;   memset(arr, ' ', sizeof(arr));   PrintTree(1, T, 1, pow(2.0, dp) - 1, 0);   for (int i = 1; i &lt;= 2 * dp - 1; i++) {     for (int j = 1; j &lt;= pow(2.0, dp) - 1; j++) {       cout &lt;&lt; arr[i][j];       if (arr[i][j] != ' ') {         if (Judge(i, j, pow(2.0, dp) - 1))           continue;         else           break;       }     }     cout &lt;&lt; endl;   }   cout &lt;&lt; sum &lt;&lt; endl;   return 0; }</pre>
这道题暂未补解析。