对于一棵有n个结点、深度为h的二叉排序树,当查找一个指定关键字的

题目

对于一棵有n个结点、深度为h的二叉排序树,当查找一个指定关键字的元素且查找失败时,最多需进行()次比较。

如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

设有关键字n=2h-1,构成二叉排序树,每个关键字查找的概率相等,查找成功的ASL最大是n()

A.对

B.错


正确答案:B

第2题:

在具有n个结点的二叉排序树上插入一个新结点时,根据n个数据元素生成一棵二叉排序树时,其时间复杂性大致为______。

A.O(n)

B.O(n2)

C.O(log2n)

D.O(nlog2n)


正确答案:D

第3题:

从n个结点的二叉排序树中查找一个元素,平均时间复杂性大致为()。


参考答案:O(log2n)

第4题:

设二叉排序树上有n个结点,则在二叉排序树上查找结点的平均时间复杂度为()。


答案:D
解析:

第5题:

设二叉排序树中有n个结点,则在二叉排序树的平均查找长度为()。


答案:B
解析:

第6题:

在查找算法中,可用平均查找长度(记为ASL)来衡量一个查找算法的优劣,其定义为:

此处Pi为表中第i个记录被查找的概率,Ci为查找第i个记录时同关键字比较的次数,n为表中记录数。

以下叙述中均假定每一个记录被查找的概率相等,即Pi=//n(i=1,2,…,n)。当表中的记录连续存储在一个一维数组中时,可采用顺序查找与折半查找方法(折半查找要求表是按关键字有序排列的)。顺序查找时的ASL为(19),折半查找时的ASL为(20)。记录的关键字有序时,用二叉排序树查找记录,在最坏的情况下,ASL为(21)。当二叉排序树是一棵平衡树时,ASL为(22)。在平衡树上删除一个结点后可以通过旋转使其平衡,最坏的情形下需(23)次旋转。

A.O(1)

B.O(log2n)

C.O(log2n2)

D.O(nlog2n)

E.O(n)


正确答案:E

第7题:

以下关于二叉排序树(或二叉查找树、二叉搜索树)的叙述中,正确的是( )

A.对二叉排序树进行先序、中序和后序遍历,都得到结点关键字的有序序列

B.含有N个结点的二叉排序树高度为【log2n】+1

C.从根到任意二个叶子结点的路径上,结点的关键字呈现有序排列的特点

D.从左到右排列同层次的结点,’其关键字呈现有序排列的特点


正确答案:D

第8题:

由关键字序列(12,7,36,25,18,2)构造一棵二叉排序树(初始为空,第一个关键字作为根结点插入,此后对于任意关键字,若小于根结点的关键字,则插入左子树中,若大于根结点的关键字,则插入右子树中,且左、右子树均为二叉排序树) ,该二叉排序树的高度(层数)为 ( ) 。

A. 6

B. 5

C. 4

D. 3

请帮忙给出正确答案和分析,谢谢!


正确答案:C

第9题:

对于一个满二叉树,共有n个结点和m个叶子结点,深度为h,则()。


答案:D
解析:

第10题:

以下关于二叉排序树(或二叉查找树、二叉搜索树)的叙述中,正确的是( )。

A.对二叉排序树进行先序、中序和后序遍历,都得到结点关键字的有序序列
B.含有n个结点的二叉排序树高度为 log2n +1
C.从根到任意一个叶子结点的路径上,结点的关键字呈现有序排列的特点
D.从左到右排列同层次的结点,其关键字呈现有序排列的特点

答案:D
解析:

更多相关问题