设m≥3为奇数。试对任意的h>0,构造一棵高度为h的m节B-树,使得若反复地对该树交替地执行插入、删除操作,则每次插入或删除操作都会引发h次分裂或合并。
第1题
设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]的首一的最小公倍式与最大公因式.
第2题
种解决冲突的方法构造哈希表,并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。①线性探测法;②链地址法。
第3题
第4题
考查任意阶的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。
第5题
设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的一个栈混洗?若是,试给出证明;否则,试举一反例。
第6题
第8题
第9题
设A,B为任意集合,证明:
(3)针对(2)举一反例,说明P(A)∪P(B)=P(A∪B)对某些集合A和B是不成立的。
第10题
设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);