数据结构错题收录（二十）

2022-12-05  本文已影响0人  程序员丶星霖

1、含有n个非叶结点的m阶B树中至少包含（）个关键字。

解析

除根结点外，m阶B树中的每个非叶结点至少有\ulcornerm/2\urcorner-1个关键字，根结点至少有一个关键字，所以总共包含的关键字最少个数=(n-1)(\ulcornerm/2\urcorner-1)+1。

答案：D

2、已知一棵5阶B树中共有53个关键字，则树的最大高度为（），最小高度为（）。

解析

5阶B树中共有53个关键字，由最大高度公式H\leq$$\log_{\ulcorner{m/2}\urcorner}((n+1)/2)+1得最大高度H\leq$$\log_3[(53+1)/2]+1=4，即最大高度为4；由最小高度公式h\geq$$\log_m(n+1)得最小高度h\geq$$\log_554=2.5，从而最小高度为3。

答案：C。B

3、已知一棵3阶B树中有2047个关键字，则此B树的最大高度为（），最小高度为（）。

解析

利用最小高度h\geq$$\log_m(n+1)和最大高度H\leq$$\log_{\ulcorner{m/2}\urcorner}((n+1)/2)+1的公式。可以算出最大高度H\leq$$\log_2[(2047+1)/2]+1=11，最小高度h\geq$$\log_3 2048=6.9，从而最小高度取7。

答案：A。D

4、下列关于B树和B+树的叙述中，不正确的是（）。

解析

B树和B+树的差异主要体现在：1.结点关键字和子树的个数；2.B+树非叶结点仅起索引作用；3.B树叶结点关键字和其他结点包含的关键字是不重复的；4.B+树支持顺序查找和随机查找。而B树仅支持随机查找。

由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找。

答案：A

5、在一棵高度为2的5阶B树中，所含关键字的个数至少是（）。

解析
答案：A

6、在一棵有15个关键字的4阶B树中，含关键字的结点的个数最多是（）。

解析

关键字数量不变，要求结点数量最多，即要求每个结点中含关键字的数量最少。根据4阶B树的定义，根结点最少含1个关键字，非根结点中最少含\ulcorner{4/2}\urcorner-1=1个关键字，所以每个结点中关键字数量最少都为1个，即每个结点都有2个分支，类似于排序二叉树，而15个结点正好可以构造一个4层的4阶B树，使得终端结点全在第四层，符合B树的定义，因此选D。

答案：D

7、B+树不同于B树的特点之一是（）。

解析

由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找（只支持多路查找）。

答案：A

8、高度为5的3阶B树含有的关键字个数至少是（）。

解析

m阶B树的基本性质：根结点以外的非叶结点最少含有\ulcorner{m/2}\urcorner-1个关键字，代入m=3得到每个非叶结点中最少包含1个关键字，而根结点含有1个关键字，因此所有非叶结点都有两个孩子。此时其树形与h=5的满二叉树相同，可求得关键字最少为31个。

答案：B

9、依次将关键字5，6，9，13，8，2，12，15插入初始为空的4阶B树后，根结点包含的关键字是（）。

解析

一个4阶B树的任意非叶结点至多含有m-1=3个关键字，在关键字依次插入的过程中，会导致结点的不断分裂，插入过程如下所示。

请添加图片描述

得到根结点包含的关键字为6，9。

答案：B

10、下列关于散列表的说法中，正确的是（）。

Ⅰ、若散列表的填装因子\alpha<1，则可避免碰撞的产生
Ⅱ、散列查找中不需要任何关键字的比较
Ⅲ、散列表在查找成功时平均查找长度与表长有关
Ⅳ、若在散列表中删除一个元素，不能简单地将该元素删除

解析
答案：D
上一篇下一篇

猜你喜欢

热点阅读