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

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

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

一、简答题

1. 简答题

最长上升子序列

一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN),我们可以得到一些上升的子序列(ai1, ai2, …, aiK),这里1 <= i1 < i2 < … < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8). 你的任务,就是对于给定的序列,求出最长上升子序列的长度。

时间限制:11000

内存限制:65536

输入

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。

输出

最长上升子序列的长度。

样例输入

7
1 7 3 5 9 4 8

样例输出

4
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; #define fio                                                                    \   ios::sync_with_stdio(0);                                                     \   cin.tie(0);                                                                  \   cout.tie(0); using namespace std; const int maxn = 1010; int a[maxn]; int maxLen[maxn]; int main() {   fio int n;   cin &gt;&gt; n;   for (int i = 1; i &lt;= n; i++) {     cin &gt;&gt; a[i];     maxLen[i] = 1;   }   for (int i = 2; i &lt;= n; i++) {     for (int j = 1; j &lt; i; j++) {       if (a[i] &gt; a[j]) {         maxLen[i] = max(maxLen[i], maxLen[j] + 1);       }     }   }   cout &lt;&lt; *max_element(maxLen + 1, maxLen + n + 1) &lt;&lt; endl; }</pre>
这道题暂未补解析。
2. 简答题

神奇的口袋

有一个神奇的口袋,总的容积是40,用这个口袋可以变出一些物品,这些物品的总体积必须是40。John现在有n个想要得到的物品,每个物品的体积分别是a1,a2……an。John可以从这些物品中选择一些,如果选出的物体的总体积是40,那么利用这个神奇的口袋,John就可以得到这些物品。现在的问题是,John有多少种不同的选择物品的方式。

时间限制:10000

内存限制:65536

输入

输入的第一行是正整数n (1 <= n <= 20),表示不同的物品的数目。接下来的n行,每行有一个1到40之间的正整数,分别给出a1,a2……an的值。

输出

输出不同的选择物品的方式的数目。

样例输入

3
20
20
20

样例输出

3
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int goods[30]; // 从前k种物品中选择一些,凑成体积w的做法数目 int ways(int w, int k) {   if (w == 0)     return 1; // 没有需要凑的体积了,刚好凑满   if (k &lt;= 0)     return 0; // 还差体积或者体积过了,但是没有物品可以选了。   if (w &gt;= goods[k]) {     return ways(w, k - 1) +            ways(w - goods[k], k - 1); // 体积:选择第k种物品 + 不选第k种物品   } else {     return ways(w, k - 1);   } } int main() {   int n;   scanf("%d", &amp;n);   for (int i = 1; i &lt;= n; i++) {     scanf("%d", &amp;goods[i]);   }   printf("%d", ways(40, n));   return 0; }</pre>
这道题暂未补解析。
3. 简答题

滑雪

Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上,这是最长的一条。

时间限制:1000

内存限制:65536

输入

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。

输出

输出最长区域的长度。

样例输入

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出

25
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;iostream&gt; using namespace std; int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}; // 控制方向的常用方法 int n, m, a[205][205], s[205][205], ans; int dfs(int x, int y) {   if (s[x][y])     return s[x][y];   s[x][y] = 1; // 自身算一个距离   for (int i = 0; i &lt; 4; i++) {     int tx = dx[i] + x, ty = dy[i] + y;     if (tx &gt; 0 &amp;&amp; tx &lt;= n &amp;&amp; ty &gt;= 1 &amp;&amp; ty &lt;= m &amp;&amp; a[x][y] &gt; a[tx][ty]) {       dfs(tx, ty);       s[x][y] = max(s[x][y], s[tx][ty] + 1);       // 记忆化     }   }   return s[x][y]; } int main() {   scanf("%d%d", &amp;n, &amp;m);   for (int i = 1; i &lt;= n; i++)     for (int j = 1; j &lt;= m; j++)       scanf("%d", &amp;a[i][j]);   for (int i = 1; i &lt;= n; i++)     for (int j = 1; j &lt;= m; j++)       ans = max(ans, dfs(i, j)); // 将每个点当成起点做dfs   printf("%d", ans);   return 0; }</pre>
解析:

解题思路

采用递推的动态规划方式求解

先用结构体保存每个点对应的原本坐标位置和高度;

将所有点按高度从小到大排序;

用一个二维数组保存输入的原本数据,

再用一个二维数组保存对应位置的最大滑行距离;

从第二个点开始求解(因为第一个点高度最低,显然滑行距离为1)

依次和它在原本坐标里的上下左右四个方向进行判断,

如果它比某一方向上的高度高,则它的滑行距离就应该是相比较的最大滑行距离+1和它保存的最大滑行距离中的最大值。

最后求完总共的点,进行遍历,得到最终最大值。

4. 简答题

删除数字

娇娇一年级了,刚刚学会了识数和比大小。有一天,她在黑板上写上了一串数字:2,1,2,5,4。接着她擦掉了第一个2,发现剩下1,2,4都在自己的位置上,即:1在第1位,2在第2位,4在第4位。

娇娇希望擦掉某些数后,剩下的数列中在自己位置上的数尽量多。她发现这个问题很有趣,想知道最多能有几个数在自己的位置上,请你帮帮她!

时间限制:1000

内存限制:65536

输入

第一行,一个整数 TestNum( ≤ 10),表示测试数据的组数。 接下来每组数据有两行,第一行:一个整数n( ≤ 1000),第二行:n个正整数(≤ 1000)。

输出

对于每组测试数据,输出一个数表示答案。

样例输入

3
5
2 1 2 5 4
7
2 2 3 2 4 5 3
10
1 1 2 2 3 3 4 4 5 5

样例输出

3
4
5

提示

第一组测试数据:擦掉第一个数,1 2 4 有 3 个数在自己的位置上。

第二组测试数据:擦掉第4个、第7个数,2 3 4 5 有 4 个数在自己的位置上。

第三组测试数据:每种相同的数擦掉一个,1 2 3 4 5 有 5 个数在自己的位置上。

查看答案与解析
答案:<p> #include &lt;bits/stdc++.h&gt; </p> <p> using namespace std; </p> <p> int d[1010][1010]; //全局变量,默认为0,避免数组过大崩溃  </p> <p> //d[i][j]表示1到i中删除j个数满足条件的最大个数  </p> <p> int main() </p> <p> { </p> <p> <span> </span>int i,j,n,a[1010];  </p> <p> <span> </span>int f=0; //初始化标记为0 </p> <p> <span> </span>cin&gt;&gt;n; </p> <p> <span> </span>for(i=1;i&lt;=n;i++){ </p> <p> <span> </span>cin&gt;&gt;a[i]; </p> <p> <span> </span>} </p> <p> <span> </span>for(i=1;i&lt;=n;i++){ </p> <p>         d[i][0]=d[i-1][0]; //未删除  </p> <p>         if(a[i]==i){ //统计初始时满足条件个数  </p> <p>         <span> </span>d[i][0]++; </p> <p>         } </p> <p>     } </p> <p> <span> </span>for(i=1;i&lt;=n;i++){ </p> <p> <span> </span>for(j=0;j&lt;=i;j++){ </p> <p>   <span> </span>if(a[i]==i-j){ //删除数之后的位置满足条件  </p> <p>                 d[i][j]=max(d[i-1][j-1],d[i-1][j]+1); </p> <p>             } </p> <p>             else{ //前i个数删除j个,考虑第i个数删和不删的情况  </p> <p> <span> </span>d[i][j]=max(d[i-1][j-1],d[i-1][j]); </p> <p> <span> </span>} </p> <p> <span> </span>} </p> <p> <span> </span>} </p> <p> <span> </span>for(int i=0;i&lt;=n;i++){ </p> <p>     <span> </span>f=max(f,d[n][i]); //找出最大值  </p> <p>     } </p> <p> <span> </span>cout&lt;&lt;f;<span> </span> </p> <p> <span> </span>return 0; </p> <p> } </p> <p> <a href="http://oj.scratchor.com/problem/CD202209_4_4 " target="_blank">&gt;&gt;试试在线提交?季卡以上会员请联系客服,<span><strong>免费</strong></span>开通OJ账号</a> </p>
解析:

解题思路

d[i][j]表示1到i中删除j个数满足条件的最大个数,

d[i][j]的前一种情况可能是d[i-1][j-1]和d[i-1][j],若第i个数删除,则为d[i][j]=d[i-1][j-1],

若第i个数不删,则d[i][j]=d[i-1][j],

考虑当a[i]==i-j时,若第i个数不删,则符合位置条件的数增加一个,所以比较d[i-1][j-1]和d[i-1][j]+1。