（1） （2） （3） （4）

4．给定无孤立点无向图G的边集：{（1，2），（1，3），（2，3），（2，4），（2，5），（3，4），（3，5）}，找出图G的一棵生成树为( )

A．{（1，2），（1，3），（2，4），（3，5）} B．{（1，2），（1，3），（2，3），（2，4）} C．{（1，2），（1，3），（3，5），（4，5）} D．{（1，2），（3，4），（3，5），（4，5）}

5．如图所示带权图，用避圈法(Kruskal算法)求一棵最小生成树并计算它的权值为( )

A．15 B．14 C．17 D．11

6．如图所示带权图，用避圈法(Kruskal算法)求一棵最小生成树并计算它的权值为( )。

A．15 B．16 C．17 D．19

7．求带权图G的最小生成树，并计算它的权值为( )。 。

A．10 B．15 C．7 D．9

8．给定权为2，6，3，8，4；则该二叉树的权为( ) A．51 B．63 C．48 D．72

18．给定权为1，9，4，7，3；构造一颗最优二叉树，则该二叉树的权为( ) A．31 B．45 C．51 D．56

9．给定权为2，6，5，9，4，1；构造一颗最优二叉树，则该二叉树的权为( ) A．48 B．51 C．55 D．64

10．给定权为3，4，5，6，7，8，9；构造一棵最优二叉树，则该二叉树的权为( ) A．96 B．85 C．120 D．116

答案：

6.1、单项选择题1、A 2、A 3、（4） 4、D 5、B 6、B 6.2、单项选择题1、B 2、（3） 3、A

6.3、单项选择题1、A 2、D 3、（3） 4、A 5、D 6、A 7、C 8、A 8、C 9、D 10、D