華南農(nóng)業(yè)大學(xué) 離散結(jié)構(gòu) 期末考試 試卷答案

《華南農(nóng)業(yè)大學(xué) 離散結(jié)構(gòu) 期末考試 試卷答案》由會員分享，可在線閱讀，更多相關(guān)《華南農(nóng)業(yè)大學(xué) 離散結(jié)構(gòu) 期末考試 試卷答案（4頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、華南農(nóng)業(yè)大學(xué)期末考試參照答案（A卷） -第 一 學(xué)期　 考試科目：　 離散構(gòu)造 　　 考試類型：（閉卷）考試　　　 考試時間：　120 　分鐘 學(xué)號 姓名 年級專業(yè) 題號 一 二 三 四 總分 得分 評閱人 考試注意事項(xiàng)： ①本試題分為試卷與答卷2部分。試卷有四大題，共6頁。 ②所有解答必須寫在答卷上，寫在試卷上不得分。 得分 一、選擇題（本大題共 25 小題，每題 2 分，共 50 分） 1 D

2、 2 B 3 C 4 A 5 C 6 C 7 A 8 B 9 B 10 B 11 B 12 A 13 C 14 C 15 C 16 B 17 D 18 D 19 D 20 D 21 A 22 B 23 D 24 C 25 C 得分 1.5CM 二、計(jì)算題：（本大題共 5 個小題，每題 5 分，共 25 分） 1、解： 2、解：(1) 集合的整除偏序關(guān)系的哈斯圖 2 3 6 4 8 9 10 12 (2)集合A沒有的最小元與最

3、大元; 極小元為2,3；極大元為8,9,10,12。 (3)集合的上界為12，下界為2，最小上界12，最大下界2。 3、解：一方面將各邊的權(quán)重按小到大排序：1,2,3,4,5,6,7,8,9 然后使用避圈法得到如下最小生成樹，其總權(quán)重為1+2+4+6+8=21 V1 V2 V6 V3 V5 V4 1 2 4 6 8 4、 5、解：如下幾種狀況： （1）四個不同名次:4!=24 （2）三個不同名次:3！4！/2!/2!=36 （3）兩個不同名次:4+6+4=14 （4）同一種名次：1 一共24+36+14+1=75 得分 三、

4、證明題：（本大題共 4 個小題，每題 5 分，共 20 分） 1、證明：p? (qùr) (p? q) ù(p? r) 2、證： (1)自反性：對于任意的 (2)對稱性：對于任意的 (3)傳遞性：對于任意的 3、證明：由于T為非平凡樹，則n>1，且任何頂點(diǎn)的度數(shù)都不小于等于1；設(shè)T中m條邊，k片樹葉(頂點(diǎn)度數(shù)為1)，則其他n-k個分支點(diǎn)的度數(shù)均不小于等于2，由握手定理與樹的性質(zhì)(m=n-1)有： ， 顯然k≥2，這闡明T至少有兩片樹葉。 4、是一種含幺半群，即獨(dú)異點(diǎn) 證明： 得分 (1) *運(yùn)算滿足封閉性 (2)

5、*滿足結(jié)合律 (a*b)*c=a*(b*c) (3)有單位元，2 由于 a*2= 2*a= (4)有元素不存在逆元 0，因此不是群 四、應(yīng)用題（2選1，兩道題都做僅以第一道算分；5分） 1、基本原則，構(gòu)造的二元樹（二叉樹）存在6片樹葉，再根據(jù)編碼一致原則，如左分支所在的邊上用0表達(dá)，右分支所在的邊用1表達(dá)或相反都可以。 good bye 的編碼根據(jù)所構(gòu)造的二元樹對照編寫 2、構(gòu)造一種圖，頂點(diǎn)表達(dá)課程，邊表達(dá)某兩門課程存在學(xué)生同步選修的情形 則問題轉(zhuǎn)換成圖著色問題，由于圖中存在最大的四階完全子圖（課程1、2、3、4），因此至少要四種顏色表達(dá)，即考試至少要安排在四個不同的時間段