一、实操题
1、1.合法出栈序列 给定一个由不同小写字母构成的长度不超过8的字符串x，现在要将该字符串的字符依次压入栈中，然后再全部弹出。 要求左边的字符一定比右边的字符先入栈，出栈顺序无要求。 再给定若干字符串，对每个字符串，判断其是否是可能的x中的字符的出栈序列。 时间限制：1000 内存限制：65536 输入 第一行是原始字符串x 后面有若干行，每行一个字符串 输出 对除第一行以外的每个字符串，判断其是否是可能的出栈序列。如果是，输出"YES"，否则，输出"NO" 样例输入 abc abc bca cab 样例输出 YES YES NO
正确答案：
略
2、2.奇怪的括号 某天小A和同学在课堂上讨论到：“栈这种数据结构真是太优美了，既简单用途又广泛。”小B仰慕 小A许久，于是他拿出了自己在网上抄写的一道题问小A，如何判断括号是否匹配呢 时间限制：1000 内存限制：65536 输入 多组数据，每组数据占一行，且都是由(、)、[、]、*、/这六种字符组成。 输出 每组数据输出一行，如果括号能匹配成功，输出True，否则输出False。括号匹配规则是： ( 和 ) 匹配 [ 和 ] 匹配 /* 和 */ 匹配 如果含有冗余字符也算匹配失败，例如 /***/ 是匹配失败的因为中间多了一个*。 样例输入 ()/*[()]*/ */**/ 样例输出 True False
正确答案：
略
3、3.区间合并 给定 n 个闭区间 [ai; bi]，其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1;2] 和 [2;3] 可以合并为 [1;3]，[1;3] 和 [2;4] 可以合并为 [1;4]，但是[1;2] 和 [3;4] 不可以合并。 我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，将这个闭区间输出，否则输出no。 时间限制：1000 内存限制：65536 输入 第一行为一个整数n，3 ≤ n ≤ 50000。表示输入区间的数量。 之后n行，在第i行上（1 ≤ i ≤ n），为两个整数 ai 和 bi ，整数之间用一个空格分隔，表示区间 [ai; bi]（其中 1 ≤ ai ≤ bi ≤ 10000）。 输出 输出一行，如果这些区间最终可以合并为一个闭区间，输出这个闭区间的左右边界，用单个空格隔开；否则输出 no。 样例输入 5 5 6 1 5 10 10 6 9 8 10 样例输出 1 10
正确答案：
略
4、4.双端队列 定义一个双端队列，进队操作与普通队列一样，从队尾进入。出队操作既可以从队头，也可以从队尾。编程实现这个数据结构。 时间限制：1000 内存限制：65535 输入 第一行输入一个整数t，代表测试数据的组数。 每组数据的第一行输入一个整数n，表示操作的次数。 接着输入n行，每行对应一个操作，首先输入一个整数type。 当type=1，进队操作，接着输入一个整数x，表示进入队列的元素。 当type=2，出队操作，接着输入一个整数c，c=0代表从队头出队，c=1代表从队尾出队。 n <= 1000 输出 对于每组测试数据，输出执行完所有的操作后队列中剩余的元素,元素之间用空格隔开，按队头到队尾的顺序输出，占一行。如果队列中已经没有任何的元素，输出NULL。 样例输入 2 5 1 2 1 3 1 4 2 0 2 1 6 1 1 1 2 1 3 2 0 2 1 2 0 样例输出 3 NULL
正确答案：
略
