首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列关于二叉排序树的说法正确的是( )。 Ⅰ.向二叉排序树中插入一个结点,所需要比较的次数可能大于此二叉排序树的高度 Ⅱ.二叉排序树一定是平衡二叉树 Ⅲ.删除二叉排序树中的一个结点,再重新插入,一定能得到原来的二叉排序树
下列关于二叉排序树的说法正确的是( )。 Ⅰ.向二叉排序树中插入一个结点,所需要比较的次数可能大于此二叉排序树的高度 Ⅱ.二叉排序树一定是平衡二叉树 Ⅲ.删除二叉排序树中的一个结点,再重新插入,一定能得到原来的二叉排序树
admin
2022-06-07
77
问题
下列关于二叉排序树的说法正确的是( )。
Ⅰ.向二叉排序树中插入一个结点,所需要比较的次数可能大于此二叉排序树的高度
Ⅱ.二叉排序树一定是平衡二叉树
Ⅲ.删除二叉排序树中的一个结点,再重新插入,一定能得到原来的二叉排序树
Ⅳ.平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树
选项
A、Ⅰ、Ⅱ、IV
B、Ⅱ、Ⅲ、Ⅳ
C、Ⅰ、Ⅳ
D、全错
答案
D
解析
Ⅰ:根据二叉排序树插入操作的步骤可知,比较次数最坏情况下等于树的高度,所以I错误。
lI:二叉排序树不一定是平衡二叉树。例如,降序的一个序列组建二叉排序树时,会出现没有右子树的二叉树,此时明显不是平衡二叉树,所以Ⅱ错误。
Ⅲ:不一定可以得到以前的排序二叉树。例如,给出一个二叉排序树,如图3-7所示。此时删除结点3,二叉排序树变为图3.7b,再插入结点3,变为图3-7c。显然图3-7a和图3—7c不是同一个二叉排序树,所以Ⅲ错误。
Ⅳ:根据平衡二叉树的概念可知,该说法是错误的,应该改为:平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉排序树(出此选项的目的是让大家记住平衡二叉树默认是二叉排序树),所以Ⅳ错误。
可能疑问点:为什么有些教材定义平衡二叉树还是二叉树,而不是二叉排序树?
提示:首先不管教材是怎么定义的,因为考研大纲没有指定教材,所以考生只能依靠大纲解析为准,如果以前认为平衡二叉树不一定是二叉排序树就把这种思想改变过来吧。
补充知识点:关于二叉排序树、完全二叉树、平衡二叉树、堆之间的关系。
(1)首先堆的建立永远都是从最后开始插,所以堆一定是完全二叉树。
(2)完全二叉树不一定是平衡二叉树,平衡二叉树也不一定是完全二叉树。因为平衡二叉树是有序的,而完全二叉树不一定有序,所以完全二叉树不一定是平衡二叉树。平衡二叉树不一定是完全二叉树比较好理解。
转载请注明原文地址:https://www.kaotiyun.com/show/Jj3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
关于DMA方式和通道方式,下列说法中错误的是()。
某计算机存储器按字节编址,虚拟(逻辑)地址空间大小为16MB,主存(物理)地址空间大小为1MB,页面大小为4KB;Cache采用直接映射方式,共8行;主存与Cache之间交换的块大小为32B。系统运行到某一时刻时,页表的部分内容和Cache的部分内容分别如
将关键字序列(7,8,30,11,18,9,14)散列存储到散列表中,散列表的存储空间是一个下标从0开始的一维数组,散列函数为:H(key)=(key×3)MOD7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。请画出所构造的散列表。
已知含有5个顶点的图G如下图所示。请回答下列问题:若己知具有n(n≥2)个顶点的图的邻接矩阵为B,则Bm(2≤m≤n)中非零元素的含义是什么?
分别以下列序列构造二叉排序树,与用其他三个序列所构造的结果不同的是()。
叙述各种文件物理组织方式的主要优缺点。
下列排序算法中,在每一趟都能选出一个元素放到其最终位置上,并且其时间性能受数据初始特性影响的是()。
二叉排序树采用二叉链表存储。写一个算法,删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树,并且高度没有增长(注意:可不考虑被删除的结点是根的情况)。
拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市,图中无向边上的权值表示两个城市间备选光纤的铺设费用。请回答下列问题。图可采用图的哪一种存储结构?给出求解计算总费用所使用的算法名称。
在测量研究中,强调对测验情境关系进行考察的心理测量理论是()
随机试题
下列关于税务师对印花税适用税率的审核,表述正确的有()。
下列各项中,属于应计入当期损益的利得的有()。
违反《个人独资企业法》规定,应当承担民事赔偿责任和缴纳罚款、罚金的,其财产不足支付的,或被判处没收财产的,应当先缴纳罚款、罚金。()
下列能体现德育方法中的榜样示范法的是()
下列不属于公共物品的是()。
A、 B、 C、 D、 B阴影部分作顺时针旋转。
Twoofthemostcommonrumorsaboutimmigrantfamiliesarethattheydon’treallywanttobecomeAmericanandthatthey’readra
下列关于模板形参的描述中,错误的是()。
Inotifiedhimthatthemeetinghadbeenpostponed.
Hedidnothingbut______lettershomeallthisafternoon.
最新回复
(
0
)