简答 查找

第九章 集合

四、应用题 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 ，表

222

长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=1,2,3,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。【东北大学 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}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。 【合肥工业大学 2000 四、3 （5分）】

21. 设输入的关键字序列为：22,41,53,33,46,30,13,01,67, Hash函数为：H（key）=key MOD 11。HASH表长度为11。试用线性探测法解决冲突，将各关键字按输入顺序填入Hash表中。【南京航空航天大学 1998 二 （10分）】

22. 设哈希(Hash)表的地址范围为0～17，哈希函数为：H (K)=K MOD 16, 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）=（关键字中第一个字母在字母表中的序号）MOD 7，用线性探测法处理冲突，求构造一个装填因子为0.7的哈希表;并分别计算出在等概率情况下查找成功与不成功的平均查找长度。【西北大学 2000 二、3 (5分)】 26. 设散列表为HT [0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为：

H0(key)=key % 13; 注:%是求余数运算(=mod)

Hi=(Hi-1+REV(key+1)+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）=K MOD P，回答下列问题： （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. 已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等概率情况）【东北大学1998一、2 (10分)】 34. 设有一棵空的３阶B-树，依次插入关键字30,20,10,40,80,58,47,50,29,22,56,98,99，请画出该树。

【华南理工大学 2001 一、5 （4分）】

35．设依以下次序给出关键字：34,16,19,21,5,49,24,62,3,17,45,8，构造3阶B-树。要求从空树开始，每插入一个关键字,画出一个树形。【南开大学 1997 六 (10分)】 36.高度为h的m阶B树至少有多少个结点？【西安电子科技大学2000软件一、6 （5分）】

37. 对下面的3阶B-树，依次执行下列操作，画出各步操作的结果。【合肥工业大学 1999 四、3 （1）插入90 （2） 插入25 （3） 插入45 （4）删除60 （5）删除80

38. 已知2棵2-3 B-树如下（省略外结点）：【吉林大学 1999 一、4 (4分)】 （1）对树（a）,请分别画出先后插入26，85两个新结点后的树形； （2）对树（b）,请分别画出先后删除53，37两个结点后的树形。

(a)

（b） 39. 四阶B树中（如图所示），插入关键字87，试画出插入调整后树的形状【东南大学 1999 五 （15分）】

30 60 80

20 25 35 50 60 70 75 82 85 90

40. 下图是5阶B树 ，画出删去P后的B树，再画出删去D后的B树。【厦门大学 2000 二、

5分）】（

2 （20/3分）】

41. 满二叉检索树符合B树定义吗？B树的插入和删除算法适用于满二叉检索树吗？为何？【东南大学 1995 五 （6分）】

42. 设有关键码序列10,20,35,40,44,51,65,70,85,91,93,95。试按照最大关键码复写原则绘出相应的2阶 B+ 树。

【山东工业大学 1996 二、1 （6分）】

43. 在一棵B+树上一般可进行那两种方式的查找运算?【北京科技大学 2001 一、8 （2分）】 44. 含9个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？

【北京轻工业学院 2000 八 （10分）】

45. 直接在二叉排序树中查找关键字K与在中序遍历输出的有序序列中查找关键字K，其效率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后对此树进行查找，其效率如何？为什么？【长沙铁道学院 1997 三、4 (3分)】

46. 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。

【厦门大学 2002 八、2 （5分）】 47. 已知长度为11的表（xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon），按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

【山东大学 2001 七 ( 7分)】

48. 用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度.【北京邮电大学 1999 七 （10分）】

49. 依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树

【华中理工大学 2000 五 （10分）】

(1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列;

(3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。 50. 已知关键字序列R={11,4,3,2,17,30,19}，请按算法步骤：【北方交通大学 1996 四】 （1）构造一棵哈夫曼树，并计算出它的带权路径长度WPL（7分）

（2）构造一棵二叉排序树，如果对每个关键字的查找概率相同，求查找成功时的平均查找长度ASL。（8分）

51. 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。

（1） 按次序构造一棵二叉排序树BS。(2) 依此二叉排序树，如何得到一个从大到小

的有序序列？

（2） 画出在此二叉排序树中删除“66”后的树结构。【同济大学 2001 一 (10分)】 52. 设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。【东北大学 2002 一 、3 (4分)】

（1）51，250，501，390，320，340，382，363 （2）24，877，125，342，501，623，421，363

53. 用关键字1,2,3,4的四个结点（1）能构造出几种不同的二叉排序树？其中（2）最优查找树有几种？（3）AVL树有几种？(4)完全二叉树有几种？试画出这些二叉排序树。【北京工业大学 1997 二、 3 ( 5分)】 类似本题的另外叙述有：

(1)设有关键字A、B、C和D，依照不同的输入顺序，共可能组成多少不同的二叉排序树。请画出其中高度较小的6种。 【北京大学 1995 】

54. 一棵具有m层的AVL树至少有多少个结点，最多有多少个结点？【浙江大学 1995 六 (8

分)】

55. 设T是一棵高度平衡树(又称平衡树)，给定关键词K，如果在T中查找K失败，且查找路径上的任一结点的平衡系数皆为零，试回答用高度平衡树插入算法在T中插入关键词为K的新结点后，树T的高度是否一定增加?并回答为什么。

【吉林大学 1996 四、2】

56．设二叉树HT是一棵高度平衡树，当使用二叉查找与插入算法插入一个新的结点时，该操作可能会破坏HT的平衡性。试列举出可能破坏HT的平衡性的所有情况，并论证你的结论的正确性（即要证明你所列举的情况恰好是可能破坏HT的平衡性的所有情况）【吉林大学1998 四 1997 六 (14分)】

57. 按下述次序输入关键字：e,i,p,k,,m,l,b,试画出AVL树的构造与调整过程。（要求画出每插入一个关键字检索树的形状及调整后的结果）。【山东大学 1992 一 、5 (3分)】 58. 已知一棵高度平衡树如下，其中各结点间大小关系（中根次序）按字典序排列，请画出

插入结点JUN后，该二叉树经平衡过程而形成的树形，并说明采用何种转动方式，标出平衡后树中各结点的平衡系数。【吉林大学 1999 一 、1 (4分)】

59. 已知长度为l2的表{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}

（1） 试按表中元素的次序依次插入一棵初始为空的二叉排序树，请画出插入之后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。 （2） 若对表中元素先进行排序构成有序表，求在等概率的情况下对此表进行折半查找成功的平均查找长度。 （3） 按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。

【中国矿业大学 2000 七（10分）】

60. 试画出从空树开始，由字符序列(t,d,e,s,u,g,b,j,a,k,r,i)构成的二叉平衡树，并为每一次的平衡处理指明旋转类型。

【清华大学 1994 三（10分）】

61. 给定关键词输入序列{CAP,AQU,PIS,ARI,TAU,GEM,CAN,LIB,VIR,LEO,SCO}，假定关键词

比较按英文字典序，

（1）试画出从一棵空树开始，依上述顺序（从左到右）输入关键词，用高度平衡树的查找和插入算法生成一棵高度平衡树的过程，并说明生成过程中采用了何种转动方式进行平衡调整，标出树中各结点的平衡系数。

（2）试画出在上述生成的高度平衡树中，用高度平衡树的删除算法先后删除结点CAN和AQU后的树形，要求删除后的树形仍为一棵高度平衡树，并说明删除过程中采用了何种转动方式进行平衡调整，标出树中各结点的平衡系数。 【吉林大学 2000 一 、5 (6分)】

62. 如图2所示是一棵正在进行插入运算的AVL树，关键码70的插入使它失去平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡。 (1) 请画出调整后的AVL树。

(2) 假设AVL树用llink-rlink法存储，t是指向根结点的指针，请用Pascal(或C)语句

表示出这个调整过程。 （说明：不必写出完整的程序，只需用几个语句表示出在本题中所给出的具体情况下调整过程中指针的变化。在调整过程中还有两个指针变量p和q可以使用。）【北京大学 1997 六（10分）】

t .

-- 100 60 + 120 · -

40 ·-- 80 -

·- 70

63. 若以序列 {Thu,Tue,Wed,Last,Fri,Sat,Mon,Sun,Next} 作为输入序列

(1) 按算法AVL-INSERT构造均高树，画出构造过程和进行平衡转换的类型。

(2) 若均高树中有n个结点，其高度为h，指出在最坏情况下，对该树的插入、删除和依次输出操作的时间复杂性。

【东南大学 1992 五（18分）】

64. 在数轴上有N个彼此相临不交的区间，每个区间下界上界都是整数。N个区间顺序为

1-N。要查找给定的X落入的区间号，您认为应怎样组织数据结构，选择什么方法最快，简述原因。

【西北大学 2000 二、4 (5分)】

65. 有一个长度为12的有序表，按对半查找法对该表进行查找，在表内各元素等概率情况

下，查找成功所需的平均比较次数是多少？【吉林大学 2001 一、 1 (3分)】

66. 若对一个线性表进行折半查找，该线性表应满足什么条件？【北京航空航天大学 1998 一、8 （4分）】

67. 在查找和排序算法中，监视哨的作用是什么？【长沙铁道学院 1997 三、3 (3分)】 68. 长度为255的有序表采用分块查找，块的大小应取多少？【首都经贸大学 1997 一、1 （4分）】

69. 用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查找长度是多少？

【厦门大学 1999 三、2】

70. 设有n个值不同的元素存于顺序结构中，试问：你能否用比（2n-3）少的比较次数选出这n个元素中的最大值和最小值？若能，请说明是如何实现的；在最坏情况下，至少要进行多少次比较。【西安电子科技大学 1996 四 （10分）】 71. 对有14个元素的有序表A[1…14]作折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有哪几个？

【燕山大学 2000 一、2 （1分）】 72. 解答下面的问题

（1）画出在递增有序表A[1..21]中进行折半查找的判定树。

（2）当实现插入排序过程时，可以用折半查找来确定第I个元素在前I-1个元素中的

可能插入位置，这样做能否改善插入排序的时间复杂度？为什么？ （3）折半查找的平均查找长度是多少？【西安电子科技大学2000计应用 八 （10分）】 73. 设有一组数据black,blue,green,purple,red,white,yellow，它们的查找概率分别为0.10,0.08,0.12,0.05,0.20,0.25,0.20。 试以它们的查找概率为权值，构造一棵次优查找树，并计算其查找成功的平均查找长度。【清华大学 1997 七 （12分）】 74. 假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：

(1).画出描述折半查找过程的判定树；

(2).若查找元素54，需依次与那些元素比较? (3).若查找元素90，需依次与那些元素比较?

(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。【华中理工大学 1999 二 (10分)】

75. 在分析二叉查找树性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为Li，那么查找失败到达失败结点时所作的数据比较次数是多少？【清华大学 1999 一、4 （2分）】

76. 设有五个数据do，for，if,repeat，while，它们排在一个有序表中，其查找概率分别

为p1 =0.2, p2=0.15，p3=0.1，p4=0.03，p5=0.01。而查找它们之间不存在数据的概率分别为q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02,q5=0.01。 do for if repeat while

q0 p1 q1 p2 q2 p3 q3 p4 q4 p5 q5

(1) 试画出对该有序表采用顺序查找时的判定树和采用折半查找时的判定树。（6分） (2) 分别计算顺序查找时的查找成功和不成功的平均查找长度，以及折半查找时的查找成功和不成功的平均查找长度。（4分）

(3) 判定是顺序查找好？还是折半查找好？（2分） 【清华大学 1999年 二 （12分）】

77. 顺序检索，二分检索，哈希（散列）检索的时间分别为O(n),O(log2n),O(1)。既然有了高效的检索方法，为什么低效的方法还不放弃？【北京邮电大学 1993 一、2 (5分)】

四．应用题

1．概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。

2．（1）散列表存储的基本思想是用关键字的值决定数据元素的存储地址 （2）散列表存储中解决碰撞的基本方法：

① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：

a．di =1，2，…，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。

22222

b．di =1，-1，2，-2，… ，?k（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。

c．di =伪随机数序列，称为随机探测再散列。

② 再散列法 Hi=RHi（key） i=1，2，…，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。

③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。

④ 建立公共溢出区 设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区 O[0..m-1]。

（3）用分离的同义词表和结合的同义词表解决碰撞均属于链地址法。链地址向量空间中的每个元素不是简单的地址，而是关键字和指针两个域，散列地址为i（0≤i≤m-1）的第一个关键字存储在地址空间向量第i个分量的“关键字”域。前者的指针域是动态指针，指向同义词的链表，具有上面③的优缺点；后者实际是静态链表，同义词存在同一地址向量空间（从最后向前找空闲单元），以指针相连。节省了空间，但易产生“堆积”，查找效率低。 （4）要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。 （5）记录 负载因子

3．评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面2题。

4．哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装满程度，该值一般取0.65~0.9。解决冲突方法见上面2题。

5．不一定相邻。哈希地址为i（0≤i≤m-1）的关键字，和为解决冲突形成的探测序列i的同义词，都争夺哈希地址i。 6．

散列地址 关键字 比较次数 0 14 1 1 01 1 2 9 1 3 23 2 4 84 5 27 6 55 1 7 20 2 8 9 3 4 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8

以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突）

23

H2=（6+2）=0（冲突） H3=（6+3）=5 所以比较了4次。 7．由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10。 （1）用除留余数法，哈希函数为H（key）=key % 7 （2） 散列地址 关键字 比较次数 0 21 1 1 15 1 2 30 1 3 36 3 4 25 1 5 40 1 6 26 2 7 37 6 8 9 （3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i（0≤i≤m-1）时的查找次数。本例中m=10。故查找失败时的平均查找长度为：

ASLunsucc=（9+8+7+6+5+4+3+2+1+1）/10=4.6 ASLsucc =16/8=2 （4）int Delete（int h[n]，int k）

// 从哈希表h[n]中删除元素k，若删除成功返回1，否则返回0 {i=k%7；// 哈希函数用上面（1），即H（key）=key % 7

if（h[i]== maxint）//maxint解释成空地址

printf（“无关键字%d\\n”，k）；return （0）；}

if（h[i]==k）{h[i]=-maxint ；return （1）；} //被删元素换成最大机器数的负数

else // 采用线性探测再散列解决冲突 {j=i;

for（d=1；d≤n-1；d++）

{i=（j+d）%n； // n为表长，此处为10

if（h[i]== maxint）return (0); //maxint解释成空地址

if（h[i]==k）{ h[i]=-maxint ；return （1）；} }//for }

printf（“无关键字%d\\n”，k）；return (0) } 8．

散列地址 关键字 比较次数 散列地址 关键字 比较次数 0 0 1 15 1 1 15 1 2 2 17 3 3 24 1 3 24 1 4 10 2 4 10 2 5 19 1 5 19 1 6 17 4 6 40 2 7 38 5 7 38 4 8 18 5 8 18 4 9 40 5 9 哈希表a: ASLsucc=24/8=3；

哈希表b: ASLsucc =18/8 9．（1）

散列地址 关键字 比较次数 0 13 1 1 22 1 2 3 4 1 2 5 6 7 67 2 8 46 1 9 10 11 12 30 1 53 1 41 1 51 1 （2）装填因子=9/13=0.7 （3）ASLsucc =11/9 （4）ASLunsucc =29/13

10． 11．ASLsucc=19/12

12．常用构造哈希函数的方法有：

（1）数字分析法 该法事先需知道关键字集合，且关键字位数比散列表地址位数多，应选数字分布均匀的位。

（2）平方取中法 将关键字值的平方取中间几位作哈希地址。

（3）除留余数法 H（key）=key%p，通常p取小于等于表长的最大素数。

（4）折叠法 将关键字分成长度相等（最后一段可不等）的几部分，进行移位叠加或间界叠加，其值作哈希地址。

（5）基数转换法 两基数要互素，且后一基数要大于前一基数。

在哈希表中删除一个记录，在拉链法情况下可以物理地删除。在开放定址法下，不能物理地删除，只能作删除标记。 该地址可能是该记录的同义词查找路径上的地址，物理的删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。

散列地址 0 关键字 13．（1）

散列地址 关键字 比较次数 0 1 4 1 2 3 12 1 4 49 1 5 38 2 6 13 1 7 24 2 8 32 1 9 21 2 10 1 2 2 3 1 4 4 5 3 6 1 7 1 8 3 9 9 10 11 12 13 14 15 1 1 3 14 01 68 27 55 19 20 84 79 23 11 10 比较次数 1 ASLsucc =（1+1+1+2+1+2+1+2）/8=11/8

ASLunsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11

（2） 13题图ASLsucc =11/8 ASLunsucc=19/11 14题（2） ASLsucc=13/8 ASLunsucc=19/11

值得指出，对用拉链法求查找失败时的平均查找长度有两种观点。其一，认为比较到空指针算失败。以本题为例，哈希地址0、2、5、7、9和10均为比较1次失败，而哈希地址1和3比较2次失败，其余哈希地址均为比较3次失败，因此，查找失败时的平均查找长度为19/11，我们持这种观点。还有另一种理解，他们认为只有和关键字比较才计算比较次数，而和空指针比较不计算。照这种观点，本题的ASLunsucc=（1+1+2+2+2）/11=8/11 14．由hashf(x)=x mod 11 可知，散列地址空间是0到10，由于有8个数据，装载因子取0.7。 （1）

散列地址 关键字 比较次数 15．

0 33 1 1 1 1 2 13 1 3 12 3 4 34 4 5 38 1 6 27 2 7 22 8 8 9 10 ASLsucc=21/8 ASLunsucc=47/11

（ASL=42/12

1）

（2）a：ASLsucc=31/12 （2）b：ASLsucc=18/12 (注：本题[x]取小于等于x的最大整数) 16．

17．查找时，对关键字49,22,38,32,13各比较一次，对21,18各比较两次

18．ASLsucc =15/10

19．ASLsuss =16/11

20．

散列地址 0 关键字 比较次数 1 ASLsucc =21/11 21．

散列地址 关键字 比较次数 22． （1）

散0 列地址 关3键2 字 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 22 1 1 33 2 2 46 1 3 13 2 4 01 4 5 67 5 6 7 8 41 1 9 53 1 10 30 3 1 1 2 1 3 1 4 2 5 1 6 2 7 3 8 2 9 4 10 3 11 231 89 79 25 47 16 38 82 51 39 151 17 63 49 24 40 10 30 31 46 47 比1 较次数 1 6 3 1 2 1 1 1 3 3 （2）查找关键字63，H（k）=63 MOD 16=15，依次与31，46，47，32，17，63比较。 （3）查找关键字60，H（k）=60 MOD 16=12，散列地址12内为空，查找失败。 （4）ASLsucc=23/11

23．设用线性探测再散列解决冲突，根据公式Snl≈（1+1/（1-α）） /2 。可求出负载因子为α=0.67。再根据数据个数和装载因子，可求出表长m=15/0.67，取m=23。设哈希函数H（key）=（关键字首尾字母在字母表中序号之和）MOD 23。

从上表求出查找成功时的平均查找长度为ASLsucc=19/15<2.0，满足要求。 24．（1）哈希函数H（key）=（关键字各字符编码之和）MOD 7 （2）

散列地址 关键字 比较次数 0 be 1 1 cd 2 1 2 2 aa 1 3 3 ab 1 4 4 ac 1 5 5 ad 1 6 1 6 bd 1 7 2 7 bc 3 8 3 8 ae 3 9 4 9 ce 9 25．α=0.7，所以表长取m=7/0.7=10 散列地址 0 关键字 比较次数 6 SAT WED SUN MON TUE THU FRI 1 1 ASLsucc=18/7 ASLunsucc=32/10 26．（1）

散列地址 0 关键字 比较次数 3 1 1 2 3 4 5 6 1 7 1 8 9 1 2 10 11 12 27 53 2 31 19 20 8 18 1 1 （2）ASLsuss =11/8 27．（1）

散列地址 0 1 关键字 2 3 4 5 1 6 1 7 2 8 3 9 1 10 11 1 3 12 3 0 3 29 200 32 45 58 100 10 126 400 比较次数 1 1 2 关键字29和45各发生一次碰撞，关键字58,126和400各发生两次碰撞，其余关键字无碰撞。 （2）

散列地址 0 关键字 比较次数 1 1 1 2 2 3 4 1 3 5 1 6 3 7 8 9 10 2 11 12 1 58 10 100 3 200 32 400 0 45 126 29 8 1 发生碰撞次数：100，126一次；200，400两次；0七次。其余关键字无碰撞。

28．由α=0.75，得表长m=11/0.75=15

（1）散列函数H（k）=k MOD 13（p取小于等于表长的最大素数）

（2）因为p=13，散列地址取0到12，用链地址法解决冲突，实际长就取13。

（2）ASLsucc=18/11 （3）ASLunsucc=24/13

29．在B-树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。B+树的非终端结点是索引部分，其查找从根开始，从根往下查到关键字后，要继续查到最下层结点，得到查找成功与否的结论。另外，B+树还可以在最下层从最小关键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

30．m阶的B+树和B-树主要区别有三：（1）有n棵子树的结点中含有n（B-树中n-1）个关键字；（2）B+树叶子结点包含了全部关键字信息，及指向含关键字记录的指针，且叶子结点本身依关键字大小自小到大顺序链接；（3）B+树的非终端结点可以看成是索引部分，结点中只含其子树（根结点）中最大（或最小）关键字。B+树的查找既可以顺序查找，也可以随机查找，B-只能顺序查找。

31．本题等价于“含有n个关键字的m阶B-树的最大高度是多少”？一次检索中最多走一条从根到叶子的路径，由于根结点至少有两棵子树，其余每个（除叶子）结点至少有?m/2?

l-1

棵子树，则第三层至少有?m/2?*2个结点，第l+1层至少有2*?m/2?个结点。设B-树深度

l-1

为l+1，即第l+1层是叶子结点，叶子结点数是n+1（下面推导），故有n+1≥2*?m/2?，

即l≤log?m/2?（

）+1。

附：推导B-树中叶子结点数s与关键字数n的关系式：s=n+1

设B-树某结点的子树数为Ci，则该结点的关键字数Ni=Ci-1。对于有k个结点的B-树，有

∑Ni=∑(Ci-1)=∑Ci-k（1≤i≤k） ……（1）

因为B树上的关键字数，即∑Ni=n （1≤i≤k） ……（2）

而B-树上的子树数可这样计算：每个结点（除根结点）都是一棵子树，设叶子（子树）数为s；则

∑Ci=(k-1)+s （1≤i≤k） ……（3）

综合（1）（2）（3）式，有s=n+1。证毕。 32．表长m=12/0.6=20 （1）H（key）=key MOD 19

（2）两次碰撞。开地址线性探测法解决冲突，即是用拉链法解决冲突。见本章四第2题（2）③

第32题用拉链法解决冲突

33．由于地址空间为10，且从100开始，故散列函数选为H（key）=key%7+100。

散列地址 100 101 102 103 104 105 106 107 108 109 关键字 98 63 2 79 1 17 1 53 1 19 1 61 2 75 3 46 5 49 10 比较次数 1 用线性探测再散列解决冲突，ASLsucc=27/10

34．

35．

36．第一层有1个结点，第二层至少有2个结点，第三层有2*?m/2?个结点，第四层有2*?m/2?

h-2

个结点，……，第h层至少有2*?m/2?个结点（h≥2）。结点总数是

2h-2h-1

1+2+2*?m/2?+2*?m/2?+…+2*?m/2?=2*?m/2?-1

2

37． 38

.

39．

40．（该题答案不唯一。如删P时，亦可将双亲结点中M下来与N一起并入左兄弟成为（K L M N）

41．满二叉检索树可以看作是三阶B-树（2—3树）。B-树的插入和删除算法不适合满二叉检索树。满二叉检索树插入和删除结点后均破坏了“多路平衡查找树”“叶子在同一层上”（查找失败结点）的定义。 42．

43．B+树的查找可从根结点开始随机查找，也可以从最小关键字起顺序查找。

44．含9个叶子结点的3阶B-树至少有4个非叶子结点，当每个非叶子结点均含3棵子树，第三层是叶子结点时就是这种情况。当4层3阶B-树有10个叶子结点时，非叶子结点达到最大值8个，其中第一层一个，第二层两个，第三层五个非叶子结点。

45．在二叉排序树上查找关键字K，走了一条从根结点至多到叶子的路径，时间复杂度是O(logn)，而在中序遍历输出的序列中查找关键字K，时间复杂度是O（n）。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是（n+1）/2，时间复杂度也是O（n）。

46．按中序遍历序列将值1~9依次标上。

47．

ASLsucc=(1*1+2*2+4*3+4*4)/11=33/11

48.

ASLsucc=32/10

49. （2）10,12,15,20,24,28,30,35,46,50,55,68

（3）ASLsucc=41/12 50．

51．

52．序列（2）

不可能是二叉 排序树

中查到363的序列。查到501后，因363<501，后面应出现小于501的数，但序列中出现了623，故不可能。

53．（1）本题的本质是给定中序序列1、2、3、4，有几种不同的二叉排序树，也即该中序序列相当多少不同的前序序列，这是树的计数问题。设中序序列中元素数为n，则二叉数的

n

数目为1/（n+1）C2n，这里n=4，故有14种。图示如下：

73题（1）次优查找树 73题（2）调整后

的次优查找树

查找成功的平均查找长度是=1*0.25+2*(0.12+0.20)+3*(0.1+0.08+0.20)+4*0.05=2.23 由于在构造次优查找树的过程中，没有考查单个关键字的相应权值，可能出现根的关键字的权值比之相邻的关键字的权值小，这时要作调整：选邻近的权值较大的关键字作次优查找树的根结点。调整后的次优查找树如图73（2）。 74．

75．这里失败结点是不存在的结点，在其双亲结点处查找失败，这时的比较次数为Li-1。

76．

（1） 顺序查找判定树

（2）ASL顺序成功 =（1p1 +2p2+3p3+4p4+5p5)=0.97

ASL折半成功 =（1p3+2（p1+p4）+3（p2+p5)=1.04 ASL折半失败 =（2q0+3q1+3q2+2q3+3q4+3q5)=1.30 ASL顺序失败 =（1q0+2q1+3q2+4q3+5q4+5q5)=1.07 （3）本题中顺序检索好。

77．时间复杂度是判断检索方法的一个重要指标，但不是唯一指标。使用什么检索方法要综合考虑。哈希检索时间O（1），查找速度最快，但需构建哈希函数，进行计算哈希地址，查找时要有解决冲突的方法；二分检索时间O（log2n），需要元素有序且顺序存储，排序操作的时间开销大；顺时检索时间最差为O（n），但对检索表无要求，数据有序无序均可，在数据量较小时使用方便。

本文来源：https://www.bwwdw.com/article/fdvx.html