思凯学习俱乐部
表，并指出查找各关键字要进行几次比较。【西安电子科技大学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）中国在职研究生网 www.zzyjs.com
思凯学习俱乐部
方法将它们存入具有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分）】 中国在职研究生网 www.zzyjs.com
思凯学习俱乐部
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
50308 2035 406080100 38. 已知2棵2-3 B-树如下（省略外结点）：【吉林大学 1999 一、4 (4分)】
（1） 对树（a）,请分别画出先后插入26，85两个新结点后的树
形； （2） 对树（b）,请分别画出先后删除53，37两个结点后的树形。
中国在职研究生网 www.zzyjs.com
思凯学习俱乐部
452430 375053 9010031261 70 (a) 45243375361 9070100 （b） 39. 四阶B树中（如图所示），插入关键字87，试画出插入调整后树的形状【东南大学 1999 五 （15分）】 30 60 80
20 35 25 50 60 70 82 85 90 75
40. 下图是5阶B树 ，画出删去P后的B树，再画出删去D后的B树。【厦门大学 2000 二、2 （20/3分）】
41. 满二叉检索树符合B树定义吗？B树的插入和删除算法适用于满二叉检索树吗？为何？【东南大学 1995 五 （6分）】
中国在职研究生网
www.zzyjs.com
思凯学习俱乐部
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) 假定每个元素的查找概率相等，试计算该二叉排序树的平均中国在职研究生网 www.zzyjs.com