点?画出这两种情况的B-树。 答：这个说法是正确的。
包含8个关键字的3阶B-树最多有7个结点，最少有4个结点。
见题图。:图如下：
13.从空树开始，依次输入20，30，50，52，60，68，70，画出建立2-3树的过程。并画出删除50和68后的B-树状态。
答：过程如下：
(1) 插入20，30： (2) 插入50： (3) 插入52： (4) 插入60： (5) 插入68： (6) 插入70： (7)删去50： (8) 删去68
14。画出依次插入z,v,o,p,w,y到图9.12(h)所示的5阶B-树的过程。
答：如图：第一步，插入z: 第二、三步,插入v,o： 第四五六步，插入p,w,y:
15. 在含有n个关键字的m阶B-树中进行查找，至多读盘多少次?完全平衡的二叉排序树的读盘次数大约比它大多少倍?
答：在含有n个关键字的m阶B-树中进行查找至多读盘次数不超过B-树高h，即logt((n+1)/2)+1
,(注，此处t为底，值是除根外的每个内部结点的最小度数┌m/2┐).
完全平衡的二叉树高为lgn,所以它的读盘次数至多也是lgn，它与上述B-树的读盘次数的比值约为lgt倍(此处底是2).
16.为什么在内存中使用的B-树通常是3阶的，而不使用更高阶的B-树?
答：因为查找等操作的cpu时间在B-树上是O(lgn?(m/lgt)),而m/lgt>1,所以m较大时它所费时间比平衡的二叉排序树上相应操作时间大得多，因
此，仅在内存中使用的B-树通常取最小值3.
17.为什么二叉排序树长高时，新结点总是一个叶子，而B-树长高时，新结点总是根?哪一种长高能保证树平衡?
答：因为在二叉排序树中，关键字总是作为一个叶子结点插入以原来的树中，所以当树增高时，新结点总是一个叶子；而B-树中关键字插入总是插入到叶子结点内部，在叶结点中的关键字数目尚未超过它能够容纳的数目之前是不会增加结点的，当关键字数超过结点可容纳的数目时，叶结点就会发生分裂，产生一个新结点(但不一定引起树增高)，并且将其中的中间结点传至上一层，只有当这种分裂操作传递至根结点并引起根结点的分裂
时，才能引起树高增加，此时产生一个新的根结点。所以说B树长高时，新结点总是根。
显然，后一种长高总能保证树的平衡。
18.已知关键字序列为(PAL,LAP,PAM,MAP,PAT,PET,SET,SAT,TAT,BAT)试为它们设计一个散列函数，将其映射到区间[0..n-1]上，要求碰撞尽可能的
少。这里n=11,13,17,19.
解：我的设计的散列函数是这样的，把关键字串中的每一个字符按其所在位置分别将其ASCII值乘以一个不同的数，然后把这些值相加的和去对n
求余，余数即为散列表中的位置。函数如下：
int Hash (char key[])
{
return (int)(key[0]+key[1]*0.618+key[2]*10)%n;
}
我们可以设计一个程序来看看用这个散列函数得到的所有关键字映射到区间的位置：
#include
#define n 11 file://先用11来代入，我们可以用13，17，19依次代入验证
int Hash (char key[])
{
return (int)(key[0]+key[1]*0.618+key[2]*10)%n;
file://此处我用了系数1，0.618和10，你也可以用其他的数代入看有没有更好的系数
} void main()
{ char
s[10][4]={\
// 以上用一个二维数组来存放关键字序列
int i; for(i=0; i<10;i++)
{
printf(\)); } } 19.对于一组给定的、固定不变的关键字序列，有可能设计出无冲突的散列函数H，此时称H为完备的散列函数(perfect hashing function)，若H能无冲突地将关键字完全填满散列表，则称H是最小完备(minimal perfect)的散列函数。通常找完备的散列函数非常困难，找最小完备的散列函数就更困难。请问： (1)若h是已知关键字集合K的完备的散列函数，若要增加一个新的关键字到集合K，一般情况下H还是完备的吗? (2)已知关键字集合为(81，129，301，38，434，216，412，487，234)，散列函数为H(x)=(x+18)/63,请问H是完备的吗?它是最小完备的吗? (3)考虑由字符串构成的关键字集合(Bret,Jane,Shirley,Bryce,Michelle,Heather)，试为散列表[0..6]设计一个完备的散列函数。(提示：考虑每个字符串的第3个字符，即s[2]) 答：(1) 一般情况下H不是完备的，如果说插入一个新的关键字它还是完备的，那么再插入一个呢?它岂不是永远是完备的散列函数了? 所以一般情况下它不能总是完备的，只有一些很少的情况下它还可能是完备的。 (2)这个H是完备的，其函数值依次为：1，2，5，0，7，3，6，8，4。如果散列表长m=9时，它就是最小完备的。 (3) 这个函数如下： int Hash (char key[]) { return key[2]%7;} 20.设散列函数为h(key)=key1,解决冲突的方法为线性探查，表中用\表示空单元。若删去散列表HT中的304(即令HT[1]=-1)之后，在表HT中查找707将会发生什么?若将删去的表项标记为\查找时探查到-2继续向前搜索，探查到-1时终止搜索。请问用这种方法删304后能否正确地查找到707? 0 1 2 3 100 ┌──┬──┬──┬──┬─┬─┬─┬─┬─┬─┬─┐ HT │202 │304 │507 │707 │ ... ... │ └──┴──┴──┴──┴─┴─┴─┴─┴─┴─┴─┘ 答：查找707时，首先根据散列函数计算得出该元素应在散列表中的0单元，但是在0单元没有找到，因此将向下一单元探查，结果发现该单元是-1(为空单元)，所以结束查找，这将导致707无法找到。 如果改用\作为删除标记，则可以正确找到707所在的结点。 21.设散列表长度为11，散列函数h(x)=x,给定的关键字序列为：1，13，13，34，38，33，27，22.试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两咱方法查找成功和失败时的平均查找长度。请问装填因子的值是什么? 答：拉链法如下图：(后面的框框就不画了) T[0..10] ┌──┐ 0│ │→ 33 → 22 ∧ ├──┤ 1│ │→ 1 → 12 →34 ∧ ├──┤ 2│ │→ 13 ∧ ├──┤ 3│ ∧ │ ├──┤ 4│ ∧ │ ├──┤ 5│ │→ 38 → 27 ∧ ├──┤ 6│ ∧ │ ├──┤ 7│ ∧ │ ├──┤ 8│ ∧ │ ├──┤ 9│ ∧ │ ├──┤ 10│ ∧ │ └──┘ 线性探查法如下图： 下标 0 1 2 3 4 5 6 7 8 9 10 ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ T[0..10]│33│1 │13│12│34│38│27│22│ │ │ │ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ 探查次数 1 1 1 3 4 1 7 8 用拉链法的查找成功平均查找长度为： ASLscuu=(1*4+2*3+3*1)/8=1.625 查找失败时平均查找长度为： ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.73 用线性探查法查找成功时平均查找长度为： ASLsucc=(1+1+1+3+4+1+7+8)/8=3.25 查找失败时平均查找长度为： ASLunsucc=(9+8+7+6+5+4+3+2+1+1+1)/11=4.3 装填因子α拉链=4/11=0.36 α线性探查=8/11=0.73 22.假定有k个关键字互为同义词，若用线性探查法把这些同义词存入散列表中，至少要进行多少次探查? 答：至少要进行1+2+3...+k-1+k次探查。 也就是说，在散列表的一连串连续空间内，第一个关键字只需探查一次，第二个就要探查2次，如此这般，第k个关键字就要探查k次才能找到位置存放。所以至少要把它们全加起来才够。 23.为什么说当装填因子非常接近1时，线性探查类似于顺序查找?为什么说当装填因子比较小(比如α=0.7左右)时，散列查找的平均查找时间为O(1)? 答：当α非常接近1时，整个散列表几乎被装满。由于线性探查法在关键字同义时解决冲突的办法是线性地向后查找，当整个表几乎装满时，它就很类似于顺序查找了。 当α比较小时，关键字碰撞的几率比较小，一般情况下只要按照散列函数计算出的结果能够1次性就找到相应结点，因此它的平均查找时间接近于1.