---------------------
请大侠给点思路，行吗？拜谢啦！

（a,b,c,d）任意加入括号可以组成多少个不同的广义表？（06年北大ds试题。）

---------------------
这个问题的解法，再ds书中有吗？还是数学的解法啊？又到底怎么解呢？
请大侠指点思路。谢谢。

PS：求人不如求己，版面上的帖子不算多，翻一遍就能找到了。而且帖子列表的右上角有一个精华按钮（不是正上方的“精华版”，而是右上角“精华 | 在线 | 事件 | 权限 | 管理”这一排按钮的第一个），重要的帖子在那里都能找到。

以下是引用borlong在2006-10-30 19:50:00的发言： 疑问3： 哪儿有06年北大ds & os 权威答案下阿？我做了一份，不知道对错啊？？？？ 大侠指点以下吧？把网址写下来，行吗？拜谢！

疑问2：

（a,b,c,d）任意加入括号可以组成多少个不同的广义表？（06年北大ds试题。）

应该是十一章广义表的内容
　下面发了下我的答案吧：
　1 (a ,(b ,c), d)   2 ((a, b, c) ,d)   3 (a, b),c d)  4 (a,(b, c, d))  5(a, b,(c, d))  只加一对括号
　6 ((a, b), (c, d))　 7 (((a, b), c), d)   8 ((a, (b, c)), d)   9 (a, (b, (c, d)))
10 (a, ((b, c), d))  加两对括号．

06年真题数据结构最后一题也说的不明不白的，　处于第n个位置的数为中位数，那么在2n个数中，只有一个中位数，那又怎么求Ａ和Ｂ的中位数？

6次，根节点1个关键码，第二层31*2=62个关键码，第三层32*31*2以此类推，
第n层有2*(32^（n-2）)*31个关键码，完全树
不难算出从第一层到最后一层，一共有5层，最后一层不满，但得算上，
于是：
在B树上要有5次访外，但别忘了B树的叶子是指向磁盘文件的，于是查找给定关键字一共需6次访外。

这些不同的广义表，只能用“列举法”来一一写出来吗？
这样很容易丢失啊？如果（a,b...z）那不是要死人啊？
请问：能否用一些数学理论方法呢？
譬如：将广义表对应成“树”等或者什么的？
然后来计算不同的树的数目，这样便可以理论化了啊？
可是，郁闷的是：广义表是和树一一对应的吗？根据我的计算，不是的啊！
那么请问：大侠们，你们想到了吗？？？？？？？

对不起，这些天在疯狂的看书啊！所以没有来上网。：）

修改的算法思路：可以用广度遍历森林。

我的理由对吗？请大侠指点阿。拜谢！

这道题，我想题目意思是说：当用A和B来重新组合成一个“非降序”数组时候，
求出这个新数组的中位数吧！否则，分别求出A和B的中位数，不就是重复了吗？

我的算法：
先对A和B进行归并到新数组C中，大小是2n。此时，C便有序。
直接在C选出中间的数值，即C[n]。

在这个归并的程序中，算法只是一个循环即可，所以复杂度为O(n).

可是-----什么是最坏的情况呢？有怎么算出来O(logn)呢？
这一点，我困惑。
请大侠指点

拜谢teng_t1986哦。

指出一点: B树中是不会存在最后一层不满的情况的。

dear teng_t1986,您 所说的不难算出，是怎么个算法，是把根节点 加上 第二层上的节点
再加上 第三层的节点 等等 之和 小于或等于 64k 吗？ 还是按照你的算法 只要最后一层节点数目 小于或等于 64k 呢？

请赐教！！
我正在迷雾中啊！

中位数！ 是中间位置的元素（只考虑位置）。还是 元素的大小（只考虑大小）位于中间数啊？

如果考虑位置，不就是O（n）,如果后者，当然是O(logn)啦。

然而 教材中推导分治法的复杂度有些复杂！
那么在考试中，如果要分析这个复杂度，也要在考试卷上写出这些过程吗？
这个问题，请大侠们赐教啊！！！！

位置????
那么复杂度不就是O(n),因为直接计算不就行啦！
至于O(logn)又是怎么理解的呢？？？

大家，新年快乐啊！！！！