数据结构和算法|集25

2010门考试提出了以下问题。

1考虑具有顶点集{ 0, 1, 2，3, 4 }的完全无向图。下面矩阵W中的条目Wij是边{i，j}的权重。 在这个图中，生成树T的最小可能权重是多少，使得顶点0是树T中的叶节点？ （A） 七, （B） 八, （C） 九, （D） 十

答复（D）

要得到顶点为0的最小生成树，首先删除第0行和第0列，然后得到剩余图的最小生成树（MST）。有了剩余图形的MST后，将MST连接到顶点0和具有最小权重的边（我们有两个选项，因为第0行中有两个1）。

2.在问题1给出的图中，该图中从顶点1到顶点2的路径P的最小可能权重是多少，使得P最多包含3条边？ （A） 七, （B） 八, （C） 九, （D） 十

答复（B） 路径：1->0->4->2 体重：1+4+3

3.简单图的度序列是图中节点的度按降序排列的序列。下列哪个序列不能是任何图的度序列？ I.7,6,5,4,4,3,2,1 二、6, 6, 6, 6, 3, 3, 2, 2 三、 7,6,6,4,4,3,2,2 四、 8,7,7,6,4,2,1,1

（A） 一和二 （B） 三、四 （C） 仅限IV （D） 二、四

答复（D）

在序列IV中，我们有一个8度的顶点，这在a中是不可能的 简单图 （没有自循环和多条边），总顶点数为8。在这样的图中，最大可能的度数是7。

在序列II中，四个顶点与其他六个顶点相连，但其余四个顶点的度数为3、3、2和2，这在一个简单的图中是不可能的（没有自循环，也没有多条边）。

4、考虑一个B+树，其中一个节点中的最大密钥数是5。任何非根节点中的最小密钥数是多少？ （A） 一, （B） 二, （C） 三, （D） 四,

答复（B） 由于密钥的最大数量是5，因此节点可以拥有的子节点的最大数量是6。通过 B树的定义 ，节点可以拥有的最小子节点数为6/2=3。因此，一个节点可以拥有的最小密钥数变为2（3-1）。

请看 门角 所有上一年的论文/解决方案/解释、教学大纲、重要日期、笔记等。

如果您发现任何答案/解释不正确，或者您想分享有关上述主题的更多信息，请发表评论。