2016年秋國家開放大學(xué)離散數(shù)學(xué)形考4試題及答案（答案全部正確）04任務(wù)_0001試卷總分：100 測試時間：0單項選擇題一、單項選擇題（共10道試題，共100分。）1.無向樹T有8個結(jié)點，則T的邊數(shù)為( ) A. 6 B. 7 C. 8 D. 92.圖G如圖三所示，以下說法正確的是 ( ) A. (a, d)是割邊 B. (a, d)是邊割集C. (a, d) ,(b, d)是邊割集D. (b, d)是邊割集3.設(shè)有向圖（a）、（b）、（c）與（d）如圖所示，則下列結(jié)論成立的是( ) 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個結(jié)點，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹 A. m-n+1B. m-nC. m+n+1D. n-m+16.設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r= ( ) A. ev2B. ve2C. ev2D. ev27.設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為( ) A. 6B. 5C. 4D. 38.如圖所示，以下說法正確的是 ( ) A. e是割點B. a, e是點割集C. b, e是點割集D. d是點割集9.無向簡單圖G是棵樹，當且僅當( ) A. G連通且邊數(shù)比結(jié)點數(shù)少1 B. G連通且結(jié)點數(shù)比邊數(shù)少1C. G的邊數(shù)比結(jié)點數(shù)少1 D. G中沒有回路10.以下結(jié)論正確的是( ) A. 無向完全圖都是歐拉圖 B. 有n個結(jié)點n1條邊的無向圖都是樹C. 無向完全圖都是平面圖 D. 樹的每條邊都是割邊04任務(wù)_0002試卷總分：100 測試時間：0單項選擇題一、單項選擇題（共10道試題，共100分。）1.設(shè)G是有n個結(jié)點，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹 A. m-n+1 B. m-n C. m+n+1 D. n-m+1 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中所有結(jié)點的度數(shù)全為偶數(shù) B. G中至多有兩個奇數(shù)度結(jié)點C. G連通且所有結(jié)點的度數(shù)全為偶數(shù) D. G連通且至多有兩個奇數(shù)度結(jié)點6.無向完全圖K4是（ ） A. 歐拉圖B. 漢密爾頓圖C. 非平面圖D. 樹7.設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r= ( ) A. ev2B. ve2C. ev2D. ev28.設(shè)圖G<V, E>，vV，則下列結(jié)論成立的是 ( ) A. deg(v)=2|E|B. deg(v)=|E|C. D. 9.以下結(jié)論正確的是( ) A. 無向完全圖都是歐拉圖B. 有n個結(jié)點n1條邊的無向圖都是樹C. 無向完全圖都是平面圖D. 樹的每條邊都是割邊10.若G是一個漢密爾頓圖，則G一定是( ) A. 平面圖B. 對偶圖C. 歐拉圖D. 連通圖04任務(wù)_0003試卷總分：100 測試時間：0單項選擇題一、單項選擇題（共10道試題，共100分。）1.無向完全圖K4是（ ） A. 歐拉圖B. 漢密爾頓圖C. 非平面圖D. 樹2.設(shè)G是有n個結(jié)點，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹 A. m-n+1B. m-nC. m+n+1D. n-m+13.如圖所示，以下說法正確的是 ( ) A. e是割點B. a, e是點割集C. b, e是點割集D. d是點割集4.若G是一個漢密爾頓圖，則G一定是( ) A. 平面圖B. 對偶圖C. 歐拉圖D. 連通圖5.設(shè)有向圖（a）、（b）、（c）與（d）如圖所示，則下列結(jié)論成立的是( ) A. （a）只是弱連通的B. （b）只是弱連通的C. （c）只是弱連通的D. （d）只是弱連通的6.無向圖G存在歐拉回路，當且僅當（ ）.A. G中所有結(jié)點的度數(shù)全為偶數(shù) B. G中至多有兩個奇數(shù)度結(jié)點C. G連通且所有結(jié)點的度數(shù)全為偶數(shù) D. G連通且至多有兩個奇數(shù)度結(jié)點7.設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是( ) 圖四 A. （a）是強連通的B. （b）是強連通的C. （c）是強連通的D. （d）是強連通的8.設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r= ( ) A. ev2B. ve2C. ev2D. ev29.設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為( ) A. 6B. 5C. 4D. 310.以下結(jié)論正確的是( ) A. 無向完全圖都是歐拉圖B. 有n個結(jié)點n1條邊的無向圖都是樹C. 無向完全圖都是平面圖D. 樹的每條邊都是割邊04任務(wù)_0004試卷總分：100 測試時間：0單項選擇題一、單項選擇題（共10道試題，共100分。）1.設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r= ( ) A. ev2B. ve2C. ev2D. ev22.如圖所示，以下說法正確的是 ( ) 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個結(jié)點，則T的邊數(shù)為( ) A. 6B. 7C. 8D. 96.設(shè)有向圖（a）、（b）、（c）與（d）如圖所示，則下列結(jié)論成立的是( ) 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的樹葉數(shù)為( ) A. 8B. 5C. 4D. 39.設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是( ) 圖四 A. （a）是強連通的B. （b）是強連通的C. （c）是強連通的D. （d）是強連通的10.設(shè)G是有n個結(jié)點，m條邊的連通圖，必須刪去G的( )條邊，才能確定G的一棵生成樹 A. m-n+1B. m-nC. m+n+1D. n-m+104任務(wù)_0005試卷總分：100 測試時間：0單項選擇題一、單項選擇題（共10道試題，共100分。）1.以下結(jié)論正確的是( ) A. 無向完全圖都是歐拉圖B. 有n個結(jié)點n1條邊的無向圖都是樹C. 無向完全圖都是平面圖D. 樹的每條邊都是割邊2.若G是一個歐拉圖，則G一定是( ) A. 平面圖B. 漢密爾頓圖C. 連通圖D. 對偶圖3.無向完全圖K4是（ ） A. 歐拉圖B. 漢密爾頓圖C. 非平面圖D. 樹4.設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是( ) 圖四 A. （a）是強連通的B. （b）是強連通的C. （c）是強連通的D. （d）是強連通的5.如圖所示，以下說法正確的是 ( ) A. e是割點B. a, e是點割集C. b, e是點割集D. d是點割集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. (d, e)是邊割集8.設(shè)圖G<V, E>，vV，則下列結(jié)論成立的是 ( ) 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的樹葉數(shù)為( ) A. 8B. 5C. 4D. 304任務(wù)_0006試卷總分：100 測試時間：0單項選擇題一、單項選擇題（共10道試題，共100分。）1.設(shè)有向圖（a）、（b）、（c）與（d）如圖所示，則下列結(jié)論成立的是( ) A. （a）只是弱連通的B. （b）只是弱連通的C. （c）只是弱連通的D. （d）只是弱連通的2.設(shè)無向圖G的鄰接矩陣為 ，則G的邊數(shù)為( ) A. 1B. 6C. 7D. 143.設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為( ) A. 6B. 5C. 4D. 34.無向簡單圖G是棵樹，當且僅當( ) A. G連通且邊數(shù)比結(jié)點數(shù)少1B. G連通且結(jié)點數(shù)比邊數(shù)少1C. G的邊數(shù)比結(jié)點數(shù)少1D. 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.設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r= ( ) A. ev2B. ve2C. ev2D. ev28.無向完全圖K4是（ ） A. 歐拉圖B. 漢密爾頓圖C. 非平面圖D. 樹9.設(shè)圖G<V, E>，vV，則下列結(jié)論成立的是 ( ) A. deg(v)=2|E|B. deg(v)=|E|C. D. 10.以下結(jié)論正確的是( ) A. 無向完全圖都是歐拉圖B. 有n個結(jié)點n1條邊的無向圖都是樹C. 無向完全圖都是平面圖D. 樹的每條邊都是割邊04任務(wù)_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.設(shè)有向圖（a）、（b）、（c）與（d）如圖所示，則下列結(jié)論成立的是( ) A. （a）只是弱連通的B. （b）只是弱連通的C. （c）只是弱連通的D. （d）只是弱連通的4.設(shè)無向圖G的鄰接矩陣為 ，則G的邊數(shù)為( ) A. 1B. 6C. 7D. 145.如圖一所示，以下說法正確的是 ( ) 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的樹葉數(shù)為( ) A. 8B. 5C. 4D. 38.無向圖G存在歐拉回路，當且僅當（ ）.A. G中所有結(jié)點的度數(shù)全為偶數(shù) B. G中至多有兩個奇數(shù)度結(jié)點C. G連通且所有結(jié)點的度數(shù)全為偶數(shù) D. G連通且至多有兩個奇數(shù)度結(jié)點9.以下結(jié)論正確的是( ) A. 無向完全圖都是歐拉圖B. 有n個結(jié)點n1條邊的無向圖都是樹C. 無向完全圖都是平面圖D. 樹的每條邊都是割邊10.無向簡單圖G是棵樹，當且僅當( ) A. G連通且邊數(shù)比結(jié)點數(shù)少1B. G連通且結(jié)點數(shù)比邊數(shù)少1C. G的邊數(shù)比結(jié)點數(shù)少1D. G中沒有回路04任務(wù)_0008試卷總分：100 測試時間：0單項選擇題一、單項選擇題（共10道試題，共100分。）1.設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r= ( ) A. ev2B. ve2C. ev2D. ev22.已知一棵無向樹T中有8個頂點，4度、3度、2度的分支點各一個，T的樹葉數(shù)為( ) A. 8 B. 5 C. 4 D. 33.若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中所有結(jié)點的度數(shù)全為偶數(shù) B. G中至多有兩個奇數(shù)度結(jié)點C. G連通且所有結(jié)點的度數(shù)全為偶數(shù) D. G連通且至多有兩個奇數(shù)度結(jié)點8.設(shè)圖G<V, E>，vV，則下列結(jié)論成立的是 ( ) A. deg(v)=2|E|B. deg(v)=|E|C. D. 9.以下結(jié)論正確的是( ) A. 無向完全圖都是歐拉圖B. 有n個結(jié)點n1條邊的無向圖都是樹C. 無向完全圖都是平面圖D. 樹的每條邊都是割邊10.圖G如圖三所示，以下說法正確的是 ( ) A. (a, d)是割邊 B. (a, d)是邊割集C. (a, d) ,(b, d)是邊割集 D. (b, d)是邊割集04任務(wù)_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.設(shè)圖G<V, E>，vV，則下列結(jié)論成立的是 ( ) A. deg(v)=2|E|B. deg(v)=|E|C. D. 5.無向圖G存在歐拉回路，當且僅當（ ）.A. G中所有結(jié)點的度數(shù)全為偶數(shù) B. G中至多有兩個奇數(shù)度結(jié)點C. G連通且所有結(jié)點的度數(shù)全為偶數(shù) D. G連通且至多有兩個奇數(shù)度結(jié)點6.以下結(jié)論正確的是( ) A. 無向完全圖都是歐拉圖B. 有n個結(jié)點n1條邊的無向圖都是樹C. 無向完全圖都是平面圖D. 樹的每條邊都是割邊7.若G是一個歐拉圖，則G一定是( ) A. 平面圖B. 漢密爾頓圖C. 連通圖D. 對偶圖8.已知一棵無向樹T中有8個頂點，4度、3度、2度的分支點各一個，T的樹葉數(shù)為( ) A. 8 B. 5 C. 4 D. 39.若G是一個漢密爾頓圖，則G一定是( ) A. 平面圖 B. 對偶圖 C. 歐拉圖 D. 連通圖10.設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r= ( ) A. ev2 B. ve2 C. ev2 D. ev204任務(wù)_0010試卷總分：100 測試時間：0單項選擇題一、單項選擇題（共10道試題，共100分。）1.設(shè)無向圖G的鄰接矩陣為 ，則G的邊數(shù)為( ) A. 1 B. 6C. 7D. 142.無向圖G存在歐拉回路，當且僅當（ ）.A. G中所有結(jié)點的度數(shù)全為偶數(shù) B. G中至多有兩個奇數(shù)度結(jié)點C. G連通且所有結(jié)點的度數(shù)全為偶數(shù) D. G連通且至多有兩個奇數(shù)度結(jié)點3.設(shè)圖G<V, E>，vV，則下列結(jié)論成立的是 ( ) A. deg(v)=2|E| B. deg(v)=|E| C. D. 4.設(shè)G是連通平面圖，有v個結(jié)點，e條邊，r個面，則r= ( ) A. ev2 B. ve2 C. ev2 D. ev25.若G是一個漢密爾頓圖，則G一定是( ) A. 平面圖 B. 對偶圖 C. 歐拉圖 D. 連通圖6.以下結(jié)論正確的是( ) A. 無向完全圖都是歐拉圖 B. 有n個結(jié)點n1條邊的無向圖都是樹C. 無向完全圖都是平面圖 D. 樹的每條邊都是割邊7.已知一棵無向樹T中有8個頂點，4度、3度、2度的分支點各一個，T的樹葉數(shù)為( ) A. 8 B. 5 C. 4 D. 38.設(shè)有向圖（a）、（b）、（c）與（d）如圖四所示，則下列結(jié)論成立的是( ) 圖四 A. （a）是強連通的 B. （b）是強連通的C. （c）是強連通的 D. （d）是強連通的9.圖G如圖二所示，以下說法正確的是 ( ) A. a是割點 B. b, c是點割集 C. b, d是點割集 D. c是點割集10.無向樹T有8個結(jié)點，則T的邊數(shù)為( ) A. 6 B. 7 C. 8 D. 9