第八章查找表答案及习题

1第八章查找表答案及习题习题8.7:H(k)=(3k)MOD11di=i((7k)MOD10+1)(i=1,2,3,…)m=p=11开放地址法双散列探测处理冲突：Hi=(Hi-1+di)MOD11关键字序列（22,41,53,46,30,13,01,67）01234567891022674130䦋㌌㏒㧀낈ᖺ琰茞ᓀ㵂Ü5346䦋㌌㏒㧀낈ᖺ琰茞ᓀ㵂Ü13䦋㌌㏒㧀낈ᖺ琰茞ᓀ㵂Ü01H(22)=(3*22)MOD11=0H(41)=(3*41)MOD11=2H(53)=(3*53)MOD11=5H(46)=(3*46)MOD11=6H(30)=(3*30)MOD11=2d1=(7*30)MOD10+1=1H1=3H(13)=(3*13)MOD11=6d1=(7*13)MOD10+1=2H1=8H(01)=(3*01)MOD11=3d1=(7*01)MOD10+1=8H1=0,8,5,2,10H(67)=(3*67)MOD11=3d1=(7*67)MOD10+1=10H1=2,1ASLsucc=(1+1+1+1+2+2+6+3)/8=17/8习题8.8:解：根据装填因子的定义可得表长m≤16，取m=16，p=13,设哈希函数：H(k)=关键字首字母序号/2，采用开放地址法线性探测处理冲突构造散列表。关键字序列:（ZHAO,QIAN,SUN,LI,ZHOU,WU,CHEN,WANG,CHANG,CHAO,YANG,JIN）1234567891011121314151617181920212223242526ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789101112131415YANGZHOUCHENCHANGCHAOJINLIQIANSUNWUZHAO22234111111习题8.8:H(ZHAO)=26/2=13H(QIAN)=17/2=8H(SUN)=19/2=9H(LI)=12/2=62H(ZHOU)=26/2=13Hi=(H(ZHOU)+di)MOD13=1H(WU)=23/2=11H(CHEN)=3/2=1Hi=(H(CHEN)+di)MOD13=2H(WANG)=23/2=11Hi=(H(WANG)+di)MOD13=12H(CHANG)=3/2=1Hi=(H(CHANG)+di)MOD13=2,3H(CHAO)=3/2=1Hi=(H(CHAO)+di)MOD13=2,3,4H(YANG)=25/2=12Hi=(H(YANG)+di)MOD13=0H(JIN)=10/2=5ASLsucc=(1*6+2*3+3*1+4*1)/12=18/12=1.5习题8.9://---链地址法存储结构---//typedefstruct{ElemTypedata;LHNode*next;}LHNode,*LHNodeptr;typedefstruct{LHNodeptr*elem;intcount;//记录数intsizeindex;//哈希表容量}LHashTable;习题8.9:StatusBuild_Hash(LHashTable&T,intm){//输入一组关键字,建立Hash表,表长为m,用链地址法处理冲突if(m1)return0;T.elem=newLHNodeptr[m];//建立表头指针向量for(i=0;im;i++)T.elem[i]=NULL;T.count=0;T.sizeindex=m;KeyTypekey;cout“请输入一组关键字,以0为结束符:\n”;cinkey;while((key!=0&&T.count=m){LHNodeptrq=newLHNode;q-data.key=key;q-next=NULL;n=H(key);if(!T.elem[n])T.elem[n]=q;//作为链表的第一个结点else{for(p=T.elem[n];p-next;p=p-next);p-next=q;//插入链表尾部.}T.count++;cinkey;3}//whilereturnOK;}//Build_Hash1:对线性表进行二分查找时，要求线性表必须()。A)以顺序方式存储B)以顺序方式存储且元素有序C)以链式方式存储D)以链式方式存储且元素有序2.关于判定树，下列说法不正确的是()。A)判定树是对有序序列进行二分查找得到的树B)n个结点的判定树的深度为log2n+1C)判定树的叶子结点都在同一层D)判定树除去最后一层结点以后是满二叉树或空二叉树3.从原理上讲，折半查找法要求查找表中各元素的键值必须是()。A)递增或递减B)递增C)递减D)无序4.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（）。A)该中间位置B)该中间位置－1C)该中间位置＋1D)该中间位置/25.在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做（）次关键码比较。A)2B)3C)4D)56.如果某二叉树的左右子树的高度差的绝对值不大于1，则一定是平衡二叉树。A)正确B)不正确7.静态查找表与动态查找表的根本区别在于().A)它们的逻辑结构不一样B)施加在其上的操作不一样C)所包含的数据元素的类型不一样D)存储实现不一样8.按{12,24,36,90,52,30}的顺序构成的平衡二叉树,其根结点是().A)24B)36C)52D)309.一棵完全二叉树一定是一棵().A)堆B)哈夫曼树C)二叉排序树D)平衡二叉树10.AVL树的任何子树都是AVL树()。A)正确B)不正确11.在散列表中，所谓同义词就是具有相同散列地址的两个数据元素（）。A）正确B）不正确12.对包含N个元素的散列表进行查找，平均查找长度（）。A）为O(log2N)B）为O(N)C）不直接依赖于ND）上述三者都不是13.哈希表的查找效率完全取决于所选取的哈希函数和处理冲突的方法（）。A)正确B)不正确14.与其它查找方法相比,散列查找法的特点是().A)通过关键字的比较进行查找B)通过关键字计算元素的存储地址进行查找4C)通过关键字计算元素的存储地址并进行一定的比较查找D)以上都不是15.假设有10个关键字，它们具有相同的散列地址，用线性探测法把这10个关键码存入散列中至少需要做（）次探测。A)110B)100C）55D）4516.采用开放地址法解决冲突的散列查找中，发生聚集的原因主要是().A)数据元素过多B)装填因子过大C)散列函数选择不好D)解决冲突的方法不好1.B2.C3.A4.B5.C6.B7.B8.B9.D10.A11.A12.D13.B14.C15.C16.C