2023年7月19日发(作者：)

_

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

04任务_0001

试卷总分：100 测试时间：0

单项选择题

一、单项选择题（共 10 道试题，共 100 分。）

1. 无向树T有8个结点，则T的边数为( )．

A. 6 B. 7 C. 8 D. 9

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

A. {(a, d)}是割边 B. {(a, d)}是边割集C. {(a, d) ,(b, d)}是边割集D. {(b,

d)}是边割集

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

A. （a）只是弱连通的B. （b）只是弱连通的C. （c）只是弱连通的D. （d）只是弱连通的

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

A. {(a, e)}是割边B. {(a, e)}是边割集C. {(a, e) ,(b, c)}是边割集D. {(d,

e)}是边割集

5. 设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．

A. m-n+1B. m-nC. m+n+1D. n-m+1

6. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．

A.

e－v＋2B.

v＋e－2C.

e－v－2D.

e＋v＋2

7. 设无向图G的邻接矩阵为，则G的边数为( )． _

A. 6B. 5C. 4D. 3

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

A.

e是割点B. {a,

e}是点割集C. {b,

e}是点割集D. {d}是点割集

9. 无向简单图G是棵树，当且仅当( )．

A.

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

C.

G的边数比结点数少1

10. 以下结论正确的是( )．

A. 无向完全图都是欧拉图

C. 无向完全图都是平面图

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

D. 树的每条边都是割边

04任务_0002

试卷总分：100 测试时间：0

单项选择题

一、单项选择题（共 10 道试题，共 100 分。）

1. 设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．

A. m-n+1 B. m-n C. m+n+1 D. n-m+1

B.

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

D.

G中没有回路．

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

A.

a是割点 B. {b,

c}是点割集 C. {b,

d}是点割集 D. {c}是点割集

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

A.

e是割点 B. {a,

e}是点割集 C. {b,

e}是点割集 D. {d}是点割集

4. 图G如图三所示，以下说法正确的是 ( ) ． _

A. {(a, d)}是割边 B. {(a, d)}是边割集 C. {(a, d) ,(b, d)}是边割集 D. {(b,

d)}是边割集

5. 无向图G存在欧拉回路，当且仅当（ ）.

A.

G中所有结点的度数全为偶数

B.

G中至多有两个奇数度结点

C.

G连通且所有结点的度数全为偶数

D.

G连通且至多有两个奇数度结点

6. 无向完全图K4是（ ）．

A. 欧拉图

B. 汉密尔顿图

C. 非平面图

D. 树

7. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．

A.

e－v＋2

B.

v＋e－2

C.

e－v－2

D.

e＋v＋2

8. 设图G＝

E>，vV，则下列结论成立的是 ( ) ．

A. deg(v)=2|E|

B. deg(v)=|E|

C.

D.

9. 以下结论正确的是( )．

A. 无向完全图都是欧拉图

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

C. 无向完全图都是平面图

D. 树的每条边都是割边 _

10. 若G是一个汉密尔顿图，则G一定是( )．

A. 平面图

B. 对偶图

C. 欧拉图

D. 连通图

04任务_0003

试卷总分：100 测试时间：0

单项选择题

一、单项选择题（共 10 道试题，共 100 分。）

1. 无向完全图K4是（ ）．

A. 欧拉图

B. 汉密尔顿图

C. 非平面图

D. 树

2. 设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．

A. m-n+1

B. m-n

C. m+n+1

D. n-m+1

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

A.

e是割点

B. {a,

e}是点割集

C. {b,

e}是点割集

D. {d}是点割集

4. 若G是一个汉密尔顿图，则G一定是( )．

A. 平面图

B. 对偶图

C. 欧拉图

D. 连通图 _

5. 设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是( )．

A. （a）只是弱连通的

B. （b）只是弱连通的

C. （c）只是弱连通的

D. （d）只是弱连通的

6. 无向图G存在欧拉回路，当且仅当（ ）.

A.

G中所有结点的度数全为偶数

B.

G中至多有两个奇数度结点

C.

G连通且所有结点的度数全为偶数

D.

G连通且至多有两个奇数度结点

7. 设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是( )．

图四

A. （a）是强连通的

B. （b）是强连通的

C. （c）是强连通的

D. （d）是强连通的

8. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．

A.

e－v＋2

B.

v＋e－2

C.

e－v－2

D.

e＋v＋2

9. 设无向图G的邻接矩阵为，则G的边数为( )． _

A. 6

B. 5

C. 4

D. 3

10. 以下结论正确的是( )．

A. 无向完全图都是欧拉图

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

C. 无向完全图都是平面图

D. 树的每条边都是割边

04任务_0004

试卷总分：100 测试时间：0

单项选择题

一、单项选择题（共 10 道试题，共 100 分。）

1. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．

A.

e－v＋2

B.

v＋e－2

C.

e－v－2

D.

e＋v＋2

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

A.

e是割点

B. {a,

e}是点割集

C. {b,

e}是点割集

D. {d}是点割集

3. 若G是一个欧拉图，则G一定是( )．

A. 平面图

B. 汉密尔顿图

C. 连通图

D. 对偶图

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

A. {(a, e)}是割边

B. {(a, e)}是边割集

C. {(a, e) ,(b, c)}是边割集

D. {(d,

e)}是边割集

5. 无向树T有8个结点，则T的边数为( )．

A. 6

B. 7

C. 8

D. 9

6. 设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是( )．

A. （a）只是弱连通的

B. （b）只是弱连通的

C. （c）只是弱连通的

D. （d）只是弱连通的

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

A.

a是割点

B. {b,

c}是点割集

C. {b,

d}是点割集

D. {c}是点割集 _

8. 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )．

A. 8

B. 5

C. 4

D. 3

9. 设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是( )．

图四

A. （a）是强连通的

B. （b）是强连通的

C. （c）是强连通的

D. （d）是强连通的

10. 设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．

A. m-n+1

B. m-n

C. m+n+1

D. n-m+1

04任务_0005

试卷总分：100 测试时间：0

单项选择题

一、单项选择题（共 10 道试题，共 100 分。）

1. 以下结论正确的是( )．

A. 无向完全图都是欧拉图

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

C. 无向完全图都是平面图

D. 树的每条边都是割边

2. 若G是一个欧拉图，则G一定是( )．

A. 平面图

B. 汉密尔顿图

C. 连通图 _

D. 对偶图

3. 无向完全图K4是（ ）．

A. 欧拉图

B. 汉密尔顿图

C. 非平面图

D. 树

4. 设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是( )．

图四

A. （a）是强连通的

B. （b）是强连通的

C. （c）是强连通的

D. （d）是强连通的

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

A.

e是割点

B. {a,

e}是点割集

C. {b,

e}是点割集

D. {d}是点割集

6. 设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是( )．

A. （a）只是弱连通的

C. （c）只是弱连通的

B. （b）只是弱连通的

D. （d）只是弱连通的

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

A. {(a, e)}是割边

B. {(a, e)}是边割集

C. {(a, e) ,(b, c)}是边割集

D. {(d,

e)}是边割集

8. 设图G＝

E>，vV，则下列结论成立的是 ( ) ．

A. deg(v)=2|E|

B. deg(v)=|E|

C.

D.

9. 若G是一个汉密尔顿图，则G一定是( )．

A. 平面图

B. 对偶图

C. 欧拉图

D. 连通图

10. 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )．

A. 8

B. 5

C. 4

D. 3

04任务_0006

试卷总分：100 测试时间：0

单项选择题

一、单项选择题（共 10 道试题，共 100 分。）

1. 设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是( )． _

A. （a）只是弱连通的

B. （b）只是弱连通的

C. （c）只是弱连通的

D. （d）只是弱连通的

2. 设无向图G的邻接矩阵为

，

则G的边数为( )．

A. 1

B. 6

C. 7

D. 14

3. 设无向图G的邻接矩阵为A. 6

B. 5

C. 4

D. 3

4. 无向简单图G是棵树，当且仅当( )．

A.

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

B.

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

C.

G的边数比结点数少1

D.

G中没有回路．

，则G的边数为( )．

5. 图G如图三所示，以下说法正确的是 ( ) ． _

A. {(a, d)}是割边

B. {(a, d)}是边割集

C. {(a, d) ,(b, d)}是边割集

D. {(b,

d)}是边割集

6. 若G是一个汉密尔顿图，则G一定是( )．

A. 平面图

B. 对偶图

C. 欧拉图

D. 连通图

7. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．

A.

e－v＋2

B.

v＋e－2

C.

e－v－2

D.

e＋v＋2

8. 无向完全图K4是（ ）．

A. 欧拉图

B. 汉密尔顿图

C. 非平面图

D. 树

9. 设图G＝

E>，vV，则下列结论成立的是 ( ) ．

A. deg(v)=2|E|

B. deg(v)=|E|

C.

D.

10. 以下结论正确的是( )．

A. 无向完全图都是欧拉图 _

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

C. 无向完全图都是平面图

D. 树的每条边都是割边

04任务_0007

试卷总分：100 测试时间：0

单项选择题

一、单项选择题（共 10 道试题，共 100 分。）

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

A. {(a, d)}是割边

B. {(a, d)}是边割集

C. {(a, d) ,(b, d)}是边割集

D. {(b,

d)}是边割集

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

A.

e是割点

B. {a,

e}是点割集

C. {b,

e}是点割集

D. {d}是点割集

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

A. （a）只是弱连通的

B. （b）只是弱连通的

C. （c）只是弱连通的 _

D. （d）只是弱连通的

4. 设无向图G的邻接矩阵为

，

则G的边数为( )．

A. 1

B. 6

C. 7

D. 14

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

A. {(a, e)}是割边

B. {(a, e)}是边割集

C. {(a, e) ,(b, c)}是边割集

D. {(d,

e)}是边割集

6. 无向完全图K4是（ ）．

A. 欧拉图

B. 汉密尔顿图

C. 非平面图

D. 树

7. 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )．

A. 8

B. 5

C. 4

D. 3

8. 无向图G存在欧拉回路，当且仅当（ ）. _

A.

G中所有结点的度数全为偶数

B.

G中至多有两个奇数度结点

C.

G连通且所有结点的度数全为偶数

D.

G连通且至多有两个奇数度结点

9. 以下结论正确的是( )．

A. 无向完全图都是欧拉图

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

C. 无向完全图都是平面图

D. 树的每条边都是割边

10. 无向简单图G是棵树，当且仅当( )．

A.

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

B.

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

C.

G的边数比结点数少1

D.

G中没有回路．

04任务_0008

试卷总分：100 测试时间：0

单项选择题

一、单项选择题（共 10 道试题，共 100 分。）

1. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．

A.

e－v＋2

B.

v＋e－2

C.

e－v－2

D.

e＋v＋2

2. 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )．

A. 8 B. 5 C. 4 D. 3

3. 若G是一个欧拉图，则G一定是( )．

A. 平面图 B. 汉密尔顿图 C. 连通图 D. 对偶图

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

A.

a是割点 B. {b,

c}是点割集 C. {b,

d}是点割集 D. {c}是点割集 _

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

A.

e是割点 B. {a,

e}是点割集 C. {b,

e}是点割集D. {d}是点割集

6. 若G是一个汉密尔顿图，则G一定是( )．

A. 平面图B. 对偶图C. 欧拉图D. 连通图

7. 无向图G存在欧拉回路，当且仅当（ ）.

A.

G中所有结点的度数全为偶数

C.

G连通且所有结点的度数全为偶数

B.

G中至多有两个奇数度结点

D.

G连通且至多有两个奇数度结点

8. 设图G＝

E>，vV，则下列结论成立的是 ( ) ．

A. deg(v)=2|E|B. deg(v)=|E|C. D.

9. 以下结论正确的是( )．

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

D. 树的每条边都是割边

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

A. {(a, d)}是割边

C. {(a, d) ,(b, d)}是边割集

B. {(a, d)}是边割集

D. {(b,

d)}是边割集

04任务_0009

试卷总分：100 测试时间：0

单项选择题

一、单项选择题（共 10 道试题，共 100 分。）

1. 无向完全图K4是（ ）．

A. 欧拉图 B. 汉密尔顿图C. 非平面图D. 树

2. 已知无向图G的邻接矩阵为，则G有（ ）． _

A. 5点，8边B. 6点，7边C. 6点，8边D. 5点，7边

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

A.

a是割点B. {b,

c}是点割集C. {b,

d}是点割集D. {c}是点割集

4. 设图G＝

E>，vV，则下列结论成立的是 ( ) ．

A. deg(v)=2|E|B. deg(v)=|E|C. D.

5. 无向图G存在欧拉回路，当且仅当（ ）.

A.

G中所有结点的度数全为偶数

C.

G连通且所有结点的度数全为偶数

6. 以下结论正确的是( )．

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

D. 树的每条边都是割边

B.

G中至多有两个奇数度结点

D.

G连通且至多有两个奇数度结点

7. 若G是一个欧拉图，则G一定是( )．

A. 平面图B. 汉密尔顿图C. 连通图D. 对偶图

8. 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )．

A. 8 B. 5 C. 4 D. 3

9. 若G是一个汉密尔顿图，则G一定是( )．

A. 平面图 B. 对偶图 C. 欧拉图 D. 连通图

10. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．

A.

e－v＋2 B.

v＋e－2 C.

e－v－2 D.

e＋v＋2

04任务_0010

试卷总分：100 测试时间：0

单项选择题

一、单项选择题（共 10 道试题，共 100 分。）

1. 设无向图G的邻接矩阵为

，

则G的边数为( )．

A. 1 B. 6C. 7D. 14

2. 无向图G存在欧拉回路，当且仅当（ ）. _

A.

G中所有结点的度数全为偶数

C.

G连通且所有结点的度数全为偶数

B.

G中至多有两个奇数度结点

D.

G连通且至多有两个奇数度结点

3. 设图G＝

E>，vV，则下列结论成立的是 ( ) ．

A. deg(v)=2|E|

B. deg(v)=|E|

C. D.

4. 设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．

A.

e－v＋2 B.

v＋e－2 C.

e－v－2 D.

e＋v＋2

5. 若G是一个汉密尔顿图，则G一定是( )．

A. 平面图 B. 对偶图 C. 欧拉图 D. 连通图

6. 以下结论正确的是( )．

A. 无向完全图都是欧拉图

C. 无向完全图都是平面图

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

D. 树的每条边都是割边

7. 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )．

A. 8 B. 5 C. 4 D. 3

8. 设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是( )．

图四

A. （a）是强连通的

C. （c）是强连通的

B. （b）是强连通的

D. （d）是强连通的

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

A.

a是割点 B. {b,

c}是点割集 C. {b,

d}是点割集 D. {c}是点割集

10. 无向树T有8个结点，则T的边数为( )．

A. 6 B. 7 C. 8 D. 9