在某个二叉查找树(即二叉排序树)中进行查找时，效率最差的情形是该二叉查找树是( )。

admin2016-05-10 8

问题在某个二叉查找树(即二叉排序树)中进行查找时，效率最差的情形是该二叉查找树是( )。

选项 A、完全二叉树
B、平衡二叉树
C、单枝树
D、满二叉树

答案C

解析本题考查数据结构基础知识。非空二叉查找树中的结点分布特点是左子树中的结点均小于树根，右子树中的结点均大于树根。因此，在二叉查找树中进行查找时，走了一条从树根出发到所找到结点的路径，到达一个空的子树则表明查找失败。根据定义，高度为h的满二叉树中有2^h一1个结点，每一层上的结点数都达到最大值。完全二叉树的最高层只要求结点先占据左边的位置。例如，高度为3的满二叉树如下图(a)所示，具有6个结点的完全二叉树如下图(b)所示。

在平衡二叉树中，任何一个结点的左子树高度与右子树高度之差的绝对值不大于1。单枝树中给每个结点只有1个子树。例如，具有3个结点的单枝树如下图所示。

显然，在结点数确定后，二叉查找树的形态为单枝树时查找效率最差。

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

在某个二叉查找树(即二叉排序树)中进行查找时，效率最差的情形是该二叉查找树是( )。

软件设计师上午基础知识考试

软考中级

在Linux网络配置中，(9)命令是用来设置主机名字的；在不使用DNS和NIS进行地址解析时，将所使用的主机名字写入(10)文件中可以保证解析器能找到主机的IP地址；解析器的功能是(11)；Linux中(12)提供名字服务；配置文件“host.conf”的

下面关于二级目录的叙述中，错误的是(1)。多级目录结构的特点是(2)。文件系统实现按名存取主要用来实现(3)。文件系统采用二级文件目录可以(4)。为了解决不同用户文件的“命名冲突”问题，通常在文件系统中采用(5)。

在WindowsServer2003上启用IIS6．0提供Web服务，创建一个Web站点并将主页文件index．asp拷贝到该Web站点的主目录下。在客户机的浏览器地址栏内输入网站的域名后提示没有权限访问该网站，则可能的原因是()。

(38)是多媒体内容描述接口标准。

网络系统中，通常把_______置于DMZ区。

湿热痢疾的特点是

医院应采取前瞻性监测方法进行全面综合性监测（）

患者女性，58岁。确诊慢性肾小球肾炎10余年，近1周来出现双下肢水肿加重．入院后应选用的胶体溶液为

某患者由于使用青霉素后引起四肢厥冷、呼吸困难，皮肤血管扩张、血压下降、昏迷，抢救时应首选

某些风险在一定的空间和时间范围内会消失，新的风险在一定的空间和时间范围内也会产生，这体现了风险的()。

()管理水平体现了商业银行的整体经营管理水平。

明清皇宫建筑的特点是()。

设A是3阶矩阵，β1，β2，β3是互不相同的3维列向量，且都不是方程组AX=0的解，记B=(β1，β2，β3)，且满足R(AB)＜R(A)，R(AB)＜R(B)．则R(AB)等于()

请编写函数fun，对长度为7个字符的字符串，除首、尾字符外，将其余5个字符按ASCH码降序排列。例如，原来的字符串为：CEAedca，排序后输出为：CedeEAa。注意：部分源程序在文件PROG1．C中。请勿改动主函数main