2. 计算机
  3. 对于二叉查找树(Binary　Search　Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行(61)遍历可以得到一个

对于二叉查找树(Binary　Search　Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行(61)遍历可以得到一个

admin2008-11-02  81
问题 对于二叉查找树(Binary　Search　Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行(61)遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算，最坏情况下的算法复杂度为(62)。
选项 A、O(n2)
B、O(nlog2n)
C、O(log2n)
D、O(n)
答案D
解析 本题考查动态查找表二叉查找树(二叉排序树)。中序遍历二叉树的过程为：若二叉树非空，则先中序遍历左子树，然后访问根结点，最后中序遍历右子树。根据二叉查找树的定义，显然，对二叉查找树进行中序遍历，得到结点元素的递增序列。在二叉查找树上进行查找的过程为：若二叉查找树非空，将给定值与根结点的关键字值相比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定值时，到根的左子树中进行查找。否则到根的右子树中进行杳找。若找到，则查找过程是走了一条从树根到所找到结点的路径：否则，查找过程终止于一棵空树。因此，在具有n个结点的二叉查找树上进行查找的算法复杂度与树的高度同阶。由于一棵二叉查找树的形态完全由输入序列决定，所以在输入序列已经有序的情况下，所构造的二叉查找树是一棵单枝树。例如，由序列(45，30，50)和序列(30，45，　50)构造的二叉查找树如图(a)、(b)所示。
转载请注明原文地址:https://kaotiyun.com/show/mBxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)