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

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

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

一、简答题

1. 简答题

双端队列

定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。

时间限制:1000

内存限制:65535

输入

第一行输入一个整数t,代表测试数据的组数。 每组数据的第一行输入一个整数n,表示操作的次数。 接着输入n行,每行对应一个操作,首先输入一个整数type。

 当type=1,进队操作,接着输入一个整数x,表示进入队列的元素。

 当type=2,出队操作,接着输入一个整数c,c=0代表从队头出队,c=1代表从队尾出队。

n <= 1000

输出

对于每组测试数据,输出执行完所有的操作后队列中剩余的元素,元素之间用空格隔开,按队头到队尾的顺序输出,占一行。如果队列中已经没有任何的元素,输出NULL。

样例输入

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

样例输出

3
NULL
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//解法1 //用deque模拟一下即可 #include &lt;bits/stdc++.h&gt; using namespace std; string s; int main() { int n,m,type,x; cin&gt;&gt;n; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;m; deque&lt;int&gt; q; for(int j=1;j&lt;=m;j++){ cin&gt;&gt;type&gt;&gt;x; if(type==1){ q.push_back(x); }else { if(x==0)q.pop_front(); else q.pop_back(); } } if(q.empty()){ cout&lt;&lt;"NULL";continue; } while(!q.empty()){ cout&lt;&lt;q.front()&lt;&lt;" "; q.pop_front(); } cout&lt;&lt;endl; } return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2 #include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;cstring&gt; #include &lt;iomanip&gt; #include &lt;iostream&gt; #include &lt;map&gt; #include &lt;queue&gt; #include &lt;set&gt; #include &lt;stack&gt; #include &lt;vector&gt; using namespace std; int n, t, type, c; int a[1005] = {0}; int Top = 0, Back = 0; int main() {   cin &gt;&gt; t;   while (t--) {     Top = 0;     Back = 0;     cin &gt;&gt; n;     while (n--) {       cin &gt;&gt; type &gt;&gt; c;       if (type == 1) {         a[Back++] = c;       } else {         if (c == 0) {           Top++;         } else {           Back--;         }       }     }     if (Top == Back) {       cout &lt;&lt; "NULL" &lt;&lt; endl;     } else {       for (int i = Top; i &lt; Back; ++i) {         cout &lt;&lt; a[i] &lt;&lt; " ";       }       cout &lt;&lt; endl;     }   }   return 0; }</pre><p><br/></p>
这道题暂未补解析。
2. 简答题

区间合并

给定 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;algorithm&gt; #include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; using namespace std; int t, n, min1, max1; struct node {   int x, y; } a[101000]; int N; int cmp(const node &amp;w, const node &amp;e) {   if (w.x &gt; e.x)     return 0;   return 1; } bool f(int i) {   min1 = a[1].x;   if (i == t)     return 1;   if (a[i + 1].x &gt;= a[i].x &amp;&amp; a[i + 1].x &lt;= max1) {     max1 = max(max1, a[i + 1].y);     f(i + 1);   } else     return 0; } int main() {   int i = 1;   cin &gt;&gt; n;   t = n;   while (n--) {     cin &gt;&gt; a[i].x &gt;&gt; a[i].y;     i++;   }   sort(a + 1, a + t + 1, cmp);   max1 = a[1].y;   if (f(1))     printf("%d %d\n", min1, max1);   else     printf("no\n");   return 0; }</pre>
这道题暂未补解析。
3. 简答题

奇怪的括号

某天小A和同学在课堂上讨论到:“栈这种数据结构真是太优美了,既简单用途又广泛。”小B仰慕小A许久,于是他拿出了自己在网上抄写的一道题问小A,如何判断括号是否匹配呢

时间限制:1000

内存限制:65536

输入

多组数据,每组数据占一行,且都是由(、)、[、]、*、/这六种字符组成。

输出

每组数据输出一行,如果括号能匹配成功,输出True,否则输出False。括号匹配规则是: ( 和 ) 匹配 [ 和 ] 匹配 /* 和 */ 匹配 如果含有冗余字符也算匹配失败,例如 /***/ 是匹配失败的因为中间多了一个*。

样例输入

()/*[()]*/
*/**/

样例输出

True
False
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; string s; int main() {   while (cin &gt;&gt; s) {     stack&lt;char&gt; st;     for (int i = 0; i &lt; s.size(); i++) {       if (st.empty()) {         st.push(s[i]);       } else {         if (s[i] == ')' &amp;&amp; st.top() == '(')           st.pop();         else if (s[i] == ']' &amp;&amp; st.top() == '[')           st.pop();         else if (s[i] == '/' &amp;&amp; st.top() == '*' &amp;&amp; st.size() &gt;= 3) {           st.pop();           char a = st.top();           st.pop();           char b = st.top();           st.pop();           if (!(a == '*' &amp;&amp; b == '/')) {             st.push(b);             st.push(a);             st.push('*');           }         } else           st.push(s[i]);       }     }     if (st.empty())       cout &lt;&lt; "True" &lt;&lt; endl;     else       cout &lt;&lt; "False" &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。
4. 简答题

合法出栈序列

给定一个由不同小写字母构成的长度不超过8的字符串x,现在要将该字符串的字符依次压入栈中,然后再全部弹出。

要求左边的字符一定比右边的字符先入栈,出栈顺序无要求。

再给定若干字符串,对每个字符串,判断其是否是可能的x中的字符的出栈序列。

时间限制:1000

内存限制:65536

输入

第一行是原始字符串x 后面有若干行,每行一个字符串

输出

对除第一行以外的每个字符串,判断其是否是可能的出栈序列。如果是,输出"YES",否则,输出"NO"

样例输入

abc
abc
bca
cab

样例输出

YES
YES
NO
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; string a, b; int main() {   cin &gt;&gt; a;   while (cin &gt;&gt; b) {     stack&lt;char&gt; st;     int j = 0;     for (int i = 0; i &lt; a.size(); i++) {       if (!st.empty())         if (st.top() == b[j]) {           st.pop();           j++;         }       st.push(a[i]);     }     while (!st.empty() &amp;&amp; st.top() == b[j] &amp;&amp; j &lt; b.size()) {       st.pop();       j++;     }     if (st.empty())       cout &lt;&lt; "YES" &lt;&lt; endl;     else       cout &lt;&lt; "NO" &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。