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