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

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

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

一、简答题

1. 简答题

生日相同 2.0

在一个有180人的大班级中,存在两个人生日相同的概率非常大,现给出每个学生的名字,出生月日。试找出所有生日相同的学生。

时间限制:1000

内存限制:65536

输入

第一行为整数n,表示有n个学生,n ≤ 180。此后每行包含一个字符串和两个整数,分别表示学生的名字(名字第一个字母大写,其余小写,不含空格,且长度小于20)和出生月(1 ≤ m ≤ 12)日(1 ≤ d ≤ 31)。名字、月、日之间用一个空格分隔

输出

每组生日相同的学生,输出一行,其中前两个数字表示月和日,后面跟着所有在当天出生的学生的名字,数字、名字之间都用一个空格分隔。对所有的输出,要求按日期从前到后的顺序输出。 对生日相同的名字,按名字从短到长按序输出,长度相同的按字典序输出。如没有生日相同的学生,输出”None”

样例输入

6
Avril 3 2
Candy 4 5
Tim 3 2
Sufia 4 5
Lagrange 4 5
Bill 3 2

样例输出

3 2 Tim Bill Avril
4 5 Candy Sufia Lagrange
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; struct student {   char name[21];   int m;   int d; }; int comp(const student &amp;a, const student &amp;b) {   if (a.m &lt; b.m)     return 1;   if (a.m &gt; b.m)     return 0;   if (a.d &lt; b.d)     return 1;   if (a.d &gt; b.d)     return 0;   if (strlen(a.name) &lt; strlen(b.name))     return 1;   if (strlen(a.name) &gt; strlen(b.name))     return 0;   if (strcmp(a.name, b.name) &lt; 0)     return 1;   if (strcmp(a.name, b.name) &gt; 0)     return 0;   return 0; } int main() {   int b[13][32] = {0};   int n;   bool bl = false;   student a[181];   scanf("%d", &amp;n);   for (int i = 1; i &lt;= n; ++i) {     scanf("%s%d%d", &amp;a[i].name, &amp;a[i].m, &amp;a[i].d);   }   sort(a + 1, a + n + 1, comp);   for (int i = 1; i &lt;= n; ++i) {     b[a[i].m][a[i].d]++;   }   for (int i = 1; i &lt;= 12; ++i) {     for (int k = 1; k &lt;= 31; ++k) {       if (b[i][k] &gt; 1) {         printf("%d %d ", i, k);         for (int j = 1; j &lt;= n; ++j) {           if (a[j].m == i &amp;&amp; a[j].d == k)             printf("%s ", a[j].name);         }         printf("\n");         bl = true;       }     }   }   if (bl == false)     printf("None");   return 0; }</pre>
这道题暂未补解析。
2. 简答题

机器翻译

VariantF的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。

假设内存中有M 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过M,软件会将新单词存入一个未使用的内存单元;若内存中已存入M 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。

假设一篇英语文章的长度为N 个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。

时间限制:1000

内存限制:262144

输入

第一行为两个正整数M 和N,代表内存容量和文章的长度。 第二行为N 个非负整数,按照文章的顺序,每个数(大小不超过1000000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。 对于50%的数据,1<=N、M<=1000; 对于100%的数据,1<=N、M<=1000000。

输出

一个整数,为软件需要查词典的次数。

样例输入

3 7 
1 2 1 5 4 4 1

样例输出

5

提示

整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况: 空:内存初始状态为空。 1. 1:查找单词1 并调入内存。 2. 1 2:查找单词2 并调入内存。 3. 1 2:在内存中找到单词1。 4. 1 2 5:查找单词5 并调入内存。 5. 2 5 4:查找单词4 并调入内存替代单词1。 6. 2 5 4:在内存中找到单词4。 7. 5 4 1:查找单词1 并调入内存替代单词2。 共计查了5 次词典。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; int word[2000]; bool sch(int tgt, int range) // 线性搜索,因为数据&lt;1000,不会超时。 {   for (int i = 0; i &lt; range; i++) {     if (word[i] == tgt) {       return true;     }   }   return false; } int main() {   int mem, num, tm, wor, ans = 0;   scanf("%d %d", &amp;mem, &amp;num);   tm = 0;   for (int i = 0; i &lt; 2000; i++) {     word[i] = -1; // 数组初始化一定要初始化成-1!!!!     // 字母代号有可能是0,所以初始化成0会出错!!!!   }   for (int i = 0; i &lt; num; i++) {     scanf("%d", &amp;wor);     // 非常节省空间和时间的模拟     if (tm &gt;= mem) {       tm = 0;     }     if (!sch(wor, mem)) {       // 自己进行轮回。。。       ans++;       word[tm] = wor;       tm++;     }   }   printf("%d", ans); }</pre>
这道题暂未补解析。
3. 简答题

括号画家

Candela是一名漫画家,她有一个奇特的爱好,就是在纸上画括号。这一天,刚刚起床的Candela画了一排括号序列,其中包含小括号()、中括号[]和大括号{},总长度为N。这排随意绘制的括号序列显得杂乱无章,于是Candela定义了什么样的括号序列是美观的:

(1) 空的括号序列是美观的;

(2) 若括号序列A是美观的,则括号序列(A)、[A]、{A}也是美观的;

(3) 若括号序列A、B都是美观的,则括号序列AB也是美观的;

例如 [(){}]() 是美观的括号序列,而 )({)[}]( 则不是。

现在Candela想知道她画出的括号序列是不是美观的。你能帮帮她吗?

时间限制:1000

内存限制:262144

输入

一个括号序列,长度不超过10000。

输出

如果它是美观的,输出Yes,否则输出No。

样例输入

{}[(){}]()

样例输出

Yes
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;iostream&gt; #include &lt;stack&gt; using namespace std; stack&lt;char&gt; str; // 判断左右两个括号是否美观 bool beauty(char s1, char s2) {   switch (s1) {   case '{':     if (s2 == '}')       return true;     else       return false;   case '[':     if (s2 == ']')       return true;     else       return false;   case '(':     if (s2 == ')')       return true;     else       return false;   } } int main() {   string Brackets;   char s;   int i = 0;   cin &gt;&gt; Brackets;   while (i &lt; Brackets.length()) {     s = Brackets[i];     i++;     str.push(s); // 将当前字符入栈     char s2 = str.top();     if (s2 == ']' || s2 == '}' ||         s2 == ')') // 是右括号,进行判断是否与左括号美观     {       str.pop();         // 将s2出栈       if (str.empty()) { // 无左括号,肯定不美观         cout &lt;&lt; "No" &lt;&lt; endl;         return 0;       }       char s1 = str.top();  // s1是左括号       if (beauty(s1, s2)) { // 美观,将s1出栈         str.pop();       } else { // 不美观         cout &lt;&lt; "No" &lt;&lt; endl;         return 0;       }     }   }   cout &lt;&lt; "Yes"; }</pre>
这道题暂未补解析。
4. 简答题

中缀表达式的值

人们熟悉的四则运算表达式称为中缀表达式,例如(23+34*45/(5+6+7))。在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆波兰表示法),并最终变为计算机可以直接执行的指令,得到表达式的值。 给定一个中缀表达式,编写程序,利用堆栈的方法,计算表达式的值。

时间限制:200

内存限制:65536

输入

第一行为测试数据的组数N 接下来的N行,每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号,操作数都是正整数,数和运算符、括号之间没有空格。中缀表达式的字符串长度不超过600。

输出

对每一组测试数据输出一行,为表达式的值

样例输入

3
3+5*8
(3+5)*8
(23+34*45/(5+6+7))

样例输出

43
64
108

提示

注意:运算过程均为整数运算(除法运算'/'即按照C++定义的int除以int的结果,测试数据不会出现除数为0的情况),输出结果也为整数(可能为负)。 中间计算结果可能为负。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int get_fast(string op) // 运算符的优先级 {   int ans = -1;   switch (op[0]) {   case '+':   case '-':     ans = 1;     break;   case '*':   case '/':     ans = 2;     break;   case '^':     ans = 3;     break;   }   return ans; } vector&lt;string&gt; scaner(string s) // 字符串拆解放入vector {   vector&lt;string&gt; ans;   string ops = "+-*/^()";   string t = "";   for (int i = 0; i &lt; s.size(); i++) {     if (s[i] &gt;= '0' &amp;&amp; s[i] &lt;= '9')       t += s[i];     else if (ops.find(s[i]) != string::npos) {       if (t.size() &gt; 0)         ans.push_back(t);       t = s[i];       ans.push_back(t);       t = "";     }   }   if (t.size())     ans.push_back(t);   return ans; } vector&lt;string&gt; infix_Suffix(vector&lt;string&gt; exp) // 中缀表达式转后缀表达式 {   vector&lt;string&gt; ans;   stack&lt;string&gt; st;   string op = "+-*/^()";   for (int i = 0; i &lt; exp.size(); i++) {     if (exp[i] == "(")       st.push(exp[i]);     else if (exp[i] == ")") {       while (st.top() != "(") {         ans.push_back(st.top());         st.pop();       }       st.pop();     } else if (op.find(exp[i]) != string::npos) {       while (st.size() &amp;&amp; get_fast(exp[i]) &lt;= get_fast(st.top())) {         ans.push_back(st.top());         st.pop();       }       st.push(exp[i]);     } else       ans.push_back(exp[i]);   }   while (st.size()) {     ans.push_back(st.top());     st.pop();   }   return ans; } int suffix_calc(vector&lt;string&gt; exp) // 后缀表达式计算结果 {   stack&lt;int&gt; num;   string ops = "+-*/^";   for (int i = 0; i &lt; exp.size(); i++) {     if (ops.find(exp[i]) != string::npos) {       int a = num.top();       num.pop();       int b = num.top();       num.pop();       if (exp[i] == "+")         num.push(b + a);       else if (exp[i] == "-")         num.push(b - a);       else if (exp[i] == "*")         num.push(b * a);       else if (exp[i] == "/")         num.push(b / a);       else if (exp[i] == "^")         num.push(pow(b * 1.0, a));     } else       num.push(atoi(exp[i].c_str()));   }   cout &lt;&lt; num.top() &lt;&lt; endl;   return num.top(); } int main() {   string s;   int n;   cin &gt;&gt; n;   while (n--) {     cin &gt;&gt; s;     vector&lt;string&gt; vs = scaner(s);     vs = infix_Suffix(vs);     suffix_calc(vs);   }   return 0; }</pre>
这道题暂未补解析。