首页 > 试题广场 >

在有序表(5,8,36,48,50,58,88)中二分查找字

[单选题]
在有序表(5,8,36,48,50,58,88)中二分查找字58时所需进行的关键字比较次数是（），对应的判定树高度为（）. 
  • 2,2
  • 2,3
  • 3,2
  • 3,3
查看正确选项
添加回答
whx.53@163.com头像 whx.53@163.com
B. 
2, 3
发表于 2015-10-20 18:44:35 回复(0)
karaysn头像 karaysn
还是应该拿笔写一下，不然老是想当然，出错
发表于 2017-10-10 10:20:03 回复(0)
Aurora1头像 Aurora1
48 8 58 5 36 50 88
发表于 2015-10-21 20:03:14 回复(3)
牛客627430号头像 牛客627430号
判定树高度怎么求
发表于 2015-10-31 14:45:07 回复(1)
lkk头像 lkk
根据有序表建立二叉排序树
      48
     /    \
   8      58
  / \      /   \
5 36   50 88
58在第二层，也就是第二次比较就可以确定了
BST的高度为3，也就是最多要经过3次排序
所以最终结果为 2,3
编辑于 2016-08-03 20:21:33 回复(3)
牛客1017932号头像 牛客1017932号
二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。
发表于 2017-08-22 09:35:19 回复(1)
沐浴星光的潇洒少年头像 沐浴星光的潇洒少年 
第一次比较（0+6）/2=3处的元素，第二次比较(3+1,6)/2=5处的元素，刚好找到，此时查找的列表元素包含50，58，88，列表长度为3应该就为判定树的高度

发表于 2015-10-21 19:48:52 回复(0)
大大大🍍头像 大大大🍍
谁tm知道要建立啥树，题目也说明一下，说不定是完全二叉树（建堆呢。。。。）
发表于 2022-08-04 09:22:11 回复(0)
凌梦初辰头像 凌梦初辰
我记得看二分法的算法是比较  
int start= 0; int end  = array.length-1;
int mid = (start+end)/2；
第一次是：3是48，先比较48！=58，而且比58小　比较2次
第二次是：5是58，比较58==58    比较1次
所以总共比较的是3次
--------------------------------------
判定树：比较1次为根节点，比较两次为第二层节点，比较n次为第n层节点。
这里我想说的是用判定树和二分法的思想还是有些不同。
节点在判定树的哪一层，则比较几次，判定树的高度，就是生成的树的高度。
大家注意进行区分。
发表于 2017-09-11 19:15:59 回复(0)
鸣酱头像 鸣酱
b树高度才是不包括叶子层
发表于 2019-04-09 08:05:20 回复(0)
向宇女同桌头像 向宇女同桌
判定树高度：生成的树的高度 比较次数：节点在第几层比较几次
发表于 2017-09-18 22:59:52 回复(0)
噗哈哈哈头像 噗哈哈哈
先将给定值K与二分查找判定树的根节点的关键字进行比较。若相等，成功；小于根节点则在根节点的左边查找；大于根节点，则在根节点的右边查找
发表于 2017-09-11 08:08:30 回复(0)
牛客700763号头像 牛客700763号
判定树高度怎么算？怎么觉得这个高应该是2
发表于 2017-04-04 11:59:17 回复(0)
周星星_头像 周星星_
【例】对于有11个结点的表，若查找的结点是表中第6个结点，则只需进行一次比较；若查找的结点是表中第3或第9个结点，则需进行二次比较；找第1，4，7，10个结点需要比较三次；找到第2，5，8，11个结点需要比较四次

ref:
http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.2.2.2.htm
发表于 2016-08-12 11:44:49 回复(0)
huixieqingchun头像 huixieqingchun
有序表，一般用数组进行存储的。
发表于 2016-05-11 16:28:53 回复(0)
提交观点

问题信息

C++工程师 树 2016 Java工程师 58集团
来自：58同城2016研发工...
难度：
15条回答 11348浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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