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

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

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

一、简答题

1. 简答题

移动路线

桌子上有一个m行n列的方格矩阵,将每个方格用坐标表示,行坐标从下到上依次递增,列坐标从左至右依次递增,左下角方格的坐标为(1,1),则右上角方格的坐标为(m,n)。

小明是个调皮的孩子,一天他捉来一只蚂蚁,不小心把蚂蚁的右脚弄伤了,于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中,蚂蚁从左下角的方格中移动到右上角的方格中,每步移动一个方格。蚂蚁始终在方格矩阵内移动,请计算出不同的移动路线的数目。

对于1行1列的方格矩阵,蚂蚁原地移动,移动路线数为1;对于1行2列(或2行1列)的方格矩阵,蚂蚁只需一次向右(或向上)移动,移动路线数也为1……对于一个2行3列的方格矩阵,如下图所示:

-------------------

|(2,1)|(2,2)|(2,3)|

-------------------

|(1,1)|(1,2)|(1,3)|

-------------------

蚂蚁共有3种移动路线:

路线1:(1,1) → (1,2) → (1,3) → (2,3)

路线2:(1,1) → (1,2) → (2,2) → (2,3)

路线3:(1,1) → (2,1) → (2,2) → (2,3)

时间限制:1000

内存限制:65536

输入

输入只有一行,包括两个整数m和n(0<m+n<=20),代表方格矩阵的行数和列数,m、n之间用空格隔开

输出

输出只有一行,为不同的移动路线的数目。

样例输入

2 3

样例输出

3
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;iostream&gt; using namespace std; const int N = 40; const int dx[2] = {0, 1}; const int dy[2] = {1, 0}; int n, m, ans = 0; bool flag = false; struct node {   int x;   int y; } st[N * N], tu[N * N][N * N]; int a[N * N]; bool ran_out(int x, int y) { return x &lt; 1 || x &gt; n || y &lt; 1 || y &gt; m; } void fuzhi(int step) {   ans++;   a[ans] = step;   flag = true;   for (int i = 0; i &lt;= step; i++) {     tu[ans][i].x = st[i].x;     tu[ans][i].y = st[i].y;   } } void dfs(int x, int y, int step) {   st[step].x = x;   st[step].y = y;   if (x == n &amp;&amp; y == m) {     fuzhi(step);     return;   }   for (int i = 0; i &lt; 2; i++) {     int xx = x + dx[i];     int yy = y + dy[i];     if (!ran_out(xx, yy)) {       dfs(xx, yy, step + 1);     }   } } int main() {   std::ios::sync_with_stdio(false);   cin &gt;&gt; n &gt;&gt; m;   dfs(1, 1, 0);   printf("%d\n", ans);   for (int i = 1; i &lt;= ans; i++)     return 0; }</pre>
这道题暂未补解析。
2. 简答题

移动办公

假设你经营着一家公司,公司在北京和南京各有一个办公地点。公司只有你一个人,所以你只能每月选择在一个城市办公。在第i个月,如果你在北京办公,你能获得Pi的营业额,如果你在南京办公,你能获得Ni的营业额。但是,如果你某个月在一个城市办公,下个月在另一个城市办公,你需要支付M的交通费。那么,该怎样规划你的行程(可在任何一个城市开始),才能使得总收入(总营业额减去总交通费)最大?

时间限制:1000

内存限制:65536

输入

输入的第一行有两个整数T(1 <= T <= 100)和M(1 <= M <= 100),T代表总共的月数,M代表交通费。接下来的T行每行包括两个在1到100之间(包括1和100)的的整数,分别表示某个月在北京和在南京办公获得的营业额。

输出

输出只包括一行,这一行只包含一个整数,表示可以获得的最大总收入。

样例输入

4 3
10 9
2 8
9 5
8 2

样例输出

31
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;iostream&gt; #include &lt;string&gt; using namespace std; int main() {   int n; // ÔÂÊý   int m; // ½»Í¨·Ñ   int a, b;   cin &gt;&gt; n &gt;&gt; m;   int d[n][2];   for (int i = 0; i &lt; n; i++) {     cin &gt;&gt; d[i][0] &gt;&gt; d[i][1];   }   for (int i = n - 2; i &gt;= 0; i--) {     d[i][1] = d[i][1] + max(d[i + 1][0] - m, d[i + 1][1]);     d[i][0] = d[i][0] + max(d[i + 1][0], d[i + 1][1] - m);   }   cout &lt;&lt; max(d[0][0], d[0][1]); }</pre>
这道题暂未补解析。
3. 简答题

最长公共子上升序列

给定两个整数序列,写一个程序求它们的最长上升公共子序列。 当以下条件满足的时候,我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , AM 的上升子序列: 存在 1 <= i1 < i2 < . . . < iN <= M ,使得对所有 1 <= j <=N,均有Sj = Aij,且对于所有的1 <= j < N,均有Sj < Sj+1。

时间限制:10000

内存限制:65536

输入

每个序列用两行表示,第一行是长度M(1 <= M <= 500),第二行是该序列的M个整数Ai (-231 <= Ai < 231 )

输出

在第一行,输出两个序列的最长上升公共子序列的长度L。在第二行,输出该子序列。如果有不止一个符合条件的子序列,则输出任何一个即可。

样例输入

5
1 4 2 5 -12
4
-12 1 2 4

样例输出

2
1 4
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; #define N 505 int dp     [N]     [N]; // dp[i][j]:x前i个元素与y前j个元素构成的以x[i]为结尾的最长公共上升子序列的长度 int x[N], y[N]; vector&lt;int&gt; seq     [N]; // seq[i]:当j为某确定值时,x前i个元素与y前j个元素构成的以x[i]为结尾的最长公共上升子序列 int main() {   int xn, yn;   cin &gt;&gt; xn;   for (int i = 1; i &lt;= xn; ++i)     cin &gt;&gt; x[i];   cin &gt;&gt; yn;   for (int i = 1; i &lt;= yn; ++i)     cin &gt;&gt; y[i];   for (int j = 1; j &lt;= yn; ++j)     for (int i = 1; i &lt;= xn; ++i) {       if (x[i] == y[j]) {         dp[i][j] = 1;         seq[i] = vector&lt;int&gt;();         for (int k = 1; k &lt; i; ++k) {           if (x[k] &lt; x[i] &amp;&amp; dp[k][j - 1] + 1 &gt; dp[i][j]) {             dp[i][j] = dp[k][j - 1] + 1;             seq[i] = seq[k];           }         }         seq[i].push_back(x[i]);       } else         dp[i][j] = dp[i][j - 1];     }   int mxi = 1;   for (int i = 1; i &lt;= xn; i++) {     if (dp[i][yn] &gt; dp[mxi][yn])       mxi = i;   }   cout &lt;&lt; dp[mxi][yn] &lt;&lt; endl;   for (int i = 0; i &lt; seq[mxi].size(); ++i)     cout &lt;&lt; seq[mxi][i] &lt;&lt; ' ';   return 0; }</pre>
这道题暂未补解析。
4. 简答题

技能树

设二叉树中每个节点的子节点数为0或2,求有N个节点高度为M的不同的二叉树有多少个

(输出 mod 9901 后的结果)。

时间限制:10000

内存限制:131072

输入

两个空格分开的整数, N和K。

输出

第 1 行: 一个整数,表示可能的技能树的个数除以9901的余数。

样例输入

5 3

样例输出

2

提示

有5个节点,高为3的两个不同的技能树。约定:n在[3,300]间,m在(1,100)间

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; #define N 310 #define M 110 #define mod 9901 int f[M][N], sum[N][M]; int main() {   int n, m;   scanf("%d%d", &amp;n, &amp;m);   f[1][1] = sum[1][1] = 1;   for (int j = 2; j &lt;= n; j++)     f[1][j] = sum[1][j] = 0;   for (int i = 2; i &lt;= m; i++) {     for (int j = 1; j &lt;= n; j++) {       f[i][j] = 0;       for (int k = 1; k &lt; j; k++)         f[i][j] = (f[i][j] + (2 * f[i - 1][k] * sum[i - 1][j - k - 1] -                               f[i - 1][k] * f[i - 1][j - k - 1]) %                                  mod) %                   mod;       sum[i][j] = (sum[i - 1][j] + f[i][j]) % mod;     }   }   printf("%d\n", f[m][n]);   return 0; }</pre>
这道题暂未补解析。