传说某大型软件公司巨难面试问题(数据结构)

Question

n个元素依次入栈,入栈后可以立即出栈,则有多少种可能的(正确的)出栈序列?
例如:123,只能有123,321,213,132,231

Answer 1

一个Catalan数的问题而已，答案已经是公认的了.数据结构书上从推导到答案都有的。

Answer 2

多看书就知道的。别太羡慕会vc会写driver会系统底层的“牛人”……

Answer 3

C(2n,n)-C(2n,n-1)
不好意思，组合C不会打，上下标不知道怎么弄，2n是下标，n和n-1是上标，

Answer 4

1/(n+1)*C(2n,n).
这题不是那么简单的，n个数，当第n个数最先出栈的时候，只有一种可能顺序：n,n-1,n-2,...1
同理当第x个数出栈的时候，除了比x先出栈的数外，其余小于x的数也只能按从大到小顺序排列了（中间可以插入比x大的数）