A.i..r-1
B.i..r
C.i+1..r
D.i..r+1
A.i≤r≤j
B.i
C.i≤r
D.i
可将算法的时间复杂度降低到O(nlog2n),算法的思想是对于关键码序列(keylow,keylow+1,…,keyhigh),轮流以keyk为根,k=low,low+1,…,h,求使得|W[low-1][k-1]-W[k][high]|达到最小的k,用keyk作为由该序列构成的拟最优二叉搜索树的根。然后对以keyu为界的左子序列和右子序列,分别施行同样的操作,建立根keyk的左子树和右子树,试编写一个函数,实现上述试探算法。要求该函数的时间复杂度应为O(nlog2n)。
此题为判断题(对,错)。
A.只经过最少次数的比较就可以找到概率最大的元素
B.经过最多次数的比较就可以找到概率最小的元素
C.找到每个元素所需要的平均比较次数为最小
D.元素搜索代价的数学期望为最小
设有一个标识符序列(else,public,return,templatc),p1=0.05,p2=0.2,p3=0.1,p4=0.05,q0=0.2,q1=0.1,q2=0.2,q3=0.05,q4=0.05,计算W[i][j]、C[i][j]和R[i][j],构造最优二叉搜索树。
二叉搜索树中,然后对树进行中序遍历,并将元素按序放人数组a中,为简单起见,假设a中的数据互不相同。试编写一个函数,从一棵二叉搜索树中删除最大元素。要求函数的时间复杂性必须是O(h),其中h是二叉搜索树的高度。
设有一个关键码的输入序列(55,31,11,37,46,73,63,02,07):
(1)从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态。若发生不平衡,指明需进行的平衡旋转的类型及平衡旋转的结果
(2)计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。