《華南農(nóng)業(yè)大學(xué) 離散數(shù)學(xué) 期末考試試卷及答案》由會員分享，可在線閱讀，更多相關(guān)《華南農(nóng)業(yè)大學(xué) 離散數(shù)學(xué) 期末考試試卷及答案（8頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、華南農(nóng)業(yè)大學(xué)期末考試試卷（A卷）
-第 一 學(xué)期 考試科目： 離散構(gòu)造
考試類型：（閉卷）考試 考試時間： 120 分鐘
學(xué)號 姓名 年級專業(yè)
題號
一
二
三
四
五
總分
得分
評閱人
□ 林旭東 □ 黃華偉 □ 朱梅階 □ 黃沛杰
考試注意事項：
①本試題分為試卷與答卷2部分。試卷有五大題，共4頁。
②所有解答必須寫在答卷上，寫在試卷上不得分。
得分
一、選擇題（本大題共 10
2、 小題，每題 2 分，共 20 分）
1、重言式的否認(rèn)是（ ）
A、重言式 B、矛盾式 C、可滿足式 D、 A-C均有也許
2、：在北京工作，：是北京人；則命題“在北京工作的人都是北京人?！笨杀磉_(dá)為______。
A、
B、
C、
D、
3、設(shè) p:天冷, q:小王穿羽絨服，下列命題中，和命題“只要天冷，小王就穿羽絨服?！蓖瑯臃柣癁?p?q 的是______。
A、如果天不冷，則小王不穿羽絨服。
B、小王穿羽絨服僅當(dāng)天冷的時候。
C、除非小王穿羽絨服，否則天不冷。
D、只有天冷，小王才穿羽絨服
4、下列哪個體現(xiàn)式錯誤_____。
3、A、
B、
C、
D、
5、設(shè)，定義A上的關(guān)系，則R具有的性質(zhì)為______。
A、自反的 B、對稱的 C、傳遞的，對稱的 D、傳遞的
6、設(shè)V=是代數(shù)系統(tǒng), R*為非零實數(shù)的集合，×為一般乘法，下面函數(shù)中是V 的自同態(tài)的是______。
A、f(x)=2x B、f(x)= -x C、 f(x)=1/x D、f(x)=x+1
7、設(shè)V=是代數(shù)系統(tǒng), Z為整數(shù)的集合，+為一般加法在，則 (-2)-3= _____。
A、-8 B、8 C、-6 D、6
8、給定
4、下列各序列，可以構(gòu)成無向簡樸圖的度數(shù)序列為______。
A、1,1,2,2,3 B、1,1,2,3,3 C、0,1,1,3,3 D、1,3,4,4,5
9、具有6 個頂點，12條邊的連通簡樸平面圖中，次數(shù)為3的面有______個。
A、5 B、 6 C、 7 D、 8
10、在下面所示的4個圖中，______不是單向連通圖。
A、
B、
C、
D、
得分
二、填空題（本大題共 15 空，每空 2 分，共 30 分）
1、p→q 的主合取范式是____________________。
2、體現(xiàn)式中謂詞的個體
5、域是，將其中的量詞消去，寫成與之等價的命題公式為__________________。
3、若明天是星期一或星期三，我就有課。若有課，今天必備課。我今天下午備課。 因此，明天不是星期一和星期三。?將命題中的4個簡樸命題依次符號化為，p：明天是星期一，q：明天是星期三，r：我有課，s：我備課。則推理的形式構(gòu)造為：前提：______________________________；結(jié)論：_____________________。
4、的前束范式為：____________________。
5、設(shè)R，S是集合上的兩個關(guān)系，其中，,則____________________。
6、設(shè)偏序集
6、的哈斯圖如右所示，若A的子集，則B的最大下界為_____。
7、在整數(shù)集上定義二元運算，有，則有關(guān)運算 的幺元是______。
8、設(shè)a是12階群的生成元，則a3是 階元素
9、若連通平面圖G有4個結(jié)點，3個面，則G有 條邊。
10、在右邊的PERT圖中，核心途徑為______。
11、一顆帶權(quán)為2,3,5,7,8,9的最優(yōu)2元樹，其權(quán)為______。
12、1400 的不同的正因子個數(shù)為______。
13、滿足等式的非負(fù)整數(shù)解的個數(shù)有______。
14、n階無向樹至少有______片樹葉。（n>=2）
得分
1.5CM
三、計算題：（
7、6+4+6+6，共 22 分）
1、設(shè)A={1, 2, 3, 4}，R={|x?A，y?A且x+y<5}
（1）寫出R的集合體現(xiàn)式和關(guān)系矩陣，畫出R的關(guān)系圖。
（2）畫出關(guān)系R的自反閉包r(R)、對稱閉包s(R)和傳遞閉包t(R)的關(guān)系圖。
2、分別畫出下面無向圖A的關(guān)聯(lián)矩陣和有向圖B的鄰接矩陣。
v1
v2
v3
v4
圖B
e1
e2
e3
e5
e4
v1
v2
V4
V3
圖A
e2
e1
e3
e4
e5
3、求下面帶權(quán)圖中v1到其他頂點的最短途徑及相應(yīng)的權(quán)。
v1
v4
v2
v3
v5
v6
3
8、
10
6
4
3
2
2
2
4
4、設(shè)有5個都市，任意兩都市之間的鐵路造價如下（以百萬元為單位）：W(v1, v2)=4, W(v1, v3)=7, W(v1, v4)=16, W(v1, v5)=10, W(v2,v3)=13, W(v2, v4)=8, W(v2, v5)=17, W(v3, v4 )=3, W(v3 ,v5)=10， W(v4, v5)=12。試求出連接5個都市的且造價最低的鐵路網(wǎng)。
四、證明題：（本大題共 4 個小題，每題 6 分，共 24 分）
1、用等值演算法證明下面的等值式
2、設(shè) A為整數(shù)集合，在 A′A上定
9、義二元關(guān)系R：
<,>?R ? x+y = u+v，證明：R是A′A上的等價關(guān)系。
3、符號化下列各命題，并闡明結(jié)論與否有效（用推理規(guī)則）。甲乙丙丁四人參與拳擊比賽，如果甲獲勝，則乙失敗；如果丙獲勝，則乙也獲勝，如果甲不獲勝，則丁不失敗。因此，如果丙獲勝，則丁不失敗。
4、設(shè)是群，給定a∈G，令H={y| y*a=a*y, y∈G}，證明：是G的子群。
五、應(yīng)用題（共4分）
若有n個人，每個人都恰有三個朋友，則n必為偶數(shù)。
華南農(nóng)業(yè)大學(xué)期末考試參照答案（A卷）
得分
一、選擇題（本大題共 10 小題，每題 2 分，共
10、20 分）
1
B
2
D
3
C
4
C
5
B
6
C
7
D
8
B
9
D
10
C
得分
二、填空題（本大題共 15 空，每空 2 分，共 30 分）
1、 ?p∨q ； 2、；
3、 (p∨q)→r, r→s, s ； ?p∧ ?q ；4、；
5、； 6、 2 ；7、 2 ；
8、 4 ； 9、 5 ； 10、v1v3v7v8；
11、 83 ； 12、 24 ； 13、 165（或
11、，或） 14、 2
得分
1.5CM
三、計算題：（6+4+6+6，共 22 分）
1、 R的集合體現(xiàn)式：
R的關(guān)系矩陣: R的關(guān)系圖：
R的自反閉包r(R)關(guān)系圖： 對稱閉包s(R)關(guān)系圖： 傳遞閉包t(R)關(guān)系圖：
2、圖A的關(guān)聯(lián)矩陣： 圖B的鄰接矩陣：
3、解：用標(biāo)號法解題如下：
r vi
v1
v2
v3
v4
v5
v6
0
0
3
12、4
￥
￥
￥
1
3/ v1
4
13
￥
￥
2
4/ v1
7
6
￥
3
7
6/ v3
10
4
7/ v3
9
5
9/ v4
w
0
3
4
7
6
9
v1到v2的最短途徑: v1 v2 ，相應(yīng)的權(quán)為3
v1到v3的最短途徑: v1 v3 ，相應(yīng)的權(quán)為4
v1到v4的最短途徑: v1 v3 v4 ，相應(yīng)的權(quán)為7
v1到v5的最短途徑: v1 v3 v5 ，相應(yīng)的權(quán)為6
v1到v6的最短途徑: v1 v3 v4 v6 ，相應(yīng)的權(quán)為9
4、
13、解：將本題用帶權(quán)圖來描述，如下圖(a)，于是求解此題便成為求帶權(quán)圖的最小生成樹問題。按Kruskal算法，下圖中(b)-(e) 就是求解最小生成樹的過程。
總造價=3+4+7+10=24萬元
得分
四、證明題：（本大題共 4 個小題，每題 5 分，共 20 分）
1、 證明：從左邊開始演算:
2、證明：
(1)自反性：對于任意的
(2)對稱性：對于任意的
(3)傳遞性：對于任意的
3、證明：1. 解：設(shè)p: 甲獲勝； q：乙獲勝；r：丙獲勝；s：丁不?。ɑ蚨～@勝）。
前提為：；； 結(jié)論為：
（1）
（2）
（3）
（4）
14、
（5）
（6）
（7）
4、證明： 對于任一a∈G，e*a=a*e，群G的幺元 e ∈H, 因此H是 G 的非空子集。
任取 a, b∈H，下面證明 a*b-1與 G 中所有的元素都可互換.
"x∈G，有
(a*b-1) *x = a*b-1*x = a*b-1* (x-1) -1 = a* (x-1*b) -1 = a* (b*x-1) -1
= a* (x*b-1) = (a*x) *b-1 = (x*a) *b-1 = x* (a*b-1)
由此可知，a*b-1 ∈H
由子群鑒定定理可知是G的子群。
得分
五、應(yīng)用題：（共4分）
證明：證明：將每個人用結(jié)點表達(dá)，當(dāng)兩個人是朋友時，則相應(yīng)兩結(jié)點連一條邊，則得一無向圖。由于每個人恰有三個朋友，因此，，由任意圖奇數(shù)度結(jié)點一定是偶數(shù)個，可知，此圖結(jié)點數(shù)一定是偶數(shù)。
華南農(nóng)業(yè)大學(xué) 離散數(shù)學(xué) 期末考試試卷及答案
