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

admin2010-05-13 53

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

ARM芯片内部集成的测试电路常采用一种被称为联合测试行动小组的国际标准测试协议，它一般用四个大写字母【59】表示，主要用于芯片内部测试及对系统进行仿真、调试，还可以实现对ARM芯片的【60】编程功能。

计算机网络由计算机等智能电子设备(网络终端)、数据链路、【43】以及网络软件等组成。网络中的每个网络终端都配一个网卡，每个网卡都有全球唯一的【44】位二进制的MAC地址。

Linux操作系统内核的网络模块可分为两部分：一部分提供对各种网络资源访问的控制，称为网络【75】；另一部分提供对各种网络硬件的支持，称为网络【76】。

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

GCC是针对Linux操作系统环境下应用程序的编译工具，下面叙述中错误的是()。

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

调试(debug)与测试(test)既有联系又有区别。验证模块／系统的功能和性能，发现错误是【77】的目的。分析所发现的错误，检查错误原因，定位故障(错误)位置和进行修改是【78】的目的。

嵌入式Linux操作系统由用户进程、OS服务组件和Linux内核3个部分组成(如图)，下面选项中正确的是()。

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

如存储器的工作频率为333MHz，数据线宽度为32位，每个周期传输1次数据，则存储器的带宽=【63】MB／s。若存储器总线采用串行总线，以10位为一个数据帧(包含一个字节的存储数据)，则总线带宽=总线频率／【64】。

车辆因故停止行驶后，车主可以办理养路费停征手续。()

结肠癌最主要的转移途径为

听觉感受器是

通过建立和健全劳动监察、劳动行政管理、劳动争议的处理机制，维护正常劳动秩序，这表现为劳动法的()基本原则。

下列说法中正确的有()。

教育学就是教育经验的汇编。()

VitruvianGymAspartofour10thanniversarycelebration,wearegivingnewmembersthechancetotryoutanyofourfitnesscl

【B1】【B4】

Hedependsmoreondiligencethanclevernessinachievinghisgoal．

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

三级数据库技术

NCRE全国计算机三级

ARM芯片内部集成的测试电路常采用一种被称为联合测试行动小组的国际标准测试协议，它一般用四个大写字母【59】表示，主要用于芯片内部测试及对系统进行仿真、调试，还可以实现对ARM芯片的【60】编程功能。

计算机网络由计算机等智能电子设备(网络终端)、数据链路、【43】以及网络软件等组成。网络中的每个网络终端都配一个网卡，每个网卡都有全球唯一的【44】位二进制的MAC地址。

Linux操作系统内核的网络模块可分为两部分：一部分提供对各种网络资源访问的控制，称为网络__________【75】；另一部分提供对各种网络硬件的支持，称为网络__________【76】。

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

GCC是针对Linux操作系统环境下应用程序的编译工具，下面叙述中错误的是()。

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

调试(debug)与测试(test)既有联系又有区别。验证模块／系统的功能和性能，发现错误是__________【77】的目的。分析所发现的错误，检查错误原因，定位故障(错误)位置和进行修改是__________【78】的目的。

嵌入式Linux操作系统由用户进程、OS服务组件和Linux内核3个部分组成(如图)，下面选项中正确的是()。

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

如存储器的工作频率为333MHz，数据线宽度为32位，每个周期传输1次数据，则存储器的带宽=【63】MB／s。若存储器总线采用串行总线，以10位为一个数据帧(包含一个字节的存储数据)，则总线带宽=总线频率／【64】。

车辆因故停止行驶后，车主可以办理养路费停征手续。()

结肠癌最主要的转移途径为

听觉感受器是

通过建立和健全劳动监察、劳动行政管理、劳动争议的处理机制，维护正常劳动秩序，这表现为劳动法的()基本原则。

下列说法中正确的有()。

教育学就是教育经验的汇编。()

VitruvianGymAspartofour10thanniversarycelebration,wearegivingnewmembersthechancetotryoutanyofourfitnesscl

【B1】【B4】

Hedependsmoreondiligencethanclevernessinachievinghisgoal．

Linux操作系统内核的网络模块可分为两部分：一部分提供对各种网络资源访问的控制，称为网络【75】；另一部分提供对各种网络硬件的支持，称为网络【76】。

调试(debug)与测试(test)既有联系又有区别。验证模块／系统的功能和性能，发现错误是【77】的目的。分析所发现的错误，检查错误原因，定位故障(错误)位置和进行修改是【78】的目的。