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

admin2009-01-19 62

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

下面关于总线的叙述中，错误的是

多媒体系统的核心软件包括(　　　)。

一幅1024×768的彩色图像，其数据量达25MB左右，若图像数据没有经过压缩处理，则该图像中的每一个像素是使用(　　　)二进位表示的。

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

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

微程序控制器比组合逻辑控制器慢，主要是由于增加了从(　　　)读取微指令的时间。

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

【　　】记录着每个文件的文件名、起始簇号、属性等信息，它与文件分配表　FAT相配合，统一管理整个磁盘的文件。

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

手工装沙弯管充装填料的目的是防止钢管的________变形。

关于伦理学的概念，错误的是

下列关于招标投标基本程序的表述，不正确的是()。

下列不属于由内部流程引起操作风险的是()。

中央银行提高法定存款准备金率时，()。

导游人员在向游客介绍下榻饭店的情况时，应注意()。

根据《中华人民共和国行政处罚法》的规定，下列情况中，行为人不受行政处罚的是()。

下列常见装置对应的物理原理错误的是()。

[*]

Ayoungster’ssocialdevelopmenthasaprofoundeffectonhisacademicprogress.Kidswhohavetroublegettingalongwiththeir

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

三级数据库技术

NCRE全国计算机三级

下面关于总线的叙述中，错误的是

多媒体系统的核心软件包括( )。

一幅1024×768的彩色图像，其数据量达25MB左右，若图像数据没有经过压缩处理，则该图像中的每一个像素是使用( )二进位表示的。

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

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

微程序控制器比组合逻辑控制器慢，主要是由于增加了从( )读取微指令的时间。

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

【 】记录着每个文件的文件名、起始簇号、属性等信息，它与文件分配表 FAT相配合，统一管理整个磁盘的文件。

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

手工装沙弯管充装填料的目的是防止钢管的________变形。

关于伦理学的概念，错误的是

下列关于招标投标基本程序的表述，不正确的是()。

下列不属于由内部流程引起操作风险的是()。

中央银行提高法定存款准备金率时，()。

导游人员在向游客介绍下榻饭店的情况时，应注意()。

根据《中华人民共和国行政处罚法》的规定，下列情况中，行为人不受行政处罚的是()。

下列常见装置对应的物理原理错误的是()。

[*]

Ayoungster’ssocialdevelopmenthasaprofoundeffectonhisacademicprogress.Kidswhohavetroublegettingalongwiththeir

多媒体系统的核心软件包括(　　　)。

一幅1024×768的彩色图像，其数据量达25MB左右，若图像数据没有经过压缩处理，则该图像中的每一个像素是使用(　　　)二进位表示的。

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

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

微程序控制器比组合逻辑控制器慢，主要是由于增加了从(　　　)读取微指令的时间。

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

【　　】记录着每个文件的文件名、起始簇号、属性等信息，它与文件分配表　FAT相配合，统一管理整个磁盘的文件。

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