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

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

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

一、简答题

1. 简答题

区间合并(2022-12-六级)

给定 n 个闭区间 [ai; bi],其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如,[1;2] 和 [2;3] 可以合并为 [1;3],[1;3] 和 [2;4] 可以合并为 [1;4],但是[1;2] 和 [3;4] 不可以合并。

我们的任务是判断这些区间是否可以最终合并为一个闭区间,如果可以,将这个闭区间输出,否则输出no。

时间限制:1000

内存限制:65536

输入

第一行为一个整数n,3 ≤ n ≤ 50000。表示输入区间的数量。 之后n行,在第i行上(1 ≤ i ≤ n),为两个整数 ai 和 bi ,整数之间用一个空格分隔,表示区间 [ai; bi](其中 1 ≤ ai ≤ bi ≤ 10000)。

输出

输出一行,如果这些区间最终可以合并为一个闭区间,输出这个闭区间的左右边界,用单个空格隔开;否则输出 no。

样例输入

5
5 6
1 5
10 10
6 9
8 10

样例输出

1 10
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; struct Nod {   int x, y;   friend bool operator&lt;(Nod a, Nod b) {     if (a.x != b.x)       return a.x &lt; b.x;     else       return a.y &lt; b.y;   } } node[50005]; int main() {   int n;   cin &gt;&gt; n;   for (int i = 0; i &lt; n; i++)     cin &gt;&gt; node[i].x &gt;&gt; node[i].y;   sort(node, node + n);   int lf = node[0].x;   int rt = node[0].y;   for (int i = 1; i &lt; n; i++) {     if (lf &lt;= node[i].x &amp;&amp; node[i].x &lt;= rt) {       rt = max(rt, node[i].y);     } else {       cout &lt;&lt; "no";       return 0;     }   }   cout &lt;&lt; lf &lt;&lt; " " &lt;&lt; rt;   return 0; }</pre>
这道题暂未补解析。
2. 简答题

电话号码(2022-12,六级)

给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如:

Emergency 911

Alice 97 625 999

Bob 91 12 54 26

在这个例子中,我们不可能拨通Bob的电话,因为Emergency的电话是它的前缀,当拨打Bob的电话时会先接通Emergency,所以这些电话号码不是一致的。

时间限制:1000

内存限制:65536

输入

第一行是一个整数t,1 ≤ t ≤ 40,表示测试数据的数目。 每个测试样例的第一行是一个整数n,1 ≤ n ≤ 10000,其后n行每行是一个不超过10位的电话号码。

输出

对于每个测试数据,如果是一致的输出“YES”,如果不是输出“NO”。

样例输入

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

样例输出

NO
YES
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5 + 10; struct Trie {   int c[10], s;   Trie() {     memset(c, 0, sizeof(c));     s = 0;   } } t[N]; int tot; void clear(int x) {   t[x].s = 0;   for (int i = 0; i &lt;= 9; i++)     if (t[x].c[i])       clear(t[x].c[i]), t[x].c[i] = 0; } char s[15]; bool bt(int x) {   int len = strlen(s + 1);   bool bk = false;   for (int i = 1; i &lt;= len; i++) {     int y = s[i] - '0';     if (!t[x].c[y])       t[x].c[y] = ++tot;     else if (i == len)       bk = true;     x = t[x].c[y];     if (t[x].s)       bk = true;   }   t[x].s++;   return bk; } int main() {   int T;   scanf("%d", &amp;T);   while (T--) {     bool bk = false;     clear(0);     tot = 0;     int n;     scanf("%d", &amp;n);     for (int i = 1; i &lt;= n; i++) {       scanf("%s", s + 1);       if (bk)         continue;       if (bt(0))         bk = true;     }     if (bk)       puts("NO");     else       puts("YES");   }   return 0; }</pre><p><span>  </span><br/></p>
这道题暂未补解析。
3. 简答题

扑克牌排序

假设这里有36张扑克牌,分别为A1~A9,B1~B9,C1~C9,D1~D9,其中A代表方片,B代表草花,C代表红桃,D代表黑桃,那么,设定如下的排序规则:

1.对于两张卡牌,X1Y1与X2Y2,X1与X2表示A~D,Y1与Y2表示1~9,如果X1与X2不同,那么依照D>C>B>A的方式进行排序

2.假如有X1与X2相同时,那么就比较Y1与Y2的大小。

例如,对于如下的四张牌,有如下的升序排序结果:

D3,C4,A4,C1

升序排序的结果为A4,C1,C4,D3

有人提出了如下的排序策略:

先建立9个队列,用于存放点数的大小,将卡牌依点数存放入各自的队列之中,然后再按队列1到队列9依次出队。

例如,对于上面的结果,依次进队后,结果如下:

队列1:C1;队列3:D3,队列4:C4,A4

将其依次出队后,结果为C1,D3,C4,A4

然后,再建立4个队列,用于存放花色。将卡牌依花色A~D存放入队列1~4中,然后再按队列1到队列4依次出队。

例如,对于上面刚刚出队的序列C1,D3,C4,A4,将其依次进队,结果如下:

队列1:A4;队列3:C1,C4;队列4:D3

将其依次出队后,结果为A4,C1,C4,D3,排序结束。

请根据上面的算法,编写一个用队列对扑克牌排序的程序,要求依照上面的排序规则,根据先花色后点数的方法进行排序。

时间限制:1000

内存限制:65536

输入

输入分为两行,第一行为一个整数n,表示一共有n张牌(1<=n<=100) 第二行用XY的形式表示每一张牌,其中X为A~D,Y为1~9

输出

输出三个部分 第一个部分为第一次进队出队的结果,用Queue1:...表示,共9行,结果用空格分隔,下同 第二部分为第二次进队出队的结果,用QueueA:...表示,共4行 第三部分为一行,即将卡牌排序后的结果(升序排序)

样例输入

8
D8 A6 C3 B8 C5 A1 B5 D3

样例输出

Queue1:A1
Queue2:
Queue3:C3 D3
Queue4:
Queue5:C5 B5
Queue6:A6
Queue7:
Queue8:D8 B8
Queue9:
QueueA:A1 A6
QueueB:B5 B8
QueueC:C3 C5
QueueD:D3 D8
A1 A6 B5 B8 C3 C5 D3 D8

提示

第二次入队出队时,可以复用第一次时9个队列中的4个。所以其实只需要开辟9个队列即可。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int main() {   int n;   string s;   queue&lt;string&gt; qn[9];   queue&lt;string&gt; color[4];   queue&lt;string&gt; qs;   cin &gt;&gt; n;   for (int i = 1; i &lt;= n; i++) {     cin &gt;&gt; s;     int t = s[1] - '0' - 1;     qn[t].push(s);   }   for (int i = 0; i &lt;= 8; i++) {     cout &lt;&lt; "Queue" &lt;&lt; i + 1 &lt;&lt; ":";     while (!qn[i].empty()) {       s = qn[i].front();       switch (s[0]) {       case 'A':         color[0].push(s);         break;       case 'B':         color[1].push(s);         break;       case 'C':         color[2].push(s);         break;       case 'D':         color[3].push(s);         break;       }       qn[i].pop();       cout &lt;&lt; s &lt;&lt; " ";     }     cout &lt;&lt; endl;   }   for (int i = 0; i &lt;= 3; i++) {     cout &lt;&lt; "Queue" &lt;&lt; (char)('A' + i) &lt;&lt; ":";     while (!color[i].empty()) {       s = color[i].front();       color[i].pop();       qs.push(s);       cout &lt;&lt; s &lt;&lt; " ";     }     cout &lt;&lt; endl;   }   while (!qs.empty()) {     cout &lt;&lt; qs.front() &lt;&lt; " ";     qs.pop();   }   return 0; }</pre>
这道题暂未补解析。
4. 简答题

现代艺术

在对二维艺术作品感到厌烦之后,伟大的艺术牛Picowso决定从事创作一项更为小众的艺术形式,一维画。

尽管目前她的画作可以用一个由颜色组成的长度为N(1~100000)的数组表示,但她的创作风格依然保持不变:从一张空白的矩形画布上,不断地画上一些矩形,在一维的情况下,这些矩形就只是一个区间。她用N种颜色,颜色编号为1~N进行创作,每种颜色只使用一次,之后使用的颜色可以完全的覆盖之前在相同位置上的颜色。

令Picowso感到十分沮丧的是,她的竞争对手Moonet似乎弄明白了如何复制她的这些一维画作,Moonet会画一些不相交的间隔,等待这些颜色晾干,然后再画另外的一些间隔,直到画完。Moonet每次每种颜色最多只能画一个间隔,但是他可以一次画不同颜色不相交的多个间隔,只要这些间隔没有重叠部分。之后Moonet再进行下一轮绘制。请计算Moonet为了复制一幅画需要画几个回合。

时间限制:10000

内存限制:65536

输入

第一行是一个整数N,之后N行包含了N个整数,范围0到N表示纸带每个格点的颜色,0表示没有涂色。

输出

输出一行,需要复制这幅画作的最少回合数,如果这幅画不可能是Picowso的画作输出-1(比如说这幅画不可能是通过一次在一条上画一层的方法进行创作的)

样例输入

7
0
1
4
5
1
3
3

样例输出

2

提示

在这个样例中,第一轮涂成0111133,第二轮涂成0145133,所以共需两轮。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int N = 100010; int end_pos[N], a[N]; int n, result, flag = 1; char v[N]; stack&lt;int&gt; s; int main() {   scanf("%d", &amp;n);   for (int i = 1; i &lt;= n; i += 1) {     scanf("%d", &amp;a[i]);     end_pos[a[i]] = i; // 记录每个颜色的终点位置   }   v[0] = 1; // 初始化 将0视为覆盖整个画布的第一种颜色   end_pos[0] = n + 1;   s.push(0);   for (int i = 1; i &lt;= n &amp;&amp; flag; i++) {     if (s.top() != a[i]) {       if (v[a[i]])         flag = 0;   // 颜色被使用过 标记非法       s.push(a[i]); // 加入新的颜色     }     v[a[i]] = 1; // 标记该颜色被使用过     result = max(result, (int)s.size());     if (i == end_pos[a[i]]) {       s.pop(); // 该颜色最后一次被使用 弹出改颜色     }   }   if (!flag)     cout &lt;&lt; -1;   else     cout &lt;&lt; result - 1;   return 0; }</pre>
这道题暂未补解析。