内容发布更新时间 : 2024/12/23 5:31:03星期一 下面是文章的全部内容请认真阅读。

12.在一棵B-树中，空指针数总是比关键字数多一个，此说法是否正确?请问包含8个关键字的3阶B-树(即2-3树)最多有几个结点?最少有几个结点?画出这两种情况的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-树的过程。

解：

(1)插入z后：

(2)插入v,o后

(3)插入 p,w,y后

16.为什么在内存中使用的B-树通常是3阶的，而不使用更高阶的B-树? 答：

因为查找等操作的cpu时间在B-树上是O(lgn·(m/lgt)),而m/lgt>1,所以m较大时它所费时间比平衡的二叉排序树上相应操作时间大得多，因此，仅在内存中使用的B-树通常取最小值3

17.为什么二叉排序树长高时，新结点总是一个叶子，而B-树长高时，新结点总是根?哪一种长高能保证树平衡? 答：

因为在二叉排序树中，关键字总是作为一个叶子结点插入以原来的树中，所以当树增高时，新结点总是一个叶子；而B-树中关键字插入总是插入到叶子结点内部，在叶结点中的关键字数目尚未超过它能够容纳的数目之前是不会增加结点的，当关键字数超过结点可容纳的数目时，叶结点就会发生分裂，产生一个新结点(但不一定引起树增高)，并且将其中的中间结点传至上一层，只有当这种分裂操作传递至根结点并引起根结点的分裂时，才能引起树高增加，此时产生一个新的根结点。所以说B树长高时，新结点总是根。 显然，后一种长高总能保证树的平衡。

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.试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么? 答：

(1)拉链法如下图：

T[0..10] ┌──┐

0│ │→ 33 → 22 →∧ ├──┤

1│ │→ 1 → 12 →34→ ∧ ├──┤

2│ │→ 13 →∧ ├──┤ 3│ ∧ │ ├──┤ 4│ ∧ │ ├──┤

5│ │→ 38 → 27 →∧ ├──┤ 6│ ∧ │ ├──┤ 7│ ∧ │ ├──┤ 8│ ∧ │ ├──┤ 9│ ∧ │