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

admin2010-05-13 61

问题设平衡的二叉排序树(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://www.kaotiyun.com/show/AjSZ777K

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

数字视频信息的数据量相当大，通常需要进行压缩处理之后才进行传输和存储。目前数字有线电视所传输的数字视频采用的压缩编码标准是()。

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

当满足一定条件时，μC／OS—II操作系统内核将进行任务调度。下列各项中属于中断级任务调度需满足的条件的是()。

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

与个人计算机(PC)相比，嵌入式系统具有许多不同的特点。下面不属于嵌入式系统特点的是()。

字符的形状有两种描述方法，其中下图所示的描述方法为【41】法，也即描述字符笔画的占位信息；另一种描述方法在字型库中记录的是每一直线和曲线的端点及控制点的坐标，称为【42】法。

小端模式下ARM指令序列如下：LDRR0，=0x13579246LDRR1，=0xl0000000STRR0，[R1，#8]!执行后，内存0x10000008中的值=【55】，R1=【56】

下面关于互联网(Internet)的叙述中错误的是()。

数据模型可分为概念数据模型和结构数据模型，层次模型是()数据模型。

泡状核细胞癌的形态特点有：

用于肝癌临床诊断的检查包括

可诱发或加重支气管哮喘的药物是

岛式土方开挖时，中部岛状土体的高度不宜大于6m。中部岛状土体高度大于规定值时，应采用二级放坡形式，每级边坡坡度不宜大于1∶1．5，总边坡坡度不应大于1∶2．0。应采用二级放坡形式的中部岛状土体高度大于()。

根据《安全生产法》的规定，股份有限责任公司安全投入的保障主体是()。

会计核算软件是指专门用于会计核算工作的计算机系统软件。()

下列各项中，符合关税减免规定的有()。(2006年)

光纤通信：光纤通信就是利用光波在光导纤维中传递各种信息。()

(2019年国考)下列与扶贫有关的说法正确的是()。

《合同法》第51条规定，无处分权的人处分他人财产，经权利人追认或者无处分权的人订立合同后取得处分权的，该合同有效。这一规定属于法律构成要素中的()。

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

三级数据库技术

NCRE全国计算机三级

数字视频信息的数据量相当大，通常需要进行压缩处理之后才进行传输和存储。目前数字有线电视所传输的数字视频采用的压缩编码标准是()。

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

当满足一定条件时，μC／OS—II操作系统内核将进行任务调度。下列各项中属于中断级任务调度需满足的条件的是()。

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

与个人计算机(PC)相比，嵌入式系统具有许多不同的特点。下面不属于嵌入式系统特点的是()。

字符的形状有两种描述方法，其中下图所示的描述方法为【41】法，也即描述字符笔画的占位信息；另一种描述方法在字型库中记录的是每一直线和曲线的端点及控制点的坐标，称为【42】法。

小端模式下ARM指令序列如下：LDRR0，=0x13579246LDRR1，=0xl0000000STRR0，[R1，#8]!执行后，内存0x10000008中的值=__________【55】，R1=__________【56】

下面关于互联网(Internet)的叙述中错误的是()。

数据模型可分为概念数据模型和结构数据模型，层次模型是()数据模型。

泡状核细胞癌的形态特点有：

用于肝癌临床诊断的检查包括

可诱发或加重支气管哮喘的药物是

岛式土方开挖时，中部岛状土体的高度不宜大于6m。中部岛状土体高度大于规定值时，应采用二级放坡形式，每级边坡坡度不宜大于1∶1．5，总边坡坡度不应大于1∶2．0。应采用二级放坡形式的中部岛状土体高度大于()。

根据《安全生产法》的规定，股份有限责任公司安全投入的保障主体是()。

会计核算软件是指专门用于会计核算工作的计算机系统软件。()

下列各项中，符合关税减免规定的有()。(2006年)

光纤通信：光纤通信就是利用光波在光导纤维中传递各种信息。()

(2019年国考)下列与扶贫有关的说法正确的是()。

《合同法》第51条规定，无处分权的人处分他人财产，经权利人追认或者无处分权的人订立合同后取得处分权的，该合同有效。这一规定属于法律构成要素中的()。

小端模式下ARM指令序列如下：LDRR0，=0x13579246LDRR1，=0xl0000000STRR0，[R1，#8]!执行后，内存0x10000008中的值=【55】，R1=【56】