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

admin2010-04-24 80

问题假设有一个长度为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)

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

数据结构

理工类

在OSI中，完成源机网络层来的数据可靠地传输到相邻节点的目标机网络层功能的层次是_______。

在数据单元上附加一些数据或是对数据单元作的密码变换，也就是信息的发送者使用公开密钥算法的主要技术产生的别人无法伪造的字符串的行为称作()

下列IP地址中属于B类地址的是()

经常被分析，非常重要的三类国际收支差额是_、_。

金融期权按行权时间的不同来划分，可以分为()

如图7．15所示交通图，试作出第一个流向图。

求下面费用矩阵对应的旅行问题的最佳路径。

设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的_______。

排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是_______。

关于审计程序，以下说法中，不恰当的是()。

下列哪项实验室检查结果不符合克罗恩病

患者女，26岁。原有风湿性主动脉瓣关闭不全，近3周乏力、发热。查体：皮肤少许瘀点，主动脉瓣区双期杂音，脾刚能触及；Hb80g／dL。导致该病最常见的病原微生物是

下列哪项为诊断黄疸的最重要依据

甲欠乙5000元，乙多次催促，甲拖延不还。后乙告诉甲必须在半个月内还钱，否则起诉。甲立即将家中仅有的值钱物品一九成新电冰箱和彩电各一台以150元价格卖给知情的丙，被乙发现。下列说法哪一项是错误的?

简述共同侵权时赔偿义务机关的确定。

下面的描述中，正确的是()。

在市场经济的条件下。如何对待重义轻利的传统?

Teachershavetobestrictwiththeirpupils,otherwisetheywillquicklyget______.

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

数据结构

理工类

在OSI中，完成源机网络层来的数据可靠地传输到相邻节点的目标机网络层功能的层次是_______。

在数据单元上附加一些数据或是对数据单元作的密码变换，也就是信息的发送者使用公开密钥算法的主要技术产生的别人无法伪造的字符串的行为称作()

下列IP地址中属于B类地址的是()

经常被分析，非常重要的三类国际收支差额是_________________、_________________。

金融期权按行权时间的不同来划分，可以分为()

如图7．15所示交通图，试作出第一个流向图。

求下面费用矩阵对应的旅行问题的最佳路径。

设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的_______。

排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是_______。

关于审计程序，以下说法中，不恰当的是()。

下列哪项实验室检查结果不符合克罗恩病

患者女，26岁。原有风湿性主动脉瓣关闭不全，近3周乏力、发热。查体：皮肤少许瘀点，主动脉瓣区双期杂音，脾刚能触及；Hb80g／dL。导致该病最常见的病原微生物是

下列哪项为诊断黄疸的最重要依据

甲欠乙5000元，乙多次催促，甲拖延不还。后乙告诉甲必须在半个月内还钱，否则起诉。甲立即将家中仅有的值钱物品一九成新电冰箱和彩电各一台以150元价格卖给知情的丙，被乙发现。下列说法哪一项是错误的?

简述共同侵权时赔偿义务机关的确定。

下面的描述中，正确的是()。

在市场经济的条件下。如何对待重义轻利的传统?

Teachershavetobestrictwiththeirpupils,otherwisetheywillquicklyget______.

经常被分析，非常重要的三类国际收支差额是_、_。