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

admin2009-01-19 80

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

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

在请求页式存储管理中，当进程对页面()时，进行地址转换操作。

使用8259A进行中断控制时，CPU首先应对8259A内部的各寄存器写入相应的【　　】命令字ICW和操作命令字OCW，即要对8259A进行初始化编程。

磁盘是PC机中的主要辅助存储器之一，它的空间结构、数据存储格式等与操作系统密切相关。在Windows98环境,下列叙述中正确的是(　　　)。

一系统采用8255A并行I/O接口，初始化时CPU所访问的端口地址为0CBH，并设定为方式1输出，则A口的地址应为(　　　)。

程序设计语言中与硬件结合最紧密的是哪一种语言?

串行通信中，若收发双方的动作由一个时序信号控制，则称为(　　　)串行通信。

如果8251A设定为异步通信方式，发送器时钟输入端和接收器时钟输入端都连接到频率为2KHz的输入信号，波特率为1200，字符数据长度为7位，1位停止位，采用偶校验，则8251A的方式控制字为【　　】。

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

数据库管理系统、图形用户界面、互联网浏览器、媒体播放器等软件，如果运行在嵌入式系统上，往往具有内部结构精简，【69】轻量化，占用存储资源【70】的特点。

设z=z(x，y)由方程x2+z2=ln(z/y)确定，求dz.

(2007年)点在铅垂平面Oxy内的运动方程式中，t为时间，v0、g为常数。点的运动轨迹应为()。

股东从保护自身利益的角度出发，在确定股利分配政策时应考虑的因素有()。(2006年)

《党政机关公文处理工作条例》规定的公文种类有()。

人民民主专政所具有的中国特色是()。

下列各项是事业单位财务管理特点的是（）。

以下关于公文常识的说法正确的是()。

Thesenaturalresourceswillbe________soonerorlaterifthepresentrateofexploitationcontinues.

【B1】【B14】

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

三级数据库技术

NCRE全国计算机三级

在请求页式存储管理中，当进程对页面()时，进行地址转换操作。

使用8259A进行中断控制时，CPU首先应对8259A内部的各寄存器写入相应的【 】命令字ICW和操作命令字OCW，即要对8259A进行初始化编程。

磁盘是PC机中的主要辅助存储器之一，它的空间结构、数据存储格式等与操作系统密切相关。在Windows98环境,下列叙述中正确的是( )。

一系统采用8255A并行I/O接口，初始化时CPU所访问的端口地址为0CBH，并设定为方式1输出，则A口的地址应为( )。

程序设计语言中与硬件结合最紧密的是哪一种语言?

串行通信中，若收发双方的动作由一个时序信号控制，则称为( )串行通信。

如果8251A设定为异步通信方式，发送器时钟输入端和接收器时钟输入端都连接到频率为2KHz的输入信号，波特率为1200，字符数据长度为7位，1位停止位，采用偶校验，则8251A的方式控制字为【 】。

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

数据库管理系统、图形用户界面、互联网浏览器、媒体播放器等软件，如果运行在嵌入式系统上，往往具有内部结构精简，__________【69】轻量化，占用存储资源__________【70】的特点。

设z=z(x，y)由方程x2+z2=ln(z/y)确定，求dz.

(2007年)点在铅垂平面Oxy内的运动方程式中，t为时间，v0、g为常数。点的运动轨迹应为()。

股东从保护自身利益的角度出发，在确定股利分配政策时应考虑的因素有()。(2006年)

《党政机关公文处理工作条例》规定的公文种类有()。

人民民主专政所具有的中国特色是()。

下列各项是事业单位财务管理特点的是（）。

以下关于公文常识的说法正确的是()。

Thesenaturalresourceswillbe________soonerorlaterifthepresentrateofexploitationcontinues.

【B1】【B14】

使用8259A进行中断控制时，CPU首先应对8259A内部的各寄存器写入相应的【　　】命令字ICW和操作命令字OCW，即要对8259A进行初始化编程。

磁盘是PC机中的主要辅助存储器之一，它的空间结构、数据存储格式等与操作系统密切相关。在Windows98环境,下列叙述中正确的是(　　　)。

一系统采用8255A并行I/O接口，初始化时CPU所访问的端口地址为0CBH，并设定为方式1输出，则A口的地址应为(　　　)。

串行通信中，若收发双方的动作由一个时序信号控制，则称为(　　　)串行通信。

如果8251A设定为异步通信方式，发送器时钟输入端和接收器时钟输入端都连接到频率为2KHz的输入信号，波特率为1200，字符数据长度为7位，1位停止位，采用偶校验，则8251A的方式控制字为【　　】。

数据库管理系统、图形用户界面、互联网浏览器、媒体播放器等软件，如果运行在嵌入式系统上，往往具有内部结构精简，【69】轻量化，占用存储资源【70】的特点。