免费版：华文慕课-数据结构栈与队列课后题
网络课课后题
1、设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6 个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是 3
解析：不难，在本子上写写画画就行
2、双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。现有4个不同的元素顺序输入到双端队列，那么可以得到 8 种不同的排列。
解析：第一个元素从左或右入队没有区别，以后每个元素都有从左和从右两种入队方式，即有2^{x-1}种方法。不要多余的去考虑中途有删除的情况。
3、编号为1，2，3，4的四辆列车，顺序开进一个栈式结构的站台；则开出车站的顺序有______种可能。 注释：例如 1, 2, 3, 4 或 4, 3, 2，1 就是其中两种可能出站序列；而 4, 3, 1, 2 是 非法序列。
解析:
出栈次序是经典的问题，与组合数学中的卡特兰数密切相关，以下只介绍朴素的思路。
先进站的车可以先开，也可以后开。只有一种情况不可能：编号大的车开出后，比其编号小的车反序开出。也即编号大的车开出后，编号比其小的车只能由大到小依次开出（中间可以插入编号更大的车，但此车后面的编号小的车也要遵守此规则）。例如312的开出顺序是不可能的。对所有车进行全排列共有4！ = 24种出法。4开头的只能有一种：4321。所以少了3的全排列-1=5种（4312,4213,4231,4132,4123）。
3开头时，必须先2后1开出，先1后2时4的位置有三种：3124、3142、3412，所以少了三种。
1或2开头时，后面的车如果是4，则最后两辆必须是3、2或3、1。所以又少了1423、2413两种。
总共少了5+3+2=10种，有24-10=14种开出法。
下面用+表示进站，-表示出站：
1234：1+ ;1- ;2+ ;2- ;3+ ;3- ;4+ ;4-
1243：1+ ;1- ;2+ ;2- ;3+ ;4+ ;4- ;3-
1324：1+ ;1- ;2+ ;3+ ;3- ;2- ;4+ ;4-
1342：1+ ;1- ;2+ ;3+ ;3- ;4+ ;4- ;2-
1432：1+ ;1- ;2+ ;3+ ;4+ ;4- ;3- ;2-
2134：1+ ;2+ ;2- ;1- ;3+ ;3- ;4+ ;4-
2143：1+ ;2+ ;2- ;1- ;3+ ;4+ ;4- ;3-
2314：1+ ;2+ ;2- ;3+ ;3- ;1- ;4+ ;4-
2341：1+ ;2+ ;2- ;3+ ;3- ;4+ ;4- ;1-
2431：1+ ;2+ ;2- ;3+ ;4+ ;4- ;3- ;1-
3214：1+ ;2+ ;3+ ;3- ;2- ;1- ;4+ ;4-
3241：1+ ;2+ ;3+ ;3- ;2- ;4+ ;4- ;1-
3421：1+ ;2+ ;3+ ;3- ;4+ ;4- ;2- ;1-
4321：1+ ;2+ ;3+ ;4+ ;4- ;3- ;2- ;1-;答案： 14
4、现有中缀表达式E=((100-4)/3+3*(36-7))*2。以下哪个是与E等价的后缀表达式？
A、( ( 100 4 – ) 3 / 3 ( 36 7 – ) * + ) 2 *（含括号了）
B、* + / – 100 4 3 * 3 – 36 7 2
C、100 4 – 3 / 3 36 7 – * + 2 *
D、* ( + / ( – 100 4 ) 3 * 3 ( – 36 7 ) ) 2（含括号了）
解析
后缀表达式：运算符号位于两个运算数之后。完全不需要括号。
题中中缀表达式用二叉树表示如图：
然后进行后序遍历
5、以下循环队列的实现方式中，长度为n的队列，所能容纳的元素个数也为n的有:
A、只用front和rear两个指针标记队列的头和尾，两个指针均为实指
B、用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数
C、用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空
D、只用front和rear两个指针标记队列的头和尾，两个指针均为虚指
解析
只用front和rear两个指针标记队列的头和尾，无法区分空队列和满队列两种状态，所以只能容纳n-1个元素。而增加len或empty都可以区分这两种状态，因此可以容纳n个元素