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

admin2010-05-13 50

问题设平衡的二叉排序树(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/j3SZ777K

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

下列系统属于实时系统的是()。

下面哪种设备是组建以太局域网必不可少的?

以下关于VxWorks操作系统的叙述中，错误的是()。

程序存储器和数据存储器仅用一套总线与CPU连接的这种存储结构称为【47】结构，程序存储器和数据存储器分开采用两套总线与CPU连接的存储结构称为【48】结构。

按照实时性能和内核结构划分，VxWorks操作系统属于()。

以下是有关TCP／IP协议中IP地址格式(IPv4)的叙述，其中错误的是()。

下面是IP协议中C类IP地址有关规定的叙述，其中正确的是()。

在μC／OS–Ⅱ中，OSInit()函数先建立最初的任务就绪表，然后建立4个空白的数据链表。这4个空白的数据链表是()。

汉字有多种不同的编码标准，下面关于不同编码标准之间关系的叙述中，错误的是()。

下面是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中的组成部分A是【41】接口；组成部分B是【42】接口。

患儿，8个月，发现面色苍白6个月，妊娠32周早产，出生体重2．3kg，牛乳喂养，未添加辅食，现体重6kg，皮肤黏膜苍白，肝肋下3cm，脾肋下1cm，Hb80g／L，红细胞3．8×1012／L，网织红细胞0．4％。其贫血程度是

防火或机械性要求高的场所，宜用()。

抗原抗体形成明显沉淀物的条件是

面黄虚浮，称为

通过检测下列哪些腺体的唾液分泌量来定量检查涎腺分泌功能

用于抗结核杆菌的药物是口服用于肠道感染或肠道手术前准备的药物是

根据《药品经营质量管理规范》，以下说法错误的是

Beinganintrovertisabadthing,right?Well,alotofpeopleseemtothinkso,judgingbythenumberofarticlesI’vereadab

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

三级数据库技术

NCRE全国计算机三级

下列系统属于实时系统的是()。

下面哪种设备是组建以太局域网必不可少的?

以下关于VxWorks操作系统的叙述中，错误的是()。

程序存储器和数据存储器仅用一套总线与CPU连接的这种存储结构称为【47】结构，程序存储器和数据存储器分开采用两套总线与CPU连接的存储结构称为【48】结构。

按照实时性能和内核结构划分，VxWorks操作系统属于()。

以下是有关TCP／IP协议中IP地址格式(IPv4)的叙述，其中错误的是()。

下面是IP协议中C类IP地址有关规定的叙述，其中正确的是()。

在μC／OS–Ⅱ中，OSInit()函数先建立最初的任务就绪表，然后建立4个空白的数据链表。这4个空白的数据链表是()。

汉字有多种不同的编码标准，下面关于不同编码标准之间关系的叙述中，错误的是()。

下面是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中的组成部分A是__________【41】接口；组成部分B是__________【42】接口。

患儿，8个月，发现面色苍白6个月，妊娠32周早产，出生体重2．3kg，牛乳喂养，未添加辅食，现体重6kg，皮肤黏膜苍白，肝肋下3cm，脾肋下1cm，Hb80g／L，红细胞3．8×1012／L，网织红细胞0．4％。其贫血程度是

防火或机械性要求高的场所，宜用()。

抗原抗体形成明显沉淀物的条件是

面黄虚浮，称为

通过检测下列哪些腺体的唾液分泌量来定量检查涎腺分泌功能

用于抗结核杆菌的药物是口服用于肠道感染或肠道手术前准备的药物是

根据《药品经营质量管理规范》，以下说法错误的是

Beinganintrovertisabadthing,right?Well,alotofpeopleseemtothinkso,judgingbythenumberofarticlesI’vereadab

下面是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图，其中的组成部分A是【41】接口；组成部分B是【42】接口。