首页 > 试题广场 >

下列选项中，不能构成折半查找中关键字比较序列的是 （）。

[单选题]

下列选项中，不能构成折半查找中关键字比较序列的是 （）。 

  • 500,200,450,180
  • 500,450,200,180
  • 180,500,200,450
  • 180,200,500,450
添加回答
推荐
艾晓米Amyfairy头像 艾晓米Amyfairy

画出查找路径图，因为折半查找的判定树是一棵二叉排序树，看其是否满足二叉排序树的要求。

很显然，选项 A 的查找路径不满足。

编辑于 2016-12-01 18:35:49 回复(4)
王道论坛头像 王道论坛

画出查找路径图，因为折半查找的判定树是一棵二叉排序树，看其是否满足二叉排序树的要求。


很显然，选项 A 的查找路径不满足。

发表于 2016-12-13 18:21:50 回复(0)
phoenixx头像 phoenixx
发表于 2017-04-08 22:36:56 回复(5)
jdx头像 jdx
发表于 2018-05-28 16:20:05 回复(0)
一条狗头像 一条狗
“不能构成折半查找中关键字比较序列的是”
意思是：答案中的序列不是要查找的数据的完整序列，只是在查找过程中比较过的关键字的序列

然后画判定树，显然A不正确
发表于 2017-02-21 17:37:58 回复(0)
sunlight_run头像 sunlight_run
判断方法：对于任意节点，后面所有要么全大于该节点，要么全小于该节点。
其实跟排序二叉树中序遍历结果是一个道理
发表于 2017-06-30 09:37:44 回复(3)
跳跳虎还是跳跳鼠头像 跳跳虎还是跳跳鼠
不能构成折半查找中关键字比较序列，其实这个压根不需要像楼上说的动手画图或者一个个比较运算。
二分查找的规律是，只要看，这个数字，然后看这个数字后面的所有数字要么都比它小，要么都比它大。理由，每次取得中点数字，然后在前半部分或者后半部分找，所以中间这个数字，后面的所有数字，要么比它小，要么多比它大

发表于 2019-01-17 17:16:42 回复(0)
BrainerGao头像 BrainerGao
发表于 2017-04-17 17:26:42 回复(2)
GerogeLiu头像 GerogeLiu

这道题的关键之处是理解题干“关键字比较序列”的意思，我按照自己的理解重新描述这个问题想必就简单了。

“假设有一个有序表进行折半查找（二分查找），关键字（中间数）选择不可能按照下列选项中进行的是：”

———只有A是不符合的

发表于 2020-01-28 09:10:12 回复(0)
倚杖听江声头像 倚杖听江声
第三个数一定在第一个数和第二个数确定范围之内
发表于 2018-08-28 09:57:03 回复(0)
强者为尊头像 强者为尊
如果要查找的数小于500，那么折半后找到200；
如果要查找的数大于200，那么折半后的数可能是450；
如果要找的数小于450，那么折半后的数可能是再200~450之间；
所以A可能是错的。
发表于 2016-12-09 10:29:52 回复(0)
沙月ちゃん头像 沙月ちゃん

看到很多画查找路径图的方法，我来说一个逻辑推断的方法。

以A选项为例：
假设要查询的数字是根据前两个数字，分类讨论，满足条件的区间只可能是或者。根据第三个数字，可以排除前者，区间范围被缩小到或者。可是第四个数字是，它不在这两个区间里，与前面推断的结论矛盾，因此A选项有误。选A。

发表于 2020-08-04 22:32:30 回复(0)
Weserubung头像 Weserubung
这是一个比较序列，也就是拿一个数（本题中未知）过来，在一棵二叉排序树上依次进行比较，答案里就是与之比较的数字，对于A答案来说，首先比较500，接下来是200，说明这个数比500小，然后接下来依次比200大，但比450小，然后再去跟180比。这问题就来了，一个数不可能已经比200大了，还会去再干女儿180比，故而这棵二叉排序树是有问题的。

发表于 2020-03-11 23:43:53 回复(0)
烟花纷笑头像 烟花纷笑
二叉排序树:
 令二叉树的每一个节点大于左子树的节点，小于右子树的节点。
 中序遍历这样的一棵树，就能实现从小到大的输出。
 插入时，每一个新节点都是插在“最低端”。
发表于 2019-11-07 19:48:23 回复(0)
贪睡的沸羊羊要冲国企头像 贪睡的沸羊羊要冲国企
利用二叉排序树，中序遍历必须严格从小到大，除了A不符合，其余都对
发表于 2024-03-14 18:00:23 回复(0)
xxxxxxxxxxxxxxxa头像 xxxxxxxxxxxxxxxa
没注意是关键字比较序列，然后又习得了二分查找的一个出题思路。关键字的比较应该满足逻辑性。
A    
500,200,450,180
      500
  说明第一次比较结果是选择500之前的区间
200
    说明第二次比较结果是选择200之后的区间
      450
    此时一定错了，因为只能在200-450的区间找数
180

前面的人总结的很对，关键字形成的树一定符合二叉树的基本性质。
发表于 2018-06-17 17:56:28 回复(1)
粗心的西红柿在吃瓜头像 粗心的西红柿在吃瓜
按照二叉排序树方式写成树之后,其余三棵二叉树中序遍历都是180,200,450,500符合二叉排序树中序遍历序列递增的特点,A选项二叉排序树中序遍历序列为200,180,450,500,所以不符合二叉排序树特点
发表于 2022-08-15 16:00:36 回复(0)
牛客20221021头像 牛客20221021
二分法比较，不会跳到已经筛掉的区间
发表于 2021-11-29 15:23:38 回复(0)
许你清安L头像 许你清安L
根据二叉搜索树，之后的序列应当是这样的：
当前的关键字 都比后面的关键字大或者小
只有每个关键字都满足才算是一次搜索序列
发表于 2021-11-04 11:39:10 回复(0)
牛客844662247号头像 牛客844662247号
<p>每个点其后皆大于或小于它</p><p><br></p>
发表于 2020-07-28 20:59:26 回复(0)
牛客818246740号头像 牛客818246740号
<p>看二叉树</p><p><br></p>
发表于 2020-06-29 18:29:20 回复(0)
提交观点

问题信息

查找
上传者：城市里的养猫者
难度：
32条回答 27627浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号