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

admin2010-05-13 71

问题设平衡的二叉排序树(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操作系统的叙述中，错误的是()。

编写μC／OS－II的中断服务子程序主要使用哪种语言?

无线局域网采用的通信协议主要是【45】，通常也称为Wi—Fi，它有几种不同的数据传输速率，其中【46】协议的数据传输速率可达108Mbps甚至更高，可以满足传输语音、数据、图像等的需要

关于μC／OS–II操作系统任务状态转移的说法中，正确的是()。

采用ADS1．2集成开发工具软件来开发基于ARM微处理器的嵌入式系统时，ADS1．2把目标文件中的信息按照三种存储区域类型来进行划分，即划分为RO段、【77】、ZI段。其中RO段是指【78】和常数的存储区域，具有只读属性。

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

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

ARM状态下指令代码长度的位数为【49】位、Thumb状态下指令代码长度的位数为【50】位。

核心能力目标是大企业发展能力目标之一，大型企业的核心能力目标主要是企业创新能力目标，包括()

具有结肠带、结肠袋和肠脂垂的肠管是()

A．蛋白质CB．蛋白质SC．凝血酶调制素D．TFPIE．抗凝血酶Ⅲ能灭活FⅤa、FⅧ的物质是

酸中毒时，肾小管重吸收和分泌功能的改变是

呕吐物多且有粪臭者见于

根据铝的工艺特点，铝合金可分为(　　)。

下列选项中，不属于商业银行在贷款审批要素管理中存在的问题的是（）。

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

三级数据库技术

NCRE全国计算机三级

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

编写μC／OS－II的中断服务子程序主要使用哪种语言?

无线局域网采用的通信协议主要是【45】，通常也称为Wi—Fi，它有几种不同的数据传输速率，其中【46】协议的数据传输速率可达108Mbps甚至更高，可以满足传输语音、数据、图像等的需要

关于μC／OS–II操作系统任务状态转移的说法中，正确的是()。

采用ADS1．2集成开发工具软件来开发基于ARM微处理器的嵌入式系统时，ADS1．2把目标文件中的信息按照三种存储区域类型来进行划分，即划分为RO段、【77】、ZI段。其中RO段是指【78】和常数的存储区域，具有只读属性。

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

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

ARM状态下指令代码长度的位数为__________【49】位、Thumb状态下指令代码长度的位数为__________【50】位。

核心能力目标是大企业发展能力目标之一，大型企业的核心能力目标主要是企业创新能力目标，包括()

具有结肠带、结肠袋和肠脂垂的肠管是()

A．蛋白质CB．蛋白质SC．凝血酶调制素D．TFPIE．抗凝血酶Ⅲ能灭活FⅤa、FⅧ的物质是

酸中毒时，肾小管重吸收和分泌功能的改变是

呕吐物多且有粪臭者见于

根据铝的工艺特点，铝合金可分为( )。

下列选项中，不属于商业银行在贷款审批要素管理中存在的问题的是（）。

ARM状态下指令代码长度的位数为【49】位、Thumb状态下指令代码长度的位数为【50】位。

根据铝的工艺特点，铝合金可分为(　　)。