设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

admin2010-05-13 61

问题设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

选项 A、O(1)
B、0(log₂n)
C、O(n)
D、0(nlog₂n)

答案2

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

三级数据库技术

NCRE全国计算机三级

某ARM处理器仅工作于Thumb–2状态，该处理器的指令宽度是()。①8位②16位③32位④64位

嵌入式系统的性能在很大程度上是由CPU决定的，CPU的性能主要表现为指令执行速度的快慢。下列选项中不直接影响CPU速度的是()。

字符在嵌入式系统内部是使用二进制编码表示的，存储一个ASCII字符需要使用【43】_个二进位，存储一个常用汉字需要使用【44】_个二进位(采用GB2312编码标准)。

下面关于存储器的叙述中，错误的是()。

片上调试技术是许多嵌入式处理器芯片采用的硬件调试技术。【79】标准是片上调试技术的一种国际标准，常用于芯片和电路板的调试。该标准中规定的TAP接口具有【80】根信号线。

ARM处理器用一条指令完成有条件的无符号数加法运算，并更新CPSR中的状态，条件是如果相等，要求指令执行R1+R2，结果送R3中，则这条指令为【55】；如果条件是大于，要求指令执行R1-R2，结果放R3中，则该指令为【56】。

广义表是线性表的推广，是由零个或多个单元素或()所组成的有限序列。

设关系R和S的元组个数分别为100和300，关系T是R与S的笛卡尔积，则T的元组个数是

与r对策生物相比，K对策生物的出生率______。

"五体"中，与肾相合的是

下列哪些污染物必须在车间内或车间处理设施排放口采样?()

在长江三峡中，以“秀”著称的是()。

“点头微笑表示肯定，摇头皱眉表示否定”体现了情绪情感的()功能。

出租车队去机场接某会议的参会者，如果每车坐3名参会者，则需另外安排一辆大巴送走余下的50人；如每车坐4名参会者，则最后正好多出3辆空车。则该车队有_________辆出租车。

设f(x)在[a，b]上连续，在(a，b)上可导，且f（A）=f（B）=1，证明：必存在ξ，η∈(a，b)，使得eη-ξ[f(η)+f’(η)]=1。

根据定积分的几何意义，下列各式中正确的是[]．

TheprototypeofBritishParliamentis

设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为 ______。

三级数据库技术

NCRE全国计算机三级

某ARM处理器仅工作于Thumb–2状态，该处理器的指令宽度是()。①8位②16位③32位④64位

嵌入式系统的性能在很大程度上是由CPU决定的，CPU的性能主要表现为指令执行速度的快慢。下列选项中不直接影响CPU速度的是()。

字符在嵌入式系统内部是使用二进制编码表示的，存储一个ASCII字符需要使用【43】_______个二进位，存储一个常用汉字需要使用【44】_______个二进位(采用GB2312编码标准)。

下面关于存储器的叙述中，错误的是()。

片上调试技术是许多嵌入式处理器芯片采用的硬件调试技术。【79】标准是片上调试技术的一种国际标准，常用于芯片和电路板的调试。该标准中规定的TAP接口具有【80】根信号线。

ARM处理器用一条指令完成有条件的无符号数加法运算，并更新CPSR中的状态，条件是如果相等，要求指令执行R1+R2，结果送R3中，则这条指令为【55】；如果条件是大于，要求指令执行R1-R2，结果放R3中，则该指令为【56】。

广义表是线性表的推广，是由零个或多个单元素或()所组成的有限序列。

设关系R和S的元组个数分别为100和300，关系T是R与S的笛卡尔积，则T的元组个数是

与r对策生物相比，K对策生物的出生率______。

"五体"中，与肾相合的是

下列哪些污染物必须在车间内或车间处理设施排放口采样?()

在长江三峡中，以“秀”著称的是()。

“点头微笑表示肯定，摇头皱眉表示否定”体现了情绪情感的()功能。

出租车队去机场接某会议的参会者，如果每车坐3名参会者，则需另外安排一辆大巴送走余下的50人；如每车坐4名参会者，则最后正好多出3辆空车。则该车队有_________辆出租车。

设f(x)在[a，b]上连续，在(a，b)上可导，且f（A）=f（B）=1，证明：必存在ξ，η∈(a，b)，使得eη-ξ[f(η)+f’(η)]=1。

根据定积分的几何意义，下列各式中正确的是[]．

TheprototypeofBritishParliamentis

字符在嵌入式系统内部是使用二进制编码表示的，存储一个ASCII字符需要使用【43】_个二进位，存储一个常用汉字需要使用【44】_个二进位(采用GB2312编码标准)。