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

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

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

一、简答题

1. 简答题

链表元素分类

给定一个单链表,请编写程序将链表元素进行分类排列,使得所有负值元素都排在非负值元素的前面,而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如:给定链表为 18→7→-4→0→5→-6→10→11→-2,K 为 10,则输出应该为 -4→-6→-2→7→0→5→10→18→11。

时间限制:1000

内存限制:65536

输入

每个输入包含一个测试用例。每个测试用例第 1 行给出:第 1 个结点的地址;结点总个数,即正整数N (≤ 105);以及正整数K (≤ 103)。结点的地址是 5 位非负整数,NULL 地址用 -1 表示。 接下来有 N 行,每行格式为: Address Data Next 其中 `Address` 是结点地址;`Data` 是该结点保存的数据,为 [-105, 105] 区间内的整数;`Next` 是下一结点的地址。题目保证给出的链表不为空。

输出

对每个测试用例,按链表从头到尾的顺序输出重排后的结果链表,其上每个结点占一行,格式与输入相同。


样例输入

00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

样例输出

33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考程序1 #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; struct Node {     int addr, data, next; }; int main() {     int head, n, k;     cin &gt;&gt; head &gt;&gt; n &gt;&gt; k;     vector&lt;Node&gt; nodes(100000);     for (int i = 0; i &lt; n; ++i) {         int addr;         cin &gt;&gt; addr;         cin &gt;&gt; nodes[addr].data &gt;&gt; nodes[addr].next;         nodes[addr].addr = addr;     }     vector&lt;Node&gt; negative, zeroToK, greater;     for (int p = head; p != -1; p = nodes[p].next) {         if (nodes[p].data &lt; 0) negative.push_back(nodes[p]);         else if (nodes[p].data &lt;= k) zeroToK.push_back(nodes[p]);         else greater.push_back(nodes[p]);     }     negative.insert(negative.end(), zeroToK.begin(), zeroToK.end());     negative.insert(negative.end(), greater.begin(), greater.end());     for (int i = 0; i &lt; negative.size(); ++i) {         if (i &lt; negative.size() - 1) negative[i].next = negative[i + 1].addr;         else negative[i].next = -1;         printf("%05d %d ", negative[i].addr, negative[i].data);         if (negative[i].next != -1) printf("%05d\n", negative[i].next);         else printf("-1\n");     }     return 0; }</pre><p><br/></p><pre class="brush:cpp;toolbar:false">//参考程序2 #include &lt;iostream&gt; #include &lt;unordered_map&gt; #include &lt;vector&gt; #include &lt;string&gt; using namespace std; struct NodeInfo { string address; int data; string next; }; int main() { string start_addr; int N, K; cin &gt;&gt; start_addr &gt;&gt; N &gt;&gt; K; unordered_map&lt;string, pair&lt;int, string&gt;&gt; node_map; for (int i = 0; i &lt; N; ++i) { string addr, next; int data; cin &gt;&gt; addr &gt;&gt; data &gt;&gt; next; node_map[addr] = {data, next}; } vector&lt;NodeInfo&gt; nodes_old; string current = start_addr; while (current != "-1") { auto&amp; p = node_map[current]; nodes_old.push_back({current, p.first, p.second}); current = p.second; } vector&lt;NodeInfo&gt; group_neg, group_mid, group_big; for (auto&amp; node : nodes_old) { if (node.data &lt; 0) { group_neg.push_back(node); } else if (node.data &lt;= K) { group_mid.push_back(node); } else { group_big.push_back(node); } } vector&lt;NodeInfo&gt; nodes_new; nodes_new.insert(nodes_new.end(), group_neg.begin(), group_neg.end()); nodes_new.insert(nodes_new.end(), group_mid.begin(), group_mid.end()); nodes_new.insert(nodes_new.end(), group_big.begin(), group_big.end()); for (int i = 0; i &lt; nodes_new.size(); ++i) { if (i == nodes_new.size() - 1) { nodes_new[i].next = "-1"; } else { nodes_new[i].next = nodes_new[i+1].address; } } for (auto&amp; node : nodes_new) { cout &lt;&lt; node.address &lt;&lt; " " &lt;&lt; node.data &lt;&lt; " " &lt;&lt; node.next &lt;&lt; endl; } return 0; }</pre><p></p>
这道题暂未补解析。
2. 简答题

出栈序列的合法性

给定一个最大容量为 m 的堆栈,将 n 个数字按 1, 2, 3, ..., n 的顺序入栈,允许按任何顺序出栈,则哪些数字序列是不可能得到的?例如给定 m=5、n=7,则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 },但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。

时间限制:1000

内存限制:65536

输入

输入第一行给出 3 个不超过 1000 的正整数:m(堆栈最大容量)、n(入栈元素个数)、k(待检查的出栈序列个数)。最后 k 行,每行给出 n 个数字的出栈序列。所有同行数字以空格间隔。

输出

对每一行出栈序列,如果其的确是有可能得到的合法序列,就在一行中输出 `YES`,否则输出 `NO`。


样例输入

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

样例输出

YES
NO
NO
YES
NO
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考程序1 #include&lt;bits/stdc++.h&gt; using namespace std; int m,n,k; bool is_possible(int out[]) { stack&lt;int&gt; s; int x=1,y=0; next: if(y==n)return 1; while(1) { if(s.size()&gt;=m||x&gt;n)return 0; s.push(x); x++; if(s.top()==out[y])break; } while(1) { if(s.size()==0)break; if(s.top()==out[y]) { s.pop(); y++; } else break; } goto next; } int main() { cin&gt;&gt;m&gt;&gt;n&gt;&gt;k; for(int i=0;i&lt;k;i++) { int out[n]; for(int j=0;j&lt;n;j++) cin&gt;&gt;out[j]; if(!is_possible(out))cout&lt;&lt;"NO"&lt;&lt;endl; else cout&lt;&lt;"YES"&lt;&lt;endl; } return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考程序2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;stack&gt; using namespace std; int main() { int m, n, k; cin &gt;&gt; m &gt;&gt; n &gt;&gt; k; while (k--) { vector&lt;int&gt; seq(n); for (int i = 0; i &lt; n; ++i) { cin &gt;&gt; seq[i]; } stack&lt;int&gt; st; int current_max = 0; bool valid = true; for (int v : seq) { if (v &gt; current_max) { int needed = v - current_max; if (st.size() + needed &gt; m) { valid = false; break; } for (int i = current_max + 1; i &lt;= v; ++i) { st.push(i); } current_max = v; st.pop(); // 弹出v } else { if (st.empty() || st.top() != v) { valid = false; break; } else { st.pop(); } } } cout &lt;&lt; (valid ? "YES" : "NO") &lt;&lt; endl; } return 0; }</pre><p></p>
这道题暂未补解析。
3. 简答题

取行李

一般机场里,航班到达后,旅客们会去到达区的行李传送带那里取自己的行李。

现假设有一座特别的机场,每条传送带只有一个取行李的窗口。旅客们必须排好队,逐一到窗口取自己的行李。但是当某人到窗口前,发现行李不是自己的,那人就只好走到队尾去等下一次机会。此时那件行李会一直等在窗口,直到它的主人把它取走。假设每一次认领需要 1 分钟,本题就要求你计算传送带清空需要的时间、以及旅客们的平均等待时间。

例如,假设行李 i 属于旅客 i。行李的到达顺序是 1、2、3,旅客的到达顺序是 2、1、3。则 1 号行李要等 2 分钟才能被主人 1 号旅客取走。这时行李队列中有 2、3,旅客队列中是 3、2。于是 2 号行李还要等 2 分钟才能被 2 号旅客取走,最后 3 号在第 5 分钟取走行李。旅客们的平均等待时间是 (2+4+5)/3 ≈ 3.7。

时间限制:1000

内存限制:65536

输入

输入首先在第一行给出一个正整数 N(≤ 103)。下一行给出 N 个数字,是 [1, N] 区间内整数的一个重排列,表示旅客队列。这里我们假设行李队列是按 1、2、……、N 有序的,并且行李 i 属于旅客 i。一行中数字间以空格分隔。

输出

在一行中输出传送带清空需要的时间、以及旅客们的平均等待时间(输出小数点后 1 位)。数字间以 1 个空格分隔,行首尾不得有多余空格。


样例输入

5
3 5 1 2 4

样例输出

9 6.0
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;vector&gt; #include &lt;iomanip&gt; using namespace std; int main() { int N; cin &gt;&gt; N; vector&lt;int&gt; passengers(N); for (int i = 0; i &lt; N; ++i) { cin &gt;&gt; passengers[i]; } queue&lt;int&gt; q; for (int p : passengers) { q.push(p); } int current_luggage = 1; int time = 0; vector&lt;int&gt; wait_time(N + 1, 0); // 使用1-based索引 while (current_luggage &lt;= N) { int p = q.front(); q.pop(); if (p == current_luggage) { time += 1; wait_time[p] = time; current_luggage += 1; } else { time += 1; q.push(p); } } int total_time = time; double sum = 0; for (int i = 1; i &lt;= N; ++i) { sum += wait_time[i]; } double avg = sum / N; cout &lt;&lt; total_time &lt;&lt; " " &lt;&lt; fixed &lt;&lt; setprecision(1) &lt;&lt; avg &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。
4. 简答题

散列表平均查找时间

本题目标很简单:首先将一系列各不相同的正整数键值插入一张散列表,随后在表中查找另外给定的一个整数键值系列,输出平均查找时间(确定一个数字在或不在表中所需要比较的次数)。这里用到的哈希函数定义为 H(key) = key % TSize,其中 TSize 是散列表的容量。使用平方探测(仅做正向递增的探测)来解决冲突。

注意散列表的容量最好是一个素数。如果用户给出的容量不是素数,你必须将容量重新定义为比用户给定容量大的一个最小的素数。

时间限制:1000

内存限制:65536

输入

输入第一行给出 3 个正整数:MSize、N、M,分别是用户定义的散列表容量、要插入的键值的数量、以及要查找的键值的数量。这 3 个数都不超过 104。 随后第二行给出 N 个各不相同的正整数键值待插入。第三行给出 M 个正整数键值待查找。同一行中数字间以一个空格分隔,数均不超过 105。

输出

如果某个数无法插入,则在一行中输出 `X cannot be inserted.`,其中 `X` 是那个输入的数字。最后一行输出全部 M 个键值的平均查找时间,精确到小数点后 1 位。


样例输入

4 5 4
10 6 4 15 11
11 4 15 2

样例输出

15 cannot be inserted.
2.8
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考程序1 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;iomanip&gt; // 找到比给定数大的最小素数 int nextPrime(int num) {     if (num &lt;= 2) return 2;     if (num % 2 == 0) num++;     while (true) {         bool isPrime = true;         for (int i = 3; i * i &lt;= num; i += 2) {             if (num % i == 0) {                 isPrime = false;                 break;             }         }         if (isPrime) break;         num += 2;     }     return num; } int main() {     int mSize, n, m;     std::cin &gt;&gt; mSize &gt;&gt; n &gt;&gt; m;     mSize = nextPrime(mSize);     std::vector&lt;int&gt; hashTable(mSize, -1);     // 插入键值     for (int i = 0; i &lt; n; ++i) {         int key;         std::cin &gt;&gt; key;         int hash = key % mSize;         bool inserted = false;         for (int j = 0; j &lt; mSize; ++j) {             int index = (hash + j * j) % mSize;             if (hashTable[index] == -1) {                 hashTable[index] = key;                 inserted = true;                 break;             }         }         if (!inserted) {             std::cout &lt;&lt; key &lt;&lt; " cannot be inserted." &lt;&lt; std::endl;         }     }     // 查找键值     int totalSearchTime = 0;     for (int i = 0; i &lt; m; ++i) {         int key;         std::cin &gt;&gt; key;         int hash = key % mSize;         for (int j = 0; j &lt;= mSize; ++j) {             totalSearchTime++;             int index = (hash + j * j) % mSize;             if (hashTable[index] == key || hashTable[index] == -1) {                 break;             }         }     }     // 输出平均查找时间     double averageSearchTime = static_cast&lt;double&gt;(totalSearchTime) / m;     std::cout &lt;&lt; std::fixed &lt;&lt; std::setprecision(1) &lt;&lt; averageSearchTime &lt;&lt; std::endl;     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考程序2 #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;iomanip&gt; #include &lt;cmath&gt; using namespace std; bool isPrime(int n) { if (n &lt;= 1) return false; for (int i = 2; i * i &lt;= n; ++i) { if (n % i == 0) return false; } return true; } int getTSize(int m) { if (isPrime(m)) return m; int t = m + 1; while (true) { if (isPrime(t)) return t; ++t; } } int main() { int MSize, N, M; cin &gt;&gt; MSize &gt;&gt; N &gt;&gt; M; int TSize = getTSize(MSize); vector&lt;int&gt; hashTable(TSize, -1); // -1表示空位置 // 插入元素到哈希表 vector&lt;bool&gt; insertedKeys(N); for (int i = 0; i &lt; N; ++i) { int key; cin &gt;&gt; key; int h = key % TSize; bool inserted = false; for (int j = 0; j &lt; TSize; ++j) { int pos = (h + j * j) % TSize; if (hashTable[pos] == -1) { hashTable[pos] = key; inserted = true; break; } } if (!inserted) { cout &lt;&lt; key &lt;&lt; " cannot be inserted." &lt;&lt; endl; } } // 计算平均查找时间 double total = 0.0; for (int i = 0; i &lt; M; ++i) { int key; cin &gt;&gt; key; int h = key % TSize; int count = 0; for (int j = 0; j &lt; TSize; ++j) { ++count; int pos = (h + j * j) % TSize; if (hashTable[pos] == -1) { break; } else if (hashTable[pos] == key) { break; } } total += count; } double avg = total / M; cout &lt;&lt; fixed &lt;&lt; setprecision(1) &lt;&lt; avg &lt;&lt; endl; return 0; }</pre><p><br/></p>
这道题暂未补解析。