首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均查找长度的数量级为 ______。
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均查找长度的数量级为 ______。
admin
2010-05-13
32
问题
设平衡的二叉排序树(AVL树)的结点个数为n,则其平均查找长度的数量级为 ______。
选项
A、O(1)
B、0(log
2
n)
C、O(n)
D、0(nlog
2
n)
答案
2
解析
平衡二叉树又称AVL树。它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和logN是同数量级的(N为结点个数)。由此,它的平均查找长度也和logN同数量级。
转载请注明原文地址:https://jikaoti.com/ti/J1C7FFFM
本试题收录于:
三级数据库技术题库NCRE全国计算机三级分类
0
三级数据库技术
NCRE全国计算机三级
相关试题推荐
无线局域网采用的通信协议主要是【45】,通常也称为Wi-Fi,它有几种不同的数据传输速率,其中【46】协议的数据传输速率可达108Mbps甚至更高,可以满足传输语音、数据、图像等的需要
如存储器的工作频率为333MHz,数据线宽度为32位,每个周期传输1次数据,则存储器的带宽=__________【63】MB/s。若存储器总线采用串行总线,以10位为一个数据帧(包含一个字节的存储数据),则总线带宽=总线频率/__________【64】。
无线局域网采用的通信协议主要是802.11,通常也称为【45】,为了能满足传输语音、数据、图像等需要,目前使用的802.11n协议其数据传输速率可达【46】Mbps甚至更高,相应的产品已经广泛使用。
基于ARM内核的嵌入式芯片中的中断控制器的功能是对芯片中相关硬件组件的中断请求进行管理和控制,一般采用___________【63】中断(VIC)或___________【64】中断(NVIC)方式管理中断。
以下不属于ARM处理器的特点是()。
下面是关于嵌入式系统使用的存储器的叙述,其中正确的是()。
与个人计算机(PC)相比,嵌入式系统具有许多不同的特点。下面不属于嵌入式系统特点的是()。
与个人计算机(PC)相比,嵌入式系统具有许多不同的特点。下面不属于嵌入式系统特点的是()。
引用一个在其它文件中的标号I~ablel的伪指令为【65】,声明一个全局标号I~able2以便其它文件引用,该伪指令为【66】。
嵌入式系统中的CPU具有一些与通用计算机所使用CPU不同的特点,下面不是其特点的是()。
随机试题
Itwilltakeyouonehourandfiftyminutes________thetopofMountTai.
肺通气的原动力来自
男,45岁,煤矿工人,被煤块砸伤腰背部后感腰痛,伴双下肢感觉运动障碍及大小便失禁24小时入院。体查:腰1椎体后突畸形,压痛,腹股沟以下平面感觉运动完全丧失。X线片示腰1椎体压缩1/2,向后成角畸形。该病常见并发症应除外
对于相互替代的产品,当一种产品价格上涨,替代品的需求就会降低。()
下列关于持有到期收益率的公式,正确的是( )。
在不同规模的投资中心之间进行业绩比较时,使用剩余收益指标优于投资报酬率指标。()
旅行社组织出境旅游,应当制作()。
一、注意事项1-本题本由给定资料与作答要求两部分构成,考试时限为150分钟。其中,阅读给定资料参考时限为40分钟,作答参考时限为110分钟。2.请在题本、答题卡指定位置上用黑色字迹的钢笔或签字笔填写自己的姓名和准考证号。并用2B铅笔在准考证号对应的数字
法律意识有不同的形态,既有宏观的,也有微观的,既有传统的,也有现代的。以下哪种法律意识的形态中集中反映一个国家或民族的法律文化、法律传统,体现一个社会法制的总体发展程度?()
Therealtrouble______theirlackofconfidenceintheirabilities.
最新回复
(
0
)