计算机科学论坛--北大考研DS经典难题系列之华山论剑(狂人请进：）

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

论剑１：
06年试题中，第三题、算法辨析题中，我想print(root)不可以打印整个森林的。
我的理由是：算法“无法”递归到森林中的另一个树上。
因为这只是对一棵连通的树进行的递归，只能深度递归一棵树而已！

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

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

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

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

曾有高手用“列举法”得出这些结果。可是我的想法：

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

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

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

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

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

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用borlong在2006-11-15 19:09:00的发言：
论剑１：
06年试题中，第三题、算法辨析题中，我想print(root)不可以打印整个森林的。
我的理由是：算法“无法”递归到森林中的另一个树上。
因为这只是对一棵连通的树进行的递归，只能深度递归一棵树而已！

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

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

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

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

曾有高手用“列举法”得出这些结果。可是我的想法：

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

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

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

1.　不可以的理由是这样的，可以像你说的　那样用广度优先遍历，这个问题在已在本版
精华贴　＜06专业试题上＞，由supremgoooo大哥和ychj大哥讨论过了，他们都是牛人．

2.　我不是什么高手，这只是我的简单想法，我认为这只是个选择题，用列举法就够了，不会是考查什么特别的方法吧，所以应该不会出现（a, b, c, d ............x, y)这种数据的．我的答案少了一种情况，由 supremgoooo大哥指出了，（a, b, c, d) 一个括号都不加（共有11种）．　题目中说任意加入括号，不知道这种情况该不该算．　书上Ｐ373有，纯表的树表示，　再入表树表示，循环表树表示．应该也可以把它与树结构对应起来吧，这里说不可以有冗余括号，所以感觉到要用纯表的树型表示，书上矩形表示原子，用圆形表示子表，所以不出现只有一个孩子结点的分支结点就满要求吧．（将矩形结点看成外部结点）．我没研究过，也没这个功底啊，望其它高手指点吧．如果要用数学的话，我感到高中数学里的排列与组合的＂插板法＂（在一列数中插入n块板子，把数组分成m组的方法），用离散数学上的组合数学里面的组合计数或是鸽巢原理应该能解吧，这个我就更不懂了，还是请教Ｌｏｇｉｃｉａｎ或是其它数学高手指点吧．
3.　这个我和你有相同的问题啊．：（　不太理解题目的意思，这个问题很早就在版上由各位牛人讨论过了（主要是针对算法的），我在＜请问06年ＤＳ真题的最后一题（求中位数）到底是什么意思？＞贴子上也问过了，你可以去看看，好像里面就有针对算法的讨论的（往后翻几页就可以了）．看了一些的carroty的回帖后我认为你的理解是对的，求合并后的2n个数组的中位数，用二分法可以在Ｏ（logn)的时间内完成吧．我没细看过，我基础不好先看基础的吧，去年考了，今年还会考吗？按习题集的意思，好像如果数组元素为偶数个时，有两个中位数．　若n=10，则5　6位的数都是中位数．

4.　 DS 疑问？？？

64阶B树中，若B树包含的关键码个数是64K(64*1024)，B树的节点均
放在磁盘里，每次只能从磁盘往内存中读入一个节点，查找一个给定
关键字的纪录是，最多需要进行（）次访外操作。

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

这个也是你的问题吧，这个在　＜06专业试题＞上也有讨论，应该很详细了，属于排序的，我还没看．

下面我问个问题吧．：）　　
在数据结构第十二章　中的，　算法12.3中，ＡＶＬ树的插入算法，
大家认为这个算法怎么样？一大堆的　if else 搞的人很晕．将　value 定义为了public，
使　val 与value直接比较了，而接在进入下层递归时还是用　rp->letfptr->add()来判断子树是不是长高了．　　递归是用栈来实现的（这个栈由系统来管理），请问栈顶当前元素可以被修改吗？　如果当前栈顶元素为p(指向某ＡＶＬ树结点的指针），而Ｐ结点的平衡因子为2或－2，不平衡需要调整，但调整后子树结点就不是Ｐ了（假如为q)．请问这时能将递归栈中的栈顶元素p 改为q吗？算法的倒数第　6　7行有，rp=RR_.........和rp=RL_．．．．，这是用来改变栈顶元素指针的吗？（递归时需要将rp和val参数也压入栈中吧）．如果不能的话，那我就不知道这个算法的递归究竟是怎么实现的了．望高手指点．

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

补充一下，看错了广义表那题不是选择题．　中位数那题，张老师已将它选为本科生作业了，要得到官方版的讲解和答案的，可以去找北大大二的本科生，因为其它读者没有密码．
　他们刚刚期中考试，这个应该也有参考价值．
　有在北大或有同学在北大读计算机的可以去找这些信息．如果那们能得到的话，麻烦发到本版啊．谢谢了．

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

问题2:好象是用组合数学里的"卡特朗"数,离散教材有关于这方面的内容.集合论部分有个例题也用到了这个知识点
问题3:是算法导论的课后习题,群里讨论过~

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用chenminyi在2006-11-25 22:09:00的发言：
问题2:好象是用组合数学里的"卡特朗"数,离散教材有关于这方面的内容.集合论部分有个例题也用到了这个知识点
[/quote]

可否具体点呢？写出算式呢？我智商不怎么高啊！所以只能打破砂锅问到底了！

[quote]以下是引用chenminyi在2006-11-25 22:09:00的发言：
问题3:是算法导论的课后习题,群里讨论过~

可否给个链接呢？拜谢啊！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

我也好久没接触组合数学了,我帮你找了一下,在王树禾的《图论》上找到了这个题(2.6),离散教材上Catalan数的介绍在388页.
《图论》上和教材上只说了2叉树的树木是c(n)(c(n)为catalan数),广义表可以是任意树,当时没看清楚,不好意思~

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

后来考虑了一下,还是得用Catalan数
假设长度为n的广义表第一个字符为A
则A可包含它后面紧接着的0~n-1个字符作为其内部字符,假设包含i个,还剩n-1-i个作为A的兄弟.
再对i个结点和n-1-i个结点进行广义表递归分割.这样令总数为长度n的函数f(n),有
f(n) = f(0)f(n-1) + f(1)f(n-2) + ... + f(n-1)f(0)
上式与catalan数的递推公式极其相似,可表示成才catalan数,最终用catalan数的公式进行计算

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

f(0) = f(1) = 1,由归纳法可证明f(n) = h(n+1) = (2n)!/((n+1)!*n!)

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用chenminyi在2006-11-29 10:54:00的发言：
f(0) = f(1) = 1,由归纳法可证明f(n) = h(n+1) = (2n)!/((n+1)!*n!)

但枚举的结果是f(4)=11啊。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

f(0)*f(3)           f(3)*f(0)           f(1)*f(2)           f(2)*f(1)
------------------------------------------------------------------------------------
A(B,C,D)           A,B,C,D            A(B),C,D           A(B,C),D
A(B,C(D))         A,B,(C(D)          A(B),C(D)          A(B(C)),D
A(B(C),D)         A,B(C),D
A(B(C,D))         A,B(C,D)
A(B(C(D)))       A,B(C(D))
一共有14种等于c(4) ,符合上面的公式!你看是不是?


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	7,628.906ms