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

admin2009-01-19 99

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

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

答案2

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

转载请注明原文地址:https://kaotiyun.com/show/TTcZ777K

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

在80×86宏汇编语言中，下列指令性语句的格式正确的是

有多种技术指标可用来衡量计算机的优劣，下述哪些可作为计算机技术指标?Ⅰ．位数Ⅱ．速度Ⅲ．容量Ⅳ．带宽Ⅴ．版本Ⅵ．可靠性

在Windows98中，msdos.sys　是一个十分重要的系统配置文件，通过对其修改(例如修改BootMulti、BootGUI、BootMenu　等命令)可以改变Windows98的启动方式。如果要使Windows98　启动时直接进入到DOS状态，该文

软盘存储器由软盘片、【　　】和软盘适配器3部分组成。目前PC主要使用5英寸(1.44MB)和25英寸(低密360KB，高密1.2MB)两种。每个磁道又分为若干个段(段又叫扇区)。

假设(AL)=12H，执行OR　AL，AL指令后，ZF和OF的状态分别为(　　　)。

当成千上万台终端设备需要相互通信时，它们之间采用固定的连接是极不经济的。解决方法是在要进行通信的终端之间建立临时连接，通信结束后再拆除连接，实现这种功能的设备称为

输入设备用于向计算机输入信息。下列设备中，哪种不是输入设备?

使用8086/8088汇编语言的伪操作命令定义：　　　　VAL　DB　93　DUP(5，2　DUP(1，2　DUP(3))，4)　　　　则在VAL存储区内前10个字节单元的数据库是(　　　)。

对于嵌入式Linux而言，Bootloader完成的工作步骤不包括如下()项。

关于DSA注射压力的叙述，下列哪几项是正确的

A、普鲁卡因B、布比卡因C、利多卡因D、阿替卡因E、丁卡因持续时间最长的局麻药物是

下列犯罪中，侵犯复杂客体的犯罪是：()

某工程单代号搭接网络计划如下图所示，节点中下方数字为该工作的持续时间，其中的关键工作有(　　)。

教育心理学界普遍认为，西方第一本《教育心理学》出版于()

2011年3月，全国政协十一届四次会议将“‘十二五’期间加快城乡社会保障一体化发展的提案”列为l号提案，建议国务院交由相关部门办理。这表明()。

(1988年)设f(x)是连续函数，且则f(7)=___________．

Asmanypeoplehitmiddleage,theyoftenstarttonoticethattheirmemoryandmentalclarityarenotwhattheyusedtobe.We

"It’ssuchasimplething,"saidJohnSpitzer,managingdirectorofequipmentstandardsfortheUnitedStatesGolfAssociation.

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

三级数据库技术

NCRE全国计算机三级

在80×86宏汇编语言中，下列指令性语句的格式正确的是

有多种技术指标可用来衡量计算机的优劣，下述哪些可作为计算机技术指标?Ⅰ．位数Ⅱ．速度Ⅲ．容量Ⅳ．带宽Ⅴ．版本Ⅵ．可靠性

在Windows98中，msdos.sys 是一个十分重要的系统配置文件，通过对其修改(例如修改BootMulti、BootGUI、BootMenu 等命令)可以改变Windows98的启动方式。如果要使Windows98 启动时直接进入到DOS状态，该文

软盘存储器由软盘片、【 】和软盘适配器3部分组成。目前PC主要使用5英寸(1.44MB)和25英寸(低密360KB，高密1.2MB)两种。每个磁道又分为若干个段(段又叫扇区)。

假设(AL)=12H，执行OR AL，AL指令后，ZF和OF的状态分别为( )。

当成千上万台终端设备需要相互通信时，它们之间采用固定的连接是极不经济的。解决方法是在要进行通信的终端之间建立临时连接，通信结束后再拆除连接，实现这种功能的设备称为

输入设备用于向计算机输入信息。下列设备中，哪种不是输入设备?

使用8086/8088汇编语言的伪操作命令定义： VAL DB 93 DUP(5，2 DUP(1，2 DUP(3))，4) 则在VAL存储区内前10个字节单元的数据库是( )。

对于嵌入式Linux而言，Bootloader完成的工作步骤不包括如下()项。

关于DSA注射压力的叙述，下列哪几项是正确的

A、普鲁卡因B、布比卡因C、利多卡因D、阿替卡因E、丁卡因持续时间最长的局麻药物是

下列犯罪中，侵犯复杂客体的犯罪是：()

某工程单代号搭接网络计划如下图所示，节点中下方数字为该工作的持续时间，其中的关键工作有( )。

教育心理学界普遍认为，西方第一本《教育心理学》出版于()

2011年3月，全国政协十一届四次会议将“‘十二五’期间加快城乡社会保障一体化发展的提案”列为l号提案，建议国务院交由相关部门办理。这表明()。

(1988年)设f(x)是连续函数，且则f(7)=___________．

Asmanypeoplehitmiddleage,theyoftenstarttonoticethattheirmemoryandmentalclarityarenotwhattheyusedtobe.We

"It’ssuchasimplething,"saidJohnSpitzer,managingdirectorofequipmentstandardsfortheUnitedStatesGolfAssociation.

在Windows98中，msdos.sys　是一个十分重要的系统配置文件，通过对其修改(例如修改BootMulti、BootGUI、BootMenu　等命令)可以改变Windows98的启动方式。如果要使Windows98　启动时直接进入到DOS状态，该文

软盘存储器由软盘片、【　　】和软盘适配器3部分组成。目前PC主要使用5英寸(1.44MB)和25英寸(低密360KB，高密1.2MB)两种。每个磁道又分为若干个段(段又叫扇区)。

假设(AL)=12H，执行OR　AL，AL指令后，ZF和OF的状态分别为(　　　)。

使用8086/8088汇编语言的伪操作命令定义：　　　　VAL　DB　93　DUP(5，2　DUP(1，2　DUP(3))，4)　　　　则在VAL存储区内前10个字节单元的数据库是(　　　)。

某工程单代号搭接网络计划如下图所示，节点中下方数字为该工作的持续时间，其中的关键工作有(　　)。