理论卷2025年3月青少年软件编程(C\C++) · 六级

YLT C++ 6级 2025.03

满分 100 · 及格 60 · 时长 60 分钟 · 共 4 题 (编程题4)

试卷阅览 · 免费预览前 10 题 · 交卷后可查看答案与解析

编程题题号 #22148

分值 25

N5656 [CIE 202503 六级 T1] 链表元素分类

题目描述

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

输入格式

每个输入包含一个测试用例。
每个测试用例第 $1$ 行给出：第 $1$ 个结点的地址；结点总个数，即正整数 $N$ （ $\le 10^5$ ）；以及正整数 $K$ （ $\le 10^3$ ）。结点的地址是 $5$ 位非负整数， $NULL$ 地址用 $-1$ 表示。
接下来有 $N$ 行，每行格式为：Address Data Next 其中 Address 是结点地址；Data 是该结点保存的数据，为 $[-10^5, 10^5]$ 区间内的整数；Next 是下一结点的地址。题目保证给出的链表不为空。

输出格式

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

样例

样例 1
输入：

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

编程题题号 #22149

分值 25

N5657 [CIE 202503 六级 T2] 出栈序列的合法性

题目描述

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

输入格式

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

输出格式

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

样例

样例 1
输入：

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

编程题题号 #22150

分值 25

N5658 [CIE 202503 六级 T3] 取行李

题目描述

一般机场里，航班到达后，旅客们会去到达区的行李传送带那里取自己的行李。
现假设有一座特别的机场，每条传送带只有一个取行李的窗口。旅客们必须排好队，逐一到窗口取自己的行李。但是当某人到窗口前，发现行李不是自己的，那人就只好走到队尾去等待下一次机会。此时那件行李会一直等在窗口，直到它的主人把它取走。假设每一次认领需要 $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 \approx 3.7$ 。

输入格式

输入首先在第一行给出一个正整数 $N$ （ $\le 10^3$ ）。
下一行给出 $N$ 个数字，是 $[1, N]$ 区间内整数的一个重排列，表示旅客队列。这里我们假设行李队列是按 $1, 2, \ldots, N$ 有序的，并且行李 $i$ 属于旅客 $i$ 。一行中数字间以空格分隔。

输出格式

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

样例

样例 1
输入：

5
3 5 1 2 4

输出：

9 6.0

编程题题号 #22151

分值 25

N5659 [CIE 202503 六级 T4] 散列表平均查找时间

题目描述

本目标很简单：首先将一系列各不相同的正整数键值插入一张散列表，随后在表中查找另外给定的一个整数键值系列，输出平均查找时间（确定一个数字在或不在表中所需要比较的次数）。
这里用到的哈希函数定义为 H(key) = key % TSize，其中 $TSize$ 是散列表的容量。使用平方探测（仅做正向递增的探测）来解决冲突。
注意散列表的容量最好是一个素数。如果用户给出的容量不是素数，你必须将容量重新定义为比用户给定容量大的一个最小的素数。

输入格式

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

输出格式

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

样例

样例 1
输入：

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

输出：

15 cannot be inserted.
2.5