首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
假设有一个长度为n的有序序列,在进行查找时,可以借助二叉树来进行,请结合二叉树的性质来分析二分查找的最坏性能和平均性能。
假设有一个长度为n的有序序列,在进行查找时,可以借助二叉树来进行,请结合二叉树的性质来分析二分查找的最坏性能和平均性能。
admin
2010-04-24
68
问题
假设有一个长度为n的有序序列,在进行查找时,可以借助二叉树来进行,请结合二叉树的性质来分析二分查找的最坏性能和平均性能。
选项
答案
假设判定树的内部结点的总数为n=2
h-1
-1。则判定树是深度为h=lg(n+1)的满二叉树,树中第k层上的结点的个数为2
h-1
,查找它们所需要比较的次数是k。则在等概率下,二分查找成功时的平均查找长度为:[*],如果n很大,则可以用如下近似公式:lg(n+1)-1,作为二分查找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度,在最坏情况下查找成功的比较次数也不超过判定树的深度。因为判定树中度数小于2的结点只可能在最下面的两层上
解析
转载请注明原文地址:https://kaotiyun.com/show/QMAx777K
本试题收录于:
数据结构题库理工类分类
0
数据结构
理工类
相关试题推荐
下列算法中属于动态路由选择算法的是()
_______由域名空间、域名服务器和地址转换请求程序三部分组成。
在因特网中被广泛使用的_______协议用到了动态路由选择算法中的链路状态路由算法。
____________即兼并与收购业务。兼并是指由两个或两个以上的企业实体形成新经济单位的交易活动;收购是指两家公司进行产权交易,由一家公司获得另一家公司的大部分或全部股权以达到控制该公司的交易活动。
下列有关现金漏损率的命题正确的是
下列关于间接融资的说法中,正确的有()
根据图1.6所示,写出其关联矩阵,指明各个顶点的度,并且指出其偶点与奇点。
设有指针head指向不带表头结点的单链表,用next表示结点的一个链域,指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中,使之成为第一个结点,则所需的操作为“p→next=head;”和“_______”。
树的后序遍历序列与其对应二叉树的_________遍历序列相同。
随机试题
Theshopassistantfindsitveryhardtosatisfythegirl,forsheistoo________aboutclothes.
下列关于资产评估报告的表述,错误的是()
A.商路B.细辛C.白前D.防己E.虎杖木质部射线较宽,导管稀少的是()
线路竣工测量的内容包括()。
阿Q的“________”使他常常陷入一种自欺欺人的精神满足状态。多年来,人们形象地称之为“________”。
自人类迈进二十一世纪以来,开发新能源成为全世界解决能源问题的共同出路。与化石燃料相比,新能源具有可再生、对环境友好等特点,更符合人类可持续发展的目标。其中,太阳能、风能、地热能、水能和潮汐能,是开发较早的新能源,已在实际生产生活中发挥了重要作用。曾一度被人
法律()是划分部门法的首要的、第一位标准。
下列事实中,能够形成不当得利之债的是()。
第3代计算机采用的电子元件是
HowInterpretersWork?I.UnderstandingA.Aboutwordsandexpressions—(1)_____wordsmaybeleftout:(1)______—Ifnotknowin
最新回复
(
0
)