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

admin2009-01-19 98

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

INC指令不影响()标志。

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

PC机的串行通信接口(COM1l、COM2)采用异步通信。异步通信的一帧信息包括起始位、数据位、奇偶校验位(可选)和【　　】。

8086　CPU　执行一条指令需要几个时钟周期，Pentium　CPU由于采用了【　　】技术，在一个时钟周期中可以执行两条指令。

PC机中DRAM内存条的类型有多种，若按存取速度从高到低的顺序排列，则正确的是：(　　　)。

计算机中由5种不同层次的存储器组成一个存储器体系，它们是寄存器、【　　】、主存储器、辅助存储器和海量存储器。

Internet采用的协议族为【　　】。

通过异步通信方式传送信息“10101010”时，若采用偶校验，则附加的校验位是【　　】。

以下哪一个不是CPU与外设进行数据交换所采用的方式

Windows98的通信子系统由一个模块化的32位保护结构组成，下列(　　　)不是它的组成部分。

Moreandmorestudentswanttostudyin"hot"majors.【C1】aresult,manystudentswantto【C2】theirinterestsandstud

控制子痫的首选药物是

凡血袋有下列情形之一的，一律不得发出，除外

融资租赁筹资的优点之一是“财务风险小，财务优势明显”，其原因在于，融资租赁无须大量资金就能迅速获得所需资产。()

Alcoholmaytastesweeterifyouwereexposedtoitbeforebirth,suggestsastudyinrats.Thefindingsmayshednewlight【C1】_

在计算机中，信息的最小单位是_________。

A=RotherhitheB=BarnesC=WillesdenD=King’sCrossWhichcity...usedtohavelotofproblemssuchasdrugs,streetcri

Theinvisibilitycloakcanmakesomethinginvisiblebywrapping______.Whatdoesitmeanby"researcherspainstakinglytunedt

A、Moreenvelopesshouldbeprepared.B、Heshouldwritemoreletters.C、Heshouldshowmorerespectforhisemployees.D、Heshoul

Kitchendutiesmayhavetraditionallybeenviewedaswomen’swork,butnotattheWhiteHouse.Untilnow:CristetaComerfordha

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

三级数据库技术

NCRE全国计算机三级

INC指令不影响()标志。

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

PC机的串行通信接口(COM1l、COM2)采用异步通信。异步通信的一帧信息包括起始位、数据位、奇偶校验位(可选)和【 】。

8086 CPU 执行一条指令需要几个时钟周期，Pentium CPU由于采用了【 】技术，在一个时钟周期中可以执行两条指令。

PC机中DRAM内存条的类型有多种，若按存取速度从高到低的顺序排列，则正确的是：( )。

计算机中由5种不同层次的存储器组成一个存储器体系，它们是寄存器、【 】、主存储器、辅助存储器和海量存储器。

Internet采用的协议族为【 】。

通过异步通信方式传送信息“10101010”时，若采用偶校验，则附加的校验位是【 】。

以下哪一个不是CPU与外设进行数据交换所采用的方式

Windows98的通信子系统由一个模块化的32位保护结构组成，下列( )不是它的组成部分。

Moreandmorestudentswanttostudyin"hot"majors.【C1】______aresult,manystudentswantto【C2】______theirinterestsandstud

控制子痫的首选药物是

凡血袋有下列情形之一的，一律不得发出，除外

融资租赁筹资的优点之一是“财务风险小，财务优势明显”，其原因在于，融资租赁无须大量资金就能迅速获得所需资产。()

Alcoholmaytastesweeterifyouwereexposedtoitbeforebirth,suggestsastudyinrats.Thefindingsmayshednewlight【C1】_

在计算机中，信息的最小单位是_________。

A=RotherhitheB=BarnesC=WillesdenD=King’sCrossWhichcity...usedtohavelotofproblemssuchasdrugs,streetcri

Theinvisibilitycloakcanmakesomethinginvisiblebywrapping______.Whatdoesitmeanby"researcherspainstakinglytunedt

A、Moreenvelopesshouldbeprepared.B、Heshouldwritemoreletters.C、Heshouldshowmorerespectforhisemployees.D、Heshoul

Kitchendutiesmayhavetraditionallybeenviewedaswomen’swork,butnotattheWhiteHouse.Untilnow:CristetaComerfordha

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

PC机的串行通信接口(COM1l、COM2)采用异步通信。异步通信的一帧信息包括起始位、数据位、奇偶校验位(可选)和【　　】。

8086　CPU　执行一条指令需要几个时钟周期，Pentium　CPU由于采用了【　　】技术，在一个时钟周期中可以执行两条指令。

PC机中DRAM内存条的类型有多种，若按存取速度从高到低的顺序排列，则正确的是：(　　　)。

计算机中由5种不同层次的存储器组成一个存储器体系，它们是寄存器、【　　】、主存储器、辅助存储器和海量存储器。

Internet采用的协议族为【　　】。

通过异步通信方式传送信息“10101010”时，若采用偶校验，则附加的校验位是【　　】。

Windows98的通信子系统由一个模块化的32位保护结构组成，下列(　　　)不是它的组成部分。

Moreandmorestudentswanttostudyin"hot"majors.【C1】aresult,manystudentswantto【C2】theirinterestsandstud