年秋国家开放大学《离散数学》形考4试题及答案(答案全部正确)

--

2016年秋国家开放大学《离散数学》形考4试题及答案(答案全部正确)

０4任务_0001

试卷总分:1００ 测试时间:0

单项选择题

一、单项选择题(共 １0 道试题，共 10０ 分。) 1． 无向树T有8个结点，则T的边数为（ )． A. ６ Ｂ. 7 C. 8 Ｄ. 9

2． 图G如图三所示，以下说法正确的是 （ ) .

Ａ． {(a， ｄ)}是割边 Ｂ． {(a, d)}是边割集Ｃ. ｛(a, d) ,(b, d）｝是边割集d）}是边割集

3. 设有向图(a）、(b)、(ｃ)与（ｄ）如图所示,则下列结论成立的是（ )．

D. {(ｂ,

A. （ａ)只是弱连通的B. （ｂ)只是弱连通的C. （ｃ）只是弱连通的４． 如图一所示，以下说法正确的是 （ ) .

Ｄ． (d）只是弱连通的

A. {(ａ, e)｝是割边B. ｛(a, e)}是边割集Ｃ. ｛(a, e） ,(b， ｃ)}是边割集D. {(d， e)}是边割集

5. 设G是有ｎ个结点,ｍ条边的连通图，必须删去G的( ）条边,才能确定G的一棵生成树． Ａ. m－ｎ+1Ｂ． m-nC. m＋n+1D． n-m+1

６. 设G是连通平面图,有v个结点,ｅ条边，r个面，则r= ( ). A. e－v+2

Ｂ. ｖ+ｅ－2

C. ｅ-v－2

D． e+v＋2

7. 设无向图G的邻接矩阵为，则G的边数为（ ）.

A． ６B. 5Ｃ． ４D. 3

8． 如图所示，以下说法正确的是 ( )．

--

--

A. ｅ是割点B. {a， ｅ}是点割集C． ｛ｂ, e}是点割集9. 无向简单图Ｇ是棵树，当且仅当（ ). A. Ｇ连通且边数比结点数少１

D． ｛d}是点割集

B. G连通且结点数比边数少1

C. G的边数比结点数少１ D. Ｇ中没有回路． 10． 以下结论正确的是( ). Ａ. 无向完全图都是欧拉图 C. 无向完全图都是平面图

B. 有n个结点n-1条边的无向图都是树

D. 树的每条边都是割边

0４任务＿０002

试卷总分:１00 测试时间：0

单项选择题

一、单项选择题（共 10 道试题，共 1０0 分。)

１. 设G是有n个结点,m条边的连通图，必须删去Ｇ的( )条边,才能确定G的一棵生成树. A. m－ｎ+1 B. m-n C. m＋n＋1 ２． 图G如图二所示,以下说法正确的是 ( ）．

Ｄ． n-m＋１

A. a是割点 B. {ｂ, c}是点割集 3. 如图所示,以下说法正确的是 ( )．

C. {ｂ, d}是点割集

D. {c}是点割集

A. e是割点 B. {a, e}是点割集 Ｃ． ｛b, e｝是点割集 割集

4. 图Ｇ如图三所示,以下说法正确的是 ( ） ．

D． {ｄ}是点

A. {(a， d)}是割边 B. {（a, d)｝是边割集 是边割集

5. 无向图G存在欧拉回路，当且仅当（ ). A. Ｇ中所有结点的度数全为偶数 B. G中至多有两个奇数度结点

Ｃ. ｛(ａ, d) ,（b, ｄ)}是边割集

D. {（b, d)}

--

--

C． G连通且所有结点的度数全为偶数 D． G连通且至多有两个奇数度结点 6. 无向完全图K4是( ). A． 欧拉图 Ｂ. 汉密尔顿图 C. 非平面图

D． 树

7. 设G是连通平面图，有ｖ个结点,e条边，ｒ个面，则r＝ ( ）． A． e-v+2 B． v＋e-２ C. e－v－2

D. ｅ＋v+2

８. 设图G＝，ｖＶ,则下列结论成立的是 （ ) ． A. dｅg(ｖ）＝２|E| Ｂ． deｇ（ｖ)＝｜E| Ｃ．

D．

９． 以下结论正确的是( )． A. 无向完全图都是欧拉图

B. 有n个结点n－1条边的无向图都是树 C. 无向完全图都是平面图

D. 树的每条边都是割边

10． 若G是一个汉密尔顿图，则Ｇ一定是( )． Ａ． 平面图 B． 对偶图 Ｃ. 欧拉图 D. 连通图

04任务_0０03

试卷总分：1０0 测试时间：０

单项选择题

一、单项选择题（共 10 道试题,共 100 分。） 1． 无向完全图K4是（ ). Ａ. 欧拉图 B． 汉密尔顿图 C. 非平面图

D. 树

2. 设Ｇ是有ｎ个结点,m条边的连通图，必须删去G的( )条边,才能确定G的一棵生成树． A. m-n+1 B. m－n C. m+n+1

D. ｎ-ｍ＋１

３. 如图所示，以下说法正确的是 ( )．

--