(全)数据结构考试内部题库含答案解析2023.docx

数据结构考试内部题库含答案解析（全考点）1、含有n个非叶结点的m阶B树中至少包含（）个关键字· • A：n(m+1)· • B：n· • C：n()· • D：(n-1)()+1解析除根结点外，m阶B树中的每个非叶结点至少有个关键字，根结点至少有一个关键字，所以总共包含的关键字最少个数=(n-1)()+1答案：D2、已知一棵5阶B树中共有53个关键字，则树的最大高度为（），最小高度为（）· • A：2· • B：3· • C：4· • D：5解析5阶B树中共有53个关键字，由最大高度公式H得最大高度=4，即最大高度为4；由最小高度公式得最小高度=2.5，从而最小高度为3答案：CB3、已知一棵3阶B树中有2047个关键字，则此B树的最大高度为（），最小高度为（）· • A：11· • B：10· • C：8· • D：7解析利用最小高度和最大高度的公式可以算出最大高度，最小高度，从而最小高度取7答案：AD4、下列关于B树和B+树的叙述中，不正确的是（）· • A：B树和B+树都能有效地支持顺序查找· • B：B树和B+树都能有效地支持随机查找· • C：B树和B+树都是平衡的多叉树· • D：B树和B+树都可以用于文件索引结构解析B树和B+树的差异主要体现在：1.结点关键字和子树的个数；2.B+树非叶结点仅起索引作用；3.B树叶结点关键字和其他结点包含的关键字是不重复的；4.B+树支持顺序查找和随机查找。

而B树仅支持随机查找由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找答案：A5、在一棵高度为2的5阶B树中，所含关键字的个数至少是（）· • A：5· • B：7· • C：8· • D：14解析答案：A6、在一棵有15个关键字的4阶B树中，含关键字的结点的个数最多是（）· • A：5· • B：6· • C：10· • D：15解析关键字数量不变，要求结点数量最多，即要求每个结点中含关键字的数量最少根据4阶B树的定义，根结点最少含1个关键字，非根结点中最少含个关键字，所以每个结点中关键字数量最少都为1个，即每个结点都有2个分支，类似于排序二叉树，而15个结点正好可以构造一个4层的4阶B树，使得终端结点全在第四层，符合B树的定义，因此选D答案：D7、B+树不同于B树的特点之一是（）· • A：能支持顺序查找· • B：节点中含有关键字· • C：根结点至少有两个分支· • D：所有叶结点都在同一层上解析由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找（只支持多路查找）。

答案：A8、高度为5的3阶B树含有的关键字个数至少是（）· • A：15· • B：31· • C：62· • D：242解析m阶B树的基本性质：根结点以外的非叶结点最少含有个关键字，代入m=3得到每个非叶结点中最少包含1个关键字，而根结点含有1个关键字，因此所有非叶结点都有两个孩子此时其树形与h=5的满二叉树相同，可求得关键字最少为31个答案：B9、依次将关键字5，6，9，13，8，2，12，15插入初始为空的4阶B树后，根结点包含的关键字是（）· • A：8· • B：6，9· • C：8，13· • D：9，12解析一个4阶B树的任意非叶结点至多含有m-1=3个关键字，在关键字依次插入的过程中，会导致结点的不断分裂，插入过程如下所示请添加图片描述得到根结点包含的关键字为6，9答案：B10、下列关于散列表的说法中，正确的是（）Ⅰ、若散列表的填装因子，则可避免碰撞的产生 Ⅱ、散列查找中不需要任何关键字的比较 Ⅲ、散列表在查找成功时平均查找长度与表长有关 Ⅳ、若在散列表中删除一个元素，不能简单地将该元素删除· • A：Ⅰ和Ⅳ· • B：Ⅱ和Ⅲ· • C：Ⅲ· • D：Ⅳ解析· • 冲突（碰撞）是不可避免的，与装填因子无关，因此需要设计处理冲突的方法，Ⅰ错误。

· • 散列查找的思想是计算出散列地址来进行查找，然后比较关键字以确定是否查找成功，Ⅱ错误· • 散列查找成功的平均查找长度与装填因子有关，与表长无关，Ⅲ错误· • 在开放地址的情形下，不能随便删除散列表中的某个元素，否则可能会导致搜索路径被中断（因此通常的做法是在要删除的地方做删除标记，而不是直接删除），Ⅳ正确答案：D1、在下图所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（）· • A：13,48· • B：24,48· • C：24,53· • D：24,90解析插入48后，该二叉树根结点的平衡因子由-1变为-2，失去平衡，需要进行两次旋转（先右旋后左旋）操作答案：C2、若平衡二叉树的高度为6，且所有非叶子结点的平衡因子均为1，则该平衡二叉树的结点总数为（）· • A：12· • B：20· • C：32· • D：33解析所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况，如下图所示对于高度为n、左右子树的高度分别为n-1和n-2、所有非叶结点的平衡因子均为1的平衡二叉树，计算总结点数的公式为=++1，=1，=2,=2+1+1=4，可推出=20。

画图法：先画出和；然后新建一个根结点，连接、构成；新建一个根结点，连接、构成......直到画出，可知的结点数为20答案：B3、若将关键字1,2,3,4,5,6,7依次插入初始为空的平衡二叉树T，则T中平衡因子为0的分支结点的个数是（）· • A：0· • B：1· • C：2· • D：3解析利用7个关键字构建平衡二叉树T，平衡因子为0的分支结点个数为3，构建的平衡二叉树及构造与调整过程如下图所示请添加图片描述答案：D4、现有一棵无重复关键字的平衡二叉树（AVL），对其进行中序遍历可得到一个降序序列下列关于该平衡二叉树的叙述中，正确的是（）· • A：根结点的度一定为2· • B：树中最小元素一定是叶结点· • C：最后插入的元素一定是叶结点· • D：树中最大元素一定是无左子树解析只有两个结点的平衡二叉树的根结点的度为1，A错误中序遍历后可以得到一个降序序列，树中最小元素一定无左子树（可能有右子树），因此不一定是叶结点，B错误最后插入的结点可能会导致平衡调整，而不一定是叶结点，C错误答案：D5、在任意一棵非空平衡二叉树（AVL树）中，删除某结点v之后形成平衡二叉树，再将v插入形成平衡二叉树。

下列关于与的叙述中，正确的是（）Ⅰ、若v是的叶结点，则与可能不相同Ⅱ、若v不是的叶结点，则与一定不相同Ⅲ、若v不是的叶结点，则与一定相同· • A：仅Ⅰ· • B：仅Ⅱ· • C：仅Ⅰ、Ⅱ· • D：仅Ⅰ、Ⅲ解析在非空平衡二叉树中插入结点，在失去平衡调整前，一定插入在叶结点的位置若删除的是的叶结点，则删除后平衡二叉树可能不会失去平衡，即不会发生调整，再插入此结点得到的二叉平衡树与相同；若删除后平衡二叉树失去平衡而发生调整，再插入结点得到的二叉平衡树与可能不同对于比较绝对的说法Ⅱ和Ⅲ，通常只需举出反例即可例如，如下图所示，删除结点0，平衡二叉树失衡调整，再插入结点0后，平衡二叉树和以前不同若删除的是的非叶结点，且删除和插入操作均没有导致平衡二叉树的调整，则该结点从非叶结点变成了叶结点，与显然不同例如，如下图所示，删除结点2，用有孩子结点3填补，再插入结点2，平衡二叉树和以前不同若删除的是的非叶结点，且删除和插入操作后导致了平衡二叉树的调整，则该结点有可能通过旋转后继续变成非叶结点，与相同例如，如下图所示，删除结点2，用右孩子结点3填补，再插入结点2，平衡二叉树失衡调整，调整后的平衡二叉树和以前相同。

答案：A6、下图所示是一棵（）· • A：4阶B树· • B：4阶B+树· • C：3阶B树· • D：3阶B+树解析关键字数量比子树数量少1，所以不是B+树，而是B树又因为m阶B树结点关键字数最多为m-1，有一个结点关键字个数为3，所以不可能为3阶答案：A7、下列关于m阶B树的说法中，错误的是（）· • A：根结点至多有m棵子树· • B：所有叶结点都在同一层次上· • C：非叶结点至少有m/2（m为偶数）或（m+1）/2（m为奇数）棵子树· • D：根结点中的数据是有序的解析除根结点外的所有非终端结点至少有棵子树对于根结点，最多有m棵子树，若其不是叶结点，则至少有2棵子树答案：C8、以下关于m阶B树的说法中，正确的是（）Ⅰ、每个结点至少有两棵非空子树 Ⅱ、树中每个结点至多有m-1个关键字 Ⅲ、所有叶结点在同一层 Ⅳ、插入一个元素引起B树结点分裂后，树长高一层· • A：Ⅰ、Ⅱ· • B：Ⅱ、Ⅲ· • C：Ⅲ、Ⅳ· • D：Ⅰ、Ⅱ、Ⅳ解析每个非根的内部结点必须至少有棵子树，而根结点至少要有两棵子树，所以Ⅰ不正确Ⅱ、Ⅲ显然正确对于Ⅳ，插入一个元素引起B树结点分裂后，只要从根结点到该元素插入位置的路径上至少有一个结点未满，B树就不会长高，如图1所示；只有当结点的分裂传到根结点，并使根结点也分裂时，才会导致树高增1，如图2所示，因此Ⅳ错误。

答案：B9、具有n个关键字的m阶B树，应有（）个叶结点· • A：n+1· • B：n-1· • C：mn· • D：nm/2解析B树的叶结点对应查找失败的情况，对有n个关键字的查找集合进行查找，失败可能性有n+1种答案：A10、高度为5的3阶B树至少有（）个结点，至多有（）个结点· • A：32· • B：31· • C：120· • D：121解析由m阶B树的性质可知，根结点至少有2棵子树；根结点外的所有非终端结点至少有棵子树，结点数最少时，3阶B树形状至少类似于一棵满二叉树，即高度为5的B树至少有-1=31个结点由于每个结点最多有m棵子树，所以当结点数最多时，3阶B树形状类似于满三叉树，结点数为(-1)/2=121答案：B。