假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。

admin2010-04-24 77

问题假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。

选项

答案假设判定树的内部结点的总数为n=2^h-1-1。则判定树是深度为h=lg(n+1)的满二叉树，树中第k层上的结点的个数为2^h-1，查找它们所需要比较的次数是k。则在等概率下，二分查找成功时的平均查找长度为：[*]，如果n很大，则可以用如下近似公式：lg(n+1)-1，作为二分查找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。因为判定树中度数小于2的结点只可能在最下面的两层上

解析

转载请注明原文地址:https://www.kaotiyun.com/show/QMAx777K

本试题收录于：数据结构题库理工类分类

数据结构

理工类

相关试题推荐

随机试题

最新回复(0)

假设有一个长度为n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。

数据结构

理工类

ATM网络支持面向连接的信元交换，数据信元交换之前必须建立________。()

下列不属于HDLC常用的操作方式的是()

通常分配给小型局域网使用的IP地址类型是()

在因特网中被广泛使用的_______协议用到了动态路由选择算法中的链路状态路由算法。

由一台中央主计算机连接大量的地理上处于分散位置的终端的系统称为_________。

简述经济增长对汇率变动的影响。

在推进利率市场化的改革进程中，存、贷款利率市场进行的顺序是_________________________________；先贷款，后存款；先长期、大额，后短期、小额。

某运输公司接受了一项货运业务，如表7．6所示，收发货点的位置如图7．33所示，求车辆最优调度方案。

对长度为20的有序表进行二分查找，试画出它的一棵判定树。

反应

治疗氨基甲酸酯类农药中毒的首选药是

城镇体系的特征不包括()。

信用卡是银行或旅行公司为了方便旅行者，在旅行者交存一定金额后签发的一种面额固定、没有指定付款人和付款地点的定额票据。()

我国地大物博，许多风景名胜和古迹分布在名山大川之中。下列关于我国风景名胜的叙述中，有错误的是()。

建设资源节约型、环境友好型社会要注意________，目前要着重解决影响社会经济发展，特别是严重危害人民群众健康的水污染、空气污染加剧问题。填入画横线部分最恰当的一项是()。

•Youwillhearthreetelephoneconversationsormessages.•Writeoneortwowordsoranumberinthenumberedspacesontheno

Oursondoesn’tknowwhat______toattheuniversity;hecan’tmakeuphismindabouthisfuture.

WhydoesthewomantakeTheoreticalDynamicsagain?