的结点，通常称为外结点。实际上这些结点不存在，指向这些结点的指针为空，B－树将记录插入在终端结点中。
⑽ 对于长度为n的线性表，若采用分块查找（假定总块数和每块长度均接近，用顺序查找确定所在块），则时间复杂性为（ ）。 【解答】O() 2. 判断题
⑴ 在索引顺序表上采用分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。
【解答】对。分块查找的平均查找长度不仅和文件中记录的个数n有关，而且和每一块中的记录个数t有关，当t取时，ASL取最小值 +1。
⑵ B—树是一种动态索引结构，它既适用于随机查找，也适用于顺序查找。【解答】错。B—树不能进行顺序查找。
⑶ 对于B—树中任何一个非叶结点中的某个关键码k来说，比k大的最小关键码和比k小的最大关键码一定都在叶结点中。【解答】对。
⑷ 在索引顺序表的查找中，对索引表既可以采取顺序查找，也可以采用折半查找。 【解答】对。因为索引表有序。
⑸ m阶B—树中每个结点的子树个数都大于或等于m/2。【解答】错。m阶的B－树中除根结点之外的所有非终端结点至少有[m/2] 棵子树。若根结点不是终端结点，则至少有两棵子树。
⑹ m阶B—树中任何一个结点的左右子树的高度都相等。【解答】对。B树都是树高平衡的。 3．对图9-2所示的3阶B—树，分别给出插入关键码为2，12，16，17和18之后的结果。
【解答】插入关键码为2，12，16，17，18之后的结果分别如图9-3中(a)、(b)、(c)、(d)、(e)所示。
4．对上题所示的3阶B—树，分别给出删除关键码为4，8，9之后的结果。【解答】删除关键码为4，8，10之后的结果如图9-4(a)，(b)，(c)所示：
5．为什么在内存中使用的B—树通常是3阶的，而不使用更高阶的B—树 【解答】作为外存上的动态查找，B—树比平衡二叉树的性能要好，但若要作为内存中的查找表，B—树却不一定比平衡二叉树性能好，因为查找等操作的时间性能在m阶B—树上是O(mlogtn）=O(log2n*(m/log2t))（n为记录个数），而m/log2t>1，故m较大时，O(mlog2n)比平衡的二叉排序树上相应操作的时间O(log2n)大得多。因此，仅在内存中使用的B—树必须取较小的m，通常取最小值m=3。
6．设有10000个记录，通过分块划分为若干子表并建立索引，那么为了提高查找效率，每一个子表的大小应设计为多大 【解答】每个子表的大小应为 。 学习自测及答案
1．在索引顺序表中，首先查找（ ），然后再查找相应的（ ），其平均查找长度等于（ ）。 【解答】索引表，块，查找索引表的平均长度与检索相应块的平均查找长度的和
2．既希望较快的查找又便于线性表动态变化的查找方法是（ ）。 A 顺序查找 B折半查找 C散列查找 D 索引顺序查找【解答】D
3．在一个3阶的B—树上，每个结点所含的子树数目最多为（ ）。 【解答】3
4．在一棵m阶的B—树中，当将一个关键码插入某结点而引起该结点分裂时，此结点原有（ ）个关键码；若删去某结点中的一个关键码，而导致结点合并时，该结点原有（ ）个关键码。 【解答】m-1， m/2 -1 5．当向B—树中插入关键码时，可能引起结点的（ ），最终可能导致整个B-树的高度（ ），当从B—树中删除关键码时，可能引起结点（ ），最终可能导致整个B—树的高度（ ）。 【解答】分裂，增加1，合并，减少1
6．在9阶B—树中，除根结点以外其他非叶子结点中的关键码个数不少于（ ）。 【解答】4
7．当向一棵m阶的B—树做插入操作时，若一个结点中的关键字个数等于（ ），则必须分裂为两个结点。A m B m-1 C m+1 D m/2 【解答】A
8．在一个5阶的B—树上，每个非终端结点所含的子树数最少为（ ）。 A 2 B 3 C 4 D 5
【解答】B 9. 给定一组记录，其关键码为字母。记录按照下面的顺序插入一棵空的B—树中：C，S，D，T，A，M，P，I，B，W，N，G，V，R，K，E，H，O，L，J。请画出插入这些记录后的3阶B—树。【解答】最后的B—树如图9-5所示。
10．已知一个B+树有5个叶子结点，每个叶子结点中的关键码如图9-6所示，请画出这棵3阶B+树，然后在此3阶B+树中插入关键码65，再画出插入后的B+树。
【解答】该B+树如图9-7所示，插入关键码65后，B+树如图9-8所示。
__
注意：本网站的文档来源于网上。仅供学习使用。请勿用于其他用途。
有图片版请到下面连接下载（pdf）：