第八章 查找表答案及习题.doc

第八章 查找表答案及习题习题8.7: H(k)=(3k) MOD 11 di=i ( (7k) MOD 10+1) (i=1,2,3,) m=p=11 开放地址法双散列探测处理冲突： Hi=(Hi-1+di) MOD 11关键字序列 （22,41,53,46,30,13,01,67）01234567891022674130琰茞5346琰茞13琰茞01H(22)=(3*22) MOD 11=0 H(41)=(3*41) MOD 11=2H(53)=(3*53) MOD 11=5 H(46)=(3*46) MOD 11=6H(30)=(3*30) MOD 11=2 d1=(7*30) MOD 10+1=1 H1=3H(13)=(3*13) MOD 11=6 d1=(7*13) MOD 10+1=2 H1=8H(01)=(3*01) MOD 11=3 d1=(7*01) MOD 10+1=8 H1=0,8,5,2,10H(67)=(3*67) MOD 11=3 d1=(7*67) MOD 10+1=10 H1=2,1ASLsucc=(1+1+1+1+2+2+6+3)/8=17/8习题8.8: 解：根据装填因子的定义可得表长m16，取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=6H(ZHOU)=26/2=13 Hi=(H(ZHOU)+di) MOD 13 =1H(WU)=23/2=11 H(CHEN)=3/2=1 Hi=(H(CHEN)+di) MOD 13 =2 H(WANG)=23/2=11 Hi=(H(WANG)+di) MOD 13 =12 H(CHANG)=3/2=1 Hi=(H(CHANG)+di) MOD 13 =2,3 H(CHAO)=3/2=1 Hi=(H(CHAO)+di) MOD 13 =2,3,4 H(YANG)=25/2=12 Hi=(H(YANG)+di) MOD 13 =0 H(JIN)=10/2=5 ASLsucc=(1*6+2*3+3*1+4*1)/12=18/12=1.5习题8.9: /- 链地址法存储结构 -/typedef struct ElemType data; LHNode *next; LHNode,*LHNodeptr;typedef struct LHNodeptr*elem; intcount;/记录数intsizeindex; /哈希表容量 LHashTable;习题8.9: Status Build_Hash(LHashTable &T, int m) /输入一组关键字,建立Hash表,表长为m,用链地址法处理冲突 if(m1) return 0; T.elem=new LHNodeptrm; /建立表头指针向量 for(i=0; im; i+) T.elemi=NULL; T.count=0; T.sizeindex=m; KeyType key; coutkey; while(key!=0 & T.countdata.key=key; q-next=NULL;n=H(key); if(!T.elemn) T.elemn=q; /作为链表的第一个结点 else for (p=T.elemn; p-next; p=p-next ) ; p-next=q; /插入链表尾部. T.count+; cinkey; /while return OK; /Build_Hash1: 对线性表进行二分查找时，要求线性表必须( )。 A)以顺序方式存储 B)以顺序方式存储且元素有序 C)以链式方式存储 D)以链式方式存储且元素有序2.关于判定树，下列说法不正确的是( )。 A)判定树是对有序序列进行二分查找得到的树 B)n个结点的判定树的深度为 log2n +1 C)判定树的叶子结点都在同一层 D)判定树除去最后一层结点以后是满二叉树或空二叉树3.从原理上讲，折半查找法要求查找表中各元素的键值必须是 ( )。 A)递增或递减 B)递增 C)递减 D)无序4.若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（ ）。 A)该中间位置 B)该中间位置1 C)该中间位置1 D)该中间位置/25.在顺序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找关键码12需做（）次关键码比较。 A)2 B)3 C)4 D)56.如果某二叉树的左右子树的高度差的绝对值不大于1，则一定是平衡二叉树。 A)正确 B)不正确7.静态查找表与动态查找表的根本区别在于( ). A)它们的逻辑结构不一样 B)施加在其上的操作不一样 C)所包含的数据元素的类型不一样 D)存储实现不一样8.按12,24,36,90,52,30的顺序构成的平衡二叉树,其根结点是( ). A)24 B)36 C)52 D)309.一棵完全二叉树一定是一棵( ). A)堆 B)哈夫曼树 C)二叉排序树 D)平衡二叉树10.AVL树的任何子树都是AVL树( )。 A)正确 B)不正确11.在散列表中，所谓同义词就是具有相同散列地址的两个数据元素（ ）。 A）正确 B）不正确12.对包含N个元素的散列表进行查找，平均查找长度（ ）。 A）为 O(log2N) B）为O(N) C）不直接依赖于N D）上述三者都不是13.哈希表的查找效率完全取决于所选取的哈希函数和处理冲突的方法（ ）。 A)正确 B)不正确14.与其它查找方法相比,散列查找法的特点是( ). A)通过关键字的比较进行查找 B)通过关键字计算元素的存储地址进行查找 C)通过关键字计算元素的存储地址并进行一定的比较查找 D)以上都不是 15.假设有10个关键字，它们具有相同的散列地址，用线性探测法把这10个关键码存入散列中至少需要做（ ）次探测。 A)110 B)100 C）55 D）4516.采