離散數(shù)學(專升本)階段性作業(yè)３總分：

10０分

考試時間:分鐘單選題1．集合A=｛1,2，…,10｝上的關系R={＜x,y＞｜x＋ｙ=10,x，yA}，則Ｒ的性質為_____。(5分)(A）

自反的（B)

對稱的(C)

傳遞的,對稱的(D)

傳遞參考答案:B２.設G是一個哈密爾頓圖，則Ｇ一定是_＿＿__。（5分）(A)

歐拉圖（B）

樹（C)

平面圖（D)

連通圖參考答案:D3.設G是一棵樹,則G的生成樹有____＿棵。(5分)(A）

0(B)

1(C)

２(D)

不能擬定參考答案：B４．設無向圖G有１6條邊且每個頂點的度數(shù)都是2,則圖G有_＿＿＿_個頂點。(5分）(A)

10(B）

4(Ｃ)

8(D）

16參考答案:D5.連通圖G是一棵樹當且僅當G中_＿_＿_。(５分）(A)

有些邊是割邊(B)

每條邊都是割邊（C）

所有邊都不是割邊（D）

圖中存在一條歐拉途徑參考答案：B6．下列哪一種圖不一定是樹_____。(5分)(A）

無簡樸回路的連通圖（B)

有n個頂點n-１條邊的連通圖（Ｃ）

每對頂點間都有通路的圖(D）

連通但刪去一條邊便不連通的圖參考答案:C多選題7.下面給出的集合中,哪一個是前綴碼__＿＿_。(5分)(Ａ）

{a,ab，1１0，a1b１1｝(B)

｛01,0０1，000，１｝(Ｃ)

{1,2，０0,01，0２10}（Ｄ)

{12,11，101,0０2,０011}參考答案：B,C,D8.集合A上的等價關系有性質＿____(５分）（Ａ)

自反性(B）

對稱性(C)

傳遞性(D)

反自反性參考答案:A,B，Ｃ9．若一棵完全二元(叉）樹有2ｎ-１個頂點,則它的樹葉片數(shù)不為_____。(４分)(A）

n(B)

2n(Ｃ)

n-１（Ｄ）

２參考答案：B,C，D10．設圖G的相鄰矩陣為,則G的頂點數(shù)與邊數(shù)不為下列結果的是__＿__．(4分)(A)

４,５(B)

5,6(Ｃ)

4，10（D）

5,8.參考答案：B，C，D判斷題11.有n個頂點ｎ-１條邊的連通圖是樹。(5分)對的錯誤參考答案：對的解題思緒：12.在有ｎ個頂點的連通圖中，其邊數(shù)最多有ｎ-1條。（5分)對的錯誤參考答案：錯誤解題思緒:13.任一無向圖中，度數(shù)為奇數(shù)的結點有偶數(shù)個。(4分)對的錯誤參考答案：對的解題思緒:14.任何連通無向圖G至少有一棵生成樹。(4分）對的錯誤參考答案:對的解題思緒:1５．集合A上的偏序關系的逆是偏序。(4分)對的錯誤參考答案:對的解題思緒：1６.不存在集合A上的既是等價關系又是偏序關系的例子。（4分）對的錯誤參考答案：錯誤解題思緒：17.集合A上的關系的傳遞閉包是包具有傳遞性的最小關系。(3分）對的錯誤參考答案：對的解題思緒:１8.設集合Ａ＝{1,2,3｝,A上的關系｛（１,１),（2，2),(２,３)，(３,2),(３,3)｝則R不具有對稱性.(３分)對的錯誤參考答案：錯誤解題思緒：填空題19.設G是5個頂點的完全圖，則從G中刪去___＿(１)＿_＿_條邊可以得到樹.(4分)（１）.參考答案:６20.一個圖的哈密爾頓路是一條通過圖中_＿__（2)____的路。(4分）(1）.參考答案：所有結點一次且恰好一次21．一棵無向樹的頂點數(shù)n與邊數(shù)m關系是＿___（3)____。(4分)（１).參考答案:m=n－122．有ｎ個結點的樹,其結點度數(shù)之和是___＿(４)_＿__。（4分)（１）.參考答案:2ｎ-2２3．設G是完全二叉