二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算

二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算24湖大计算机/软件工程考研|查找相关例题解析1.设有5个数据do、for、if、repeat、while,它们排在一个有序表中,其查找概率分别是p1=0.2,p2=0.15,p3=0.1,p4=0.03,p5=0.01。而查找它们之间不存在数据的概率分别为q0=0.2,q1=0.15,q2=

24湖大计算机/软件工程考研|查找相关例题解析   1.设有5个数据do、for、if、repeat、while,它们排在一个有序表中,其查找概率分别是p1=0.2,p2=0.15,p3=0.1,p4=0.03,p5=0.01。而查找它们之间不存在数据的概率分别为q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02, q5=0.01,该有序表如下:
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算   (1)试画出对该有序表分别采用顺序查找和折半查找时的判定树。   (2)分别计算顺序查找的查找成功和不成功的平均查找长度。   (3)分别计算折半查找的查找成功和不成功的平均查找长度。   答:(1)对该有序表分别采用顺序查找和折半查找时的判定树分别如图9.2和9.3所示。   (2)对于顺序查找,成功查找到第i个素需要i次比较,不成功查找需要比较的次数为对应外部结点的层次减1:
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算   (3)对于折半查找,成功查找需要比较的次数为对应内部结点的层次,不成功查找需要比较的次数为对应外部结点的层次减 1:
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算   
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算   
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算   2.对于A[0..10]有序表,在等概率的情况下,求采用折半查找法时成功和不成功的平均查找长度。对于有序表(12,18,24,35,47,50,62,83,90,115,134),当用折半查找法查找90时,需进行多少次查找可确定成功;查找47时需进行多少次查找可确定成功;查找100时,需进行多少次查找才能确定不成功。   答:对于 A[0..10]有序表构造的判定树如图 9.4(a)所示。因此有:   
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算   对于题中给定的有序表构造的判定树如图9.4(b)所示。查找90时,关键字比较次序是50、90,比较2次。查找47时,关键字比较次序是 50、24、35、47,比较4次。查找100时,关键字比较次序是50、90、115,比较3次
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算   3.有以下查找算法:   int fun(int a[],int n,int k)   {inti;   for(i=0;i<n;i+=2)   if(a[i]==k)return i;   for (i=1;i<n;i+=2)   if (a[i]==k)   return i;   return -1;   }   (1)指出fun(a,n,k)算法的功能。   (2)当a[]={2,6,3,8,1,7,4,9}时,执行fun(a,n,1)后的返回结果是什么?一共进行了几次比较。(3)当a[]={2,6,3,8,1,7,4,9}时,执行fun(a,n,5)后的返回结果是什么?一共进行了几次比较。   答:(1)fun(a,n,k)算法的功能是在数组a[0..n-1]中查找素值为k的素。若找到了返回k对应素的下标;否则返回-1。算法先在奇数序号的素中查找,如没有找到,再在偶数序号的素中查找。   (2)当a[]={2,6,3,8,1,7,4,9}时,执行fun(a,n,1)后的返回结果是4,表示查找成功。一共进行了3次比较。   (3)当a[]={2,6,3,8,1,7,4,9}时,执行fun(a,n,5)后的返回结果是-1,表示查找不成功。一共进行了8次比较。   4.假设一棵二叉排序树的关键字为单个字母,其后序遍历序列为ACDBFIJHGE, 回答以下问题:   (1)画出该二叉排序树;   (2)求在等概率下的查找成功的平均查找长度。   (3)求在等概率下的查找不成功的平均查找长度。   答:(1)该二叉排序树的后序遍历序列为ACDBFIJHGE,则中序遍历序列为ABCDEFGHIJ,由后序序列和中序序列构造的二叉排序树如图9.5所示
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算   (2)ASL成功=(1×1+2×2+4×3+2×4+1×5)/10=3。   (3)ASL不成功=(6×3+3×4+2×5)/11=3.64。   5.证明如果一棵非空二叉树(所有结点值均不相同)的中序遍历序列是从小到大有序的,则该二叉树是一棵二叉排序树。   证明:对于关键字为k的任一结点a,由中序遍历过程可知,在中序遍历序列中,它的左子树的所有结点的关键字排在k的左边,它的右子树的所有结点的关键字排在k的右边, 由于中序序列是从小到大排列的,所以结点a的左子树中所有结点的关键字小于k,结点a 的右子树中所有结点的关键字大于k,这满足二叉排序树的性质,所以该二叉树是一棵二叉排序树。   6.由23、12、45关键字构成的二叉排序树有多少棵,其中属于平衡二叉树的有多少棵?   答:这里n=3,构成的二叉排序树的个数为5,如图9.6所示。   其中的平衡二叉树有1棵,为图中第3棵。   利用普里姆算法从顶点0出发构造的最小生成树为:{(0,1),(0,3),(1, 2),(2,5),(5,4)}。   利用克鲁斯卡尔算法构造出的最小生成树为:{(0, 1),(0,3),(1,2),(5,4),(2,5)}
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算
二叉排序树的平均查找长度怎么求_二叉排序树平均查找长度怎么计算

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/89032.html

(0)
上一篇 2024年 6月 21日
下一篇 2024年 6月 21日

相关推荐

关注微信