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

admin2009-01-19 89

问题设平衡的二叉排序树(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全国计算机三级

若将第6题程序中的JNENEXT指令修改为JENEXT指令，则程序执行结束后，NUM内存单元中得到的结果是______。

运行下面的汇编语言程序，在NUM内存单元中得到的结果是______。DSEGSEGMENTDATDB5,13,4,-2,-6,23,3,1,9,0CNTEQUS

Windows98支持多种不同的文件系统，以管理不同类型的外存。在下列文件系统中，限定文件名长度只能为30多个字符的是

下列指令序列执行后，AL寄存器中的内容为【　　】。　　　MOV　AL，1　　　SAL　AL，1　　　MOV　BL，AL　　　SAL　AL，1　　　SAL　AL，1　　　ADD　AL，SL

在下列有关386处理器工作模式的叙述中，错误的是

Pentium微处理器采用了超标量体系结构。Pentium4微处理器的指令流水线有(　　　)条。

下面是一台“500万像素的数码相机”的有关叙述：Ⅰ．该数码相机的CCD像素数目为500万Ⅱ．该数码相机拍摄的相片理论上最多只能有500万个像素Ⅲ．该数码相机可拍摄最高分辨率为3000×2000的相片以上叙述中，正确的是___

计算机病毒具有破坏性、隐蔽性、______、潜伏性和激发性等主要特点。

在完全二叉树的顺序存储中，若结点i有左子女，则其左子女是结点()。

ItwasSunday.Thetrainswerecrowded.Agentlemanwaswalkingalongtheplatform【21】aplace.Inoneof【22】hesawavacantseat

以下有关苯巴比妥钠作用的叙述，哪些是正确的：

下颌牙体长轴近远中向倾斜最大的是

民事诉讼中的举证期限()。

设x1，x2，…，xn是来自总体N(μ，σ2)的样本，μ，σ2未知，，Q＞0。则检验假设H0：μ=0时应选取的统计量是：

林某和赵某离婚，孩子林冰经法院判决，由林某抚养，后赵某与王某结婚，应负责履行林冰教育义务的是()。

被称为中国伟大的革命先行者的是()。

国务院办公厅印发《国民旅游休闲纲要(2013—2020年)》。关于此纲要，下列说法正确的是()。

生命周期法将管理系统的开发过程划分为(64)。

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

三级数据库技术

NCRE全国计算机三级

若将第6题程序中的JNENEXT指令修改为JENEXT指令，则程序执行结束后，NUM内存单元中得到的结果是______。

运行下面的汇编语言程序，在NUM内存单元中得到的结果是______。DSEGSEGMENTDATDB5,13,4,-2,-6,23,3,1,9,0CNTEQUS

Windows98支持多种不同的文件系统，以管理不同类型的外存。在下列文件系统中，限定文件名长度只能为30多个字符的是

下列指令序列执行后，AL寄存器中的内容为【 】。 MOV AL，1 SAL AL，1 MOV BL，AL SAL AL，1 SAL AL，1 ADD AL，SL

在下列有关386处理器工作模式的叙述中，错误的是

Pentium微处理器采用了超标量体系结构。Pentium4微处理器的指令流水线有( )条。

下面是一台“500万像素的数码相机”的有关叙述：Ⅰ．该数码相机的CCD像素数目为500万Ⅱ．该数码相机拍摄的相片理论上最多只能有500万个像素Ⅲ．该数码相机可拍摄最高分辨率为3000×2000的相片以上叙述中，正确的是___

计算机病毒具有破坏性、隐蔽性、______、潜伏性和激发性等主要特点。

在完全二叉树的顺序存储中，若结点i有左子女，则其左子女是结点()。

ItwasSunday.Thetrainswerecrowded.Agentlemanwaswalkingalongtheplatform【21】aplace.Inoneof【22】hesawavacantseat

以下有关苯巴比妥钠作用的叙述，哪些是正确的：

下颌牙体长轴近远中向倾斜最大的是

民事诉讼中的举证期限()。

设x1，x2，…，xn是来自总体N(μ，σ2)的样本，μ，σ2未知，，Q＞0。则检验假设H0：μ=0时应选取的统计量是：

林某和赵某离婚，孩子林冰经法院判决，由林某抚养，后赵某与王某结婚，应负责履行林冰教育义务的是()。

被称为中国伟大的革命先行者的是()。

国务院办公厅印发《国民旅游休闲纲要(2013—2020年)》。关于此纲要，下列说法正确的是()。

生命周期法将管理系统的开发过程划分为(64)。

下列指令序列执行后，AL寄存器中的内容为【　　】。　　　MOV　AL，1　　　SAL　AL，1　　　MOV　BL，AL　　　SAL　AL，1　　　SAL　AL，1　　　ADD　AL，SL

Pentium微处理器采用了超标量体系结构。Pentium4微处理器的指令流水线有(　　　)条。