第8章-查找-习题参考答案

1习题八参考答案一、选择题1．对线性表进行二分查找时，要求线性表必须(B)A.以顺序方式存储B.以顺序方式存储，且结点按关键字值有序排列C.以链接方式存储D.以链接方式存储，且结点按关键字值有序排列2.用二分查找法查找具有n个结点的顺序表时，查找每个结点的平均比较次数是(D)A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)3.对长度为4的顺序表进行查找，若查找第一个记录的概率为1/24,查找第二个记录的概率为1/6,查找第三个记录的概率为2/3,查找第四个记录的概率为1/8,则查找任意一个记录的平均查找长度为(A)A.23/8B.20/8C.17/8D.14/84.若有一个长度为64的有序表，现用二分查找方法查找某一记录，则查找不成功，最多需要比较(B)次。A.9B.7C.5D.35.当采用分块查找时，数据的组织方式为(C)A.数据必须有序B.数据不必有序C.数据分成若干块，每块内数据不必有序，但块间必须有序D.数据分成若干块，每块内数据必须有序，但块间不必有序6.一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该平衡二叉树共有(C)个结点。A.2k-1-1B.2k-1+1C.2k-1D.2k+17.具有5层结点的平衡二叉树至少有(B)个结点。A.10B.12C.15D.178.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为(D)A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构9.以下有关m阶B-树的叙述中，错误的是(B)。A.根结点至多有m棵子树B.每个结点至少有2m棵子树C.所有叶子结点都在同一层上D.每个结点至多有m-1个关键字10．哈希表的地址区间为0～17，哈希函数为h(key)=K%17。采用线性探测法处理冲突，并将关键字序列{26，25，72，38，8，18,59}依次存储到哈希表中，则在哈希表中查找元素59需要搜索的次数为(C)。A.2B.3C.4D.5二、填空题1．动态查找表和静态查找表的主要区别在于动态查找表有插入和删除操作。2．假定待查找记录个数为n,则在等概率的情况下，顺序查找在查找成功情况下的平均查找长度为(n+1)/2；在查找失败情况下的平均查找长度为n+1。3.对线性表进行二分查找时，要求线性表必须以顺序方式存储，且数据有序。4.分块查找分为两个阶段，分别是确定待查元素所在的块和在块内查找待查的元素。5．哈希法存储中，冲突指的是不同关键字值对应到相同的存储地址。6.一棵二叉排序树用中序遍历输出的信息是递增序列。7．深度为4的平衡二叉树中至少有7个结点，至多有15个结点。8．引入B-树的根本原因是减少查找一个元素需要访问的外存的次数。9．哈希法存储的基本思想是根据关键字来决定存储地址。10．设计一个好的哈希函数，其函数值应该以同等概率取其值域的每个值。三、算法设计题1．基于SeqList类，设计带监视哨的顺序查找算法，要求把监视哨设置在n号单元。参考答案：publicintseqSearchWithGuard(Comparablekey){inti=length()-1;2getRecord()[i].setKey(key);//哨兵设置在第n号单元i=0;while((getRecord()[i].getKey()).compareTo(key)!=0){i++;}if(ilength()-1){returni;}else{return-1;}}2．基于SeqList类，设计一个递归算法，实现二分查找。参考答案：publicintbinarySearchRecursively(intlow,inthigh,Comparablekey){intmid,result;if(low=high){mid=(low+high)/2;//中间位置，当前比较元素位置result=getRecord()[mid].getKey().compareTo(key);if(result0){returnbinarySearchRecursively(low,mid-1,key);//查找成功}elseif(result0){returnbinarySearchRecursively(mid+1,high,key);}else{returnmid;}}return-1;//查找不成功}3．基于BSTree类，设计一个算法，判断所给的二叉树是否为二叉排序树。参考答案：publicclassExercise8_3_3extendsBSTree{booleanflag=true;Comparablelastkey=newKeyType(0);//判断二叉树T是否二叉排序树,是则返回true,否则返回falsebooleanIs_BSTree(BiTreeNodeT){if(T.getLchild()!=null&&flag){Is_BSTree(T.getLchild());}if(lastkey.compareTo(((RecordNode)T.getData()).getKey())0){flag=false;//与其中序前驱相比较}((KeyType)lastkey).setKey(((KeyType)(((RecordNode)T.getData()).getKey())).getKey());3if(T.getRchild()!=null&&flag){Is_BSTree(T.getRchild());}returnflag;}}4．基于BSTree类，设计一个算法，输出给定二叉排序树中值最大的结点。参考答案：BiTreeNodemaxNode(BiTreeNodeT){if(T==null){System.out.println(这是一颗空树.);returnnull;}else{BiTreeNodeq=T;while(q.getRchild()!=null){q=q.getRchild();}returnq;}}5．基于BSTree类，设计一个算法，求出指定结点在给定的二叉排序树中所在的层数。参考答案：publicclassExercise8_3_5extendsBSTree{staticintlevel=0;//层数staticbooleanfound=false;publicstaticintlevelOfNode(BiTreeNodep,Comparablekey){if(p!=null&&!found){level++;if(key.compareTo(((RecordNode)p.getData()).getKey())==0){found=true;;}else{levelOfNode(p.getLchild(),key);//在左子树中查找levelOfNode(p.getRchild(),key);//在右子树中查找if(!found){level--;}}}returnlevel;}}46．基于BSTree类，设计一个算法，在二叉排序树中以非递归方式查找值为key的结点。参考答案：publicObjectsearchBSTNonRecur(BiTreeNodep,Comparablekey){while(p!=null){if(key.compareTo(((RecordNode)p.getData()).getKey())==0)//查找成功{returnp.getData();}elseif(key.compareTo(((RecordNode)p.getData()).getKey())0){p=p.getLchild();//在左子树中查找}else{p=p.getRchild();//在右子树中查找}}returnnull;}