一、简答题
1、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
解析：
为了解决这个问题，我们可以按照以下步骤操作：
- 创建一个空的哈希表来存储已经遇到的绝对值。
- 创建一个空链表来保存被删除的节点。
- 遍历给定的链表。对于每个节点，执行以下操作：
- 获取节点的键值并取其绝对值。
- 检查该绝对值是否已在哈希表中。
- 如果不在哈希表中，将该绝对值添加到哈希表，并将节点添加到保留的链表中。
- 如果已在哈希表中，将节点添加到被删除的链表中。
- 输出保留的链表和被删除的链表。
注意：在遍历链表时，需要同时更新节点的下一个节点的地址，以确保链表的完整性。此外，需要注意空地址NULL的处理，题目中已给出空地址用-1表示。在添加节点到链表时，如果遇到一个空地址，直接跳过该节点。
具体实现时，可以使用数组或哈希表来模拟哈希表的功能。由于题目中结点的地址是非负的5位整数，可以使用一个大小为100000的数组来存储已遇到的绝对值，其中数组索引代表键值，数组元素的值代表该键值是否已遇到（0代表未遇到，1代表已遇到）。这样可以在O(1)的时间复杂度内检查一个键值是否已遇到。
对于输出部分，按照题目要求的格式输出保留的链表和被删除的链表即可。
2、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：
5
40 5 8 3 2
/ * - +
样例2：
5
2 5 8 4 4
\* / - +
样例输出
样例1：
2
样例2：
ERROR: 5/0
解析：
根据题目描述，我们需要设计一个利用堆栈结构的简单计算器。主要思路是将输入的数字和运算符分别压入两个堆栈S1和S2中。然后，按照等号键的操作，不断地从S1和S2中弹出元素进行计算，并将结果压回S1。
具体实现时，需要注意以下几点：
- 读取输入时，要分别处理数字和运算符的输入，并按照顺序压入相应的堆栈。
- 在执行计算时，要按照运算符的优先级进行，例如先乘除后加减。
- 如果遇到除法操作且分母为零的情况，需要特殊处理，输出错误信息并结束程序。
- 最后，S1堆栈中剩下的就是计算结果，需要将其输出。
根据以上解析，我们可以编写相应的代码来实现这款简单计算器。
3、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
解析：
根据题目描述，我们需要模拟队列的进出操作来判断给定的出队序列是否可能得到。通过创建一个空队列，并依次将入队序列中的元素入队，然后检查出队序列中的元素是否能从队列中按序出队，可以判断出一个出队序列是否可能得到。在这个过程中，我们需要保证出队的顺序与入队的顺序一致，并且队列中始终存在要出的元素。如果在这个过程中发现任何不一致或队列中元素不足的情况，就说明该出队序列不可能得到。通过这样的模拟，我们可以对每一个待查验的出队序列进行判断，并输出对应的结果。
4、4.整型关键字的平方探测法散列
本题的任务很简单：将给定的无重复正整数序列插入一个散列表，输出每个输入的数字在表中的位置。所用的散列函数是 H(key) = key % TSize，其中 TSize 是散列表的表长。要求用平方探测法（只增不减，即H(Key)+i2）解决冲突。
注意散列表的表长最好是个素数。如果输入给定的表长不是素数，你必须将表长重新定义为大于给定表长的最小素数。
时间限制：4000
内存限制：65536
输入
首先第一行给出两个正整数 MSize（≤ 104）和 N（≤ MSize），分别对应输入的表长和输入数字的个数。随后第二行给出 N 个不重复的正整数，数字间以空格分隔。
输出
在一行中按照输入的顺序给出每个数字在散列表中的位置（下标从 0 开始）。如果某个数字无法插入，就在其位置上输出 `-`。输出间以 1 个空格分隔，行首尾不得有多余空格。
样例输入
4 4
10 6 4 15
样例输出
0 1 4 -
解析：
本题主要考察散列表（哈希表）的实现以及平方探测法解决冲突的策略。
- 读取输入：使用标准输入读取表长 MSize 和数字个数 N。
- 素数判断与重新定义：若 MSize 不是素数，需找到大于 MSize 的最小素数并重新定义表长。可以使用素数判断算法（如试除法）来实现。
- 初始化散列表：根据找到的素数表长，初始化一个数组作为散列表，所有位置默认为空。
- 计算哈希值：对于每个输入的数字，使用散列函数 H(key) = key % TSize 计算其哈希值。
- 平方探测法解决冲突：若计算出的哈希值位置已被占用（即散列表中该位置已有数字），则使用平方探测法寻找下一个可用的位置。具体实现时，可以使用一个探测次数 i，初始化为 0，然后不断尝试 H(key) + i^2 的位置，直到找到空位置或探测次数超过某个阈值。
- 插入数字并记录位置：在找到的位置插入数字，并记录下每个数字插入的位置。
- 输出结果：按照输入的顺序，输出每个数字在散列表中的位置。若某个数字无法插入（即散列表中所有位置均被占用且无法通过平方探测法找到空位置），则对应位置输出“-”。
注意：在实现过程中需要注意处理数组边界情况，确保探测过程不会超出数组范围。同时，由于内存限制为 65536，需要合理选择表长和数据类型，以确保内存使用合理。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
