A.O(n2)B.O(nlog2n)C.O(log2n)D.O(n)

Question

A．O(n2)

B．O(nlog2n)

C．O(log2n)

D．O(n)

Answer 1

正确答案：D
解析：本题考查动态查找表二叉查找树(二叉排序树)。中序遍历二叉树的过程为：若二叉树非空，则先中序遍历左子树，然后访问根结点，最后中序遍历右子树。根据二叉查找树的定义，显然，对二叉查找树进行中序遍历，得到结点元素的递增序列。在二叉查找树上进行查找的过程为：若二叉查找树非空，将给定值与根结点的关键字值相比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定值时，到根的左子树中进行查找。否则到根的右子树中进行杳找。若找到，则查找过程是走了一条从树根到所找到结点的路径：否则，查找过程终止于一棵空树。因此，在具有n个结点的二叉查找树上进行查找的算法复杂度与树的高度同阶。由于一棵二叉查找树的形态完全由输入序列决定，所以在输入序列已经有序的情况下，所构造的二叉查找树是一棵单枝树。例如，由序列(45，30，50)和序列(30，45，　50)构造的二叉查找树如图(a)、(b)所示。