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

admin2009-01-19 92

问题设平衡的二叉排序树(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/TTcZ777K

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

三级数据库技术

NCRE全国计算机三级

相关试题推荐

随机试题

最新回复(0)

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

三级数据库技术

NCRE全国计算机三级

下面不具备多道程序设计的特点的是

在指令“ADDR，Ad”中，源操作数在前，目的操作数在后，该指令执行的操作是(　　　)。

Internet　的主干线路传输速率很高，能达到几十或几百Mb/s，甚至达到几十或几百Gb/s。一般采用______作为传输介质。

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

在微机系统中，CPU是在时钟信号控制下，按节拍有序地执行指令序列。从取指令开始，经过分析指令、对操作数寻址，然后______保存操作结果，这个过程称为指令执行周期。

请编制程序，其功能是：内存中连续存放着20个无符号字节数序列，请将它们排成升序(从小到大)。例如：内存中有01H,04H,02H…(假设后17个字节均大与04H)结果为01H,02H,04H…(后跟17个字节，按从小到大的顺

Windows98注册表的数据结构是层次型的，最高层共有6个根键，其中有些是主根键，有些是动态键或别名。主根键的个数有(　　　)个。

CCD芯片的像素数目是数码相机的重要性能指标，它与可拍摄的图像分辨率有密切的关系。假定一台200万像素数码相机，它所拍摄的像片能达到的最大分辨率是多少?______

微处理器在执行一条指令时，主要将它分解成以下几个步骤去完成，其中顺序正确的是

患者，男，36岁。平素嗜酒，今晨脘腹痞闷，口苦纳少，口干不欲饮，舌红苔黄腻，脉滑数。治疗最佳方为

女性，35岁。诉水肿就诊。尿液检查蛋白(+)，红细胞5～10个／HP，白细胞2～3个／HP，颗粒管型0～2个／HP，拟诊慢性肾炎。体检时最可能发现水肿的部位是

关于刑事诉讼法定代理人与诉讼代理人的区别，下列哪些选项是正确的?

()是中华民族的优良传统，是一个人立足于社会的基本准则，也是对从业者的道德要求。

在借贷记账法下，将账户划分为借、贷两方，哪一方登记增加，哪一方登记减少的依据是()。

下列各项中，不属于社会审计实施阶段工作的是()。

张先生提前为3岁的儿子未来的小学教育进行投资规划，下列投资中比较适合的是()。

单利和复利的区别在于()。

LRU页面调度算法是选择()的页面先调出。

A、JasondamagedMike’scarinanoccident.B、Jasonjustboughtanewcar.C、JasonboughtanewcarforMike.D、Jasoncouldn’tfi

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

三级数据库技术

NCRE全国计算机三级

下面不具备多道程序设计的特点的是

在指令“ADDR，Ad”中，源操作数在前，目的操作数在后，该指令执行的操作是( )。

Internet 的主干线路传输速率很高，能达到几十或几百Mb/s，甚至达到几十或几百Gb/s。一般采用______作为传输介质。

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

在微机系统中，CPU是在时钟信号控制下，按节拍有序地执行指令序列。从取指令开始，经过分析指令、对操作数寻址，然后______保存操作结果，这个过程称为指令执行周期。

请编制程序，其功能是：内存中连续存放着20个无符号字节数序列，请将它们排成升序(从小到大)。例如：内存中有01H,04H,02H…(假设后17个字节均大与04H)结果为01H,02H,04H…(后跟17个字节，按从小到大的顺

Windows98注册表的数据结构是层次型的，最高层共有6个根键，其中有些是主根键，有些是动态键或别名。主根键的个数有( )个。

CCD芯片的像素数目是数码相机的重要性能指标，它与可拍摄的图像分辨率有密切的关系。假定一台200万像素数码相机，它所拍摄的像片能达到的最大分辨率是多少?______

微处理器在执行一条指令时，主要将它分解成以下几个步骤去完成，其中顺序正确的是

患者，男，36岁。平素嗜酒，今晨脘腹痞闷，口苦纳少，口干不欲饮，舌红苔黄腻，脉滑数。治疗最佳方为

女性，35岁。诉水肿就诊。尿液检查蛋白(+)，红细胞5～10个／HP，白细胞2～3个／HP，颗粒管型0～2个／HP，拟诊慢性肾炎。体检时最可能发现水肿的部位是

关于刑事诉讼法定代理人与诉讼代理人的区别，下列哪些选项是正确的?

()是中华民族的优良传统，是一个人立足于社会的基本准则，也是对从业者的道德要求。

在借贷记账法下，将账户划分为借、贷两方，哪一方登记增加，哪一方登记减少的依据是()。

下列各项中，不属于社会审计实施阶段工作的是()。

张先生提前为3岁的儿子未来的小学教育进行投资规划，下列投资中比较适合的是()。

单利和复利的区别在于()。

LRU页面调度算法是选择()的页面先调出。

A、JasondamagedMike’scarinanoccident.B、Jasonjustboughtanewcar.C、JasonboughtanewcarforMike.D、Jasoncouldn’tfi

在指令“ADDR，Ad”中，源操作数在前，目的操作数在后，该指令执行的操作是(　　　)。

Internet　的主干线路传输速率很高，能达到几十或几百Mb/s，甚至达到几十或几百Gb/s。一般采用______作为传输介质。

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

Windows98注册表的数据结构是层次型的，最高层共有6个根键，其中有些是主根键，有些是动态键或别名。主根键的个数有(　　　)个。