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

admin2009-01-19 91

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

下面是汇编语言程序设计中关于过程调用和宏调用的叙述，其中错误的是：

Windows　2000内置的支持多媒体功能的组件中，能够从模拟视频采集数字视频信号，将数据进行压缩后存储到文件中，并对视频信息进行处理的是【　　】。

控制器包括指令寄存器、指令译码器以及定时与控制电路。根据【　　】的结果，以一定的时序发出相应的控制信号，用来控制指令的执行。

某计算机主存容量为2048KB，这里2048KB即为(　　　)个字节。

根据下面的程序段，AL寄存器中的数据是(　　　)。NUM　　DW　　　　　　?NAME　　DW　　　　10　DUP　(?)CNT　　EQU　　　　　10LEN　　EQU　　　　　＄—NUMMOV　　AL，LEN

(　　　)为计算机辅助设计的英文缩写。

目前，我国家庭计算机用户接入互联网的几种方法中，传输速度最快的是(　　　)。

下面(　　　)不能将字节变量X的属性修改为字节变量Y。

硬盘的平均等待时间是指数据所在扇区转到磁头下方所需的平均时间，它与盘片的转速有关。目前主流硬盘的转速多为5400rpm、7200rpm、10000rpm。转速为7200rpm的硬盘，其平均等待时间约为

男，30岁。风湿性心脏病病史10年，今晨突感右上下肢活动不便，不能下床，护士发现其口角歪斜，应首先考虑发生了

在海关监管工作中，为征税提供实际依据，为缉查走私、违法行为提供证据的步骤是()

对于承包人提出的索赔申请，监理工程师应重新计算索赔费用，包括()。

施工现场综合考评的对象是()。

根据建造师注册规定，下列申请人的注册申请将不予批准的是()。

()是感知运动技能发展的关键期，也是智力技能形成的奠基阶段。

已知反比例函数y=的图象位于第一、第三象限，则k的取值范围是()．

现代社会中不同国家仍存在不同的政治制度，目前主要有资本主义政治制度和社会主义政治制度两大类型。我国的政治制度是社会主义性质的政治制度，其主要特征是()。

Whatpersonalqualitiesaredesirableinateacher?Probablynotwopeoplewoulddrawupapproximatelysimilarlists,butI【M1】_

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

三级数据库技术

NCRE全国计算机三级

下面是汇编语言程序设计中关于过程调用和宏调用的叙述，其中错误的是：

Windows 2000内置的支持多媒体功能的组件中，能够从模拟视频采集数字视频信号，将数据进行压缩后存储到文件中，并对视频信息进行处理的是【 】。

控制器包括指令寄存器、指令译码器以及定时与控制电路。根据【 】的结果，以一定的时序发出相应的控制信号，用来控制指令的执行。

某计算机主存容量为2048KB，这里2048KB即为( )个字节。

根据下面的程序段，AL寄存器中的数据是( )。NUM DW ?NAME DW 10 DUP (?)CNT EQU 10LEN EQU ＄—NUMMOV AL，LEN

( )为计算机辅助设计的英文缩写。

目前，我国家庭计算机用户接入互联网的几种方法中，传输速度最快的是( )。

下面( )不能将字节变量X的属性修改为字节变量Y。

硬盘的平均等待时间是指数据所在扇区转到磁头下方所需的平均时间，它与盘片的转速有关。目前主流硬盘的转速多为5400rpm、7200rpm、10000rpm。转速为7200rpm的硬盘，其平均等待时间约为

男，30岁。风湿性心脏病病史10年，今晨突感右上下肢活动不便，不能下床，护士发现其口角歪斜，应首先考虑发生了

在海关监管工作中，为征税提供实际依据，为缉查走私、违法行为提供证据的步骤是()

对于承包人提出的索赔申请，监理工程师应重新计算索赔费用，包括()。

施工现场综合考评的对象是()。

根据建造师注册规定，下列申请人的注册申请将不予批准的是()。

()是感知运动技能发展的关键期，也是智力技能形成的奠基阶段。

已知反比例函数y=的图象位于第一、第三象限，则k的取值范围是()．

现代社会中不同国家仍存在不同的政治制度，目前主要有资本主义政治制度和社会主义政治制度两大类型。我国的政治制度是社会主义性质的政治制度，其主要特征是()。

Whatpersonalqualitiesaredesirableinateacher?Probablynotwopeoplewoulddrawupapproximatelysimilarlists,butI【M1】_

Windows　2000内置的支持多媒体功能的组件中，能够从模拟视频采集数字视频信号，将数据进行压缩后存储到文件中，并对视频信息进行处理的是【　　】。

控制器包括指令寄存器、指令译码器以及定时与控制电路。根据【　　】的结果，以一定的时序发出相应的控制信号，用来控制指令的执行。

某计算机主存容量为2048KB，这里2048KB即为(　　　)个字节。

根据下面的程序段，AL寄存器中的数据是(　　　)。NUM　　DW　　　　　　?NAME　　DW　　　　10　DUP　(?)CNT　　EQU　　　　　10LEN　　EQU　　　　　＄—NUMMOV　　AL，LEN

(　　　)为计算机辅助设计的英文缩写。

目前，我国家庭计算机用户接入互联网的几种方法中，传输速度最快的是(　　　)。

下面(　　　)不能将字节变量X的属性修改为字节变量Y。