UC知道问几道关于数据结构题
来源：百度知道 编辑：UC知道 时间：2024/05/25 04:40:06
[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]
您给看看我哪点做错了，谢谢了
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。如若把后面这部分