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/94033.html
