首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均检索长度为
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均检索长度为
admin
2010-05-13
50
问题
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均检索长度为
选项
A、O(1)
B、O(log
2
n)
C、O(n)
D、O(nlog
2
n)
答案
2
解析
平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1,若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡酌。因为AVL树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和log
2
n是同数量级的(N为结点个数)。因此,它的平均查找长度也和log
2
n同数量级。
转载请注明原文地址:https://kaotiyun.com/show/j3SZ777K
本试题收录于:
三级数据库技术题库NCRE全国计算机三级分类
0
三级数据库技术
NCRE全国计算机三级
相关试题推荐
下列系统属于实时系统的是()。
下面哪种设备是组建以太局域网必不可少的?
以下关于VxWorks操作系统的叙述中,错误的是()。
程序存储器和数据存储器仅用一套总线与CPU连接的这种存储结构称为【47】结构,程序存储器和数据存储器分开采用两套总线与CPU连接的存储结构称为【48】结构。
按照实时性能和内核结构划分,VxWorks操作系统属于()。
以下是有关TCP/IP协议中IP地址格式(IPv4)的叙述,其中错误的是()。
下面是IP协议中C类IP地址有关规定的叙述,其中正确的是()。
在μC/OS–Ⅱ中,OSInit()函数先建立最初的任务就绪表,然后建立4个空白的数据链表。这4个空白的数据链表是()。
汉字有多种不同的编码标准,下面关于不同编码标准之间关系的叙述中,错误的是()。
下面是嵌入式系统硬件部分的逻辑组成及其与外部世界关系的示意图,其中的组成部分A是__________【41】接口;组成部分B是__________【42】接口。
随机试题
患儿,8个月,发现面色苍白6个月,妊娠32周早产,出生体重2.3kg,牛乳喂养,未添加辅食,现体重6kg,皮肤黏膜苍白,肝肋下3cm,脾肋下1cm,Hb80g/L,红细胞3.8×1012/L,网织红细胞0.4%。其贫血程度是
防火或机械性要求高的场所,宜用()。
抗原抗体形成明显沉淀物的条件是
面黄虚浮,称为
通过检测下列哪些腺体的唾液分泌量来定量检查涎腺分泌功能
用于抗结核杆菌的药物是口服用于肠道感染或肠道手术前准备的药物是
根据《药品经营质量管理规范》,以下说法错误的是
根据《建设工程工程量清单计价规范》GB50500—2013,某工程项目的钢筋由发包人在施工合同签订后,与承包人一起招标采购,编制招标工程量清单时,招标人将HR335钢筋暂估价定为4200元/吨,已知市场平均价格为3650元/吨,若甲投标人自行采购,其采购单
中国工人的勤劳、踏实、肯干是世所公认的,勤劳度和敬业度反差鲜明,说明其背后应有更深层原因。勤劳度由个体自身素质所决定,敬业度取决于劳动力市场状况。一个勤劳度很高的个体,在不尽如人意的劳动力市场中,很难表现出让人满意的敬业度来。如果工人对企业缺乏起码的认同感
Beinganintrovertisabadthing,right?Well,alotofpeopleseemtothinkso,judgingbythenumberofarticlesI’vereadab
最新回复
(
0
)