首页 软考中级软件设计师正文

下面关于二叉排序树的叙述,错误的是()。(2009年上半年软件设计师上午基础知识真题解析)

下面关于二叉排序树的叙述,错误的是()。(2009年上半年软件设计师上午基础知识真题析)
A、对二叉排序树进行中序遍历,必定得到节点关键字的有序序列
B、依据关键字无序的序列建立二叉排序树,也可能构造出单支树
C、若构造二叉排序树时进行平衡化处理,则根节点的左子树节点数与右子树节点数的差值一定不超过 1
D、若构造二叉排序树时进行平衡化处理,则根节点的左子树高度与右子树高度的差值一定不超过 1






参考答案:C
参考解析:本题考查数据结构方面的基础知识。
二叉排序树或者是一棵空树,或者是具有如下性质的二叉树:①若它的左子树非空,则其左子树上所有节点的关键字均小于根节点的关键字;②若它的右子树非空,则其右子树上所有节点的关键字均大于根节点的关键字;③左、右子树本身就是两棵二叉排序树。由上述定义可知,二叉排序树是一个有序表,对二叉排序树进行中序遍历,可得到一个关键字递增排序的序列。对于给定的关键字序列,可从空树开始,逐个将关键字插入树中来构造一棵二叉排序树。其过程是:每读入一个关键字值,就建立一个新节点。若二叉排序树非空,则将 新节点的关键字与根节点的关键字相比较,如果小于根节点的值,则插入到左子树中,否则插入到右子树中;若二叉排序树为空树,则新节点作为二叉排序树的根节点。显然,若关键字初始序列已经有序,则构造出的二叉排序树一定是单枝树(每个节点只有一个孩子)。为了使在二叉排序树上进行的查找操作性能最优,构造二叉排序树时需进行平衡化处理,使每个节点左、右子树的髙度差的绝对值不超过 1。

* 注意事项

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,转载需标明出处。
软考题网站(https://ruankaoti.com/)提供的相关试题资料仅供个人复习参考使用
如果您有更好的解答,欢迎留言评论。

本文链接:https://ruankaoti.com/post/8040.html

发表评论

评论列表(0人评论 , 119人围观)
☹还没有评论,来说两句吧...

阅读更多

微信扫码,加入打卡学习群,分享学习资料