《数据结构习题索引技术》由会员分享，可在线阅读，更多相关《数据结构习题索引技术（9页珍藏版）》请在金锄头文库上搜索。
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. 判断题 在索引顺序表上采用分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。【解答】对。分块查找的平均查找长度不仅和文件中记录的个数n有关，而且和每一块中的记录个数t有关，当t取 时，ASL取最小值 +1。 B树是一种动态索引结构，它既适用于随机查找，也适用于顺序查找。【解答】错。B树不能进行顺序查找。 对于B树中任何一个非叶结点中的某个关键码k
4、来说，比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
5、)、(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/log2t1，故m较大时，O (mlog2n)比平衡的二叉排序树上相应操作的时间O(log2n)大得多。因此，仅在内存中使用的B树必须
6、取较小的m，通常取最小值m=3。6设有10000个记录，通过分块划分为若干子表并建立索引，那么为了提高查找效率，每一个子表的大小应设计为多大？【解答】每个子表的大小应为 。学习自测及答案1在索引顺序表中，首先查找（ ），然后再查找相应的（ ），其平均查找长度等于（ ）。【解答】索引表，块，查找索引表的平均长度与检索相应块的平均查找长度的和2既希望较快的查找又便于线性表动态变化的查找方法是（ ）。A 顺序查找 B折半查找 C散列查找 D 索引顺序查找【解答】D3在一个3阶的B树上，每个结点所含的子树数目最多为（ ）。【解答】34在一棵m阶的B树中，当将一个关键码插入某结点而引起该结点分裂时，此结
7、点原有（ ）个关键码；若删去某结点中的一个关键码，而导致结点合并时，该结点原有（ ）个关键码。【解答】m-1， ?m/2? -15当向B树中插入关键码时，可能引起结点的（ ），最终可能导致整个B-树的高度（ ），当从B树中删除关键码时，可能引起结点（ ），最终可能导致整个B树的高度（ ）。【解答】分裂，增加1，合并，减少16在9阶B树中，除根结点以外其他非叶子结点中的关键码个数不少于（ ）。【解答】47当向一棵m阶的B树做插入操作时，若一个结点中的关键字个数等于（ ），则必须分裂为两个结点。A m B m-1 C m+1 D m/2 【解答】A8在一个5阶的B树上，每个非终端结点所含的子树数最少为（ ）。A 2 B 3 C 4 D 5【解答】B9. 给定一组记录，其关键码为字母。记录按照下面的顺序插入一棵空的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所示。 / 文档可自由编辑打印
