本文共 868 字,大约阅读时间需要 2 分钟。
答案:A
答案解析:
折半查找判定树实际上是一棵二叉排序树,它的中序序列是一个有序序列。可以在树结点上依次填上相应的元素,符合折半查找规则的树即是所求。 B选项4、5相加除二向上取整,7、8相加除二向下取整,矛盾。C选项,3、4相加除二向上取整,6、7相加除二向下取整,矛盾。D选项,1、10相加除二向下取整,6、7相加除二向上取整,矛盾。A符合折半查找规则,正确。分析:
折半查找整个算法中,关于mid的取值向上/向下需要统一。 如果待查找序列中节点总数是偶数,计算mid值的时候一定涉及向上/向下取值问题。将上述规律带入图中进行验证:
A:正确; B:对于节点4和5,5作为mid,且4为其左子树,说明是向上取整;对于节点7和8,7作为mid,且8为其右子树,说明是向下取整。矛盾,说明B错; C、D同理。总结:
注意:折半查找整个算法中,关于mid的取值向上/向下需要统一。 向上取整: mid 和子树比较,mid大于子树就是向上取整; 向下取整: mid 和子树比较, mid小于子树就是向下取整;原链接:https://blog.csdn.net/qq_41754065/article/details/106590844
点个赞👍🙏 谢谢,这个对我真的很重要!