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

admin2010-05-13 34

问题设平衡的二叉排序树(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全国计算机三级

为了使操作系统容易在不同的硬件平台上进行移植，一些嵌入式操作系统包含有一个硬件抽象层，硬件抽象层的英文缩写是【71】，它位于【72】和硬件之间，从而隐藏了硬件平台的差异，避免了操作系统对硬件的直接访问。

实时操作系统完成每次任务所需时间的偏差称为【75】。评价实时系统的实时性最重要的指标是【76】，即系统从事件请求开始到任务完成的时间间隔。

为提高SoC的设计效率，减少重复开发，通常大多以IP核为基础，在单个芯片上集成处理器、存储器和各种接口等组件，组成一个相当完整的计算机系统。按照IC设计文件的类型，IP核通常分为三种：【41】核、固核和【42】核。

如下几种Bootloader中，用于Linux操作系统引导程序加载时所支持不同体系结构处理器种类最多的是()。

为了使操作系统容易在不同的硬件平台上进行移植，一些嵌入式操作系统包含有一个硬件抽象层，硬件抽象层的英文缩写是_【71】，它位于_【72】和硬件之间，从而隐藏了硬件平台的差异，避免了操作系统对硬件的直接访问。

Linux内核主要由5个子系统组成，下面选项中不属于这5个子系统的是()。

下列选项中用于完成创建任务的自用栈空间的μC／OS–Ⅱ程序源代码的是()。

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

下列关于嵌入式系统的软件结构的描述中，不正确的是()。

在ARMCortex—M3中可实现中断嵌套，中断可以改为比之前的中断服务程序更高的优先级，并且可以在运行时改变优先级状态，使用末尾连锁连续中断需要消耗_【51】个时钟周期，而普通中断需要_【52】个时钟周期。

对水泥砂浆的抗压强度若设计无规定，其抗压强度不得低于()。

A．RNA聚合酶B．末端转移酶C．碱性磷酸酶D．反转录酶合成cDNA用

下列选项中，可以适用属地原则确立我国《刑法》对案件的效力的有：()

《公路工程施工监理规范》中所指的“三级监理机构”是指()

假设要在表格的某行中填入数据序列2000～2020，下列哪种方法最好?()

所谓小康水平，是指在温饱的基础上，生活质量进一步提高，达到丰衣足食。()

将紫色洋葱鳞叶外表皮细胞置于30％的蔗糖溶液数分钟后，结果如图1所示，紫色分部的区域和影响色素分布的结构分别是()。

根据维果茨基的观点，心理机能由低级向高级发展的标志有()(2013．70)

设(1)求y(0)，y’(0)，并证明：(1一x2)y’’一xy’=4；(2)求的和函数及级数的值．

软件是指

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

三级数据库技术

NCRE全国计算机三级

为了使操作系统容易在不同的硬件平台上进行移植，一些嵌入式操作系统包含有一个硬件抽象层，硬件抽象层的英文缩写是【71】，它位于【72】和硬件之间，从而隐藏了硬件平台的差异，避免了操作系统对硬件的直接访问。

实时操作系统完成每次任务所需时间的偏差称为__________【75】。评价实时系统的实时性最重要的指标是__________【76】，即系统从事件请求开始到任务完成的时间间隔。

如下几种Bootloader中，用于Linux操作系统引导程序加载时所支持不同体系结构处理器种类最多的是()。

Linux内核主要由5个子系统组成，下面选项中不属于这5个子系统的是()。

下列选项中用于完成创建任务的自用栈空间的μC／OS–Ⅱ程序源代码的是()。

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

下列关于嵌入式系统的软件结构的描述中，不正确的是()。

在ARMCortex—M3中可实现中断嵌套，中断可以改为比之前的中断服务程序更高的优先级，并且可以在运行时改变优先级状态，使用末尾连锁连续中断需要消耗_________【51】个时钟周期，而普通中断需要_________【52】个时钟周期。

对水泥砂浆的抗压强度若设计无规定，其抗压强度不得低于()。

A．RNA聚合酶B．末端转移酶C．碱性磷酸酶D．反转录酶合成cDNA用

下列选项中，可以适用属地原则确立我国《刑法》对案件的效力的有：()

《公路工程施工监理规范》中所指的“三级监理机构”是指()

假设要在表格的某行中填入数据序列2000～2020，下列哪种方法最好?()

所谓小康水平，是指在温饱的基础上，生活质量进一步提高，达到丰衣足食。()

将紫色洋葱鳞叶外表皮细胞置于30％的蔗糖溶液数分钟后，结果如图1所示，紫色分部的区域和影响色素分布的结构分别是()。

根据维果茨基的观点，心理机能由低级向高级发展的标志有()(2013．70)

设(1)求y(0)，y’(0)，并证明：(1一x2)y’’一xy’=4；(2)求的和函数及级数的值．

软件是指

实时操作系统完成每次任务所需时间的偏差称为【75】。评价实时系统的实时性最重要的指标是【76】，即系统从事件请求开始到任务完成的时间间隔。

在ARMCortex—M3中可实现中断嵌套，中断可以改为比之前的中断服务程序更高的优先级，并且可以在运行时改变优先级状态，使用末尾连锁连续中断需要消耗_【51】个时钟周期，而普通中断需要_【52】个时钟周期。