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

admin2009-01-19 46

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

Pentium微处理器执行程序时，若遇到异常则进行异常处理。如果处理完毕后仍返回出现异常的指令重新执行，则这种异常属于哪一种类型?

在取样频率、量化位数、声道数目等参数一定时，数字波形声音的码率(bit　rate)主要由它所采用的【　　】方法决定。

下列程序执行后，SI寄存器中的内容是【　　】。MOV　SI，-1MOV　CL，4SAL　SI，CLAND　SI，5FFOHOR　SI，9FOFHNOT　SI

磁盘是PC机中的主要辅助存储器之一，它的空间结构、数据存储格式等与操作系统密切相关。在Windows98环境,下列叙述中正确的是(　　　)。

按工作方式分类，热敏型打印机属于(　　　)。

有一家庭PC机用户使用Modem通过电话线上网，如在网络空闲的时间从网上下载文件，1小时时间下载了大约20　MB数据。试问所用Modem　的数据传输速率是(　　　)。

DRAM是靠MOS电路中的栅极电容上的电荷来记忆信息的。为了防止数据丢失，需定时给电容上的电荷进行补充，这是通过以一定的时间间隔将DRAM各存储单元中的数据读出并再写入实现的，该过程称为DRAM的______。

在Windows98中可以安装三种网络服务软件，即Microsoft网络上的文件与打印机共享、NetWare网络上的文件与打印机共享，以及NetWare【　　】服务。

丙氨酸氨基转移酶增高，首先应考虑

下列各项中()属于项目的直接费用。

“建筑工程一切险”规定公司承担保险责任的除外责任有(　　)；

以下哪项通常不是正规预算过程的优点?

个人住房贷款可实行的担保方式是()。[2015年5月真题]

某公司年终利润分配前的股东权益项目资料如表1所示。公司股票的每股现行市价为35元。要求：若按1股换2股的比例进行股票分割，分析完成分割后股东权益各项目的金额以及每股净资产有何变化。

下列描述属于“网络教育”特点的有()。

文化是相对于物质文明而言的。（）

由商品的价格变动所引起的商品相对价格的变动，进而由商品的相对价格变动所引起的商品需求量的变动，称为()。

设f(x)在区间[0,1]上连续，在(0,1)内可导，且满足证明存在ξ∈(0,1)使得f’(ξ)=2ξf(ξ).

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

三级数据库技术

NCRE全国计算机三级

Pentium微处理器执行程序时，若遇到异常则进行异常处理。如果处理完毕后仍返回出现异常的指令重新执行，则这种异常属于哪一种类型?

在取样频率、量化位数、声道数目等参数一定时，数字波形声音的码率(bit rate)主要由它所采用的【 】方法决定。

下列程序执行后，SI寄存器中的内容是【 】。MOV SI，-1MOV CL，4SAL SI，CLAND SI，5FFOHOR SI，9FOFHNOT SI

磁盘是PC机中的主要辅助存储器之一，它的空间结构、数据存储格式等与操作系统密切相关。在Windows98环境,下列叙述中正确的是( )。

按工作方式分类，热敏型打印机属于( )。

有一家庭PC机用户使用Modem通过电话线上网，如在网络空闲的时间从网上下载文件，1小时时间下载了大约20 MB数据。试问所用Modem 的数据传输速率是( )。

DRAM是靠MOS电路中的栅极电容上的电荷来记忆信息的。为了防止数据丢失，需定时给电容上的电荷进行补充，这是通过以一定的时间间隔将DRAM各存储单元中的数据读出并再写入实现的，该过程称为DRAM的______。

在Windows98中可以安装三种网络服务软件，即Microsoft网络上的文件与打印机共享、NetWare网络上的文件与打印机共享，以及NetWare【 】服务。

丙氨酸氨基转移酶增高，首先应考虑

下列各项中()属于项目的直接费用。

“建筑工程一切险”规定公司承担保险责任的除外责任有( )；

以下哪项通常不是正规预算过程的优点?

个人住房贷款可实行的担保方式是()。[2015年5月真题]

某公司年终利润分配前的股东权益项目资料如表1所示。公司股票的每股现行市价为35元。要求：若按1股换2股的比例进行股票分割，分析完成分割后股东权益各项目的金额以及每股净资产有何变化。

下列描述属于“网络教育”特点的有()。

文化是相对于物质文明而言的。（）

由商品的价格变动所引起的商品相对价格的变动，进而由商品的相对价格变动所引起的商品需求量的变动，称为()。

设f(x)在区间[0,1]上连续，在(0,1)内可导，且满足证明存在ξ∈(0,1)使得f’(ξ)=2ξf(ξ).

在取样频率、量化位数、声道数目等参数一定时，数字波形声音的码率(bit　rate)主要由它所采用的【　　】方法决定。

下列程序执行后，SI寄存器中的内容是【　　】。MOV　SI，-1MOV　CL，4SAL　SI，CLAND　SI，5FFOHOR　SI，9FOFHNOT　SI

磁盘是PC机中的主要辅助存储器之一，它的空间结构、数据存储格式等与操作系统密切相关。在Windows98环境,下列叙述中正确的是(　　　)。

按工作方式分类，热敏型打印机属于(　　　)。

有一家庭PC机用户使用Modem通过电话线上网，如在网络空闲的时间从网上下载文件，1小时时间下载了大约20　MB数据。试问所用Modem　的数据传输速率是(　　　)。

在Windows98中可以安装三种网络服务软件，即Microsoft网络上的文件与打印机共享、NetWare网络上的文件与打印机共享，以及NetWare【　　】服务。

“建筑工程一切险”规定公司承担保险责任的除外责任有(　　)；