首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于二叉查找树(Binary Search Tree),若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此,对任意一棵二叉查找树进行(61)遍历可以得到一个
对于二叉查找树(Binary Search Tree),若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此,对任意一棵二叉查找树进行(61)遍历可以得到一个
admin
2008-11-02
74
问题
对于二叉查找树(Binary Search Tree),若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此,对任意一棵二叉查找树进行(61)遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算,最坏情况下的算法复杂度为(62)。
选项
A、O(n
2
)
B、O(nlog
2
n)
C、O(log
2
n)
D、O(n)
答案
D
解析
本题考查动态查找表二叉查找树(二叉排序树)。中序遍历二叉树的过程为:若二叉树非空,则先中序遍历左子树,然后访问根结点,最后中序遍历右子树。根据二叉查找树的定义,显然,对二叉查找树进行中序遍历,得到结点元素的递增序列。在二叉查找树上进行查找的过程为:若二叉查找树非空,将给定值与根结点的关键字值相比较,若相等,则查找成功;若不等,则当根结点的关键字值大于给定值时,到根的左子树中进行查找。否则到根的右子树中进行杳找。若找到,则查找过程是走了一条从树根到所找到结点的路径:否则,查找过程终止于一棵空树。因此,在具有n个结点的二叉查找树上进行查找的算法复杂度与树的高度同阶。由于一棵二叉查找树的形态完全由输入序列决定,所以在输入序列已经有序的情况下,所构造的二叉查找树是一棵单枝树。例如,由序列(45,30,50)和序列(30,45, 50)构造的二叉查找树如图(a)、(b)所示。
转载请注明原文地址:https://kaotiyun.com/show/mBxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
该网络采用核心层、汇聚层、接入层的三层架构。根据层次化网络设计的原则,数据包过滤、协议转换应在(11)层完成;(12)层提供高速骨=F线路;MAC层过滤和IP地址绑定在(13)层完成。(12)
该网络采用核心层、汇聚层、接入层的三层架构,所有计算机都采用静态IP地址。为了防止恶意用户盗用IP地址,网管员可采用(3)的策略来防止IP地址盗用,该策略应在三层架构中的(4)层实施。企业架设Web服务器对外进行公司及产品宣传,同时
阅读以下说明,回答问题1至问题4。[说明]某企业网拓扑结构如图1-1所示。企业根据网络需求购置了如下设备,其基本参数如表1-1所示。根据网络需求、拓扑图和设备参数类型,图1-1中设备1应选择类型为(1)的设备,设备2应选择类
该企业有部分分支机构地处其他省市,计划采用MPLSVPN进行网络互连,清根据MPLSVPN的技术原理回答以下问题:MPLS技术主要是为了提高路由器转发速率而提出的,其核心思想是利用标签交换取代复杂的路由运算和路由交换;该技术实现的核心就是把(1)封装
【说明】某单位网络结构如下图所示,其中维护部通过DDN专线远程与总部互通。核心交换机Switch1的部分配置如下,请根据说明和网络拓扑图完成下列配置。…Switch1(config)#interfacevlan1Switc
在下图所示的树型文件系统中,方框表示目录,圆圈表示文件,“/”表示路径中的分隔符,“/”在路径之首时表示根目录。图中,(10)。假设当前目录是D1,进程A以如下两种方式打开文件f1。①fd1=open("(11)/f1",o_R
码是一些码字组成的集合。一对码字之间的海明距离是(16),一个码的海明距离是所有不同码字的海明距离的(17)。如果要检查出d位错,那么码的海明距离是(18)。如果信息长度为5位,要求纠正1位错,按照海明编码,需要增加的校验位是(19)。以太网中使用的校验码
(71)analysis emphasizes the drawing of pictorial system models to document and validate both existing and/or proposed systems. U
OOA(Object-Oriented Analysis)模型由5个层次和5个活动组成,5个层次不包括(51),5个活动不包括(52)。OOA在定义属性的同时,还要识别实例连接。实例连接是一个实例对象与另一个实例对象的(53)关系。
随机试题
下列哪种情况不是鼻咽癌放疗需包括Ⅰb淋巴引流区的原因
患者,青年女性,左小腿被车轮轧伤,患肢明显肿胀,拍X线示,左胫骨中段骨折,行石膏托外固定,在观察早期骨筋膜室综合征时,哪项体征更有意义( )
多头犊牛突发羞明,流泪,眼睑痉挛,局部增温,1~2日内角膜中央出现微黄色浑浊,继而出现圆形溃疡,周边有新生血管形成。该病的病原为
决定梗死灶形状的主要因素是
2005年1月,商某因故意杀人罪被提起公诉,在诉讼过程中被害人程某的父亲程父对商某提出附带民事诉讼。下列陈述中,哪些属于在刑事诉讼中附带民事诉讼原告人程父依法享有的权利?( )
挂失止付并不是票据丧失后采取的必经措施,而只是一种暂时的预防措施。()
南京某国际旅行社组团赴境外旅游,后来发现有两人滞留不归,作为组团社应及时向()报告。
关于审稿制度的说法,错误的是()。
Whatisprobablytheman’sposition?
Mostparents,Isuppose,havehadtheexperienceofreadingabedtimestorytotheirchildren.Andtheymusthave【C1】______how
最新回复
(
0
)