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

admin2010-05-13 36

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

S3C2410与一位共阳接法的8段LED数码管的连接如下图所示。下面与该图相关的叙述中，错误的是()。

以下属于按指令集结构划分嵌入式处理器的分类是()。

下图是数字信号处理器(DSP)的典型应用方式，其中的①、②和③分别是()。

UNIX、嵌入式Linux、winCE、MacOS、AndroidOS和DOS操作系统是典型的单内核(也称为宏内核)操作系统，相对于微内核操作系统，下面不属于单内核操作系统缺点的是()。

手机最基本的功能是打电话，在发送话音信号时必须对讲话声音进行数字化，下面有关音频信号数字化的叙述中，错误的是()。

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

对于下图所示的采用行扫描方法的矩阵式键盘电路，在确定键盘中哪一个键被按下的过程中，需采用四根：I／O引脚GPG4-GPG7作为行扫描信号的输【63】，四根I／O引脚GPF5-GPF8作为输【64】。

数据库管理系统中，为了保证事务的正确执行，维护数据库的完整性，要求数据库系统维护以下事务特性：()、一致性、隔离性和持久性。

WWW是以超文本标注语言为基础，能够提供面向Internet服务的信息浏览系统，WWW系统的结构采用了()模式。

将函数展开为x一1的幂级数，并指出收敛区间(不考虑端点)．

矿山井巷工程的开拓方式分为()。

客户对交易结算报告的内容有异议的，应当在期货交易所规定的时间内向期货公司提出书面异议。()

要保持一国长期的经济增长，政府可以选择的经济政策包括()。[2003年真题]

投资者对某项资产合理要求的最低收益率，称为（）。

资产负债表是根据()这一会计等式编制而成的。

马克思认为，科学是“历史的有力杠杆”，是“最高意义上的革命力量”。这句话表明()

设f(x)二阶连续可导，f′(0)=0，且则()．

ReadingPassage2hastenparagraphs,A-J.Whichparagraphsstatethefollowinginformation?WritetheappropriatelettersA