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

admin2009-01-19 82

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

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

答案2

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

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

在以下有关显示器性能参数的叙述中，错误的是

下面关于8237可编程DMA控制器的叙述中，错误的是

下面关于总线的叙述中，错误的是

在人机交互设备与人机接口之间的信息传输中，当前大多数采用(　　　)通信方式。

PC机中，I/O端口常用的地址范围是(　　　)。

以太网中的计算机相互通信时，为了避免冲突，采用下面哪一种方法和协议?

Windows98是由多个模块组成的一个功能强大的操作系统，下列哪个模块负责处理键盘和鼠标的输入，井以窗口、图标、菜单和其他界面元素的形式完成输出任务?

(2011年04月)企业出于自身利益的考虑，未向消费者披露与产品相关的价值、功效、用途或安全的信息，这种不道德行为属于_________。

A、高热骤降，涕泪横流。两目红赤B、高热不退，咳嗽气促，鼻煽痰鸣C、壮热起伏，烦躁不安，咳嗽阵作D、高热不退，烦躁谵妄，四肢抽搐E、咽喉肿痛，咳声重浊，声如犬吠麻疹邪毒攻喉证在麻疹的基础上证见

燥邪犯肺证与肺阴虚证的鉴别要点是

下列选项中，属于煤矿安全监察方式的是()。

该书法作品的作者是()。

现在很多人在街头进行街头绘画或者临摹世界名画，在人行通道演奏乐器，精湛的技艺经常引起人们的围观。这种现象引起了交通堵塞，你是街道办事处的工作人员，你将会如何劝阻，请现场模拟一下。

下边对加点词语的解释不合文意的一项是。从文章中我们可以看出作者的性格倾向于。

在中国确立社会主义制度是中国共产党在波澜壮阔的历史进程中为中华民族作出的三个伟大历史贡献之一。社会主义基本制度的确立()

顺序执行下列两个语句的输出结果是_________。Strings="全国计算机等级考试"；Systeth.out.println(s.length())

OntheOriginofBodyLanguageTheOriginofBodyLanguagehasalottodowiththeemotions.Theemotionsareahottopicof

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

三级数据库技术

NCRE全国计算机三级

在以下有关显示器性能参数的叙述中，错误的是

下面关于8237可编程DMA控制器的叙述中，错误的是

下面关于总线的叙述中，错误的是

在人机交互设备与人机接口之间的信息传输中，当前大多数采用( )通信方式。

PC机中，I/O端口常用的地址范围是( )。

以太网中的计算机相互通信时，为了避免冲突，采用下面哪一种方法和协议?

Windows98是由多个模块组成的一个功能强大的操作系统，下列哪个模块负责处理键盘和鼠标的输入，井以窗口、图标、菜单和其他界面元素的形式完成输出任务?

(2011年04月)企业出于自身利益的考虑，未向消费者披露与产品相关的价值、功效、用途或安全的信息，这种不道德行为属于_________。

A、高热骤降，涕泪横流。两目红赤B、高热不退，咳嗽气促，鼻煽痰鸣C、壮热起伏，烦躁不安，咳嗽阵作D、高热不退，烦躁谵妄，四肢抽搐E、咽喉肿痛，咳声重浊，声如犬吠麻疹邪毒攻喉证在麻疹的基础上证见

燥邪犯肺证与肺阴虚证的鉴别要点是

下列选项中，属于煤矿安全监察方式的是()。

该书法作品的作者是()。

现在很多人在街头进行街头绘画或者临摹世界名画，在人行通道演奏乐器，精湛的技艺经常引起人们的围观。这种现象引起了交通堵塞，你是街道办事处的工作人员，你将会如何劝阻，请现场模拟一下。

下边对加点词语的解释不合文意的一项是______。从文章中我们可以看出作者的性格倾向于______。

在中国确立社会主义制度是中国共产党在波澜壮阔的历史进程中为中华民族作出的三个伟大历史贡献之一。社会主义基本制度的确立()

顺序执行下列两个语句的输出结果是_________。Strings="全国计算机等级考试"；Systeth.out.println(s.length())

OntheOriginofBodyLanguageTheOriginofBodyLanguagehasalottodowiththeemotions.Theemotionsareahottopicof

在人机交互设备与人机接口之间的信息传输中，当前大多数采用(　　　)通信方式。

PC机中，I/O端口常用的地址范围是(　　　)。

下边对加点词语的解释不合文意的一项是。从文章中我们可以看出作者的性格倾向于。