第九章集合
四、应用题
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）=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和线性探测再散列处理冲突的方法在地址空间A[0..15]中构造哈希表。【燕山大学1999 八（14分）】
13. 设哈希函数H（k）=3 K mod 11，散列地址空间为0～10，对关键字序列（32,13,49,24,38,21,4,12）按下述两种解决冲突的方法构造哈希表（1）线性探测再散列（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。【北方交通大学 1998 三（18分）】
14. 使用散列函数hashf(x)=x mod 11,把一个整数值转换成散列表下标，现要把数据：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）=K MOD 13，给定的键值序列为13,41,15,44,06,68,12,25,38,64,19,49，画出用链地址法处理冲突构造得的哈希表。【福州大学 1998 三、3 (6分)】
17. 设散列函数H(k)=K mod 7,散列表的地址空间为0-6，对关键字序列{32,13,49,18,22,38,21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。【西安电子科技大学1999计应用一、5 （5分）】
18. 选取哈希函数Ｈ（key）=key mod 7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。
【大连海事大学2001 八 (10分)】
19. 设散列函数为H(K)=K MOD 11,解决冲突的方法为链接法，试将下列关键字集合{35,67,42,21,29,86,95,47,50,36,91}依次插入到散列表中（画出散列表的示意图）。并计算平均查找长度ASL。【首都经贸大学 1997 三（10分）】
20. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。