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

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

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

一、简答题

1. 简答题

开餐馆

北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, … mn 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。

时间限制:1000

内存限制:65536

输入

标准的输入包含若干组测试数据。输入第一行是整数T (1 <= T <= 1000) ,表明有T组测试数据。紧接着有T组连续的测试。每组测试数据有3行, 第1行:地点总数 n (n < 100), 距离限制 k (k > 0 && k < 1000). 第2行:n 个地点的位置m1 , m2, … mn ( 1000000 > mi > 0 且为整数,升序排列) 第3行:n 个地点的餐馆利润p1 , p2, … pn ( 1000 > pi > 0 且为整数)

输出

对于每组测试数据可能的最大利润

样例输入

2
3 11
1 2 15
10 2 30
3 16
1 2 15
10 2 30

样例输出

40
30
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; int f[1010], a[1010], v[1010]; int main() {   int t, o, i, j, k, n, m, maxn;   cin &gt;&gt; t;   for (o = 1; o &lt;= t; o++) {     cin &gt;&gt; n &gt;&gt; k;     for (i = 1; i &lt;= n; i++)       cin &gt;&gt; a[i];     for (i = 1; i &lt;= n; i++)       cin &gt;&gt; v[i];     memset(f, 0, sizeof(f));     f[1] = v[1];     for (i = 2; i &lt;= n; i++) {       maxn = 0;       for (j = 1; j &lt; i; j++)         if (f[j] &gt; maxn &amp;&amp; a[i] - a[j] &gt; k)           maxn = f[j];       f[i] = v[i] + maxn;     }     maxn = 0;     for (i = 1; i &lt;= n; i++)       maxn = max(maxn, f[i]);     cout &lt;&lt; maxn &lt;&lt; endl;   }   return 0; }</pre><p><span><span></span></span></p><pre class="brush:cpp;toolbar:false">//C语言实现的代码: #include &lt;stdio.h&gt; #include &lt;stdbool.h&gt; int max(int a, int b) {     return (a &gt; b) ? a : b; } int maxProfit(int m[], int p[], int n, int k) {     int dp[100];     dp[0] = p[0];     for (int i = 1; i &lt; n; i++) {         dp[i] = p[i];         for (int j = i - 1; j &gt;= 0; j--) {             if (m[i] - m[j] &gt; k) {                 dp[i] = max(dp[i], dp[j] + p[i]);             }         }     }     int maxProfit = 0;     for (int i = 0; i &lt; n; i++) {         maxProfit = max(maxProfit, dp[i]);     }     return maxProfit; } int main() {     int T;     scanf("%d", &amp;T);     while (T--) {         int n, k;         scanf("%d %d", &amp;n, &amp;k);         int m[100];         int p[100];         for (int i = 0; i &lt; n; i++) {             scanf("%d", &amp;m[i]);         }         for (int i = 0; i &lt; n; i++) {             scanf("%d", &amp;p[i]);         }         int result = maxProfit(m, p, n, k);         printf("%d\n", result);     }     return 0; }</pre>
这道题暂未补解析。
2. 简答题

邮票收集

小A是个邮票收集爱好家,他有n种面值的邮票,每种邮票都有无数张。一天小B想要寄信,需要一共面值和为k的邮票组合。小A想要知道拼出面值为k的邮票最少需要多少张。

时间限制:1000

内存限制:131072

输入

输入是多组数据。(不超过10组) 每组数据的第一行正整数n,k,表示邮票的种类数目和目标要拼出的钱。(0 < n ≤ 100, 0 < k ≤ 1000 ) 接下来的一行有n个正整数ai(0 < ai ≤ 1000)。 若n=k=0表示输入结束。

输出

每组数据输出一行一个数,分别表示拼出k需要的最少的邮票数量。 如果不存在能够拼出k的方案,输出-1。


样例输入

4 10
1 2 3 4 
5 16
1 2 3 4 5 
2 7
4 5
0 0

样例输出

3
4
-1

提示

第一组数据: 10 = 4+4+2 第二组数据:16 = 5+5+5+1 第三组数据: 不存在。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; int a[1010], f[1010]; int main() {   int n, k, i, j;   cin &gt;&gt; n &gt;&gt; k;   while (n != 0 &amp;&amp; k != 0) {     for (i = 1; i &lt;= n; i++)       cin &gt;&gt; a[i];     for (i = 1; i &lt;= k; i++)       f[i] = 1000000000;     f[0] = 0;     for (i = 1; i &lt;= n; i++)       for (j = a[i]; j &lt;= k; j++)         f[j] = min(f[j], f[j - a[i]] + 1);     if (f[k] != 1000000000)       cout &lt;&lt; f[k] &lt;&lt; endl;     else       cout &lt;&lt; -1 &lt;&lt; endl;     cin &gt;&gt; n &gt;&gt; k;   }   return 0; }</pre>
这道题暂未补解析。
3. 简答题

带通配符的字符串匹配

 通配符是一类键盘字符,当我们不知道真正字符或者不想键入完整名字时,常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等,其中,“?”可以代替一个字符,而“*”可以代替零个或多个字符。

你的任务是,给出一个带有通配符的字符串和一个不带通配符的字符串,判断他们是否能够匹配。

例如,1?456 可以匹配 12456、13456、1a456,但是却不能够匹配23456、1aa456;

2*77?8可以匹配 24457798、237708、27798。

时间限制:1000

内存限制:65536

输入

输入有两行,每行为一个不超过20个字符的字符串,第一行带通配符,第二行不带通配符

输出

如果两者可以匹配,就输出“matched”,否则输出“not matched”


样例输入

1*456?
11111114567

样例输出

matched
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;string&gt; using namespace std; int f[3005][3005] = {0}, q[3005] = {0}, prt[3005][3005] = {0}; string st1, st2; int gcd(int a, int b) {   if (b == 0)     return a;   return gcd(b, a % b); } void Get(int x, int y) {   if (x == 0 &amp;&amp; y == 0)     return;   int lx = x - 1, ly = prt[x][y];   if (st1[x] == '*' &amp;&amp; y != ly) {     q[++q[0]] = y - ly;   }   Get(lx, ly); } int main() {   cin &gt;&gt; st1 &gt;&gt; st2;   int i, j, k, bj, div, ans = 0, len1 = st1.length(), len2 = st2.length();   st1 = ' ' + st1;   st2 = ' ' + st2;   f[0][0] = 1;   for (i = 1; i &lt;= len1; i++)     for (j = 0; j &lt;= len2; j++) {       if (st1[i] == '?' || st1[i] == st2[j]) {         f[i][j] = f[i - 1][j - 1];         if (f[i][j])           prt[i][j] = j - 1;       } else if (st1[i] == '*') {         for (k = j, bj = 0; k &gt;= 0; k--)           if (f[i - 1][k]) {             bj = 1;             break;           }         if (bj) {           f[i][j] = 1;           prt[i][j] = k;         }       }     }   if (f[len1][len2]) {     cout &lt;&lt; "matched\n";   } else     cout &lt;&lt; "not matched";   return 0; }</pre>
这道题暂未补解析。
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 个数在自己的位置上。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; struct node {   int data, lenth;   int next; } a[1010]; int main() {   int t, n, i, j, p, maxn, o;   cin &gt;&gt; t;   for (o = 1; o &lt;= t; o++) {     cin &gt;&gt; n;     for (i = 1; i &lt;= n; i++)       cin &gt;&gt; a[i].data;     a[n].lenth = 1;     a[n].next = 0;     for (i = n - 1; i &gt;= 1; i--) {       maxn = p = 0;       for (j = i + 1; j &lt;= n; j++)         if ((a[j].lenth &gt; maxn) &amp;&amp; (a[i].data &lt; a[j].data)) {           p = j;           maxn = a[j].lenth;         }       a[i].lenth = maxn + 1;       a[i].next = p;     }     maxn = j = 0;     for (i = 1; i &lt;= n; i++)       if (a[i].lenth &gt; maxn) {         maxn = a[i].lenth;         j = i;       }     cout &lt;&lt; maxn &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。