题目：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 410 6 4 15 1111 4 15 2样例输出15 cannot be inserted.2.8

题目：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 个空格分隔，行首尾不得有多余空格。样例输入53 5 1 2 4样例输出9 6.0

题目：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 51 2 3 4 5 6 73 2 1 7 5 6 47 6 5 4 3 2 15 6 4 3 7 2 11 7 6 5 4 3 2样例输出YESNONOYESNO

题目：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 1023333 10 2777700000 0 9999900100 18 1230968237 -6 2333333218 -4 0000048652 -2 -199999 5 6823727777 11 4865212309 7 33218样例输出33218 -4 6823768237 -6 4865248652 -2 1230912309 7 0000000000 0 9999999999 5 2333323333 10 0010000100 18 2777727777 11 -1

题目：4.整型关键字的平方探测法散列本题的任务很简单：将给定的无重复正整数序列插入一个散列表，输出每个输入的数字在表中的位置。所用的散列函数是 H(key) = key % TSize，其中 TSize 是散列表的表长。要求用平方探测法（只增不减，即H(Key)+i2）解决冲突。注意散列表的表长最好是个素数。如果输入给定的表长不是素数，你必须将表长重新定义为大于给定表长的最小素数。时间限制：4000内存限制：65536输入首先第一行给出两个正整数 MSize（≤ 104）和 N（≤ MSize），分别对应输入的表长和输入数字的个数。随后第二行给出 N 个不重复的正整数，数字间以空格分隔。输出在一行中按照输入的顺序给出每个数字在散列表中的位置（下标从 0 开始）。如果某个数字无法插入，就在其位置上输出 `-`。输出间以 1 个空格分隔，行首尾不得有多余空格。样例输入4 410 6 4 15样例输出0 1 4 -

题目：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 410 2 3 4 510 3 2 5 45 10 3 2 42 3 10 4 53 5 10 4 2样例输出yesnoyesno

题目：2.简单计算器本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。计算器由两个堆栈组成，一个堆栈 S1 存放数字，另一个堆栈 S2 存放运算符。计算器的最下方有一个等号键，每次按下这个键，计算器就执行以下操作：\- 1. 从 S1 中弹出两个数字，顺序为 n1 和 n2；\- 2. 从 S2 中弹出一个运算符 op；\- 3. 执行计算 n2 op n1；\- 4. 将得到的结果压回 S1。直到两个堆栈都为空时，计算结束，最后的结果将显示在屏幕上。时间限制：7000内存限制：65536输入输入首先在第一行给出正整数 N（1 < N ≤ 103），为 S1 中数字的个数。 第二行给出 N 个绝对值不超过 100 的整数；第三行给出 N-1 个运算符 —— 这里仅考虑 `+`、`-`、`*`、`/` 这四种运算。一行中的数字和符号都以空格分隔。输出将输入的数字和运算符按给定顺序分别压入堆栈 S1 和 S2，将执行计算的最后结果输出。注意所有的计算都只取结果的整数部分。题目保证计算的中间和最后结果的绝对值都不超过 109。 如果执行除法时出现分母为零的非法操作，则在一行中输出：`ERROR: X/0`，其中 `X` 是当时的分子。然后结束程序。样例输入样例1：540 5 8 3 2/ * - +样例2：52 5 8 4 4\* / - +样例输出样例1：2样例2：ERROR: 5/0

题目：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 599999 -7 8765423854 -15 0000087654 15 -100000 -15 9999900100 21 23854样例输出00100 21 2385423854 -15 9999999999 -7 -100000 -15 8765487654 15 -1

题目：4.

题目：3.