数据结构
相似问题和答案
第1题：
如下所示是一棵5阶B树，该B树现在的层数为2。从该B树中删除关键码38后，该B树的第2层的结点数为
A．6
B．7
C．8
D．9
第2题：
试题基于以下的5阶B树结构，该B树现在的层数为2。
往该B树中插入关键码72后，该B树的第2层的结点数为________。
A．6
B．7
C．8
D．9
解析：对于叶结点处于第i层的B树，插入的关键码总是进入第i层的结点若要插入72，要插入的那个结点已经包含4个关键码，是满的，不能往里面插了。在这种情况下，要把这个结点分裂成两个，并把中间的一个关键码拿出来插到结点的双亲结点里去。本题插入72后，树的有关部分变为：
所以，往该树中插入关键码72后，该树的第2层的结点数为8。
第3题：
●最佳二叉搜索树是 (36) 。
(36) A．关键码个数最少的二叉搜索树
B．搜索时平均比较次数最少的二叉搜索树
C．所有结点的左子树都为空的二叉搜索树
D．所有结点的右子树都为空的二叉搜索树
【解析】最佳二叉搜索树是搜索时平均比较次数最少的二叉搜索树。
第4题：
基于以下的5阶B树结构。
往该B树中插入关键码72后，该B树的叶结点数为
A．5
B．6
C．7
D．8
解析：关键码为72的叶结点应当是“64 70 73 78”的孩子结点。
第5题：
在一棵度为4的树中，度为4的结点个数为1，度为3的结点个数为2，度为2的结点个数为 2，则叶子结点个数为( )。
A．8
B．9
C．10
D．11
解析：对一棵树，除了根结点外，其余每个结点入度都为1，因此树的度的和为结点数减1，设叶子结点数为x，则结点总数为(1+2+2+x)，度的和为x+4。同时所有结点中只有叶子结点的度为0，所以x+4=4*1+3*2+2*2，得到x=10。
第6题：
在深度为5的完全二又树中，叶子结点的个数最多为_______。
【答案】16
【解析】在深度为5的完全二叉树中，就属深度为5的满二叉树中的叶子结点的个数最多， 这些叶子结点均在最后一层(即第5层)上。 又根据二叉树的性质1：在二叉树的第k层上．最多有2k-1(k1)个结点。因此．在第5层上最多的结点数为25-1=16。
第7题：
基于以下的5阶B树结构，该B树现在的层数是2。
往该B树中插入关键码72后，该B树的第2层的结点数为
A．6
B．7
C．8
D．9
解析：原来结点为7个，现在在第二层插入72后，结点为8个。
第8题：
第9题：
5阶的B树中，每个结点最多有( )个关键码。
A．3
B．4
C．5
D．6
解析：在最坏情况下，对含有n个关键字的m阶B树，其深度L满足如下条件：n+12*({m/2})1L-1”，5阶B树中每个结点最多有4个。
第10题：
如下所示是一棵5阶B树，从该B树中删除关键码41后，该B树的叶结点数为
A．6
B．7
C．8
D．9