设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为

admin2009-01-19 45

问题设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为

选项 A、O(1)
B、O(log₂n)
C、O(n)
D、O(n log₂n)

答案2

解析平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1，若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点韵左右子树的深度之差都不超过1，则可以证明它的深度和log₂n是同数量级的(N为结点个数)。因此，它的平均查找长度也和log₂n同数量级。

转载请注明原文地址:https://jikaoti.com/ti/wJQ7FFFM

本试题收录于：三级数据库技术题库NCRE全国计算机三级分类

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为

三级数据库技术

NCRE全国计算机三级

Pentium微处理器工作在实地址模式，使用A19-A0的20根地址线，该处理器支持的最大物理地址空间为_______。

下面选项中错误的说法是(　　　)。

PC机使用的键盘是一种非编码键盘，键盘本身仅仅识别按键的位置，向PC机提供的是该按键的【　　】码，然后由系统软件把它们转换成规定的编码，如ASCII码。

按照Pentium微处理器的存储器分页管理机制，线性地址00COFFFCH　的页表基地址是【　　】。

在PC机中，为使微处理器与主存(用DRAM芯片构成的)之间的速度得以匹配，目前采用的主要方法是在二者之间加上二级高速缓存(L2Cache)。这种二级高速缓存是用______芯片构成的。

在下列进程调度算法中，可能引起进程长时间得不到运行的算法是(　　　)。

计算机病毒是一种具有破坏性的计算机程序，它是

电动机的起动转矩必须大于负载转矩。若软起动器不能起动某负载，则可改用的起动设备是()。

技术创新是企业创新的重要内容，是一个整体的动态概念，包括()过程。

延伸率表示钢材的以下哪种性能?[2011—022，2010—014]

下面四个选项中正确的是()。

从施工生产方面来选择价值工程对象时，一般首先选择的工程产品具有的共同特征是()。

天文学属于导游人员的()

Theworkers’demandsare_________：They’reaskingforonlyasmallincreaseintheirwages.

“随着新生产力的获得……人们也就会改变自己的一切社会关系，手推磨产生的是封建主义的社会，蒸汽磨产生的是工业资本家的社会。”这段话表明科学技术是()。

根据以下资料，回答问题。中非贸易额2008年突破了1000亿美元，其中中国对非洲出口508亿美元，自非洲进口560亿美元。2000年至2008年，中非贸易占中国对外贸易总额的比重由2．2％升至4．2％。2009年，中非贸易额910．7亿美元。20

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均检索长度为

三级数据库技术

NCRE全国计算机三级

Pentium微处理器工作在实地址模式，使用A19-A0的20根地址线，该处理器支持的最大物理地址空间为_______。

下面选项中错误的说法是( )。

PC机使用的键盘是一种非编码键盘，键盘本身仅仅识别按键的位置，向PC机提供的是该按键的【 】码，然后由系统软件把它们转换成规定的编码，如ASCII码。

按照Pentium微处理器的存储器分页管理机制，线性地址00COFFFCH 的页表基地址是【 】。

在PC机中，为使微处理器与主存(用DRAM芯片构成的)之间的速度得以匹配，目前采用的主要方法是在二者之间加上二级高速缓存(L2Cache)。这种二级高速缓存是用______芯片构成的。

在下列进程调度算法中，可能引起进程长时间得不到运行的算法是( )。

计算机病毒是一种具有破坏性的计算机程序，它是

电动机的起动转矩必须大于负载转矩。若软起动器不能起动某负载，则可改用的起动设备是()。

技术创新是企业创新的重要内容，是一个整体的动态概念，包括()过程。

延伸率表示钢材的以下哪种性能?[2011—022，2010—014]

下面四个选项中正确的是()。

从施工生产方面来选择价值工程对象时，一般首先选择的工程产品具有的共同特征是()。

天文学属于导游人员的()

Theworkers’demandsare_________：They’reaskingforonlyasmallincreaseintheirwages.

“随着新生产力的获得……人们也就会改变自己的一切社会关系，手推磨产生的是封建主义的社会，蒸汽磨产生的是工业资本家的社会。”这段话表明科学技术是()。

根据以下资料，回答问题。中非贸易额2008年突破了1000亿美元，其中中国对非洲出口508亿美元，自非洲进口560亿美元。2000年至2008年，中非贸易占中国对外贸易总额的比重由2．2％升至4．2％。2009年，中非贸易额910．7亿美元。20

下面选项中错误的说法是(　　　)。

PC机使用的键盘是一种非编码键盘，键盘本身仅仅识别按键的位置，向PC机提供的是该按键的【　　】码，然后由系统软件把它们转换成规定的编码，如ASCII码。

按照Pentium微处理器的存储器分页管理机制，线性地址00COFFFCH　的页表基地址是【　　】。

在下列进程调度算法中，可能引起进程长时间得不到运行的算法是(　　　)。