1) 填空题第一道全错,你多虑了。在内存中,其实n,D,P都是一样的存储大小,但是因为题目并没有告诉你n,D之类的值需要多大空间存储。你假设为1,其实你是有一定的想法,但是不严谨,老师会认为你概念并不清楚。因此你只需去掉你多余的考虑就全对了。

2) 第三大题的第二小问,修改算法题错了。
    注意题意,在算法原有框架的基础上改写。
    你的算法中出现了new结点的字样。是在重新建树吗？肯定是不得分的。
    这个题有两种修改办法: 一种是用消除尾递归的办法; 另一种是不消除尾递归,直接分叉递归。
    
    

这棵树是这样的：

第0层：*（1点）W

第1层：****（4点）W，R

第2层：********。。。。**（20点）W，R

第3层： ********。。。。。。** （100串） R
后面的R，W表示读，写。每一条记录都要从第3层移动动到第一层：先从第3层读出写到第2层，从第2层读出写到第1层，从第1层读出写到第0层。这就60000次。但是，我考虑到归并树的结构，根节点实际上只有1个节点，所以它还要被读出来写到结果串中，这又20000次，所以共80000次。

ychj大哥：
（1）填空题第一道，我上面写的是我去年考试时写的答案，如果让我现在写，我的答案是：DE+2，（2P+E）n+3。这是我个人对这道题的理解，当然我认为写DE，（2P+E）n是有一定道理的，但是我不会这样写。

（2）第三大题的第二小问，这道题改法太多了。我认为你给的解法：“这个题有两种修改办法: 一种是用消除尾递归的办法; 另一种是不消除尾递归,直接分叉递归。”是这道题最正确的解法！

我意思是说，别人可以认为它的结果是DE，（2P+E）n，从而认为我写的错误。但是你应该能理解我的思路。

我这样写是因为我看到这个题后首先想到的是表定义的类，私有变量里需要包含对表访问时所需要的指针，一旦这个类被实例化，这些指针显然也是需要空间的。

数据结构有时候是很严谨的：例如我认为无头表中的curr可以指向有头表中的fence，但是张铭老师说这样不行。这件事我至今想不通。原因可能就是我只从课本出发，没有实践过吧。在实际编程中的一些约定俗成的东西，你肯定比我体会深。

再说这个题，大家都认为是DE，（2P+E）n，那就是它吧，但是假如考场上遇到这个题，我是会坚持写DE+2，（2P+E）n+3的。

以下是引用ychj在2006-11-11 2:01:00的发言： Sorry, Supremgoooo老弟是不是生气了？ 我只是谈我对问题的观点,并没有任何攻击的意思,请别误会。 如果措辞有不妥,请谅解。

恩，中位数这道题太深刻了。我考前太自信，想着专业课没有题不会做的，答卷时我认为我这个题一定能做出来，所以就一直在做。以至于最后在35分钟内疯狂的写完OS。

06年我差40多分，就算专业分数再高点也没用。失败原因主要是心态问题，12月我发现数学，英语还有很多没看，加上各科期末考试比较忙，而且我3年结束本科的计划也动摇了——因为我发现自己在很多地方都达不到研究生水平，所以就不想再复习考研了。

07考db：DM/OLAP

以下是引用computerlover在2006-11-11的发言： 请问Supremgoooo兄，广义表加括号那题，有11种不同的广义表，是怎么求得的，我只能得到10种，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))  加两对括号． 请问还有那种我没写出。谢谢了！ 兄弟今年考的怎么样啊，求中位数那题就做个一个多小时，专业课还答的不错啊。你考的是那个方向啊？

其使我迷惑的只是那句解释“一趟指归并树的一层”，你的答案是共需3趟，我知道你是指那棵归并树有3层，也就是你把那句解释中的“归并树”作为一个整体，一个名词来理解，我一开始也是这样，所以我最初的答案也是3趟，但后来我有想了下：把归并作为动词，把“树的一层”作宾语的理解（因为它是问“共需进行____趟”而不是“共需设置____趟”），：）即对每层树的一个状态的一次归并作为“一趟”.在然后我也不知道该怎么算趟数了……郁闷。
共计80000次访外是正确的。

（这是从考研论坛上，清华大学版面上ＺＴ）

我应该是这样的人吧，但只是眼下还有2个多月了，而政治．英语还．．．．．．．．．
尽量努力吧，争取多考点．

1.第四题我认为第一个空是3，（我的思路是5路归并第一趟由100个串变为20个串，然后用三趟归并完），但我第二个空认为是60000，（我认为每一趟归并就是全部的记录读一次，然后写一次，故3×2×10000，不知哪里不完善？）望解答！

2.然后就是那个简答题第一题了：我看了书上写的是把该节点的路径上的父结点连接在根节点上，所以我的答案是：
    a          d
                 e      f     j
                h      g    b     c
                                    k
   不知道我是不是书上的概念理解错了？

3.然后说一下算法辨析的第二问：
修改为：
前面都不动，下面的修改：
for(TreeNode<T> *tmp=rt;tmp!=null;tmp=tmp->RightSibling())
      Print(tmp->LeftMostChild());
完

4.我用的空位二填写的代码是：break，我记得break是跳出本次循环，不知道continue的意思也是如此吗，还是另有深意，或者break不是如此使用？

5.最后一题吗，我认为不是很难，就是类似于二分查找的思路，不过就是两个数组同时进行，一个数组的中间值大于另一个的，则两个数组的left，right同时变，这样保证每次变化元素的总个数总是100，不过不知道在考试的紧张环境下能否做得出来。
不过对于第二问我有些疑惑，证明时间复杂性，不好写啊！要是我考试的时候写的话估计就会用决策树加一些文字描述。理论证明没有啦！