《華南農(nóng)業(yè)大學(xué) 離散結(jié)構(gòu) 期末考試 試卷答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《華南農(nóng)業(yè)大學(xué) 離散結(jié)構(gòu) 期末考試 試卷答案（4頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、華南農(nóng)業(yè)大學(xué)期末考試參照答案（A卷）
-第 一 學(xué)期 考試科目： 離散構(gòu)造
考試類型：（閉卷）考試 考試時(shí)間： 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 個(gè)小題，每題 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）四個(gè)不同名次:4!=24
（2）三個(gè)不同名次:3！4！/2!/2!=36
（3）兩個(gè)不同名次:4+6+4=14
（4）同一種名次：1
一共24+36+14+1=75
得分
三、
4、證明題：（本大題共 4 個(gè)小題，每題 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個(gè)分支點(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á)，即考試至少要安排在四個(gè)不同的時(shí)間段
華南農(nóng)業(yè)大學(xué) 離散結(jié)構(gòu) 期末考試 試卷答案
