首页 › 试卷 › C/C++编程考级 › C/C++编程六级 › 2024年12月电子学会青少年软件编程(C/C++)6级等级考试真题试卷

2024年12月电子学会青少年软件编程(C/C++)6级等级考试真题试卷 VIP

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

一、简答题

1. 简答题

链表去重

给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉。即对每个键值 K,只有第一个绝对值等于 K 的结点被保留。同时,所有被删除的结点须被保存在另一个链表上。

例如给定 L 为 21→-15→-15→-7→15,你需要输出去重后的链表 21→-15→-7,还有被删除的链表 -15→15。

时间限制:5000,内存限制:65536

输入

输入在第一行给出 L 的第一个结点的地址和一个正整数 N(≤ 105,为结点总数)。一个结点的地址是非负的 5 位整数,空地址 NULL 用 -1 来表示。 

随后 N 行,每行按以下格式描述一个结点: 地址 键值 下一个结点 其中 地址 是该结点的地址,键值 是绝对值不超过104的整数,下一个结点 是下个结点的地址。

输出

首先输出去重后的链表,然后输出被删除的链表。每个结点占一行,按输入的格式输出。

样例输入

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

样例输出

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//该答案由AI生成 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;unordered_set&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;iomanip&gt; using namespace std; struct Node {     int address;     int key;     int next; }; int main() {     int start, n;     cin &gt;&gt; start &gt;&gt; n;          // 用数组存储所有节点,索引为节点地址     vector&lt;Node&gt; nodes(100000);     for (int i = 0; i &lt; n; i++) {         int addr, key, next;         cin &gt;&gt; addr &gt;&gt; key &gt;&gt; next;         nodes[addr] = {addr, key, next};     }          unordered_set&lt;int&gt; seen;  // 记录已出现过的绝对值     vector&lt;Node&gt; kept;       // 保留链表的节点     vector&lt;Node&gt; removed;    // 删除链表的节点          int current = start;     while (current != -1) {         int absKey = abs(nodes[current].key);         if (seen.find(absKey) == seen.end()) {             seen.insert(absKey);             kept.push_back(nodes[current]);         } else {             removed.push_back(nodes[current]);         }         current = nodes[current].next;     }          // 输出保留链表     for (int i = 0; i &lt; kept.size(); i++) {         printf("%05d %d ", kept[i].address, kept[i].key);         if (i &lt; kept.size() - 1) {             printf("%05d\n", kept[i + 1].address);         } else {             printf("-1\n");         }     }          // 输出删除链表     for (int i = 0; i &lt; removed.size(); i++) {         printf("%05d %d ", removed[i].address, removed[i].key);         if (i &lt; removed.size() - 1) {             printf("%05d\n", removed[i + 1].address);         } else {             printf("-1\n");         }     }          return 0; }</pre>
这道题暂未补解析。
2. 简答题

简单计算器

本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。计算器由两个堆栈组成,一个堆栈 S1 存放数字,另一个堆栈 S2 存放运算符。

计算器的最下方有一个等号键,每次按下这个键,计算器就执行以下操作:

(1)从 S1 中弹出两个数字,顺序为 n1 和 n2;

(2)从 S2 中弹出一个运算符 op;

(3)执行计算 n2 op n1;

(4)将得到的结果压回 S1。

直到两个堆栈都为空时,计算结束,最后的结果将显示在屏幕上。

时间限制:7000,内存限制:65536

输入

输入首先在第一行给出正整数 N(1 < N ≤ 10^3),为 S1 中数字的个数。 

第二行给出 N 个绝对值不超过 100 的整数;

第三行给出 N-1 个运算符 —— 这里仅考虑 +、-、*、/ 这四种运算。一行中的数字和符号都以空格分隔。

输出

将输入的数字和运算符按给定顺序分别压入堆栈 S1 和 S2,将执行计算的最后结果输出。

注意所有的计算都只取结果的整数部分。题目保证计算的中间和最后结果的绝对值都不超过 109。

如果执行除法时出现分母为零的非法操作,则在一行中输出:ERROR: X/0,其中 X 是当时的分子。然后结束程序。

样例输入1

5
40 5 8 3 2
/ * - +

样例输出1

2

样例输入2

5
2 5 8 4 4
* / - +

样例输出2

ERROR: 5/0
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//该答案由AI生成 #include &lt;iostream&gt; #include &lt;stack&gt; #include &lt;string&gt; using namespace std; int main() {     int n;     cin &gt;&gt; n;          stack&lt;int&gt; nums;     for (int i = 0; i &lt; n; i++) {         int num;         cin &gt;&gt; num;         nums.push(num);     }          stack&lt;char&gt; ops;     for (int i = 0; i &lt; n - 1; i++) {         char op;         cin &gt;&gt; op;         ops.push(op);     }          while (!ops.empty()) {         int n1 = nums.top();         nums.pop();         int n2 = nums.top();         nums.pop();         char op = ops.top();         ops.pop();                  int result;         if (op == '+') {             result = n2 + n1;         } else if (op == '-') {             result = n2 - n1;         } else if (op == '*') {             result = n2 * n1;         } else if (op == '/') {             if (n1 == 0) {                 cout &lt;&lt; "ERROR: " &lt;&lt; n2 &lt;&lt; "/0" &lt;&lt; endl;                 return 0;             }             result = n2 / n1;  // 整数除法         }                  nums.push(result);     }          cout &lt;&lt; nums.top() &lt;&lt; endl;          return 0; }</pre>
这道题暂未补解析。
3. 简答题

两头进一头出

某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。现给定入队的序列,请你判断一系列出队序列是否可能。

例如按 1、2、3、4、5 的顺序入队,则 1、3、2、5、4 这样的出队序列是可以得到的,但 5、1、3、2、4 就是不可能得到的。

时间限制:4000,内存限制:65536

输入

输入首先在一行中给出两个正整数 N 和 K(≤ 10),分别是入队元素的个数和待查验的序列个数。

随后一行给出 N 个两两不同的整数组成的入队序列;再跟着 K 行,每行给出由 N 个入队整数组成的出队序列。同行整数间以空格分隔。

输出

对每个需要查验的出队序列,如果是可能的,则在一行中输出 yes,否则输出 no。

样例输入

5 4
10 2 3 4 5
10 3 2 5 4
5 10 3 2 4
2 3 10 4 5
3 5 10 4 2

样例输出

yes
no
yes
no
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//该答案由AI生成 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;deque&gt; #include &lt;set&gt; #include &lt;map&gt; using namespace std; bool check(vector&lt;int&gt;&amp; in, vector&lt;int&gt;&amp; out, const map&lt;int, int&gt;&amp; index_map) {     deque&lt;int&gt; deq;     set&lt;int&gt; inDeque;     int n = in.size();     int i0 = 0, j0 = 0;     while (i0 &lt; n) {         if (!deq.empty() &amp;&amp; deq.front() == out[i0]) {             int x = deq.front();             deq.pop_front();             inDeque.erase(x);             i0++;         } else {             if (inDeque.find(out[i0]) != inDeque.end()) {                 return false;             }             if (j0 &gt;= n) {                 return false;             }             auto it = index_map.find(out[i0]);             if (it == index_map.end()) {                 return false;             }             int pos = it-&gt;second;             if (pos &lt; j0) {                 return false;             }             for (int k = j0; k &lt; pos; k++) {                 deq.push_back(in[k]);                 inDeque.insert(in[k]);             }             deq.push_front(in[pos]);             inDeque.insert(in[pos]);             j0 = pos + 1;             int x = deq.front();             deq.pop_front();             inDeque.erase(x);             i0++;         }     }     return true; } int main() {     int N, K;     cin &gt;&gt; N &gt;&gt; K;     vector&lt;int&gt; in(N);     map&lt;int, int&gt; index_map;     for (int i = 0; i &lt; N; i++) {         cin &gt;&gt; in[i];         index_map[in[i]] = i;     }     for (int i = 0; i &lt; K; i++) {         vector&lt;int&gt; out(N);         for (int j = 0; j &lt; N; j++) {             cin &gt;&gt; out[j];         }         if (check(in, out, index_map)) {             cout &lt;&lt; "yes" &lt;&lt; endl;         } else {             cout &lt;&lt; "no" &lt;&lt; endl;         }     }     return 0; }</pre>
这道题暂未补解析。
4. 简答题

整型关键字的平方探测法散列

本题的任务很简单:将给定的无重复正整数序列插入一个散列表,输出每个输入的数字在表中的位置。所用的散列函数是 H(key) = key % TSize,其中 TSize 是散列表的表长。要求用平方探测法(只增不减,即H(Key)+i2)解决冲突。

注意散列表的表长最好是个素数。如果输入给定的表长不是素数,你必须将表长重新定义为大于给定表长的最小素数。

时间限制:4000,内存限制:65536

输入

首先第一行给出两个正整数 MSize(≤ 10^4)和 N(≤ MSize),分别对应输入的表长和输入数字的个数。

随后第二行给出 N 个不重复的正整数,数字间以空格分隔。

输出

在一行中按照输入的顺序给出每个数字在散列表中的位置(下标从 0 开始)。如果某个数字无法插入,就在其位置上输出 -。输出间以 1 个空格分隔,行首尾不得有多余空格。

样例输入

4 4
10 6 4 15

样例输出

0 1 4 -
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//该答案由AI生成 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cmath&gt; using namespace std; bool isPrime(int num) {     if (num &lt;= 1) return false;     if (num == 2) return true;     if (num % 2 == 0) return false;     for (int i = 3; i &lt;= sqrt(num); i += 2) {         if (num % i == 0) return false;     }     return true; } int nextPrime(int n) {     if (n &lt;= 1) return 2;     int prime = n;     bool found = false;     while (!found) {         prime++;         if (isPrime(prime)) found = true;     }     return prime; } int main() {     int MSize, N;     cin &gt;&gt; MSize &gt;&gt; N;          int TSize = MSize;     if (!isPrime(TSize)) {         TSize = nextPrime(MSize);     }          vector&lt;int&gt; hashTable(TSize, -1);     vector&lt;string&gt; results;          for (int idx = 0; idx &lt; N; idx++) {         int key;         cin &gt;&gt; key;                  bool inserted = false;         for (int i = 0; i &lt; TSize; i++) {             int pos = (key % TSize + i * i) % TSize;             if (hashTable[pos] == -1) {                 hashTable[pos] = key;                 results.push_back(to_string(pos));                 inserted = true;                 break;             }         }         if (!inserted) {             results.push_back("-");         }     }          for (int i = 0; i &lt; results.size(); i++) {         if (i &gt; 0) cout &lt;&lt; " ";         cout &lt;&lt; results[i];     }     cout &lt;&lt; endl;          return 0; }</pre>
这道题暂未补解析。