2022年索引技术 .pdf

《2022年索引技术 .pdf》由会员分享，可在线阅读，更多相关《2022年索引技术 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 9 章 索引技术课后习题讲解1. 填空题 在索引表中，每个索引项至少包含（）和（）等信息【解答】关键码，关键码对应的记录在存储器中的位置 在线性索引中，（）称为稠密索引【解答】若文件中的每个记录对应一个索引项 分块有序是指将文件划分为若干块，（）无序，（）有序。【解答】块内，块间 在分块查找方法中，首先查找（），然后查找相应的（）。【解答】索引表，块 在 10 阶 B树中根结点所包含的关键码个数最多为（），最少为（）。【解答】 9，1 【分析】 m 阶的 B树中每个结点至多有m 棵子树，若根结点不是终端结点，则至少有两棵子树，每个结点中关键码的个数为子树的个数减1。 一棵 5 阶 B树中，

2、除根结点外，每个结点的子树树目最少为（），最多为（）。【解答】 3，5 【分析】m 阶的 B树中每个结点至多有m 棵子树，除根结点之外的所有非终端结点至少有?m/2? 棵子树。 对于包含 n 个关键码的m 阶 B树，其最小高度是（），最大高度是（）。【解答】 logm(n+1)， logm/2(n+1)/2 在一棵 B树中删除关键码，若最终引起树根结点的合并，则新树比原树的高度（）。【解答】减少1 层 在一棵高度为h 的 B树中，叶子结点处于第（）层，当向该B树中插入一个新关键码时，为查找插入位置需读取（）个结点。【解答】 h+1 ，h 【分析】 B树的叶子结点可以看作是外部结点（即查找失败）

3、的结点，通常称为外结点。实际上这些结点不存在，指向这些结点的指针为空，B树将记录插入在终端结点中。 对于长度为n 的线性表，若采用分块查找（假定总块数和每块长度均接近，用顺序查找确定所在块），则时间复杂性为（）。【解答】 O() 2. 判断题 在索引顺序表上采用分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 【解答】对。分块查找的平均查

4、找长度不仅和文件中记录的个数n 有关，而且和每一块中的记录个数t 有关，当 t 取 时， ASL取最小值+1 。 B树是一种动态索引结构，它既适用于随机查找，也适用于顺序查找。【解答】错。 B树不能进行顺序查找。 对于 B树中任何一个非叶结点中的某个关键码k 来说，比 k 大的最小关键码和比k 小的最大关键码一定都在叶结点中。【解答】对。 在索引顺序表的查找中，对索引表既可以采取顺序查找，也可以采用折半查找。【解答】对。因为索引表有序。 m 阶 B树中每个结点的子树个数都大于或等于?m/2? 。【解答】错。 m 阶的 B树中除根结点之外的所有非终端结点至少有m/2 棵子树。若根结点不是终端结点

5、，则至少有两棵子树。 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)所示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 4对上题所示的3 阶 B树，分别给出删除关键码为

6、4，8，9 之后的结果。【解答】删除关键码为4，8，10 之后的结果如图9-4(a) ，(b) ，(c) 所示：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 5为什么在内存中使用的B树通常是 3 阶的，而不使用更高阶的B树？【解答】作为外存上的动态查找，B树比平衡二叉树的性能要好，但若要作为内存中的查找表，B树却不一定比平衡二叉树性能好，因为查找等操作的时间性能在m 阶 B树上是 O(mlogtn ） =O(log2n*(m/

7、log2t)（n 为记录个数） ， 而 m/log2t1， 故 m 较大时，O(mlog2n) 比平衡的二叉排序树上相应操作的时间O(log2n)大得多。因此，仅在内存中使用的B树必须取较小的m，通常取最小值m=3 。6设有 10000 个记录，通过分块划分为若干子表并建立索引，那么为了提高查找效率，每一个子表的大小应设计为多大？【解答】每个子表的大小应为。学习自测及答案1在索引顺序表中，首先查找（），然后再查找相应的（），其平均查找长度等于（）。【解答】索引表，块，查找索引表的平均长度与检索相应块的平均查找长度的和2既希望较快的查找又便于线性表动态变化的查找方法是（）。A 顺序查找B 折半查

8、找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树中，除根结点以外其他非叶子结点中的关键码个数不少于（）。【解答

9、】 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 【解答】 B 9. 给定一组记录，其关键码为字母。记录按照下面的顺序插入一棵空的B树中：C，S，D，T，A，M，P，I，B，

10、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 所示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -