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

admin2010-05-13 40

问题设平衡的二叉排序树(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://jikaoti.com/ti/tWC7FFFM

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

以下关于互联网IP地址的叙述中，错误的是()。

以ARM内核为基础的嵌入式处理器芯片采用系统总线与外围总线的层次结构方式构建片上系统，下面列出的组件中，不与外围总线相连的组件是()。

为了连接ARM内核与处理器芯片中的其他各种组件，ARM公司定义了总线规范，该规范用4个大写英文字母表示为【57】，即先进的微控制器【58】体系结构。

以下关于ARM处理器寄存器说法错误的是()。

一幅没有经过数据压缩的彩色图像，其数据量是768KB，分辨率为1024×768，那么它每个像素的像素深度是()。

下面是有关嵌入式系统的最小系统组成的叙述：Ⅰ．嵌入式最小系统包括嵌入式处理器Ⅱ．嵌入式最小系统包括电源电路Ⅲ．嵌入式最小系统包括时钟电路Ⅳ．嵌入式最小系统包括复位电路上述叙述中，正确的是()。

下图给出了产生嵌入式处理器时钟信号的两种方法，其中左图为使用_【55】时钟信号发生器产生嵌入式处理器时钟信号的方法，右图为使用_【56】时钟信号源产生嵌入式处理器时钟信号的方法。

汉字有多种不同的编码标准，下面关于不同编码标准之间关系的叙述中，错误的是()。

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

在ADS1．2的集成开发环境中，若生成的输出文件需要包含所有的调试信息，那么，生成目标应该选择为【79】_。若目标系统地址映射关系比较复杂时，应使用【80】_格式的文件来说明地址映射方式。

钢管、钢罐一旦被雷击穿，其介质对周围环境造成危险时。其壁厚不得小于多少毫米允许作为接闪器?[2004年第111题]

脾的功能有()、调节血细胞数量、贮血和免疫。

常用来焊接铝镁合金以外的铝合金的通用焊丝牌号是HS331。()

下列有关皮质激素的叙述正确的是

糖皮质激素影响伤口愈合的主要原因是()。

A．阿卡波糖B．二甲双胍C．罗格列酮D．西格列汀E．格列吡嗪属于α-葡萄糖苷酶抑制剂的是()。

从界面管理的角度来说，对待纵向方面的问题应采取等级弱化的原则，即采取措施()，实行一体化管理。

采用适当方法对设计概算进行审查，是确保审查质量、提高审查效率的关键。其中，对审查中发现的主要问题以及有较大偏差的设计进行复核，对重要、关键设备和生产装置或投资较大的项目进行复查是()。

阅读下面材料，回答问题。某教师回到办公室说：“二(2)的学生真笨，这堂课我连续讲了三遍，他们还是不会，我是发挥了教师的主导作用了，他们不会我有什么办法?”你如何理解教师的主导作用?

CriticsmaintainthatthefictionofHermanMelville(1819-1891)haslimitations,suchasitslackofinventiveplotsafterMoby

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

三级数据库技术

NCRE全国计算机三级

以下关于互联网IP地址的叙述中，错误的是()。

以ARM内核为基础的嵌入式处理器芯片采用系统总线与外围总线的层次结构方式构建片上系统，下面列出的组件中，不与外围总线相连的组件是()。

为了连接ARM内核与处理器芯片中的其他各种组件，ARM公司定义了总线规范，该规范用4个大写英文字母表示为【57】，即先进的微控制器【58】体系结构。

以下关于ARM处理器寄存器说法错误的是()。

一幅没有经过数据压缩的彩色图像，其数据量是768KB，分辨率为1024×768，那么它每个像素的像素深度是()。

下面是有关嵌入式系统的最小系统组成的叙述：Ⅰ．嵌入式最小系统包括嵌入式处理器Ⅱ．嵌入式最小系统包括电源电路Ⅲ．嵌入式最小系统包括时钟电路Ⅳ．嵌入式最小系统包括复位电路上述叙述中，正确的是()。

下图给出了产生嵌入式处理器时钟信号的两种方法，其中左图为使用___________【55】时钟信号发生器产生嵌入式处理器时钟信号的方法，右图为使用___________【56】时钟信号源产生嵌入式处理器时钟信号的方法。

汉字有多种不同的编码标准，下面关于不同编码标准之间关系的叙述中，错误的是()。

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

在ADS1．2的集成开发环境中，若生成的输出文件需要包含所有的调试信息，那么，生成目标应该选择为【79】_______。若目标系统地址映射关系比较复杂时，应使用【80】_______格式的文件来说明地址映射方式。

钢管、钢罐一旦被雷击穿，其介质对周围环境造成危险时。其壁厚不得小于多少毫米允许作为接闪器?[2004年第111题]

脾的功能有()、调节血细胞数量、贮血和免疫。

常用来焊接铝镁合金以外的铝合金的通用焊丝牌号是HS331。()

下列有关皮质激素的叙述正确的是

糖皮质激素影响伤口愈合的主要原因是()。

A．阿卡波糖B．二甲双胍C．罗格列酮D．西格列汀E．格列吡嗪属于α-葡萄糖苷酶抑制剂的是()。

从界面管理的角度来说，对待纵向方面的问题应采取等级弱化的原则，即采取措施()，实行一体化管理。

采用适当方法对设计概算进行审查，是确保审查质量、提高审查效率的关键。其中，对审查中发现的主要问题以及有较大偏差的设计进行复核，对重要、关键设备和生产装置或投资较大的项目进行复查是()。

阅读下面材料，回答问题。某教师回到办公室说：“二(2)的学生真笨，这堂课我连续讲了三遍，他们还是不会，我是发挥了教师的主导作用了，他们不会我有什么办法?”你如何理解教师的主导作用?

CriticsmaintainthatthefictionofHermanMelville(1819-1891)haslimitations,suchasitslackofinventiveplotsafterMoby

下图给出了产生嵌入式处理器时钟信号的两种方法，其中左图为使用_【55】时钟信号发生器产生嵌入式处理器时钟信号的方法，右图为使用_【56】时钟信号源产生嵌入式处理器时钟信号的方法。

在ADS1．2的集成开发环境中，若生成的输出文件需要包含所有的调试信息，那么，生成目标应该选择为【79】_。若目标系统地址映射关系比较复杂时，应使用【80】_格式的文件来说明地址映射方式。