華南農業大學離散結構期末考試2019答案

華南農業大學期末考試試卷（　a　卷）

2008　學年第二學期考試科目：　　　離散結構考試型別：（閉卷）　　　考試時間：　 120 　分鐘學號姓名年級專業

注意事項：1．考試時間120分鐘，閉卷考試2．試卷共五大題，滿分100分

3．全部答案寫在答題紙上，試卷紙上答題無效一、填空（每空2分，共30分）

1125

3、__； 41

5全為169

725845

910310、；

112rs123

13a14否

15是二、選擇題（每題2分，共30分）

三、計算題（每題6分，共18分）

1、p=1

鄰接矩陣

通路長度小於或等於6的條數為11

2、6階所有非同構的無向樹有6棵

3關係矩陣

關係圖：

傳遞閉包：t(r)=r

四、證明題（每題6分，共18分）

1、證明：設g中兩奇數度結點分別為u 和v，若 u，v不連通，則g至少有兩個連通分支g1、g2 ，使得u和v分別屬於g1和g2，於是g1和g2中各含有1個奇數度結點，這與圖論基本定理矛盾，因而u，v一定連通。

2、由於t為非平凡樹，則n>1，且任何頂點的度數都大於等於1；設t中m條邊，k片樹葉(頂點度數為1)，則其餘n-k個分支點的度數均大於等於2，由握手定理與樹的性質(m=n-1)有：

，顯然k≥2，這說明t至少有兩片樹葉。

3、首先證明r是對稱的

==〉（因為r自反的）==〉（r是迴圈的）即再證r是傳遞的

若根據r是迴圈的可以得到而已經證明r是對稱的，所以可以得到即所以r是傳遞的，得證。

五、應用題（4分）

至少要2次稱重，在天平秤上每次稱重結果有三種可能性。所以稱重序列的決策樹是三元的在決策樹裡至少有8個樹葉，這是因為有8種可能的結果（理論上每枚硬幣都有可能是偽幣）。確定偽幣所需要的最大稱重次數是決策樹的高度。

具體為：

第一次稱重6枚硬幣，再根據相應的結果調整第二次所需要稱重的硬幣。