单选题 （共 8 题 ），每题只有一个选项正确
下面哪一种图不一定是树（）。
$\text{A.}$ . 无回路的连通图
$\text{B.}$ 有 $n$ 个顶点 $n-1$ 条边的连通图
$\text{C.}$ 每对顶点之间都有通路的图
$\text{D.}$ 连通但删去一条边则不连通的图
n阶非平凡的无向树至少有（）片树叶。
$\text{A.}$ 2
$\text{B.}$ 3
$\text{C.}$ 4
$\text{D.}$ 5
设图 $G$ 是有 6 个顶点的连通图, 总度数为 20 ,则从 $G$ 中删去（ ）边后使之变成树。
$\text{A.}$ 10
$\text{B.}$ 5
$\text{C.}$ 3
$\text{D.}$ 2
图中所示为 7 个城市间直接通信线路的预测造价, 则各个城市之间能够通信的最小总造价为:
$\text{A.}$ 72
$\text{B.}$ 40
$\text{C.}$ 59
$\text{D.}$ 48
下面给出的符号串集合中, 哪一个不是前缀码？（）
$\text{A.}$ $\{0,10,110,1111\}$
$\text{B.}$ $\{1101,1001,101,110\}$
$\text{C.}$ $\{01,001,000,10\}$
$\text{D.}$ $\{b, c, a a, a c, a b a, a b c\}$
5 个结点的简单平面图的边数最多是（）.
$\text{A.}$ 7
$\text{B.}$ 8
$\text{C.}$ 9
$\text{D.}$ 10
二部图 $K_{2,3}$ 是（）。
$\text{A.}$ 欧拉图
$\text{B.}$ 哈密顿图
$\text{C.}$ 非平面图
$\text{D.}$ 平面图
若简单连通图 $G$ 有 4 个结点, 3 个面, 则 $G$ 有 （）条边.
$\text{A.}$ 3
$\text{B.}$ 4
$\text{C.}$ 5
$\text{D.}$ 2
填空题 （共 2 题 ），请把答案直接填写在答题纸上
一颗无向树 $T$ 有 5 片树叶, 3 个 2 度分支点, 其的分支都是 3 度顶点, 则 $T$ 有 $\qquad$个顶点.
无向图 $G$ 具有生成树, 当且仅当 $\qquad$ . $G$ 的所有生成树中 $\qquad$的生成树称为最小生成树。
解答题 （共 3 题 ），解答过程应写出必要的文字说明、证明过程或演算步骤
下图为一连通赋权图, 计算该图的最小生成树和权值.
图 $G$ 是一个简单且连通的平面图, 顶点数为 11 ,其无限面的次数为 8 , 其余有限面的次数都为 6 ,计算平面图 $G$ 的边数和面数.
G 为 $n$ 个结点 $m$ 条边, 每个面的的次数至少为 4 的连通平面图, 证明: $m \leqslant 2 n-4$.