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

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

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

一、简答题

1. 简答题

电话号码

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

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;iostream&gt; #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; using namespace std; int t; int n; int FLAG; // FLAG=1代表互不构成后缀,FLAG=0代表摸一个单词构成后缀 struct Node {   struct Node *next[10]; // 定义一个指针数组next,里面的元素都是Node类型的指针   int is_Cover; // 定义这个节点的访问次数   int is_End; // 定义这个节点是否是一个电话号的最后一个字符 }; void Init(Node *a) // 初始化节点i {   memset(a-&gt;next, 0, sizeof(a-&gt;next)); // next[0]~next[9]都是指针NULL   a-&gt;is_Cover = 0;   a-&gt;is_End = 0; } // 内存友好型函数:释放内存 void DELETE(Node *root) {   for (int i = 0; i &lt; 10; i++) {     if (root-&gt;next[i]) {       DELETE(root-&gt;next[i]);     } // 递归法释放内存   }   free(root); // 递归到底层,root-&gt;next[0~9]都是NULL,直接释放root即可 } void insert(Node *root, char *temp) {   Node *p = root;   int id;       // 0~9   while (*temp) // 字符串指针未到底   {     id = *temp - '0';     if (p-&gt;next[id] == NULL) {       p-&gt;next[id] = (Node *)malloc(sizeof(Node)); // 先申请内存空间       Init(p-&gt;next[id]); // 再对这个节点进行初始化     }     p = p-&gt;next[id]; // 指针往下移动     if (p-&gt;is_End) {       FLAG = 0;     } // 这个点是其他电话号的最后一个数字,包含着其他单词的前缀     p-&gt;is_Cover++;     temp++; // 字符指针向下移动   }   if (p-&gt;is_Cover &gt; 1) {     FLAG = 0;   } // 执行到这里说明temp字符串是其他长字符串的前缀,temp字符串较短   p-&gt;is_End = 1; // 设置字符串末尾标志 } int main() {   char ss[15];   cin &gt;&gt; t;   while (t--) {     Node *root = (Node *)malloc(sizeof(Node));     Init(root);     FLAG = 1; // 没有特殊情况不构成后缀     cin &gt;&gt; n;     while (n--) {       scanf("%s", ss);       if (FLAG) {         insert(root, ss);       } // 前面都没有前缀的发生,可以继续插入     }     if (FLAG == 0) {       cout &lt;&lt; "NO" &lt;&lt; endl;     } else {       cout &lt;&lt; "YES" &lt;&lt; endl;     }     DELETE(root); // 释放内存   }   return 0; }</pre>
这道题暂未补解析。
2. 简答题

字符串插入

有两个字符串str和substr,str的字符个数不超过10,substr的字符个数为3。(字符个数不包括字符串结尾处的'\0'。)将substr插入到str中ASCII码最大的那个字符后面,若有多个最大则只考虑第一个。

时间限制:1000

内存限制:65536

输入

输入包括若干行,每一行为一组测试数据,格式为 str substr

输出

对于每一组测试数据,输出插入之后的字符串。

样例输入

abcab eee
12343 555

样例输出

abceeeab
12345553
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; using namespace std; typedef char ElemType; const int M = 14; typedef struct {   ElemType data[M];   int length; } SqList; void lnitList(SqList &amp;L) { L.length = 0; } void f(SqList &amp;s1, SqList s2) {   ElemType maxc = s1.data[0];   int index = 0;   int j = 0;   for (int i = 0; i &lt; s1.length; i++) {     if (maxc &lt; s1.data[i]) {       index = i;       maxc = s1.data[i];     }   }   s1.data[s1.length] = 0;   s1.data[s1.length + 3] = '\0';   for (int i = s1.length; i &gt; index; i--) {     s1.data[i + 3] = s1.data[i];   }   for (int i = index + 1; i &lt;= index + 3; i++) {     s1.data[i] = s2.data[j++];   }   s1.length += 3; } int main() {   SqList s1, s2;   while (cin &gt;&gt; s1.data &gt;&gt; s2.data) {     lnitList(s1);     lnitList(s2);     s1.length = strlen(s1.data);     s2.length = strlen(s2.data);     f(s1, s2);     cout &lt;&lt; s1.data &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。
3. 简答题

栈基本操作

依次读入序列元素1,2,...,n进栈,每进一个元素,机器可要求下一个元素进栈或弹栈,如此进行。给定一个输入序列,判断栈空时弹出的元素构成的序列是否可能等于给定的序列,如果是则输出栈的操作过程,否则输出“NO”。

时间限制:1000

内存限制:65535

输入

输入分两行 第一行为n的值(即序列元素个数) 第二行为给定的输入序列(序列元素均为整型)

输出

如果输入序列能够由题目规定的操作得到,则输出对栈的操作过程 否则直接输出“NO”

样例输入

7
4 5 3 6 2 7 1

样例输出

PUSH 1
PUSH 2
PUSH 3
PUSH 4
POP 4
PUSH 5
POP 5
POP 3
PUSH 6
POP 6
POP 2
PUSH 7
POP 7
POP 1

提示

给定序列中有可能有不在1...n之间的数字

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; const int MAXL = 100010; vector&lt;int&gt; v; int n; int visited[MAXL]; bool isLegal() {   stack&lt;int&gt; sk;   int idx = 1;   int k = 0;   while (idx &lt;= n) {     sk.push(idx++);     while (!sk.empty() &amp;&amp; sk.top() == v[k]) {       sk.pop();       k++;     }   }   return sk.empty() &amp;&amp; k == n; } int main() {   // 数据的输入和非法输入判断   cin &gt;&gt; n;   for (int i = 0; i &lt; n; i++) {     int tmp;     cin &gt;&gt; tmp;     if (visited[tmp] || tmp &lt;= 0 || tmp &gt; n) {       cout &lt;&lt; "NO" &lt;&lt; endl;       system("pause");       return 0;     }     v.push_back(tmp);     visited[tmp] = 1;   }   // 判断是否合法   if (!isLegal()) {     cout &lt;&lt; "NO" &lt;&lt; endl;     system("pause");     return 0;   }   // 模拟栈   stack&lt;int&gt; sk;   int i = 0;      // i是出栈的指针   int j = 1;      // j是入栈的指针   while (i &lt; n) { // 最后一个操作是出栈     if (!sk.empty() &amp;&amp; sk.top() == v[i]) {       cout &lt;&lt; "POP " &lt;&lt; v[i] &lt;&lt; endl;       sk.pop();       i++;     } else {       cout &lt;&lt; "PUSH " &lt;&lt; j &lt;&lt; endl;       sk.push(j);       j++;     }   }   system("pause"); }</pre>
这道题暂未补解析。
4. 简答题

滑动窗口

给定一个长度为n(n<=10^6)的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。

下面是一个例子:

数组是 [1 3 -1 -3 5 3 6 7], k = 3。

窗口位置 最小值 最大值

[1  3  -1] -3  5  3  6  7 -1 3

 1 [3  -1  -3] 5  3  6  7 -3 3

 1  3 [-1  -3  5] 3  6  7 -3 5

 1  3  -1 [-3  5  3] 6  7 -3 5

 1  3  -1  -3 [5  3  6] 7 3 6

 1  3  -1  -3  5 [3  6  7] 3 7

你的任务是得到滑动窗口在每个位置时的最大值和最小值。

时间限制:20000

内存限制:65536

输入

输入包括两行。 第一行包括n和k,分别表示数组的长度和窗口的大小。 第二行包括n个数字。

输出

输出包括两行。 第一行包括窗口从左至右移动的每个位置的最小值。 第二行包括窗口从左至右移动的每个位置的最大值。

样例输入

8 3
1 3 -1 -3 5 3 6 7

样例输出

-1 -3 -3 -3 3 3
3 3 5 5 6 7
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; typedef long long ll; const int N = 1e6 + 10; int a[N], q[N]; int n, k; int main() {   cin &gt;&gt; n &gt;&gt; k;   for (int i = 1; i &lt;= n; i++) {     cin &gt;&gt; a[i];   }   // 最小值队列  建立单调递增队列   int h = 0, t = -1;   for (int i = 1; i &lt;= n; i++) {     if (t &gt;= h &amp;&amp; q[h] &lt; i - k + 1)       h++;     while (t &gt;= h &amp;&amp; a[i] &lt;= a[q[t]])       t--;     q[++t] = i;     if (i &gt;= k)       printf("%d ", a[q[h]]);   }   printf("\n");   // 最大值队列  建立单调递减队列   h = 0, t = -1;   for (int i = 1; i &lt;= n; i++) {     // 队列中有元素且队头元素不在窗口[i-m+1,i]内,队头出队     if (h &lt;= t &amp;&amp; q[h] &lt; i - k + 1)       h++;     // 队列中有元素且当前值&gt;=队尾值,队尾出队     while (h &lt;= t &amp;&amp; a[i] &gt;= a[q[t]])       t--;     // 下标入队,便于队头出队     q[++t] = i;     // 使用队头最大值     if (i &gt;= k)       printf("%d ", a[q[h]]);   }   return 0; }</pre>
这道题暂未补解析。