SDUT离散数学实验4-图论测试。主要由单选组成，单选19道。
温馨提示：题目顺序和题目选项顺序可能有所不同
单选题
1-1
设G是连通平面图，G中有6个顶点8条边，则G的面的数目是
A.3
B.4
C.5
D.6
1-2
无向图G=<V, E>中顶点间的连通关系是V上的 ( )关系。
A.恒等关系
B.相容关系
C.等价关系
D.偏序关系
1-3
现有n个盒子，若每2个盒子里都恰有1个相同颜色的球，每种颜色的球恰好有2个，并放在不同盒子里，请问这n个盒子里的球共有多少种不同的颜色？
A.n(n-1)/2
B.n
C.n*n
D.n(n-1)
1-4
网球锦标赛共有7名选手闯入总决赛。比赛采用单淘汰制，需要多少场比赛才能决出冠军。
A.5
B.6
C.4
D.7
1-5
设无向图G有16条边，有3个4度结点，4个3度结点，其余顶点的度数均小于等于2，则G中至少有几个顶点？
A.11
B.12
C.15
D.14
1-6
下面哪个图是欧拉图？
A.三个长方形组成的长方形
B.两个正方形组成的复杂图形
C.三角形组成的复杂图形
D.游泳圈图形
1-7
用克鲁斯科尔算法求下列图的最小生成树的树权是
A.35
B.40
C.36
D.34
1-8
无向完全图K5要得到一棵生成树，需要删除( )条边。
A.4
B.7
C.6
D.5
1-9
下面哪个不是下图的边割集？
A {（v 1,v 2）,(v 3,v 4)} B {（v 4,v 5）,(v 5,v 6)}
C {(v 6,v 7)} D {（v 6,v 7）,(v 5,v 6)}
A.D
B.A
C.B
D.C
1-10
图中既是欧拉图又是哈密顿图的是：
A.K10
B.K3,3
C.K6
D.K9
1-11
以下哪个图不是欧拉图？
A.一个正方形
B.一个房子图形
C.一个水滴的复杂图形
D.一个负责的正方形对称图形
1-12
以下说法正确的是？
A.图同构是一种等价关系。
B.任意有向图中，所有顶点的入度之和与所有顶点出度之和不相等
C.非负整数序列 (5, 4, 3, 2, 2) 是简单图的度数序列
D.非负整数序列 (3, 3, 3, 1) 不是图的度数序列
1-13
给定一组权值1,2,3,4,5,6,7,8，构造一棵最优三叉树，这棵最优三叉树有( )个内点？树的高度是( ) 。
A.4, 4
B.5, 3
C.5, 4
D.4, 3
1-14
下面哪个是平面图？
A. K 3,3 ; B. K 5 ; C . K 4 ; D. 彼得森图
A.C
B.A
C.B
D.D
1-15
设简单图G有12条边. 若G的每个顶点的度都相同，则G的顶点个数至少为：
A.4
B.3
C.8
D.6
1-16
对于下图，以下哪个不是它的点割集：
A {V 4} B {v 6} C {v 1,v 3} D {v 4，v 5}
A {V 4} B {v 6} C {v 1,v 3} D {v 4，v 5}
A.C
B.D
C.B
D.A
1-17
在有n个顶点的连通图中，其边数是多少？
A.最多有n条
B.最多有n-1条
C.最少n-1条
D.最少n条
1-18
在含有t片树叶的完全二叉树中有( ) 条边。
A.2t
B.2t-1
C.t
D.2t-2
1-19
给定一组权值1,1,3,4,6,8构造一棵最优二叉树。该最优二叉树的树权是()，树高是()。
A.55,4
B.53,5
C.55,5
D.53,4
