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

admin2010-07-20 19

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

选项 A、O(1)
B、O(log2n)
C、O(n)
D、O(nlog2n)

答案B

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

Sybase公司目前的企业级服务器ASE支持下述哪些功能？Ⅰ．JAVA语言和XML语言Ⅱ．服务器之间的失败转移Ⅲ．保证分布式事务处理的完整性

设根结点的层次为0，则高度为k的二叉树的最大结点数为

联网的各个计算机共享一个公共通信信道，当一台计算机发送消息时，所有其他计算机都能“收听”到此消息。这种网络称为【】网络。

当对视图进行UPDATE、INSERT和DELETE操作时，为了保证被操作的行满足视图定义中子查询语句的谓词条件，应在视图定义语句中使用可选择项【】。

数据库管理系统的数据操纵语言(DML)所实现的操作一般包括

计算机语言是一类面向计算机的人工语言，它是进行程序设计的工具，又称为程序设计语言。现有的程序设计语言一般可分为3类，它们是

存取方法设计是数据库设计的_________阶段的任务。

下列关于计算机系统工作原理的叙述中，_______是正确的。

Oracle产品中CASE工具的名称是【】。

设有栈S和队列Q，其初始状态为空，元素a1、a2、a3、a4、a5、a6依次入栈，出栈的元素则进入队列Q，若6个元素出列的顺序是a2、a4、a3、a6、a5、a1，则栈的容量至少是多大?

男，41岁。因土石方塌方受伤，腰部疼痛，自行行走来诊。X线平片示第一腰椎压缩骨折，椎体前缘压缩约1／4。最佳治疗方案是

某代谢性酸中毒患者[HCO3-]为15mmol／L，该患者首选的溶液是

对胸腔积液的超声描述，正确的是

关于小儿动脉导管未闭的叙述，正确的是

选择和确立教育目的时，在基本价值取向方面，长期存在的对立是()的对立。

根据下面材料回答下列题。2007年1～9月，高新技术产业产值最高的区域的产值是最低区域的()。

已知函数f(u)具有二阶导数，且f’(0)=1，函数y=y(x)由方程y－xey－1=1所确定。设z=f(lny－sinx)，求dz／dx|x=0，d2z／dx2|x=0。

创建查询的方法有两种，分别为“使用向导”创建和【】创建。