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

admin2010-04-24 91

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

数据结构

理工类

HTTP的核心问题是()

数据链路层通过使用计数器和_______来保证每帧都能被正确地递交给目标网络层一次。

下列IP地址有误的是()

________提供在串行通信线路上封装IP分组的简单方法，用以远程用户通过电话线和MODEM能方便地接入TCP／IP网络。()

使用PPP协议传输4000个汉字(双字节)的文章，PPP帧的控制字符为10个字节，若已知净荷域最大值使用默认长度1500字节，问需要分为几帧传输才能完全传完?帧长总共为多少字节?

货币供给的过程可分为两个紧密相连的部分，他们分别是_、_________。

一个运输问题的运价、产量、销量由表4．38给出，用最小元素法写出初始调运方案表。

用匈牙利算法求解下述指派问题．效率矩阵如下：

有两个化肥厂A1、A2，存储化肥数量分别为800t和1000t，现将这些化肥运到三个市场B1、B2、B3去出售，各市场需求量分别为300t、950t、650t．已知各化肥厂到各市场的单位运费如下表试建立该问题的数学模型，使总运费

按照《环境影响评价公众参与暂行办法》的规定，建设单位或者其委托的环境影响评价机构，可以采取(　　　)方式，公开便于公众理解的环境影响评价报告书的简本。

关于工业项目建设地点的选择，下列说法正确的是()。

()是指在一定职业活动中应遵循的、体现一定职业特征的、调整一定职业关系的职业行为准则和规范。

计算应纳税所得额时，下列()项目不得在企业所得税前扣除。

福利管理的流程包括()。

网络的______称为拓扑结构。

相比较于2005年，2010年该县的GDP值()。

[2005年]设函数u(x，y)=φ(x+y)+φ(x—y)+∫x-yx+yψ(t)dt，其中φ具有二阶导数，ψ具有一阶导数，则必有()．

A、Nosmokingordrinkingguaranteeshappiness.B、Kidswithhappycharactersarelessinclinedtodrink.C、Unhappykidsaremore

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

数据结构

理工类

HTTP的核心问题是()

数据链路层通过使用计数器和_______来保证每帧都能被正确地递交给目标网络层一次。

下列IP地址有误的是()

________提供在串行通信线路上封装IP分组的简单方法，用以远程用户通过电话线和MODEM能方便地接入TCP／IP网络。()

使用PPP协议传输4000个汉字(双字节)的文章，PPP帧的控制字符为10个字节，若已知净荷域最大值使用默认长度1500字节，问需要分为几帧传输才能完全传完?帧长总共为多少字节?

货币供给的过程可分为两个紧密相连的部分，他们分别是___________、___________________。

一个运输问题的运价、产量、销量由表4．38给出，用最小元素法写出初始调运方案表。

用匈牙利算法求解下述指派问题．效率矩阵如下：

有两个化肥厂A1、A2，存储化肥数量分别为800t和1000t，现将这些化肥运到三个市场B1、B2、B3去出售，各市场需求量分别为300t、950t、650t．已知各化肥厂到各市场的单位运费如下表试建立该问题的数学模型，使总运费

按照《环境影响评价公众参与暂行办法》的规定，建设单位或者其委托的环境影响评价机构，可以采取( )方式，公开便于公众理解的环境影响评价报告书的简本。

关于工业项目建设地点的选择，下列说法正确的是()。

()是指在一定职业活动中应遵循的、体现一定职业特征的、调整一定职业关系的职业行为准则和规范。

计算应纳税所得额时，下列()项目不得在企业所得税前扣除。

福利管理的流程包括()。

网络的______称为拓扑结构。

相比较于2005年，2010年该县的GDP值()。

[2005年]设函数u(x，y)=φ(x+y)+φ(x—y)+∫x-yx+yψ(t)dt，其中φ具有二阶导数，ψ具有一阶导数，则必有()．

A、Nosmokingordrinkingguaranteeshappiness.B、Kidswithhappycharactersarelessinclinedtodrink.C、Unhappykidsaremore

货币供给的过程可分为两个紧密相连的部分，他们分别是_、_________。

按照《环境影响评价公众参与暂行办法》的规定，建设单位或者其委托的环境影响评价机构，可以采取(　　　)方式，公开便于公众理解的环境影响评价报告书的简本。

　　相比较于2005年，2010年该县的GDP值()。