设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

admin2010-05-13 50

问题设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

选项 A、O(1)
B、0(log₂n)
C、O(n)
D、0(nlog₂n)

答案2

解析平衡二叉树又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的(N为结点个数)。由此，它的平均查找长度也和logN同数量级。

转载请注明原文地址:https://kaotiyun.com/show/LMSZ777K

本试题收录于：三级数据库技术题库NCRE全国计算机三级分类

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

三级数据库技术

NCRE全国计算机三级

以下不属于ARM处理器的特点是()。

下列术语中，并非用于描述数字图像参数的是()。

嵌入式系统开发时，由于受到目标机资源的限制，需要建立一个【77】与目标机组成的调试架构来完成开发工作。若目标机为裸机环境时，通常需要通过【78】接口来完成硬件环境测试及初始软件的调试和下载。

Linux内核由若干个子系统组成，一般来说下面哪一个不是Linux内核的子系统()。

实时系统对时间约束要求的严格性，使【73】陛成为实时系统的一项重要性能要求，它是指RTOS能够对外部事件的【74】时间和实时任务的执行时间进行判断，以确定被事件触发的实时任务能否在规定的时间内完成。

设U是所有属性的集合，X、Y、Z都是U的子集，且Z=U-X-Y。下面关于多值依赖的叙述中，不正确的是

单链表的每个结点中包括一个指针link，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针P指向的的单链表结点之后，下面的操作序列中哪一个是正确的？

如果对闲暇的需求增加()

依据()的不同，可以将论证分为演绎论证、归纳论证和类比论证。

颈动脉鞘内包绕的解剖结构为

关于有效数字的叙述，正确的是

城镇体系本身及其所有城镇在其发挥功能作用正常运行的过程中，与外界环境产生密切的相互作用，呈现出不同的扩散特征，这体现了城镇体系的()特征。

当收益率向上倾斜，并且投资人确信收益率曲线继续保持上升的趋势，投资者会购买比要求的期限短的股票。()

甲县人民代表大会代表张某，在他当选为代表一年后，迁入乙县居住。他应（）。

泛化指某种特定刺激的条件反应形成后，另外一些类似的刺激会诱发同样的条件反应。新刺激越近似于原刺激，条件反应被诱发的可能性就越大。根据上述定义，下列可以称为泛化现象的是：

下列各组词语中，没有错别字的一组是：

Imagineananimalthatbecomesfrozenincoldweather.Then,whenitgetswarmer,theanimalsimplyunfreezesandgoesbacktoi

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

三级数据库技术

NCRE全国计算机三级

以下不属于ARM处理器的特点是()。

下列术语中，并非用于描述数字图像参数的是()。

嵌入式系统开发时，由于受到目标机资源的限制，需要建立一个__________【77】与目标机组成的调试架构来完成开发工作。若目标机为裸机环境时，通常需要通过__________【78】接口来完成硬件环境测试及初始软件的调试和下载。

Linux内核由若干个子系统组成，一般来说下面哪一个不是Linux内核的子系统()。

设U是所有属性的集合，X、Y、Z都是U的子集，且Z=U-X-Y。下面关于多值依赖的叙述中，不正确的是

单链表的每个结点中包括一个指针link，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针P指向的的单链表结点之后，下面的操作序列中哪一个是正确的？

如果对闲暇的需求增加()

依据()的不同，可以将论证分为演绎论证、归纳论证和类比论证。

颈动脉鞘内包绕的解剖结构为

关于有效数字的叙述，正确的是

城镇体系本身及其所有城镇在其发挥功能作用正常运行的过程中，与外界环境产生密切的相互作用，呈现出不同的扩散特征，这体现了城镇体系的()特征。

当收益率向上倾斜，并且投资人确信收益率曲线继续保持上升的趋势，投资者会购买比要求的期限短的股票。()

甲县人民代表大会代表张某，在他当选为代表一年后，迁入乙县居住。他应（）。

泛化指某种特定刺激的条件反应形成后，另外一些类似的刺激会诱发同样的条件反应。新刺激越近似于原刺激，条件反应被诱发的可能性就越大。根据上述定义，下列可以称为泛化现象的是：

下列各组词语中，没有错别字的一组是：

Imagineananimalthatbecomesfrozenincoldweather.Then,whenitgetswarmer,theanimalsimplyunfreezesandgoesbacktoi

嵌入式系统开发时，由于受到目标机资源的限制，需要建立一个【77】与目标机组成的调试架构来完成开发工作。若目标机为裸机环境时，通常需要通过【78】接口来完成硬件环境测试及初始软件的调试和下载。