编程题 共4道
链表去重
给定一个带整数键值的链表 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
样例输出
23854 -15 99999
99999 -7 -1
00000 -15 87654
简单计算器
本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。计算器由两个堆栈组成，一个堆栈 S1 存放数字，另一个堆栈 S2 存放运算符。计算器的最下方有一个等号键，每次按下这个键，计算器就执行以下操作：
- 1. 从 S1 中弹出两个数字，顺序为 n1 和 n2；
- 2. 从 S2 中弹出一个运算符 op；
- 3. 执行计算 n2 op n1；
- 4. 将得到的结果压回 S1。
直到两个堆栈都为空时，计算结束，最后的结果将显示在屏幕上。
时间限制：7000
输入首先在第一行给出正整数 N（1 < N ≤ 103），为 S1 中数字的个数。 第二行给出 N 个绝对值不超过 100 的整数；第三行给出 N-1 个运算符 —— 这里仅考虑 `+`、`-`、`*`、`/` 这四种运算。一行中的数字和符号都以空格分隔。
将输入的数字和运算符按给定顺序分别压入堆栈 S1 和 S2，将执行计算的最后结果输出。注意所有的计算都只取结果的整数部分。题目保证计算的中间和最后结果的绝对值都不超过 109。 如果执行除法时出现分母为零的非法操作，则在一行中输出：`ERROR: X/0`，其中 `X` 是当时的分子。然后结束程序。
样例1：
5
40 5 8 3 2
/ * - +
样例2：
2 5 8 4 4
* / - +
2
ERROR: 5/0
两头进一头出
某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。现给定入队的序列，请你判断一系列出队序列是否可能。例如按 1、2、3、4、5 的顺序入队，则 1、3、2、5、4 这样的出队序列是可以得到的，但 5、1、3、2、4 就是不可能得到的。
时间限制：4000
输入首先在一行中给出两个正整数 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
整型关键字的平方探测法散列
本题的任务很简单：将给定的无重复正整数序列插入一个散列表，输出每个输入的数字在表中的位置。所用的散列函数是 H(key) = key % TSize，其中 TSize 是散列表的表长。要求用平方探测法（只增不减，即H(Key)+i2）解决冲突。
注意散列表的表长最好是个素数。如果输入给定的表长不是素数，你必须将表长重新定义为大于给定表长的最小素数。
首先第一行给出两个正整数 MSize（≤ 104）和 N（≤ MSize），分别对应输入的表长和输入数字的个数。随后第二行给出 N 个不重复的正整数，数字间以空格分隔。
在一行中按照输入的顺序给出每个数字在散列表中的位置（下标从 0 开始）。如果某个数字无法插入，就在其位置上输出 `-`。输出间以 1 个空格分隔，行首尾不得有多余空格。
4 4
10 6 4 15
0 1 4 -