问几道关于数据结构题

Question

例：改进的kmp算法中字符串“abaababa”的nextval数组值是[]
[A]01010101 [B]01122343 [C]01234567 [D]01021040
例：六个不同元素依次进栈，能得到[ ]种不同的出栈序列
[A]42 [B]82 [C]132 [D]192
例：一棵深度为7的满二叉树共有[ ]个非终端结点。
[A]31[B]63[C]127[D]225

能否给出解题步骤
请教“大鱼bigfish ”
1、能否告诉我“出栈序列”的公式在严薇敏书里哪个地方能找到吗？我翻了半天也没看见。
2、关于kmp改进算法您给看一下，我始终得不出b的选项
我的做法：
1 2 3 4 5 6 7 8
a b a a b a b a
0 1 1 2 2 3 4 3 //next[j] 我的计算里，b选项是next的算法
0 1 0 2 1 0 4 0 //nextval[j]
您给看看我哪点做错了，谢谢了

Answer 1

1. B 见严蔚敏书中模式匹配KMP算法例题，方法一样，这里不详述
2. C 套公式.
[1/(n+1)]C(n 2n)=(1/7)C(6 12)=(1/7)(12*11*10*9*8*7)/(6*5*4*3*2*1)=132
3. B 非终端结点数=全部结点数-终端结点数=2^n-1)-2^(n-1)=2^7-1-2^(7-1)=127-64=63
-------------------
对不起。看错题目了，呵呵。第1题的答案是D,没注意说的是改进的算法。
---
出栈序列统计公式在严的书里没有，但是可以推导：
问题：编号为 1 到 n 的 n 个元素，顺序的进入一个栈，则可能的出栈序列有多少种？
对问题的转化与思考：n 个元素进栈和出栈，总共要经历 n 次进栈和 n 次出栈。这就相当于对这 2n 步操作进行排列。
一 个模型：一个 n*n 的正方形网格，从左上角顶点到右下角顶点，只能向右走和向下走。问共有多少种走法。如果将向右走对应上述问题的进栈，向下走对应上述问题的出栈，那么，可以视此模型为对上述问题的具体描述。而解决此问题，只要在总共从左上角到右下角的2n步中，选定向右走的步数，即共有C(n 2n)中走法。
但是存在一个问题，如果走法越过了对角线，那么对应到上述问题是出栈数比入栈数多，这是不符合实际的。
对以上模型进行处理，对角线将以上正方形网格分成两部分，只留下包含对角线在内的下半部分，那么就不会出现越过对角线的问题。
问题等价于：n个1和n个0组成一2n位的2进制数，要求从左到右扫描，1的累计数不小于0的累计数，试求满足这条件的数有多少？
解答： 设P2n为这样所得的数的个数。在2n位上填入n个1的方案数为 C（n 2n）
不填1的其余n位自动填以数0。从C（n 2n）中减去不符合要求的方案数即为所求。
不合要求的数指的是从左而右扫描，出现0的累计数超过1的累计数的数。

不合要求的数的特征是从左而右扫描时，必然在某一奇数2m+1位上首先出现m+1个的累计数，和m个1的累计数。
此 后的2（n－m）－1位上有n－m个1，n－m－1个0。如若把后面这部分2（n－m）－1位，0与1交换，使之成为n－m个0，n－m－1个1，结果得 1个由n＋1个0和n－1个1组成的2n位数，即一个不合要求的数对应于一个由n－1个0和n＋1个1组成的一个排列。
反过来，任何一个 由n＋1个0，n－1个1组成的2n位数，由于0的个数多2个，2n是偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面的部分，令0 和1互换，使之成为由n个0和n个1组成的2n位数。即n＋1个0和n－1个1组成的2n位数，必对应于一个不合要求的数。

用上述方法建立了由n＋1个0和n－1个1组成的2n位数，与由n个0和n个1组成的2n位数中从左向右扫描出现0的累计数超过1的累计数的数一一对应。

例如 10100101

是由4个0和4个1组成的8位2进制数。但从左而右扫描在第5位（显示为红色）出现0的累计数3超过1的累计数2，它对应于由3个1，5个0组成的10100010。
反过来 10100010 对应于 10100101
因而不合要求的2n位数与n＋1个0，n－1个1组成的排列一一对应，故有
P2n ＝∫n =C（n 2n）— C（n＋1 2n）=(2n)!/[(n+1)n!]=[1/(n+1)]C(n 2n)
这个结果是一个“卡塔兰数”Catalan，在组合数学中有介绍，可以参阅有关资料。
---------------------
另外一种方法：
编号为1,2,3,4,5,6的六个数，顺序压入堆栈，可能的出栈序列有多少种？
解：将所有可能的操作过程用op(1,2,...,n)表示。(n=6)
则op(1,2,...,n)只可能是这样一个序列:
push 1
op(2,3,...,k)
pop 1
op(k+1, k+2, ..., n)
这里，k可以是1, 2, ..., n。
根据数学上的乘法原理，可知op(1,2,...,n)的可能性有：
count_op(n) = for (k = 1; k <= n; ++k) count_op(k-1)*count_op(n-k);
所以：// 以下count_op简记为op
op(0) = 1
op(1) = 1
op(2) = op(0)*op(1) + op(1)*op(0) = 2
op(3) = op(0)*op(2) + op(1)*op(1) + op(2)*op(0) = 5
op(4) = op(0)*op(3) + op(1)*op(2) + op(2)*op(1) + op(3)*op(0) = 14
op(5) = op(0)*op(4) + op(1)*op(3) + op(2)*op(2) + op(3)*op(1) +op(4)*op(0) = 42
op(6) = op(0)*op(5) + op(1)*op(4) + op(2)*op(3) + op(3)*op(2) + op(4)*op(1) + op(5)*op(0) = 132

Answer 2

我的答案:
1.A
Next[] 0 1 1 2 2 3 4 3
Nextval[]0 1 0 2 1 0 4 0
2.132
C(2n n)/(n+1)种出栈序列
3.127个,也就是求深度为6的满二叉树的结点个数