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

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

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

一、简答题

1. 简答题

漫漫回国路

2020年5月,国际航班机票难求。一位在美国华盛顿的中国留学生,因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况,求问他回不回得来(不考虑转机次数和机票价格)。

时间限制:1000

内存限制:65536

输入

第一行为case个数n(n < 10)。 每一个case,第一行为机场个数N,N ≤ 10。 之后的N行,每一行包含N个整数。第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)个整数代表从第i个机场出发到第j个机场的能买到的航班的最低票价t(0 < t < 10000)。如果不幸没有航班,那么用-1表示。第i行第i个整数为0。 起点华盛顿杜勒斯国际机场的编号为1,终点北京首都国际机场的编号为N。

输出

每一个case一行。 能够回国,输出字符串:YES。如果无法回国,输出字符串:NO

样例输入

2
3
0 100 -1
-1 0 200
-1 -1 0
4
0 1 5 -1
3 0 1 -1
2 4 0 -1
4 1 1 0

样例输出

YES
NO
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">// 广搜 #include &lt;bits/stdc++.h&gt; using namespace std; int a[12][12], n; bool v[12][12]; bool bfs(int p) {   queue&lt;int&gt; q;   q.push(p);   v[p][p] = true;   while (!q.empty()) {     int h = q.front();     q.pop();     for (int i = 1; i &lt;= n; i++) {       if (!v[h][i] &amp;&amp; a[h][i] &gt; 0) {         if (i == n)           return true;         else {           q.push(i);           v[h][i] = true;         }       }     }   }   return false; } int main() {   int k;   cin &gt;&gt; k;   while (k--) {     cin &gt;&gt; n;     for (int i = 1; i &lt;= n; i++)       for (int j = 1; j &lt;= n; j++)         cin &gt;&gt; a[i][j];     if (bfs(1))       cout &lt;&lt; "YES" &lt;&lt; endl;     else       cout &lt;&lt; "NO" &lt;&lt; endl;   }   return 0; }</pre><pre class="brush:cpp;toolbar:false">// 参考代码2 // 深度优先搜索 #include &lt;stdbool.h&gt; #include &lt;stdio.h&gt; #define MAX_N 10 #define INF 10000 int airports[MAX_N][MAX_N]; // 存储机场之间的航班票价 bool visited[MAX_N];        // 记录机场是否被访问过 int n;      // 机场个数 bool found; // 是否找到回国路径 void dfs(int start, int end) {   if (start == end) {     found = true; // 找到回国路径     return;   }   visited[start] = true;   for (int i = 1; i &lt;= n; i++) {     if (!visited[i] &amp;&amp; airports[start][i] != -1) {       dfs(i, end);     }   } } bool canReturn() {   found = false;   for (int i = 1; i &lt;= n; i++) {     visited[i] = false;   }   dfs(1, n);   return found; } int main() {   int cases;   scanf("%d", &amp;cases);   while (cases--) {     scanf("%d", &amp;n);     for (int i = 1; i &lt;= n; i++) {       for (int j = 1; j &lt;= n; j++) {         scanf("%d", &amp;airports[i][j]);       }     }     if (canReturn()) {       printf("YES\n");     } else {       printf("NO\n");     }   }   return 0; }</pre>
这道题暂未补解析。
2. 简答题

通配符匹配

给定一个字符串s和一个字符模式p,请实现一个支持'?'和'*'的通配符匹配功能。

其中‘?’可以匹配任何单个字符,如‘a?c’可以成功匹配‘aac’,‘abc’等字符串,但不可匹配‘ac’,‘aaac’等字符串 。

‘*’ 可以匹配任意长度字符串(包括空字符串),如‘a*c’可以成功匹配‘ac’,‘abdc’,‘abc’,‘aaac’等字符串,但不可匹配‘acb’,‘cac’等字符串。

两个字符串完全匹配才算匹配成功。

时间限制:2000

内存限制:262144

输入

输入为一个数字n表示测试字符串与字符模式对数,换行。(n ≤ 30) 后续2n行为每组匹配的s与p,每行字符串后换行。 s 非空,只包含从 a-z 的小写字母。 p 非空,只包含从 a-z 的小写字母,以及字符 ? 和 *。 字符串s和p的长度均小于50

输出

每一组匹配串匹配成功输出‘yes’,否则输出‘no’。

样例输入

3
abc
abc
abc
a*c
abc
a??c

样例输出

yes
yes
no
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;cstring&gt; using namespace std; bool isMatch(char* s, char* p) {     int m = strlen(s);     int n = strlen(p);     int i = 0; // s的指针     int j = 0; // p的指针     int star = -1; // 上一个星号的位置     int match = 0; // 上一个星号匹配到的位置     while (i &lt; m) {         if (j &lt; n &amp;&amp; (p[j] == '?' || s[i] == p[j])) { // '?'或者相等的情况             i++;             j++;         }         else if (j &lt; n &amp;&amp; p[j] == '*') { // '*'的情况             star = j; // 保存上一个星号的位置             match = i; // 保存当前匹配到的位置             j++; // p的指针向后移动一位         }         else if (star != -1) { // p中有星号,并且当前字符和p的字符不同,则回溯             j = star + 1; // p的指针回到上一个星号的下一位             match++; // 匹配位置向后移动一位             i = match; // s的指针回到上一个星号匹配到的位置的下一位         }         else { // 最后一种情况,匹配失败             return false;         }     }     while (j &lt; n &amp;&amp; p[j] == '*') { // 如果p中还有星号,则可以匹配空字符串         j++;     }     return j == n; // s和p都遍历完了才算匹配成功 } int main() {     int n; // 测试样例数     cin &gt;&gt; n;     char s[51]; // s的最大长度为50,再加上一个结束符'\0'     char p[51]; // p的最大长度为50,再加上一个结束符'\0'     for (int i = 0; i &lt; n; i++) {         cin &gt;&gt; s &gt;&gt; p;         if (isMatch(s, p)) {             cout &lt;&lt; "yes" &lt;&lt; endl;         }         else {             cout &lt;&lt; "no" &lt;&lt; endl;         }     }     return 0; }</pre>
这道题暂未补解析。
3. 简答题

求逆序对数

对于一个长度为N的整数序列A,满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序

请求出整数序列A的所有逆序对个数

时间限制:500

内存限制:65536

输入

输入包含多组测试数据,每组测试数据有两行 第一行为整数N(1 <= N <= 20000),当输入0时结束 第二行为N个整数,表示长为N的整数序列

输出

每组数据对应一行,输出逆序对的个数

样例输入

5
1 2 3 4 5
5
5 4 3 2 1
1
1
0

样例输出

0
10
0
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 20005; int merge(int a[], int s, int m, int e) {   vector&lt;int&gt; a1;   int m1 = s, m2 = m + 1, c = 0;   while (m1 &lt;= m &amp;&amp; m2 &lt;= e) {     if (a[m1] &gt; a[m2]) {       c += m - m1 + 1;       a1.push_back(a[m2]);       m2++;     } else {       a1.push_back(a[m1]);       m1++;     }   }   while (m1 &lt;= m) {     a1.push_back(a[m1]);     m1++;   }   while (m2 &lt;= e) {     a1.push_back(a[m2]);     m2++;   }   int k = 0;   for (int i = s; i &lt;= e; i++)     a[i] = a1[k++];   return c; } int solve(int a[], int s, int e) {   if (s &gt;= e)     return 0;   int m = (s + e) / 2;   int l = solve(a, s, m);   int r = solve(a, m + 1, e);   int l_r = merge(a, s, m, e);   return l + r + l_r; } int main() {   int n;   int a[N];   while (scanf("%d", &amp;n) &amp;&amp; n != 0) {     for (int i = 0; i &lt; n; i++)       scanf("%d", &amp;a[i]);     int sum = solve(a, 0, n - 1);     cout &lt;&lt; sum &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。
4. 简答题

分成互质组

给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?

时间限制:1000

内存限制:65536

输入

第一行是一个正整数n。1 <= n <= 10。 第二行是n个不大于10000的正整数。

输出

一个正整数,即最少需要的组数。

样例输入

6
14 20 33 117 143 175

样例输出

3
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false;">// 参考答案1: #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int N = 15; int n, cnt, ans = N, p[N]; vector&lt;int&gt; s[N]; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } bool check(int k, int x) {   for (int i = 0; i &lt; s[k].size(); i++)     if (gcd(s[k][i], x) &gt; 1)       return false;   return true; } void dfs(int u) {   if (u == n) {     ans = min(ans, cnt);     return;   }   for (int i = 0; i &lt; cnt; i++)     if (check(i, p[u])) {       s[i].push_back(p[u]);       dfs(u + 1);       s[i].pop_back();     }   s[cnt++].push_back(p[u]);   dfs(u + 1);   s[--cnt].pop_back(); } int main() {   cin &gt;&gt; n;   for (int i = 0; i &lt; n; i++)     cin &gt;&gt; p[i];   dfs(0);   cout &lt;&lt; ans &lt;&lt; endl;   return 0; }</pre><p><span>  </span><br/></p><pre class="brush:cpp;toolbar:false">// 参考答案2: #include &lt;iostream&gt; using namespace std; const int N = 15; int n; int p[N]; int group[N][N]; bool used[N]; int ans = N; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } bool check(int group[], int k, int x) {   for (int i = 0; i &lt; k; i++)     if (gcd(p[group[i]], x) &gt; 1)       return false;   return true; } void dfs(int g, int gc, int cnt, int start) {   if (g &gt;= ans)     return;   if (cnt == n)     ans = g;   bool flag = false;   for (int i = start; i &lt; n; i++)     if (!used[i] &amp;&amp; check(group[g], gc, p[i])) {       used[i] = true;       group[g][gc] = i;       dfs(g, gc + 1, cnt + 1, i + 1);       used[i] = false;       flag = true;     }   if (!flag)     dfs(g + 1, 0, cnt, 0); } int main() {   cin &gt;&gt; n;   for (int i = 0; i &lt; n; i++)     cin &gt;&gt; p[i];   dfs(1, 0, 0, 0);   cout &lt;&lt; ans &lt;&lt; endl;   return 0; }</pre><p><br/><span></span></p>
这道题暂未补解析。