![](https://static.youtibao.com/asksite/comm/h5/images/m_q_title.png)
[主观题]
若输入的有序序列S1和S2以平衡二叉搜索树(而非序列)的方式给出,则:a)如教材344页代码12.8和346页代码12.9所示的两个median()算法,分别应做哪些调整?b)调整之后的计算效率如何?
查看答案
![](https://static.youtibao.com/asksite/comm/h5/images/solist_ts.png)
设有一个关键码的输入序列(55,31,11,37,46,73,63,02,07):
(1)从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态。若发生不平衡,指明需进行的平衡旋转的类型及平衡旋转的结果
(2)计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
A.可以使用gets函数为a输入数据
B.可以使用gets函数为s1输入数据
C.不能使用gets函数为s2输入数据
D.可以使用scanf函数为s1和s2输入数据
可将算法的时间复杂度降低到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、大于等于