设m≥3为奇数。试对任意的h＞0，构造一棵高度为h的m节B-树，使得若反复地对该树交替地执行插入、删除操作，则每次插入或删除操作都会引发h次分裂或合并。

设f(x)，g(x)∈Px,f(x)g(x)≠0,令{f(x)}={h(x)∈P|x|f(x)h(x)}

试证:

1)是P[x]的线性子空间:

2)

3)

这里f(x).g(x).(f(x)g(x))分别为f(x),g(x]的首一的最小公倍式与最大公因式.

种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASL_succ和ASL_unsucc。①线性探测法;②链地址法。

考查任意阶的B-树T。

a)若T的初始高度为1，而在经过连续的若干次插入操作之后，高度增加至h且共有n个内部节点，则在此过程中T总共分裂过多少次？

b)在如上过程中，每一关键码的插入，平均引发了多少次分裂操作？

c)若T的初始高度为h且含有n个内部节点，而在经过连续的若干次删除操作之后高度下降至1，则在此过程中T总共合并过多少次？

d)设T的初始高度为1，而且在随后经过若干次插入和删除操作——次序任意，且可能彼此相间。试证明：若在此期间总共做过S次分裂和M次合并，且最终共有n个内部节点，高度为h，则必有：S-M=n-h。

设B为A=(1，2，3，...，n)的任一排列。

a)试证明，B是A的一个栈混洗，当且仅当对于任意1≤i＜j＜k≤n，P中都不含如下模式：{...，k，...，i，...，j，...}

b)若对任意1≤i＜j＜k＜n，B中都不含模式{...，j+1，...，i，...，j，...}，则B是否必为A的一个栈混洗？若是，试给出证明;否则，试举一反例。

c)若对任意1＜i＜j＜k≤n，B中都不含模式{...，k，...，j-1，...，j，...}，则B是否必为A的一个栈混洗？若是，试给出证明;否则，试举一反例。

设A，B为任意集合，证明：

(3)针对(2)举一反例，说明P(A)∪P(B)=P(A∪B)对某些集合A和B是不成立的。

设X，Y是两个相互统计独立的二元随机变量，其取“0”或“1”的概率为

等概率分布。定义另一个二元随机变量Z，而且XYZ=(一般乘积)，试计算：

(1)H(X)，H(Y),H(Z);

(2)H(XY)，H(XZ)，H(YZ)，H(XYZ);

(3)H(X|Y)，H(X|Z)，H(Y|Z)，H(Z|X)，H(Z|Y);

(4)H(X|YZ)，H(Y|XZ)，H(Z|XY);

(5)I(X;Y)，I(X;Z)，I(Y;Z);

(6)I(X;Y|Z)，I(Y;X|Z)，I(Z;X|Y)，I(Z;Y|X);

(7)I(XY;Z),I(X;YZ)，I(Y;XZ);