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

admin2009-01-19 111

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

下面关于8237可编程DMA控制器的叙述中，错误的是：

在80×86宏汇编语言中，下列指令性语句的格式正确的是

Pentium微处理器复位后，首先进入哪一种工作模式?

在指令“ADDR，Ad”中，源操作数在前，目的操作数在后，该指令执行的操作是(　　　)。

操作系统的特征有并发性、______、虚拟和异步性。

RAID是一种提高磁盘存储速度、容量和可靠性的技术。下面有关RAID的叙述中，错误的是(　　　)。

Windows98是由多个模块组成的一个功能强大的操作系统，下列哪个模块负责处理键盘和鼠标的输入，井以窗口、图标、菜单和其他界面元素的形式完成输出任务?

请编制程序，其功能是：内存中连续存放着20个十六位二进制数，对每个数逻辑右移，使其最低位为"1"(值为零的字不变)。例如：内存中有A704H(1010011100000100B),0000H,9A58H…结果为29C1H(0

当计算机接通电源后，Windows98引导过程分四个步骤进行，第一步执行的是(　　　)。

影响心搏骤停患者预后最主要的因素是

下列药物不属于中枢兴奋药的为

A．尿蛋白定量＞150mg/24hB．新鲜尿沉渣镜检红细胞＞3个/HPC．尿中含血量达lml/L时，外观呈洗肉水样D．12小时尿沉渣计数管型＞5000个E．新鲜尿沉渣镜检白细胞＞5个/HP

新生儿病理性黄疸，下列哪项是错误的

建设项目业主项目管理团队的负责人是()。

某工程项目建成投产后，正常生产年份的总成本费用为1000万元，其中期间费用150万元，借款利息20万元，固定资产折旧100万元，无形资产摊销费50万元，则其经营成本为()万元。

某企业为增值税一般纳税人，2012年5月该企业销售额为7000万元，按照增值税基本税率计算，该企业本月的增值税销项税额为()万元。

设A=，已知A有三个线性无关的特征向量且λ=2为矩阵A的二重特征值，求可逆矩阵P，使得P－1AP为对角矩阵．

Whatfactorswouldyoulookforinabondwhenseekingtominimizeyourinterestraterisk?

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

三级数据库技术

NCRE全国计算机三级

下面关于8237可编程DMA控制器的叙述中，错误的是：

在80×86宏汇编语言中，下列指令性语句的格式正确的是

Pentium微处理器复位后，首先进入哪一种工作模式?

在指令“ADDR，Ad”中，源操作数在前，目的操作数在后，该指令执行的操作是( )。

操作系统的特征有并发性、______、虚拟和异步性。

RAID是一种提高磁盘存储速度、容量和可靠性的技术。下面有关RAID的叙述中，错误的是( )。

Windows98是由多个模块组成的一个功能强大的操作系统，下列哪个模块负责处理键盘和鼠标的输入，井以窗口、图标、菜单和其他界面元素的形式完成输出任务?

请编制程序，其功能是：内存中连续存放着20个十六位二进制数，对每个数逻辑右移，使其最低位为"1"(值为零的字不变)。例如：内存中有A704H(1010011100000100B),0000H,9A58H…结果为29C1H(0

当计算机接通电源后，Windows98引导过程分四个步骤进行，第一步执行的是( )。

影响心搏骤停患者预后最主要的因素是

下列药物不属于中枢兴奋药的为

A．尿蛋白定量＞150mg/24hB．新鲜尿沉渣镜检红细胞＞3个/HPC．尿中含血量达lml/L时，外观呈洗肉水样D．12小时尿沉渣计数管型＞5000个E．新鲜尿沉渣镜检白细胞＞5个/HP

新生儿病理性黄疸，下列哪项是错误的

建设项目业主项目管理团队的负责人是()。

某工程项目建成投产后，正常生产年份的总成本费用为1000万元，其中期间费用150万元，借款利息20万元，固定资产折旧100万元，无形资产摊销费50万元，则其经营成本为()万元。

某企业为增值税一般纳税人，2012年5月该企业销售额为7000万元，按照增值税基本税率计算，该企业本月的增值税销项税额为()万元。

设A=，已知A有三个线性无关的特征向量且λ=2为矩阵A的二重特征值，求可逆矩阵P，使得P－1AP为对角矩阵．

Whatfactorswouldyoulookforinabondwhenseekingtominimizeyourinterestraterisk?

在指令“ADDR，Ad”中，源操作数在前，目的操作数在后，该指令执行的操作是(　　　)。

RAID是一种提高磁盘存储速度、容量和可靠性的技术。下面有关RAID的叙述中，错误的是(　　　)。

当计算机接通电源后，Windows98引导过程分四个步骤进行，第一步执行的是(　　　)。