1、1 n个结点的完全无向图，共有（ ）条边
A、n条
B、 n-2条
C、 (n-1)n条
D、 (n-1)n/2条
2、2 图的组成要素有（ ）。
A、点
B、点即点之间的连线
C、点和权
D、点、边和权
3、3 哥尼斯堡七桥问题中存在欧拉回路，即一个步行者能通过每座桥一次且仅一次回到原出发地。
4、4 任意一个图都是自身的子图。
第二十五讲 最小支撑树与最短路问题
5、1 以下叙述中不正确的是（ ）。
A、树的点数等于边数加1
B、树的任意两点间只有一条链
C、任何不连通图都不是树
D、树是边数最少的图
6、2 n 个结点的树，共有( )条边（ ）。
A、n 条边
B、n-1 条边
C、n+1 条边
D、2n 条边
7、3 下图中的最小树所有边的权数之和为（ ）。
A、26
B、24
C、23
D、20
8、4 求图的最小支撑树，主要有哪些方法
A、“避圈法”Kruskal算法
B、 “破圈法”(管梅谷算法)
C、Dijkstra标号法
D、 Warshall- Floyd算法
9、5 Dijkstra标号法可以求任意两点之间的最短路。
10、6 图的最小支撑树一定唯一。
第二十六讲 最大流问题
11、1 下列说法正确的是
A、割集是子图
B、割量等于割集中弧的流量之和
C、割量大于等于最大流量
D、割量小于等于最大流量
12、2 下列说法错误的是
A、容量不超过流量
B、流量非负
C、容量非负
D、发点流出的合流等于收点流入的合流
13、3 甲乙两城市之间存在一公路网络，为了判断两小时内能否有9000辆车从甲城到乙城，应借助( )。
A、树的生成法
B、求最大流法
C、求最小生成树法
D、求最短路法
14、4 求最大流的方法有
A、 “避圈法”Kruskal算法
B、Ford―Fulkerson法
C、Dijkstra标号法
D、Warshall- Floyd算法
15、5 可行流是最大流的充要条件是不存在发点到收点的增广链。
16、6 最大流等于最大流量。
第二十七讲 最小费用最大流问题
17、1 下列说法正确的是
A、最大流量等于最大割量
B、最大流量等于最小割量
C、任意流量不小于最小割量
D、最大流量不小于任意割量
18、2 关于最大流量问题，以下叙述( )正确。
A、一个容量网络的最大流是唯一确定的
B、达到最大流的方案是唯一的
C、当用标号法求最大流时，可能得到不同的最大流方案
D、当最大流方案不唯一时，得到的最大流量相同。
19、3 关于增广链，以下叙述( )正确。
A、 增广链是一条从发点到收点的有向链，这条链上各条边的方向必一致。
B、 增广链是一条从发点到收点的有向链，这条链上各条边的方向可不一致。
C、 增广链上与发点到收点方向一致的边必须是非饱和边，方向相反的边必须是流量大于零的边。
D、 增广链上与发点到收点方向一致的边必须是流量小于容量的边，方向相反的边必须是流量等于零的边。
20、4 计算最小费用最大流，要同时将最短路问题与最大流问题的算法结合起来。
21、5 某个网络最小费用最大流与这个网络的最大流相比较，它们的最大流量值相等，但流量不相同。
