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

admin2009-01-19 86

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

PC机鼠标是采用串行方法的输入设备，现行PC机鼠标与主机的连接接口大多采用(　　　)。

PC机数据总线信号的状态是(　　　)。

Windows98中的文件管理系统从逻辑结构上看大致分为三个层次：第一层是可安装的文件系统管理器，第二层是各种文件系统，第三层是【　　】。

在HDLC　同步方式通信中，设同步字符为7EH。如果信息帧中包含有一数据为EFH，发送时，它被转换为(　　　)。

在Windows98中，下列(　　　)软件组件为应用程序提供了一种极其方便的途径去控制各种多媒体设备，使得多媒体的控制操作与特定的硬件无关。

甲、乙两台PC机通过其串行接口进行全双工通信时，若使用发送数据信号TxD和接收数据信号RxD交换信息，则下面关于两机串口信号线连接的叙述中，正确的是(　　　)。

下面的选项中与实时系统无必然联系的属性是()。

数据库管理系统、图形用户界面、互联网浏览器、媒体播放器等软件，如果运行在嵌入式系统上，往往具有内部结构精简，【69】轻量化，占用存储资源【70】的特点。

如何进行纯铜焊前表面的化学清洗?

圆板牙的前角数值沿切削刃变化，（）处前角最大。

慢性萎缩性胃炎可以发生

下列财产可以抵押的有()。

根据《建设工程质量管理条例》的规定，下列(　　)对分包工程的质量承担连带责任。

下列各项不属于常用固定资产折旧方法的是()。

2005年，我国公布的规范企业在银行问债券市场向合格机构投资者发行短期融资券的法规有()。

我国现行的学科门类分为()类。

A--AccountantB--AnnouncerC--ArchitectD--Associateprof

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

三级数据库技术

NCRE全国计算机三级

PC机鼠标是采用串行方法的输入设备，现行PC机鼠标与主机的连接接口大多采用( )。

PC机数据总线信号的状态是( )。

Windows98中的文件管理系统从逻辑结构上看大致分为三个层次：第一层是可安装的文件系统管理器，第二层是各种文件系统，第三层是【 】。

在HDLC 同步方式通信中，设同步字符为7EH。如果信息帧中包含有一数据为EFH，发送时，它被转换为( )。

在Windows98中，下列( )软件组件为应用程序提供了一种极其方便的途径去控制各种多媒体设备，使得多媒体的控制操作与特定的硬件无关。

甲、乙两台PC机通过其串行接口进行全双工通信时，若使用发送数据信号TxD和接收数据信号RxD交换信息，则下面关于两机串口信号线连接的叙述中，正确的是( )。

数码相机在成像过程中需要进行下列处理： Ⅰ．将光信号转换为电信号 Ⅱ．将影像聚焦在成像芯片(CCD或CMOS)上 Ⅲ．进行模/数转换，变成数字图像 Ⅳ．将数字图像存储在存储器中 其处理顺序是( )。

下面的选项中与实时系统无必然联系的属性是()。

数据库管理系统、图形用户界面、互联网浏览器、媒体播放器等软件，如果运行在嵌入式系统上，往往具有内部结构精简，【69】轻量化，占用存储资源【70】的特点。

如何进行纯铜焊前表面的化学清洗?

圆板牙的前角数值沿切削刃变化，（）处前角最大。

慢性萎缩性胃炎可以发生

下列财产可以抵押的有()。

根据《建设工程质量管理条例》的规定，下列( )对分包工程的质量承担连带责任。

下列各项不属于常用固定资产折旧方法的是()。

2005年，我国公布的规范企业在银行问债券市场向合格机构投资者发行短期融资券的法规有()。

我国现行的学科门类分为()类。

A--AccountantB--AnnouncerC--ArchitectD--Associateprof

PC机鼠标是采用串行方法的输入设备，现行PC机鼠标与主机的连接接口大多采用(　　　)。

PC机数据总线信号的状态是(　　　)。

Windows98中的文件管理系统从逻辑结构上看大致分为三个层次：第一层是可安装的文件系统管理器，第二层是各种文件系统，第三层是【　　】。

在HDLC　同步方式通信中，设同步字符为7EH。如果信息帧中包含有一数据为EFH，发送时，它被转换为(　　　)。

在Windows98中，下列(　　　)软件组件为应用程序提供了一种极其方便的途径去控制各种多媒体设备，使得多媒体的控制操作与特定的硬件无关。

甲、乙两台PC机通过其串行接口进行全双工通信时，若使用发送数据信号TxD和接收数据信号RxD交换信息，则下面关于两机串口信号线连接的叙述中，正确的是(　　　)。

根据《建设工程质量管理条例》的规定，下列(　　)对分包工程的质量承担连带责任。