折半查找,不成功的平均搜索长度怎么算的?

博出我天地2022-10-04 11:39:541条回答

折半查找,不成功的平均搜索长度怎么算的?
17、7-7 设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908.试画出对其进行折半搜索时的判定树,并计算搜索不成功的平均搜索长度.
折半搜索时的判定树为：
ASLUNSUCC=1/15（3*1+4*14）=59/15
我觉得应该是这样的=1/15（4*1+5*14）

已提交，审核后显示！提交回复

共1条回复

wx15001 共回答了22个问题 | 采纳率90.9%: 你数一下最后的叶子结点应该有而没有的孩子是几个; 1年前

相关推荐

数据结构折半查找对17个元素的查找表做折半查找,则查找长度为5的元素下标依次是( )A8,7 B5,10,12 C9,1 数据结构折半查找 对17个元素的查找表做折半查找,则查找长度为5的元素下标依次是( )A8,7 B5,10,12 C9,16 D 9,17 jby043011年前1: sjlmsvv 共回答了20个问题 | 采纳率90%

这个答案不太全吧,查找长度为5的序列不是只有两个数,如果说下标的起点和终点才是两个数,以下开始按起点和终点来确定

首先需要判断起点下标是0还是1
如果是1,合法下标范围是1..17,第一次折半查找查找的下标是(1+17)/2 = 9；
如果是0,合法下标范围是0..16,第一次折半查找的下标是(0+16)/2 = 8；
因此答案B可以排除

从D答案可以推断出,合法下标范围应当是从1开始,所以A也被排除

按照答案C、D的提示（最终查找的下标为16和17）,因此,第二次折半的范围是在9的右半
这个下标是：(10+17)/2下取整得到13
继续查找右半得到第三次折半查找的下标为(14+17)/2 下取整得到15
继续查找右半得到第四次折半查找的下标为(16+17)/2 下取整得到16
也就是说,第4次折半就找到了下标为16的元素,当然查找长度就是4,因此答案C也被排除

下面继续查找右半得到第五次折半查找的下标为(17+17)/2 下取整得到17
因此查找长度为5的下标依次是：9, 13, 15, 16, 17,答案就是D

其实如果构建一棵表长17的折半查找判定树,是很容易从上面看出结果来的,而且如果下标从0开始,则答案就是A,依次访问下标的次序是8, 3, 5, 6, 7

1年前查看全部

借地,救命,请教几个DS题!（1）折半查找有序表（4,6,12,20,28,38,50,70,88,100）,若查找表中 借地,救命,请教几个DS题! （1）折半查找有序表（4,6,12,20,28,38,50,70,88,100）,若查找表中元素20,它将依次与表中元素（）比较大小.答案是不是：4,6,12,20 （2）哈希函数值发生冲突的原因是因为关键字相等（判断——这句话是错的吗?）（3）若对序列（tang deng an wan shi bai fang liu）按字典排序,快速排序第一躺的结果是（）（4）若对序列（tang deng an wan shi bai fang liu）按字典排序,初始步长为4的希望尔排序的第一躺的结果是（）如果问题弱,请海涵,我很白痴, 偷不好抢抢不如骗1年前1: 紫色芬芳共回答了23个问题 | 采纳率95.7%

第一题, 折半查找的思路：先给每个关键字编号,这道题是从1到10编号.其中low=1,high=10；第一躺查找的编号应该是mid=（low+high）/2（取整）的关键字,也就是第5个关键字28. 比较之后发现28>20,所以20一定在28的左边.所以low不变,high=mid-1=4. 第二躺查找的编号mid=（low+high）/2=2,所以和6比较. 因为6

1年前查看全部

在下列查找方法中,平均查找速度最快的是( A)顺序查找 B)折半查找 c)分块查找 D)二叉排序树查找 在下列查找方法中,平均查找速度最快的是( A)顺序查找 B)折半查找 c)分块查找 D)二叉排序树查找 在下列查找方法中,平均查找速度最快的是( A)顺序查找 B)折半查找 c)分块查找 D)二叉排序树查找 娃哈哈90l51年前1: 没有名字可注共回答了11个问题 | 采纳率100%

是B,

1年前查看全部

数据结构,折半查找判定树对于数列{25,30,8,5,1,27,24,10,20,21,9,28,7,13,15},假定 数据结构,折半查找判定树 对于数列{25,30,8,5,1,27,24,10,20,21,9,28,7,13,15},假定每个结点的查找概率相同,若用顺序存储结构组织该数列,则查找一个数的平均比较次数为（）.若按二叉排序树组织该数列,则查找一个数的平均比较次数为（）. 【解答】8,59/15 8是怎么样算得.那个59/15 是怎么画得,为什么我算得时 49/15 Liseker1年前1: zhiqin_0703 共回答了17个问题 | 采纳率76.5%

你的二叉排序树可能画错了吧,我算得也是59/15

1年前查看全部

请教一道选择题，关于折半查找对应判定树的深度问题 请教一道选择题，关于折半查找对应判定树的深度问题 对表长为n的有序表进行折半查找，其判定树的高度为（） A. 不小于log2(n+1)的最小整数 B. 不大于log2(n+1)的最大整数 C. 不小于log2n的最小整数 D. 不大于log2n的最大整数 我算了半天，总是和答案不对。 先让大家帮忙算一下吧。答案先不透露了。 麻烦各位了。 华进先生：我选的也是C，可答案是A。是不是印错了？ shanoo1年前3: legend-1 共回答了24个问题 | 采纳率83.3%

是A~

1年前查看全部

顺序表｛1,2,3,4,5,6,7,8,9,10,11,12,13,14,15｝当用折半查找,查关键字1,8,17时比较 顺序表｛1,2,3,4,5,6,7,8,9,10,11,12,13,14,15｝当用折半查找,查关键字1,8,17时比较次序分别为（）,（）,（）. 谈谈情作作案1年前1: mrzhoujinsong 共回答了16个问题 | 采纳率87.5%

//实现过程如下：
#include
using namespace std;
int a[]={1,2,3,4,5,5,7,8,9,10,11,12,13,14,15};
int b[10];
int Binary_Search(int num)
{
int l=0;
int r=14; //最后一个数的下标
int mid;
int ans=0;
while(l<=r)
{
mid=(l+r)/2;
b[ans]=a[mid];
ans++;
if(a[mid]==num) return ans;
else if(a[mid]else r=mid-1;
}
return ans;
}
int main()
{
int n;
while(cin>>n)
{
int t=Binary_Search(n);
cout<<"比较次数为: "<cout<<"依次比较的数为：";
for(int i=0;icout<<'n';
}
return 0;
}
//答案为4 1 4

1年前查看全部

适用于折半查找的表的存储方式以及元素排列要求为a.链接方式存储元素无序b.链接方式存储元素有序c.顺序方式存储元素 适用于折半查找的表的存储方式以及元素排列要求为a.链接方式存储元素无序b.链接方式存储元素有序c.顺序方式存储元素无序d.顺序方式存储元素有序 sunyj19801年前1: jensenhuangpu 共回答了28个问题 | 采纳率82.1%

首先,要折半查找,就要求元素有序,否则折半根本没有意义其次,为了方便查找,最好使用顺序方式存储因此,答案是D

1年前查看全部

【数据结构】请教一道题,关于二分查找（折半查找）的平均搜索长度. 【数据结构】请教一道题,关于二分查找（折半查找）的平均搜索长度. 对于长度为9的有序顺序表,若采用折半搜索,在等概率情况下搜索成功的平均搜索长度为( )的值除以9. A、20 B、18 C、25 D、22答案是： efefgrgr1年前1: 58f21y4 共回答了18个问题 | 采纳率83.3%

可以设这九个数依次为1-2-3-4-5-6-7-8-9,那么按照二分查找：第一次应该找到的是[1+9]/2=5（这就是说数字5搜索的长度为1）；第二次可以找到2个数字是[1+5]/2=3或[5+9]/2=7（3和7的搜索长度为2）；……第三次可以找到4个数字是2、4、6、8；第四次可以找到2个数字是1、9；因此将以上九个数字的搜索长度相加可以得到：1+2*2+3*4+2*4=1+4+12+8=25 即可选出答案C祝你学习愉快,考研顺利!加油!

1年前查看全部

14.\x05对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找,则查找元素26 14.x05对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找,则查找元素26的查找长度( ). A.2 B.3 C.4 D.5 天使妍妍1年前1: 七彩虹KKo 共回答了22个问题 | 采纳率86.4%

答案为C、4
共有9个数
第一次：（1+9）/2=5 第5个数为37,26小于37,所以往左边找
第二次：（1+4）/2=2.5 取4,第2个数为12,26大于12,所以往12的右边找
第三次：（3+4）/2=3.5 取3,为20
第四次：（4+4）/2=4 为26
所以为4 顺序为37 12 20 26

1年前查看全部

已知11个元素的有序表为（5,13,19,21,37,56,64,75,80,88,92）,请写出折半查找的算法程序,查 已知11个元素的有序表为（5,13,19,21,37,56,64,75,80,88,92）,请写出折半查找的算法程序,查找 只为此帖的用户名1年前1: 都市农夫共回答了23个问题 | 采纳率95.7%

查找什么?

1年前查看全部

C++折半查找求源代码练习3　折半查找。　　查找是计算机应用的重要方面之一。排序是为了便于查找，提高查找的速度。如，设 C++折半查找求源代码 练习3　折半查找。 查找是计算机应用的重要方面之一。排序是为了便于查找，提高查找的速度。如，设要从n个数中去查找x是否存在，最原始的办法就是从头到尾逐个去找，这种查找称为顺序查找，它是无序数据查找的有效方法，当被查找的元素为15个时，循环的次数最多为14次。但对一个已经排好序的数列来说，它就是一种效率最低的算法，一般采用折半查找法，下面我们就来讨论它的算法。 假定有以下15个整数： 12 15 17 24 28 32 45 67 89 145 167 178 211 235 269 待查找的数放在x中，折半查找将按图示的方式进行: 先找中间的67去比， 若相等，则找到了； 若小于67则到左边分支去找， 若大于67则到右边分支去找。 同样方法一直查找到没有分支可查找为止。显而易见，这种查找方法最多只需查找四次就能判断出找得到还是找不到。因此这种查找方法优于顺序查找方法。 折半查找的算法如下： 首先需要设三个指示器top、bot、mid，分别指向查找范围的顶部、底部和中间位置。假定有15个元素，则一开始top=1、bot=15、mid=(top+bot) div 2，这时一定bot大于top，接着进行以下判断： ①如果x=a[mid]，则设查到标志为true，打印的有关信息。 ②否则若x　　③如果x>a[mid]，则下一步查找范围应该在mid+1到bot之间，改变top使之等于mid+1。 重复以上过程直到已经打到为止。 请同学们实现程序的编码。 样例： Please enter 15 integer number: 12 15 17 24 28 32 45 67 89 145 167 178 211 235 269 Input x to look for: 28 Find 28 , it postion is 5 抱着苦涩去幸福1年前1: 我的心醉了无痕共回答了21个问题 | 采纳率90.5%

#include
int main()
{
int i,x;
int top=1,bot=15,mid;
int str[15];
printf("Please enter 15 integer number:n");
for(i=0;i

1年前查看全部

急!在有序表A[1...20]中,按折半查找,则查找长度是5的数是多少? 急!在有序表A[1...20]中,按折半查找,则查找长度是5的数是多少? 希望高人说明解题过程,非常感谢啊! nhz7151年前1: 之戏共回答了20个问题 | 采纳率95%

a10 1
a5 a15 2
a2 a7 a12 a18 3
a1 a3 a6 a8 a11 a13 a16 a19 4
a4 a9 a14 a17 a20 5
画出二叉查找树，所在层次就是查找长度
第五层有5个元素查找长度为5的有5个

1年前查看全部

设有序表有100个元素,在折半查找时,最大比较次数是_________,最小比较次数是_____________. woai1091年前2: zpy1113 共回答了16个问题 | 采纳率81.3%

最大是7 最小是1

1年前查看全部

设顺序表中有1000个元素,采用折半查找时,最大比较次数为多少次?最小比较次数为多少?要求具体算法 fuangkj1年前1: drewtow 共回答了15个问题 | 采纳率73.3%

反复递归即可最小当然是一次啦最大就是不停的找呀
代码如下
import java.util.Scanner;
public class HalfSearch {
static StringBuffer bf = new StringBuffer();
static int a = 0;
static int count = 0;
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入要查找的数");
a = scanner.nextInt();
Search(0,1000);
System.out.println(bf +" "+ count);
}
public static int Search(int min ,int max) {
int half = (max+min)/2;
if (a < half) {
bf.append(half).append(";");
count++;
return Search(min,half);
}
else if (a > half){
bf.append(half).append(";");
count++;
return Search(half,max);
}
else {
bf.append(half);
count++;
return a;
}
}
}

1年前查看全部

折半查找,不成功的平均搜索长度 怎么算的?

共1条回复

相关推荐

大家在问

折半查找,不成功的平均搜索长度怎么算的?