38. 假设root是一棵给定的非空查找树，对于下面给出的子程序，当执行注释中给出的调用语句时，就可以实现如下的操作：在非空查找树root中查找值为k 的结点；若值为k的结点在树中，且是一个叶子结点，则删除此叶子结点，同时置success 为“真”；若值为k的结点不在树中，或者虽然在树中，但不是叶子结点，则不进行删除，仅置success为“假”。应注意到非空查找树只包含一个结点情况，此时树中的唯一结点，既是根结点，也是叶子结点。
#include
struct node *left， *right; } node;
node *root; int k，success;
void del_leaf(node **t, int k, int *sn) { node *p, *pf; p=*t; *sn=0; while(_（1）_&&!*sn) if (k==p->key) *sn =1;
else { _（2）_;
if (k
if (*sn && p->left==NULL && p->right==null)
{ if (_（3）_ )
if (pf->left ==p ) pf ->left=null; else pf->right=null; else _（4）_ ; free(p); } else *sn=0;
/*call form :del_leaf( &root, k, &success);*/ 【上海大学 1999 一、2 （8分）】 四、应用题 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}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。 【合肥工业大学 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 （5分）】 （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两个结点后的树形。
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 二、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） （2）
按次序构造一棵二叉排序树BS。(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 63. 若以序列 {Thu,Tue,Wed,Last,Fri,Sat,Mon,Sun,Next} 作为输入序列
(1) 按算法AVL-INSERT构造均高树，画出构造过程和进行平衡转换的类型。
(2) 若均高树中有n个结点，其高度为h，指出在最坏情况下，对该树的插入、删除和依次输出操作的时间复杂性。
· - 70