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

admin2009-01-19 51

问题设平衡的二叉排序树(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://kaotiyun.com/show/uLcZ777K

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

在虚拟存储器中，当程序正在执行时，由(　　　)完成地址转换。

下面关于PC机连网接入技术的叙述中，错误的是

Windows98安装后会在硬盘上生成一个较复杂的文件夹结构，用户如果能对之有所了解，则有利于对系统进行管理和维护。在下列文件夹中，哪个文件夹的内容与开始菜单中的“文档”子菜单的内容相对应?

Pentium微处理器的寄存器组是在8086/8088微处理器的基础上扩展起来的。下面是关于Pentium微处理器中寄存器组的叙述，其中正确的是

使用8259A进行中断控制时，CPU首先应对8259A内部的各寄存器写入相应的【　　】命令字ICW和操作命令字OCW，即要对8259A进行初始化编程。

Pentium　微处理器在保护模式下，当段描述符中设定粒度G=0，则段的大小最大可达到(　　　)。

以太网是采用总线结构的一种局域网。在以太网中，所有的结点(计算机或其他设备)通过以太网卡和电缆联结到一条总线上，并采用______方式进行相互间的数据通信。

把高级程序设计语言编制的源程序转换成机器能执行的程序，这是由系统软件编译器和______完成的。

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

为保证胎盘和肾脏的血液灌流量，孕妇睡眠时应采取【】

毒蛇咬伤最有效的早期治疗方法是()

牙的组成部分不包括

患者男，15岁。胸闷胸痛2个月，伴低热1个月余，患者行MR扫描图像如下，最有可能的诊断是

忠者，男性，58岁，诊断为急性心肌梗死，医嘱要求查肌酸激酶同工酶(CK-MB)，护士制订的适宜的采血时间是

某企业转让一座库房，已知其原价为100万元，已提折旧80万元，转让价格10万元，并取支票一张。下列说法中正确的有(　　)。

企业当期产生的外币报表折算差额，应在利润表“财务费用”项目中列示。()

东华门美食坊夜市是北京最著名的小吃夜市，商户统一的标志是()

(1)吃药；(2)吃烧烤；(3)腹泻；(4)医院检查；(5)康复。就给出的五个事件，排列出最合乎逻辑的一种事件顺序：（）。

下列文言句式特点与其他三项不同的是()。

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

三级数据库技术

NCRE全国计算机三级

在虚拟存储器中，当程序正在执行时，由( )完成地址转换。

下面关于PC机连网接入技术的叙述中，错误的是

Windows98安装后会在硬盘上生成一个较复杂的文件夹结构，用户如果能对之有所了解，则有利于对系统进行管理和维护。在下列文件夹中，哪个文件夹的内容与开始菜单中的“文档”子菜单的内容相对应?

Pentium微处理器的寄存器组是在8086/8088微处理器的基础上扩展起来的。下面是关于Pentium微处理器中寄存器组的叙述，其中正确的是

使用8259A进行中断控制时，CPU首先应对8259A内部的各寄存器写入相应的【 】命令字ICW和操作命令字OCW，即要对8259A进行初始化编程。

Pentium 微处理器在保护模式下，当段描述符中设定粒度G=0，则段的大小最大可达到( )。

以太网是采用总线结构的一种局域网。在以太网中，所有的结点(计算机或其他设备)通过以太网卡和电缆联结到一条总线上，并采用______方式进行相互间的数据通信。

把高级程序设计语言编制的源程序转换成机器能执行的程序，这是由系统软件编译器和______完成的。

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

为保证胎盘和肾脏的血液灌流量，孕妇睡眠时应采取【】

毒蛇咬伤最有效的早期治疗方法是()

牙的组成部分不包括

患者男，15岁。胸闷胸痛2个月，伴低热1个月余，患者行MR扫描图像如下，最有可能的诊断是

忠者，男性，58岁，诊断为急性心肌梗死，医嘱要求查肌酸激酶同工酶(CK-MB)，护士制订的适宜的采血时间是

某企业转让一座库房，已知其原价为100万元，已提折旧80万元，转让价格10万元，并取支票一张。下列说法中正确的有( )。

企业当期产生的外币报表折算差额，应在利润表“财务费用”项目中列示。()

东华门美食坊夜市是北京最著名的小吃夜市，商户统一的标志是()

(1)吃药；(2)吃烧烤；(3)腹泻；(4)医院检查；(5)康复。就给出的五个事件，排列出最合乎逻辑的一种事件顺序：（）。

下列文言句式特点与其他三项不同的是()。

在虚拟存储器中，当程序正在执行时，由(　　　)完成地址转换。

使用8259A进行中断控制时，CPU首先应对8259A内部的各寄存器写入相应的【　　】命令字ICW和操作命令字OCW，即要对8259A进行初始化编程。

Pentium　微处理器在保护模式下，当段描述符中设定粒度G=0，则段的大小最大可达到(　　　)。

某企业转让一座库房，已知其原价为100万元，已提折旧80万元，转让价格10万元，并取支票一张。下列说法中正确的有(　　)。