《2016年秋國家開放大學(xué)《離散數(shù)學(xué)》形考4試題及答案(答案全部正確)》由會(huì)員分享，可在線閱讀，更多相關(guān)《2016年秋國家開放大學(xué)《離散數(shù)學(xué)》形考4試題及答案(答案全部正確)（15頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2016年秋國家開放大學(xué)《離散數(shù)學(xué)》形考4試題及答案（答案全部正確） 04任務(wù)_0001 試卷總分：100 測試時(shí)間：0 單項(xiàng)選擇題 一、單項(xiàng)選擇題（共10道試題，共100分。） 1.無向樹T有8個(gè)結(jié)點(diǎn)，則T的邊數(shù)為( )． 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.設(shè)有向圖（a）、（b）、（c）與（d）如圖所示，則下列結(jié)論成立的是( )．

2、 A. （a）只是弱連通的B. （b）只是弱連通的C. （c）只是弱連通的D. （d）只是弱連通的 4.如圖一所示，以下說法正確的是 ( ) ． A. {(a, e)}是割邊B. {(a, e)}是邊割集C. {(a, e) ,(b, c)}是邊割集D. {(d, e)}是邊割集 5.設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹． A. m-n+1B. m-nC. m+n+1D. n-m+1 6.設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )． A. e－v＋2B. v＋e－2C. e－v－2D.

3、 e＋v＋2 7.設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為( )． A. 6B. 5C. 4D. 3 8.如圖所示，以下說法正確的是 ( )． A. e是割點(diǎn)B. {a, e}是點(diǎn)割集C. {b, e}是點(diǎn)割集D. ievbyqtbdd是點(diǎn)割集 9.無向簡單圖G是棵樹，當(dāng)且僅當(dāng)( )． A. G連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1 B. G連通且結(jié)點(diǎn)數(shù)比邊數(shù)少1 C. G的邊數(shù)比結(jié)點(diǎn)數(shù)少1 D. G中沒有回路． 10.以下結(jié)論正確的是( )． A. 無向完全圖都是歐拉圖 B. 有n個(gè)結(jié)點(diǎn)n－1條邊的無向圖都是樹 C. 無向完全圖都是平面圖

4、D. 樹的每條邊都是割邊 04任務(wù)_0002 試卷總分：100 測試時(shí)間：0 單項(xiàng)選擇題 一、單項(xiàng)選擇題（共10道試題，共100分。） 1.設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹． A. m-n+1 B. m-n C. m+n+1 D. n-m+1 2.圖G如圖二所示，以下說法正確的是 ( )． A. a是割點(diǎn) B. {b, c}是點(diǎn)割集 C. {b, d}是點(diǎn)割集 D. {c}是點(diǎn)割集 3.如圖所示，以下說法正確的是 ( )． A. e是割點(diǎn)

5、 B. {a, e}是點(diǎn)割集 C. {b, e}是點(diǎn)割集 D. ievbyqtbdd是點(diǎn)割集 4.圖G如圖三所示，以下說法正確的是 ( ) ． A. {(a, d)}是割邊 B. {(a, d)}是邊割集 C. {(a, d) ,(b, d)}是邊割集 D. {(b, d)}是邊割集 5.無向圖G存在歐拉回路，當(dāng)且僅當(dāng)（ ）. A. G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) B. G中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) C. G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) D. G連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) 6.無向完全圖K4是（ ）． A. 歐拉圖 B. 漢密爾頓圖 C. 非平面圖 D. 樹

6、 7.設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )． A. e－v＋2 B. v＋e－2 C. e－v－2 D. e＋v＋2 8.設(shè)圖G＝，vV，則下列結(jié)論成立的是 ( ) ． A. deg(v)=2|E| B. deg(v)=|E| C. D. 9.以下結(jié)論正確的是( )． A. 無向完全圖都是歐拉圖 B. 有n個(gè)結(jié)點(diǎn)n－1條邊的無向圖都是樹 C. 無向完全圖都是平面圖 D. 樹的每條邊都是割邊 10.若G是一個(gè)漢密爾頓圖，則G一定是( )． A. 平面圖 B. 對(duì)偶圖 C. 歐拉圖 D. 連通圖

7、04任務(wù)_0003 試卷總分：100 測試時(shí)間：0 單項(xiàng)選擇題 一、單項(xiàng)選擇題（共10道試題，共100分。） 1.無向完全圖K4是（ ）． A. 歐拉圖 B. 漢密爾頓圖 C. 非平面圖 D. 樹 2.設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹． A. m-n+1 B. m-n C. m+n+1 D. n-m+1 3.如圖所示，以下說法正確的是 ( )． A. e是割點(diǎn) B. {a, e}是點(diǎn)割集 C. {b, e}是點(diǎn)割集 D. ievbyqtbdd是點(diǎn)割集 4.若G是一個(gè)漢密爾頓圖，則G一定是( )．

8、 A. 平面圖 B. 對(duì)偶圖 C. 歐拉圖 D. 連通圖 5.設(shè)有向圖（a）、（b）、（c）與（d）如圖所示，則下列結(jié)論成立的是( )． A. （a）只是弱連通的 B. （b）只是弱連通的 C. （c）只是弱連通的 D. （d）只是弱連通的 6.無向圖G存在歐拉回路，當(dāng)且僅當(dāng)（ ）. A. G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) B. G中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) C. G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) D. G連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) 7.設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是( )． 　　　　　　　　　　　　　圖四 A

9、. （a）是強(qiáng)連通的 B. （b）是強(qiáng)連通的 C. （c）是強(qiáng)連通的 D. （d）是強(qiáng)連通的 8.設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )． A. e－v＋2 B. v＋e－2 C. e－v－2 D. e＋v＋2 9.設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為( )． A. 6 B. 5 C. 4 D. 3 10.以下結(jié)論正確的是( )． A. 無向完全圖都是歐拉圖 B. 有n個(gè)結(jié)點(diǎn)n－1條邊的無向圖都是樹 C. 無向完全圖都是平面圖 D. 樹的每條邊都是割邊 04任務(wù)_0004 試卷總分：100 測試時(shí)間：0 單項(xiàng)選擇題

10、 一、單項(xiàng)選擇題（共10道試題，共100分。） 1.設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )． A. e－v＋2 B. v＋e－2 C. e－v－2 D. e＋v＋2 2.如圖所示，以下說法正確的是 ( )． A. e是割點(diǎn) B. {a, e}是點(diǎn)割集 C. {b, e}是點(diǎn)割集 D. ievbyqtbdd是點(diǎn)割集 3.若G是一個(gè)歐拉圖，則G一定是( )． A. 平面圖 B. 漢密爾頓圖 C. 連通圖 D. 對(duì)偶圖 4.如圖一所示，以下說法正確的是 ( ) ． A. {(a, e)}是割邊 B. {(a, e)}是邊

11、割集 C. {(a, e) ,(b, c)}是邊割集 D. {(d, e)}是邊割集 5.無向樹T有8個(gè)結(jié)點(diǎn)，則T的邊數(shù)為( )． A. 6 B. 7 C. 8 D. 9 6.設(shè)有向圖（a）、（b）、（c）與（d）如圖所示，則下列結(jié)論成立的是( )． A. （a）只是弱連通的 B. （b）只是弱連通的 C. （c）只是弱連通的 D. （d）只是弱連通的 7.圖G如圖二所示，以下說法正確的是 ( )． A. a是割點(diǎn) B. {b, c}是點(diǎn)割集 C. {b, d}是點(diǎn)割集 D. {c}是點(diǎn)割集 8.已知一棵無向樹T中有8個(gè)頂點(diǎn)，4度、

12、3度、2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為( )． A. 8 B. 5 C. 4 D. 3 9.設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是( )． 　　　　　　　　　　　　　圖四 A. （a）是強(qiáng)連通的 B. （b）是強(qiáng)連通的 C. （c）是強(qiáng)連通的 D. （d）是強(qiáng)連通的 10.設(shè)G是有n個(gè)結(jié)點(diǎn)，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹． A. m-n+1 B. m-n C. m+n+1 D. n-m+1 04任務(wù)_0005 試卷總分：100 測試時(shí)間：0 單項(xiàng)選擇題 一、單項(xiàng)

13、選擇題（共10道試題，共100分。） 1.以下結(jié)論正確的是( )． A. 無向完全圖都是歐拉圖 B. 有n個(gè)結(jié)點(diǎn)n－1條邊的無向圖都是樹 C. 無向完全圖都是平面圖 D. 樹的每條邊都是割邊 2.若G是一個(gè)歐拉圖，則G一定是( )． A. 平面圖 B. 漢密爾頓圖 C. 連通圖 D. 對(duì)偶圖 3.無向完全圖K4是（ ）． A. 歐拉圖 B. 漢密爾頓圖 C. 非平面圖 D. 樹 4.設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是( )． 　　　　　　　　　　　　　圖四 A. （a）是強(qiáng)連通的 B. （b）是強(qiáng)

14、連通的 C. （c）是強(qiáng)連通的 D. （d）是強(qiáng)連通的 5.如圖所示，以下說法正確的是 ( )． A. e是割點(diǎn) B. {a, e}是點(diǎn)割集 C. {b, e}是點(diǎn)割集 D. ievbyqtbdd是點(diǎn)割集 6.設(shè)有向圖（a）、（b）、（c）與（d）如圖所示，則下列結(jié)論成立的是( )． A. （a）只是弱連通的 B. （b）只是弱連通的 C. （c）只是弱連通的 D. （d）只是弱連通的 7.如圖一所示，以下說法正確的是 ( ) ． A. {(a, e)}是割邊 B. {(a, e)}是邊割集 C. {(a, e) ,(b, c)}是邊割集 D.

15、{(d, e)}是邊割集 8.設(shè)圖G＝，vV，則下列結(jié)論成立的是 ( ) ． A. deg(v)=2|E| B. deg(v)=|E| C. D. 9.若G是一個(gè)漢密爾頓圖，則G一定是( )． A. 平面圖 B. 對(duì)偶圖 C. 歐拉圖 D. 連通圖 10.已知一棵無向樹T中有8個(gè)頂點(diǎn)，4度、3度、2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為( )． A. 8 B. 5 C. 4 D. 3 04任務(wù)_0006 試卷總分：100 測試時(shí)間：0 單項(xiàng)選擇題 一、單項(xiàng)選擇題（共10道試題，共100分。） 1.設(shè)有向圖（a）、（b）、（c

16、）與（d）如圖所示，則下列結(jié)論成立的是( )． A. （a）只是弱連通的 B. （b）只是弱連通的 C. （c）只是弱連通的 D. （d）只是弱連通的 2.設(shè)無向圖G的鄰接矩陣為 ， 則G的邊數(shù)為( )． A. 1 B. 6 C. 7 D. 14 3.設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為( )． A. 6 B. 5 C. 4 D. 3 4.無向簡單圖G是棵樹，當(dāng)且僅當(dāng)( )． A. G連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1 B. G連通且結(jié)點(diǎn)數(shù)比邊數(shù)少1 C. G的邊數(shù)比結(jié)點(diǎn)數(shù)少1 D. G中沒有回路． 5.圖G如圖三所示，以下說法正確的是 (

17、 ) ． A. {(a, d)}是割邊 B. {(a, d)}是邊割集 C. {(a, d) ,(b, d)}是邊割集 D. {(b, d)}是邊割集 6.若G是一個(gè)漢密爾頓圖，則G一定是( )． A. 平面圖 B. 對(duì)偶圖 C. 歐拉圖 D. 連通圖 7.設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )． A. e－v＋2 B. v＋e－2 C. e－v－2 D. e＋v＋2 8.無向完全圖K4是（ ）． A. 歐拉圖 B. 漢密爾頓圖 C. 非平面圖 D. 樹 9.設(shè)圖G＝，vV，則下列結(jié)論成立的是

18、 ( ) ． A. deg(v)=2|E| B. deg(v)=|E| C. D. 10.以下結(jié)論正確的是( )． A. 無向完全圖都是歐拉圖 B. 有n個(gè)結(jié)點(diǎn)n－1條邊的無向圖都是樹 C. 無向完全圖都是平面圖 D. 樹的每條邊都是割邊 04任務(wù)_0007 試卷總分：100 測試時(shí)間：0 單項(xiàng)選擇題 一、單項(xiàng)選擇題（共10道試題，共100分。） 1.圖G如圖三所示，以下說法正確的是 ( ) ． A. {(a, d)}是割邊 B. {(a, d)}是邊割集 C. {(a, d) ,(b, d)}是邊割集 D. {(b, d)}是邊割集

19、 2.如圖所示，以下說法正確的是 ( )． A. e是割點(diǎn) B. {a, e}是點(diǎn)割集 C. {b, e}是點(diǎn)割集 D. ievbyqtbdd是點(diǎn)割集 3.設(shè)有向圖（a）、（b）、（c）與（d）如圖所示，則下列結(jié)論成立的是( )． A. （a）只是弱連通的 B. （b）只是弱連通的 C. （c）只是弱連通的 D. （d）只是弱連通的 4.設(shè)無向圖G的鄰接矩陣為 ， 則G的邊數(shù)為( )． A. 1 B. 6 C. 7 D. 14 5.如圖一所示，以下說法正確的是 ( ) ． A. {(a, e)}是割邊 B. {(a, e)}是邊割集 C.

20、 {(a, e) ,(b, c)}是邊割集 D. {(d, e)}是邊割集 6.無向完全圖K4是（ ）． A. 歐拉圖 B. 漢密爾頓圖 C. 非平面圖 D. 樹 7.已知一棵無向樹T中有8個(gè)頂點(diǎn)，4度、3度、2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為( )． A. 8 B. 5 C. 4 D. 3 8.無向圖G存在歐拉回路，當(dāng)且僅當(dāng)（ ）. A. G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) B. G中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) C. G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) D. G連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) 9.以下結(jié)論正確的是( )． A. 無向完全圖都是歐拉圖 B. 有n個(gè)

21、結(jié)點(diǎn)n－1條邊的無向圖都是樹 C. 無向完全圖都是平面圖 D. 樹的每條邊都是割邊 10.無向簡單圖G是棵樹，當(dāng)且僅當(dāng)( )． A. G連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1 B. G連通且結(jié)點(diǎn)數(shù)比邊數(shù)少1 C. G的邊數(shù)比結(jié)點(diǎn)數(shù)少1 D. G中沒有回路． 04任務(wù)_0008 試卷總分：100 測試時(shí)間：0 單項(xiàng)選擇題 一、單項(xiàng)選擇題（共10道試題，共100分。） 1.設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )． A. e－v＋2 B. v＋e－2 C. e－v－2 D. e＋v＋2 2.已知一棵無向樹T中有8個(gè)頂點(diǎn)，4度、3度、2度的分

22、支點(diǎn)各一個(gè)，T的樹葉數(shù)為( )． A. 8 B. 5 C. 4 D. 3 3.若G是一個(gè)歐拉圖，則G一定是( )． A. 平面圖 B. 漢密爾頓圖 C. 連通圖 D. 對(duì)偶圖 4.圖G如圖二所示，以下說法正確的是 ( )． A. a是割點(diǎn) B. {b, c}是點(diǎn)割集 C. {b, d}是點(diǎn)割集 D. {c}是點(diǎn)割集 5.如圖所示，以下說法正確的是 ( )． A. e是割點(diǎn) B. {a, e}是點(diǎn)割集 C. {b, e}是點(diǎn)割集D. ievbyqtbdd是點(diǎn)割集 6.若G是一個(gè)漢密爾頓圖，則

23、G一定是( )． A. 平面圖B. 對(duì)偶圖C. 歐拉圖D. 連通圖 7.無向圖G存在歐拉回路，當(dāng)且僅當(dāng)（ ）. A. G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) B. G中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) C. G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) D. G連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) 8.設(shè)圖G＝，vV，則下列結(jié)論成立的是 ( ) ． A. deg(v)=2|E|B. deg(v)=|E|C. D. 9.以下結(jié)論正確的是( )． A. 無向完全圖都是歐拉圖B. 有n個(gè)結(jié)點(diǎn)n－1條邊的無向圖都是樹 C. 無向完全圖都是平面圖D. 樹的每條邊都是割邊 10.圖G如圖三所示，以下說法正確

24、的是 ( ) ． A. {(a, d)}是割邊 B. {(a, d)}是邊割集 C. {(a, d) ,(b, d)}是邊割集 D. {(b, d)}是邊割集 04任務(wù)_0009 試卷總分：100 測試時(shí)間：0 單項(xiàng)選擇題 一、單項(xiàng)選擇題（共10道試題，共100分。） 1.無向完全圖K4是（ ）． A. 歐拉圖 B. 漢密爾頓圖C. 非平面圖D. 樹 2.已知無向圖G的鄰接矩陣為，則G有（ ）． A. 5點(diǎn)，8邊B. 6點(diǎn)，7邊C. 6點(diǎn)，8邊D. 5點(diǎn)，7邊 3.圖G如圖二所示，以下說法正確的是 ( )．

25、 A. a是割點(diǎn)B. {b, c}是點(diǎn)割集C. {b, d}是點(diǎn)割集D. {c}是點(diǎn)割集 4.設(shè)圖G＝，vV，則下列結(jié)論成立的是 ( ) ． A. deg(v)=2|E|B. deg(v)=|E|C. D. 5.無向圖G存在歐拉回路，當(dāng)且僅當(dāng)（ ）. A. G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) B. G中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) C. G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) D. G連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) 6.以下結(jié)論正確的是( )． A. 無向完全圖都是歐拉圖B. 有n個(gè)結(jié)點(diǎn)n－1條邊的無向圖都是樹 C. 無向完全圖都是平面圖D. 樹的每條邊都是割邊 7.若G是一個(gè)歐

26、拉圖，則G一定是( )． A. 平面圖B. 漢密爾頓圖C. 連通圖D. 對(duì)偶圖 8.已知一棵無向樹T中有8個(gè)頂點(diǎn)，4度、3度、2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為( )． A. 8 B. 5 C. 4 D. 3 9.若G是一個(gè)漢密爾頓圖，則G一定是( )． A. 平面圖 B. 對(duì)偶圖 C. 歐拉圖 D. 連通圖 10.設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )． A. e－v＋2 B. v＋e－2 C. e－v－2 D. e＋v＋2 04任務(wù)_0010 試卷總分：100 測試時(shí)間：0 單項(xiàng)選

27、擇題 一、單項(xiàng)選擇題（共10道試題，共100分。） 1.設(shè)無向圖G的鄰接矩陣為 ， 則G的邊數(shù)為( )． A. 1 B. 6C. 7D. 14 2.無向圖G存在歐拉回路，當(dāng)且僅當(dāng)（ ）. A. G中所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) B. G中至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) C. G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) D. G連通且至多有兩個(gè)奇數(shù)度結(jié)點(diǎn) 3.設(shè)圖G＝，vV，則下列結(jié)論成立的是 ( ) ． A. deg(v)=2|E| B. deg(v)=|E| C. D. 4.設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )． A. e－

28、v＋2 B. v＋e－2 C. e－v－2 D. e＋v＋2 5.若G是一個(gè)漢密爾頓圖，則G一定是( )． A. 平面圖 B. 對(duì)偶圖 C. 歐拉圖 D. 連通圖 6.以下結(jié)論正確的是( )． A. 無向完全圖都是歐拉圖 B. 有n個(gè)結(jié)點(diǎn)n－1條邊的無向圖都是樹 C. 無向完全圖都是平面圖 D. 樹的每條邊都是割邊 7.已知一棵無向樹T中有8個(gè)頂點(diǎn)，4度、3度、2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為( )． A. 8 B. 5 C. 4 D. 3 8.設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是( )． 　　　　　　　　　　　　　圖四 A. （a）是強(qiáng)連通的 B. （b）是強(qiáng)連通的 C. （c）是強(qiáng)連通的 D. （d）是強(qiáng)連通的 9.圖G如圖二所示，以下說法正確的是 ( )． A. a是割點(diǎn) B. {b, c}是點(diǎn)割集 C. {b, d}是點(diǎn)割集 D. {c}是點(diǎn)割集 10.無向樹T有8個(gè)結(jié)點(diǎn)，則T的邊數(shù)為( )． A. 6 B. 7 C. 8 D. 9