12. 使用散列函数hashf(x)=x mod 11,把一个整数值转换成散列表下标，现要把数据：1,13,12,34,38,33,27,22插入到散列表中。 （1）使用线性探查再散列法来构造散列表。（2）使用链地址法构造散列表。
针对这两种情况，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。
13. 已知长度为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表在等概率查找情况下，查找成功的平均查找长度。
14. 设散列函数H(k)=K mod 7,散列表的地址空间为0-6，对关键字序列
{32,13,49,18,22,38,21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。
15. 选取哈希函数Ｈ（key）=key mod 7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。
16. 设散列函数为H(K)=K MOD 11,解决冲突的方法为链接法，试将下列关键字集合{35,67,42,21,29,86,95,47,50,36,91}依次插入到散列表中（画出散列表的示意图）。并计算平均查找长度ASL。
17. 设输入的关键字序列为：22,41,53,33,46,30,13,01,67, Hash函数为：H（key）=key MOD 11。HASH表长度为11。试用线性探测法解决冲突，将各关键字按输入顺序填入Hash表中。 18. 设哈希(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) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
19. 试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过
2.0。并请验证你造的哈希表的实际平均查找长度是否满足要求。
（CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,WANG,CAO,YUN,CHANG,YANG）
20. 设a,b,c,d,e五个字符的编码分别为1,2,3,4,5，并设标识符依以下次序出现：
ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（Hash）方法将它们存入具有10个位置的表中。
（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；（2）线性探测再散列法解决冲突。
写出上述各关键字在表中位置。
21. 对以下关键字序列建立哈希表：(SUN,MON,TUE,WED,THU,FRI,SAT)，哈希函数为H（K）=（关键字中第一个字母在字母表中的序号）MOD 7，用线性探测法处理冲突，求构造一个装填因子为0.7的哈希表;并分别计算出在等概率情况下查找成功与不成功的平均查找长度。 22. 设散列表为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个关键码后的散列表；(2)计算搜索成功的平均搜索长度ASL。 23. 设一个散列表含hashsize=13个表项，其下标从0到12，采用线性探查法解决冲突。请按以下要求，将关键码{10,100,32,45,58,126,3,29,200,400,0}散列到表中。
（1）散列函数采用除留余数法，用%hashsize（取余运算）将各关键码映像到表中，请指出每一个产生冲突的关键码可能产生多少次冲突。
（2）散列函数采用先将关键码各位数字折叠相加，再用%hashsize将相加的结果映像到表中的办法。请指出每一个产生冲突的关键字码可能产生多少次冲突。
24. 已知一组关键字为（26,36,41,38,44,15,68,12,06,51,25），用链地址法解决冲突。假
设装填因子a=0.75，散列函数的形式为H（K）=K MOD P，回答下列问题： （1） 构造出散列函数；（2）计算出等概率情况下查找成功的平均查找长度；） （3） 计算出等概率情况下查找失败的平均查找长度； 25. 在B-树和B+树中查找关键字时，有什么不同？ 26. 简要叙述B树(有些教材中称为B-树)与B+树的区别?
27. 包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？（要求写出推导过程。） 28. 给定关键码序列（26,25,20,33,21,24,45,204,42,38,29,31），要用散列法进行存储，规定负载因子α=0.6。
（1）请给出除余法的散列函数。
（2）用开地址线性探测法解决碰撞，请画出插入所有的关键码后得到的散列表，并指出发生碰撞的次数。
29. 已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突用开型寻址法的线性探测法解决。要求写出选用的散列函数；形成的散列表；计算出查找成功时平均查找长度与查找不成功的平均查找长度。（设等概率情况） 30.高度为h的m阶B树至少有多少个结点？
31. 满二叉检索树符合B树定义吗？B树的插入和删除算法适用于满二叉检索树吗？为何？ 32. 在一棵B+树上一般可进行那两种方式的查找运算? 44. 含9个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？ 33. 直接在二叉排序树中查找关键字K与在中序遍历输出的有序序列中查找关键字K，其效率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后对此树进行查找，其效率如何？为什么？
34. 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。 35. 用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度.
36. 依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树
(1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列;
(3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。
37. 用关键字1,2,3,4的四个结点（1）能构造出几种不同的二叉排序树？其中（2）最优查找树有几种？（3）AVL树有几种？(4)完全二叉树有几种？试画出这些二叉排序树。
类似本题的另外叙述有：
(1)设有关键字A、B、C和D，依照不同的输入顺序，共可能组成多少不同的二叉排序树。请画出其中高度较小的6种。
38. 一棵具有m层的AVL树至少有多少个结点，最多有多少个结点？
39. 设T是一棵高度平衡树(又称平衡树)，给定关键词K，如果在T中查找K失败，且查找路径上的任一结点的平衡系数皆为零，试回答用高度平衡树插入算法在T中插入关键词为K的新结点后，树T的高度是否一定增加?并回答为什么。
40. 在数轴上有N个彼此相临不交的区间，每个区间下界上界都是整数。N个区间顺序为
1-N。要查找给定的X落入的区间号，您认为应怎样组织数据结构，选择什么方法最快，简述原因。
41. 有一个长度为12的有序表，按对半查找法对该表进行查找，在表内各元素等概率情况
下，查找成功所需的平均比较次数是多少？
42. 若对一个线性表进行折半查找，该线性表应满足什么条件？ 43. 长度为255的有序表采用分块查找，块的大小应取多少？
44. 用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查找长度是多少？
45. 设有n个值不同的元素存于顺序结构中，试问：你能否用比（2n-3）少的比较次数选出这n个元素中的最大值和最小值？若能，请说明是如何实现的；在最坏情况下，至少要进行多少次比较。
46. 对有14个元素的有序表A[1?14]作折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有哪几个？
47. 设有五个数据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。
(1) 试画出对该有序表采用顺序查找时的判定树和采用折半查找时的判定树。
(2) 分别计算顺序查找时的查找成功和不成功的平均查找长度，以及折半查找时的查找成功和不成功的平均查找长度。
(3) 判定是顺序查找好？还是折半查找好？
48. 顺序检索，二分检索，哈希（散列）检索的时间分别为O(n),O(log2n),O(1)。既然有了高效的检索方法，为什么低效的方法还不放弃？
五、算法设计题
1．请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。
类似本题的另外叙述有：
（1）试写一个判别给定二叉树是否为二叉排序树的算法。
（2）某二叉树采用链接存储，其结点结构是：（lc,data,rc）。 lc和rc分别是指向左子树根和右子树根的指针域。data为结点数据域。试写出判断该二叉树是否为二叉排序树的算法（不许另设空间，但可以设一些辅助指针）。设二叉排序树左子树每个结点值<根结点值，右子树每个结点的值≥根结点的值。二叉树是递归定义的。按此定义写出判断某二叉树是否为二叉排序树的算法。
(3) 编写判定给定的二叉树是否是二叉排序树的函数。
2．某个任务的数据模型可以抽象为给定的K个集合：S1，S2，?，Sk。其中Si(1<=i<=k)中的元素个数不定。在处理数据过程中将会涉及到元素的查找和新元素的插入两种操作，查找和插入时用一个二元组（i,x）来规定一个元素，i是集合的序号，x是元素值。设计一种恰当的数据结构来存储这k个集合的元素，并能高效的实现所要求的查找和插入操作。
（1）借助Pascal的数据类型来构造和描述你所选定的数据结构，并且说明选择的理由；
（2）若一组数据模型为S1={10.2, 1.7, 4.8, 16.2 }, S2={1.7, 8.4, 0.5 }, S3={4.8, 4.2,
3.6, 2.7, 5.1, 3.9 }, 待插入的元素二元组为(2, 11.2 )和(1, 5.3 ), 按你的设计思想画出插入元素前后的数据结构状态。
3. 写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。用类PASCAL（或C）语言将上述算法写为过程形式。
4. 已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p为fp的左孩子，试编写算法，删除p所指结点。
5．二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。
6. 设记录R1,R2,?,Rn按关键字值从小到大顺序存储在数组r[1..n]中,在r[n+1]处设立一个监督哨,其关键字值为+∞; 试写一查找给定关键字k 的算法;并画出此查找过程的判定树,求出在等概率情况下查找成功时的平均查找长度。
7．试编写算法，在根结点指针为t的m-阶B树上查找关键字k,返回记录(pt,i,tag).若查找成功，则特征位tag=1,等于k的关键字即为指针pt所指结点中的第i个关键字；若查找不成功，则特征位tag=0，等于k的关键字应插入到指针pt所指结点中第i个和第i+1个关键字之间。简化B-树存储结构如下所示：
type mblink=↑mbnode mbnode=record keynum:integer; parent:mblink;
key:array[1..m] of keytp {关键字} ptr:array [0..m] of mblink end;
result=record pt:mblink; i:integer; tag:(0..1) end;
（注：所用语言C, PASCAL等都可使用编制算法。若算法不用类PASCAL描述，要给出相应语言的结构描述。题目中给出的结构说明可供参考，也可自行给出）
8. 元素集合已存入整型数组A[1..n]中，试写出依次取A中各值A[i](1<=i<=n)构造一棵二叉排序树T的非递归算法：CSBT(T,A)