课程课件作业空chapter9.pdfVIP

1.在二叉排序树中，凡是新的点，都是没有

_____的。

A.孩子B.关键字

C.平衡因子D.赋值

2.有一个长度为12的有序表，按折半查找法对该

表进行查找，在表内各元素等概率情况下，查

找成功所需的平均比较次数为_____。

A.35/12B.37/12

C.39/12D.43/12

1

3.如下图所示的一棵二叉排序树，其不成功的平

均查找长度是_____。

A.21/7B.28/7

C.15/6D.21/6

4.采用分块查找时，若线性表有625个元素，

查找每个元素的概率相同，假设采用顺序查找来

确定结点所在的块，则每块分为_____个结点最

佳。

A.9B.25

C.6D.625

(提示：p.226，若用顺序查找确定所在的块，容易证明，

当s取n1/2时，ASLbs取最小值n1/2+1）

3

5.具有5层结点的AVL树，至少有个结点。

A.10B.12

C.15D.17

6.下面关于B-树和B+树的叙述中，不正确的结论是

______。

A.B-树和B+树都能有效地支持顺序查找

B.B-树和B+树都能有效地支持随机查找

C.B-树和B+树都是平衡的多路查找树

D.B-树和B+树都可以用于文件索引结构

4

7.设哈希表长m=12，哈希函数H(key)=keyMOD11。

表中已有4个结点，addr(15)=4,，addr(38)=5，

addr(61)=6，addr(84)=7，其余地址为空，如用二次

探测再散列法处理，则关键字为49的结点的地

址是_____。

A.8B.3

C.5D.9

5

8.判断以下叙述的正确性。

1)一个10阶的B-树上，除根以外每个非终端结点中所含

关键字的数目最多允许为9个，最少允许为5个。()

2)在哈希中，装填因子α越大，则存取元素时发生

的可能性越大；α越小，则存取元素时发生

的可能性越小。(