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

admin2009-01-19 93

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

下面不具备多道程序设计的特点的是

当RESET信号位高电平时，虚拟空间为(　　　)。

Internet使用TCP/IP协议实现了全球范围的计算机网络的互连，连接在Internet上的每一台主机都有一个IP地址，下面(　　　)不能作为IP地址。

在默认情况下，Windows98操作系统安装后，会在C盘上生成一个Windows文件夹(含多个子文件夹)。其中用于存储系统开机、关机和报警等声音信息的子文件夹是(　　　)。

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

请编制程序，其功能是：内存中连续存放着20个无符号二进制字序列Xi(i＝1,2,…,20)，字的最高3位为000，此序列对应某一信号在一段时间内的连续变化，现对该信号进行一阶低通数字滤波，其滤波方程为：Yi＝(15*Yi-1/16)+(Xi/16)

CCD芯片的像素数目是数码相机的重要性能指标，它与可拍摄的图像分辨率有密切的关系。假定一台200万像素数码相机，它所拍摄的像片能达到的最大分辨率是多少?______

已知R0=1，R1=2，R2=3，R3=4，则执行下列指令后：ANDR0，R2，R3ORRR4，R1，R0ADDR5，R1，R4SUBR1，R5，R4指令序列执行后，R1=【53】和R5=【54】

在Web2．0时代生产模式中，以（）为中心。

在Windows7中，“任务栏”___________。

由半夏、茯苓、橘皮、前胡、桔梗、苏叶、甘草、大枣、生姜、杏仁、枳壳组成的方剂是

关于C型预防性充填，正确的是

商业企业单位在实施会计电算化时，一般需选择()。

关于期刊办刊常用的市场定位途径，理解错误的有()。

某不超过200的自然数除以5余1，除以7余2，除以11余2，问这个数除以13余数是多少?

Whenolderpeoplecannolongerremembernamesatacocktailparty,theytendtothinkthattheirbrainpowerisdeclining.Butm

在公钥加密机制中，公开的是()。

•Readthetextbelowabouthowtodenycustomers’claims.•Inmostofthelines34—45thereisoneextraword.Itiseithergr

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

三级数据库技术

NCRE全国计算机三级

下面不具备多道程序设计的特点的是

在用扫描仪进行图像扫描前，可以设置一些参数来调整图像的质量和文件大小。下面给出一些可能的设置： Ⅰ．文件类型 Ⅱ．分辨率 Ⅲ．颜色数目 Ⅳ．扫描范围上述( )设置会影响图像文件数据量的大小。

当RESET信号位高电平时，虚拟空间为( )。

Internet使用TCP/IP协议实现了全球范围的计算机网络的互连，连接在Internet上的每一台主机都有一个IP地址，下面( )不能作为IP地址。

在默认情况下，Windows98操作系统安装后，会在C盘上生成一个Windows文件夹(含多个子文件夹)。其中用于存储系统开机、关机和报警等声音信息的子文件夹是( )。

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

请编制程序，其功能是：内存中连续存放着20个无符号二进制字序列Xi(i＝1,2,…,20)，字的最高3位为000，此序列对应某一信号在一段时间内的连续变化，现对该信号进行一阶低通数字滤波，其滤波方程为：Yi＝(15*Yi-1/16)+(Xi/16)

CCD芯片的像素数目是数码相机的重要性能指标，它与可拍摄的图像分辨率有密切的关系。假定一台200万像素数码相机，它所拍摄的像片能达到的最大分辨率是多少?______

已知R0=1，R1=2，R2=3，R3=4，则执行下列指令后：ANDR0，R2，R3ORRR4，R1，R0ADDR5，R1，R4SUBR1，R5，R4指令序列执行后，R1=【53】和R5=【54】

在Web2．0时代生产模式中，以（）为中心。

在Windows7中，“任务栏”___________。

由半夏、茯苓、橘皮、前胡、桔梗、苏叶、甘草、大枣、生姜、杏仁、枳壳组成的方剂是

关于C型预防性充填，正确的是

商业企业单位在实施会计电算化时，一般需选择()。

关于期刊办刊常用的市场定位途径，理解错误的有()。

某不超过200的自然数除以5余1，除以7余2，除以11余2，问这个数除以13余数是多少?

Whenolderpeoplecannolongerremembernamesatacocktailparty,theytendtothinkthattheirbrainpowerisdeclining.Butm

在公钥加密机制中，公开的是()。

•Readthetextbelowabouthowtodenycustomers’claims.•Inmostofthelines34—45thereisoneextraword.Itiseithergr

当RESET信号位高电平时，虚拟空间为(　　　)。

Internet使用TCP/IP协议实现了全球范围的计算机网络的互连，连接在Internet上的每一台主机都有一个IP地址，下面(　　　)不能作为IP地址。

在默认情况下，Windows98操作系统安装后，会在C盘上生成一个Windows文件夹(含多个子文件夹)。其中用于存储系统开机、关机和报警等声音信息的子文件夹是(　　　)。