第8章 查找 例题精讲1. 在等概率条件下顺序查找在查找成功时的平均查找长度ASL(n1)/2。改进的顺序查找顺序表末尾设一个监视哨查找不成功的比较次数为n1。解析:ASL(123...n)/nn(n1)/2/n(n1)/22. 线性表以D方式存储能进行折半查找。A. 关键字有序的B. 顺充C. 链接D. 关键字有序的顺序解析折半查找要求能够随机存取通过下标直接访问中间元素只有顺序存储如数组支持随机访问。链表无法高效折半。注意折半查找要求线性表本身关键字有序但存储方式必须为顺序。3. 查找表642021385668788588100。1画出折半查找的判定树2查找到68要进行多少次元素间的比较3要查32经多少次查找确定查不到4求等概率条件下成功查找的平均查找长度答1判定树如下2查找到68要进行3次元素间的比较3要查32经4次查找确定查不到4成功查找的平均查找长度(12*24*34*4)/11(141216)/1133/113解析画判定树时不是使用元素的值而是使用其编号。用mid(lowhigh)/2求出根结点mid(010)/25用同样的方式求出左子树和右子树的根结点。6420213856687885881000 1 2 3 4 5 6 7 8 9 104. 给出二叉排序树的定义答二叉排序树的三要素根结点大于或等于左子树上所有结点的值根结点小于或等于右子树上所有结点的值左、右子树也分别是一棵二叉排序树通常不考虑等于的情况。5. 下述结论是否正确若二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值则该二叉树是二叉排序树。答不正确。举例如下6. 对A进行中序遍历遍历所得到的序列是有序序列。A. 二叉排序树B. 完全二叉树C. 满二叉树D. 哈夫曼树7. 给定序列{91861022118207}依次取序列中的数构造一棵二叉排序树给出该树的中序遍历序列。答二叉排序树如下:中序遍历序列如下:6 7 8 9 10 11 18 20 22解析中序遍历二叉排序树的结果是一个从小到大排列的有序序列做题时直接写出从小到大的序列就对了。8. 设数据集合a{112583107139}1分别从前向后和从后向前依次取a中各数据构造两棵二叉排序树它们的高度各为多少2说明如何依据此二叉树得到a的有序序列。3对上述二叉树进行查找成功查找到7要进行多少次元素间的比较。4画出在二叉树中删除12后的树结构。答1从前向后依次取a中各数据构造的二叉排序树如下高度为6层从后向前依次取a中各数据构造的二叉排序树如下高度为4层2对1中的二叉排序树进行中序遍历可得到a的有序序列3以9为根结点的二叉排序树查找7要进行2次元素间的比较。以1为根结点的二叉排序树查找7要进行5次元素间的比较。4二叉树中删除12后的树结构如下9. 把9个数123...9填入下图所示的二叉树使树中除叶结点外每个结点的值都大于其左子树上的结点的值小于其右子树上的结点的值。把3.5作为结点插入该树使该树仍具上述性质。答结果树如下把3.5作为结点插入后的结果树如下10. 在有序表{10233236536668768790101}中用折半查找值53时经D次比较后查找成功。A. 6B. 3C. 8D. 411. 有一个长度为11的有序表按折半查找对该表进行查找在等概率情况下查找成功的平均比较次数为B。A. 29/11B. 33/11C. 26/11D. 30/11解析其二叉判定树如下等概率情况下查找成功的次数(12*24*34*4)/1133/1112. 设数据集合a{627430155648}在不改变树的结构的条件下能否把a中的数据填入以下两棵树的树结点中使树成为二叉树。1如不能说明理由如果能则把数据填入。2对该二叉排序树中进行查找说出不成功查找有多少种可能画出不成功查找树的示意图。3不成功查找的平均查找长度是多少为了成功查找到56需要进行多少次元素间的比较答1图1不可能因为右子树需要3个结点而左子树只需要2个结点。图2可能如下所示2不成功查找有7种可能示意图如下3不成功查找的平均查找长度(26*3)/720/7成功查找到56需要进行3次元素间的比较13. 设数据集a{52,20,46,38,5,64,40}所构造的一棵二叉排序树如下图。1画出在树中依次插入结点485055的图结构在树中成功查找到38和46各要进行多少次元素间的比较2画出在二叉树排序树中依次删除52046后的树结构答1依次插入结点485055后的二叉排序树如下成功查找到38和46各要进行4次和3次元素间的比较2依次删除52046后的树结构如下14. 以下函数在a[0]到a[n-1]中用折半查找算法查找关键字等于k的记录查找成功返回该记录的下标失败则返回-1完成程序中的空格。typedef struct{int key;......}NODE;int Binary_Search(NODE a[ ],int n,int k){int low,mid,high;low0;highn-1;while(lowhigh){mid(lowhigh)/2;if(a[mid].keyk){returnmid;else if(a[mid].keyk){lowmid1;}highmid-1;}}return -1;}15. 以下函数是二叉排序树的查找算法若二叉树为空则返回根结点的指针否则返回值是指向树结点的结构指针p查找成功p指向查到的树结点不成功p指向为NULL,完成程序中的空格。typedef struct Bnode{int key;struct Bnode *left;struct Bnode *right;}Bnode;Bnode *Bsearch(Bnode *bt,int k){Bnode *p;if(btNULL){return (bt);}pbt;while(p-key!k){if(kp-key){pp-left;}else{pp-right;}if(pNULL){break;}}returnp;}