简答-查找

第九章集合四、应用题1.名词解释：哈希表【燕山大学1999一、4（2分）】【哈尔滨工业大学1999一、3（3分）】【首都经贸大学1997一、2（4分）】同义词：【山东大学1998二、1(2分)】【山东工业大学2000二、1（2分）】叙述B-树定义，主要用途是什么？它和B+树的主要差异是什么？【青岛大学2001五（5分）】B-树【南开大学1996五、4(3分)1998五、4(4分)2000二、2（2）】【山东大学2000三(8分)】平衡二叉树（AVL树）？【南开大学1996五、3(3分)1998五、3(4分)】【厦门大学1998四、2（5分）】平衡因子【西北工业大学1999一、2(3分)】平均查找长度（ASL）【西北工业大学1999一、3(3分)】trie树。【中山大学1997一、3（3分）】2.回答问题并填空（1）（2分）散列表存储的基本思想是什么？（2）（4分）散列表存储中解决碰撞的基本方法有哪些？其基本思想是什么？（3）（４分）用分离的同义词子表解决碰撞和用结合的同义词表解决碰撞属于哪种基本方法？他们各有何特点？（4）（３分）用线性探查法解决碰撞时，如何处理被删除的结点？为什么？（5）（２分）散列法的平均检索长度不随()的增加而增加，而是随()的增大而增加。【山东工业大学1999四（15分）】3.如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。【南京航空航天大学1996九、2（6分）】4．HASH方法的平均查找路长决定于什么？是否与结点个数N有关？处理冲突的方法主要有哪些？【中国人民大学2000一、4（4分）】5．在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？【西安电子科技大学2000计应用一、8（5分）】6.设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=keymod7，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di)mod10(di=12,22,32,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。【东北大学2002二、2（5分）】7.对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法；【东北大学2001六(18分)】8.设哈希表a、b分别用向量a[0..9],b[0..9]表示，哈希函数均为H（key）=keyMOD7,处理冲突使用开放定址法，Hi=[H(key)+Di]MOD10,在哈希表a中Di用线性探测再散列法，在哈希表b中Di用二次探测再散列法,试将关键字{19,24,10,17,15,38,18,40}分别填入哈希表a,b中,并分别计算出它们的平均查找长度ASL。【北京工业大学1998三(8分)】9.采用哈希函数Ｈ（k）=3*kmod13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51（1）构造哈希表（画示意图）；（2）装填因子；等概率下（3）成功的和（4）不成功的平均查找长度。【北京工业大学2000三(8分)】10.设一组数据为{1,14,27,29,55,68,10,11,23}，现采用的哈希函数是H(key)=keyMOD13，即关键字对13取模，冲突用链地址法解决，设哈希表的大小为13(0..12)，试画出插入上述数据后的哈希表。【南京理工大学1996三、3（5分）】11.设散列表长度为14，散列函数h(x)=，其中i为健值中第一个字母在字母表中的序号，若健值的输入顺序为Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec，用拉链法处理冲突，要求：（1）构造散列表（2）求出在等概率情况下，查找成功的平均查找长度。【厦门大学2001二、2（24%/3分）】12.常用的构造哈希函数的方法有哪些？若在哈希表中删除一个记录，应如何操作？为什么？已知一组关键字为（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函数H(Key)=KeyMOD13和线性探测再散列处理冲突的方法在地址空间A[0..15]中构造哈希表。【燕山大学1999八（14分）】13.设哈希函数H（k）=3Kmod11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。【北方交通大学1998三（18分）】14.使用散列函数hashf(x)=xmod11,把一个整数值转换成散列表下标，现要把数据：1,13,12,34,38,33,27,22插入到散列表中。（1）使用线性探查再散列法来构造散列表。（5分）（2）使用链地址法构造散列表。（5分）针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。（5分）【清华大学1998五（15分）】15.已知长度为12的表(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)(1)试按表中元素的顺序依次插入一棵初始为空的分类二叉树，试画出插入完成之后的分类二叉树并计算其在等概率查找情况下，查找成功的平均查找长度。(2)试用以下两种方法构造两个Hash表，Hash函数H(K)=[i/2],其中i为关键字K中第一个字母在字母表中的序号，[x]表示取整数。a.用线性探测开放定址法处理冲突(散列地址空间为0～16);b.用链地址法处理,然后分别求出这两个Hash表在等概率查找情况下，查找成功的平均查找长度。【上海海运学院1996五（15分）】16.设散列函数为H（K）=KMOD13，给定的键值序列为13,41,15,44,06,68,12,25,38,64,19,49，画出用链地址法处理冲突构造得的哈希表。【福州大学1998三、3(6分)】17.设散列函数H(k)=Kmod7,散列表的地址空间为0-6，对关键字序列{32,13,49,18,22,38,21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。【西安电子科技大学1999计应用一、5（5分）】18.选取哈希函数Ｈ（key）=keymod7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。【大连海事大学2001八(10分)】19.设散列函数为H(K)=KMOD11,解决冲突的方法为链接法，试将下列关键字集合{35,67,42,21,29,86,95,47,50,36,91}依次插入到散列表中（画出散列表的示意图）。并计算平均查找长度ASL。【首都经贸大学1997三（10分）】20.已知散列表的地址空间为A[0..11]，散列函数H（k）=kmod11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。【合肥工业大学2000四、3（5分）】21.设输入的关键字序列为：22,41,53,33,46,30,13,01,67,Hash函数为：H（key）=keyMOD11。HASH表长度为11。试用线性探测法解决冲突，将各关键字按输入顺序填入Hash表中。【南京航空航天大学1998二（10分）】22.设哈希(Hash)表的地址范围为0～17，哈希函数为：H(K)=KMOD16,K为关键字，用线性探测再散列法处理冲突，输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49)造出哈希表，试回答下列问题：(1)画出哈希表示意图；(2)若查找关键字63，需要依次与哪些关键字比较?(3)若查找关键字60，需要依次与哪些关键字比较?(4)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。【华中理工大学1999三（10分）】23.试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过2.0。并请验证你造的哈希表的实际平均查找长度是否满足要求。（CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,WANG,CAO,YUN,CHANG,YANG）【清华大学1996五】24.设a,b,c,d,e五个字符的编码分别为1,2,3,4,5，并设标识符依以下次序出现：ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（Hash）方法将它们存入具有10个位置的表中。（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。【南开大学1998六(10分)】25.对以下关键字序列建立哈希表：(SUN,MON,TUE,WED,THU,FRI,SAT)，哈希函数为H（K）=（关键字中第一个字母在字母表中的序号）MOD7，用线性探测法处理冲突，求构造一个装填因子为0.7的哈希表;并分别计算出在等概率情况下查找成功与不成功的平均查找长度。【西北大学2000二、3(5分)】26.设散列表为HT[0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：H0(key)=key%13;注:%是求余数运算(=mod)Hi=(Hi-1+REV(key+1)%11+1)%13;i=1,2,3,…,m-1其中，函数REV（x）表示颠倒10进制数x的各位，如REV（37）=73，REV（7）=7等。若插入的关键码序列为(2,8,31,20,19,18,53,27)。(1)(8分)试画出插入这8个关键码后的散列表；(2)(5分)计算搜索成功的平均搜索长度ASL。【清华大学2000八(13分）】27.设一个散列表含hashsize=13个表项，其下标从0到12，采用线性探查法解决冲突。请按以下要求，将关键码{10,100,32,45,58,126,3,29,200,400,0}散列到表中。（1）散列函数采用除留余数法，用%hashsize（取余运算）将各关键码映像到表中，请指出每一个产生冲突的关键码可能产生多少次冲突。（7分）（2）散列函数采用先将关键码各位数字折叠相加，再用%hashsize将相加的结果映像到表中的办法。请指出每一个产生冲突的关键字码可能产生多少次冲突。【清华大学2001五（15分）】28.已知一组关键字为（26,36,41,38,44,15,68,12,06,51,25），用链地址法解决冲突。假设装填因子a=0.75，散列函数的形式为H（K）=KMODP，回答下列问题：（1）构造出散列函数；（3分）（2）计算出等概率情况下查找成功的平均查找长度；（3分）（3）计算出等概率情况下查找失败的平均查找长度；（3分）【东北大学1999一、3(共9分)】29.在B-树和B+树中查找关键字时，有什么不同？【东北大学2002一、5(2分)】30.简要叙述B树(有些教材中称为B-树)与B+树的区别?【南京航空航天大学1999六（5分）】31.包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？（要求写出推导过程。）【北京大学1997五、2（6分）】32.给定关键码序列（26,25,20,33,21,24,45,204,42,38,29,31），要用散列法进行存储，规定负载因子α=0.6。（1）请给出除余法的散列函数。（2）用开地址线性探测法解决碰撞，请画出插入所有的关键码后得到的散列表，并指出发生碰撞的次数。【北京大学1997三（6分）】33.已知记录关键字集