简答查找试卷.docVIP

第九章 集合 四、应用题 名词解释： 哈希表【燕山大学 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）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(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）=key MOD 7,处理冲突使用开放定址法，Hi=[H(key)+Di]MOD 10,在哈希表a中Di用线性探测再散列法，在哈希表b中Di用二次探测再散列法,试将关键字{19,24, 10,17,15,38,18,40}分别填入哈希表a,b中,并分别计算出它们的平均查找长度ASL。【北京工业大学 1998 三 (8分)】 9. 采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［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)=key MOD 13， 即关键字对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)=Key MOD 13和线性探测再散列处理冲