首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
对于二叉查找树(Binary Search Tree),若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此,对任意一棵二叉查找树进行(61)遍历可以得到一个
对于二叉查找树(Binary Search Tree),若其左子树非空,则左子树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此,对任意一棵二叉查找树进行(61)遍历可以得到一个
admin
2008-11-02
67
问题
对于二叉查找树(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在ServerA的IPSec安全策略配置过程中,ServerA和ServerB-之间通信的IPSec筛选器“许可”属性设置为“协商安全”,并且安全措施为“加密并保持完整性”,如图4-4所示。根据上述安全策略填写图4-5中的空格,表示完整的IPSec数据包格
阅读以下说明,回答问题1至问题5。[说明]某公司采用WindowsServer2003操作系统构建了一个企业网站,要求用户输入https://www.test.com。访问该网站。该服务器同时又配置了FTP服务,域名为ftp.test.
在Linux操作系统下,可通过命令(2)显示路由信息。若主机所在网络的网关IP地址为192.168.0.254,则可使用命令(3)adddefault(4)192.168.0.254添加网关为默认路由。备选答案:A.gat
在一个基于TCP/IP协议的网络中,每台主机都有一个IP地址,根据获得IP地址方式的不同,可以分为静态IP和动态IP。例如:用宽带入网,会有一个固定的IP地址,每次连入Internet,你的IP都一样;而用拨号上网,每次连入Internet时都从ISP那里
阅读以下说明,回答以下问题。将解答填入答题纸对应的解答栏内。【说明】某公司总部内采用RIP协议,网络拓扑结构如下图所示。根据业务需求,公司总部的192.168.40.0/24网段与分公司192.168.100.0/24网段通过VPN实现
阅读以下说明,回答问题,将解答填入答题纸对应的解答栏内。【说明】图2-1为某公司数据中心拓扑图,两台存储设备用于存储关系型数据库的结构化数据和文档、音视频等非结构化文档,规划采用的RAID组合方式如图2-2、图2-3所示。图2-2所示的RAID方
在下图所示的树型文件系统中,方框表示目录,圆圈表示文件,“/”表示路径中的分隔符,“/”在路径之首时表示根目录。图中,(10)。假设当前目录是D1,进程A以如下两种方式打开文件f1。①fd1=open("(11)/f1",o_R
ISDN是由(51)定义的一种网络设备标准。在ISDN的各种设备之间定义可(52)个参考点,其中把网络终端设备和用户终端设备分开的参考点为(53)。若一个大的企业要连入ISDN,要用到一个叫NT2的设备,NT2实际上就是(54)。ISDN网络的构成不包括(
某软件设计师自行将他人使用C程序语言开发的控制程序转换为机器语言形式的控制程序,并固化在芯片中,该软件设计师的行为()。
OOA(Object-Oriented Analysis)模型由5个层次和5个活动组成,5个层次不包括(51),5个活动不包括(52)。OOA在定义属性的同时,还要识别实例连接。实例连接是一个实例对象与另一个实例对象的(53)关系。
随机试题
Theoldcarpentercanbeangryfornoreasonattimes;mysympathyisforhis________apprentice.
根据世界银行咨询服务合同标准文本,对于非复杂的咨询服务采购可采用()的计价方式。
根据《城乡规划法》第三十七条和第三十八条的规定,下列选项中不属于建设用地规划管理程序的是()。
万泰进出口公司从德国进口一台模具加工机床,发票分别列明:设备价款CIF上海USD600000,机器进口后的安装调试费为USD20000,卖方佣金USD2000,与设备配套使用的操作系统使用费USD80000。该批货物经海关审定的成交价格应为(
最低备付金可用于完成交收,但不能划出。()
下列属于“情感态度与价值观”目标的是()。
在教与学构成的主要矛盾中,教是矛盾的主要方面,是因为()。
德育内容具有历史性、阶级性和()。
Thetenantleftnothingbehindexceptsome______ofpaper,cloth,etc.
PurpleCloudMountain,whosenamecomesfromtherainbowsfrequentlyappearontopofthemountainthatgivestherangeapurple
最新回复
(
0
)