1、華南農業大學期末考試試卷（A卷）2011-2012學年第 一 學期 考試科目： 離散結構 考試類型：（閉卷）考試 考試時間：120 分鐘學號 姓名 年級專業 題號一二三四五總分得分評閱人 林旭東 黃華偉 朱梅階 黃沛杰考試注意事項： 本試題分為試卷與答卷2部分。試卷有五大題，共4頁。所有解答必須寫在答卷上，寫在試卷上不得分。得分一、選擇題（本大題共 10 小題，每小題 2 分，共 20 分）1、重言式的否定是（ ）A、重言式 B、矛盾式 C、可滿足式 D、 A-C均有可能2、：在北京工作，：是北京人；則命題“在北京工作的人都是北京人。”可表示為_。A、 B、C、 D、3、設 p:天冷, q:小

2、王穿羽絨服，下列命題中，和命題“只要天冷，小王就穿羽絨服。”一樣符號化為 p®q 的是_。A、如果天不冷，則小王不穿羽絨服。B、小王穿羽絨服僅當天冷的時候。C、除非小王穿羽絨服，否則天不冷。D、只有天冷，小王才穿羽絨服4、下列哪個表達式錯誤_。A、 B、 C、 D、 5、設，定義A上的關系，則R具有的性質為_。A、自反的 B、對稱的C、傳遞的，對稱的 D、傳遞的6、設V=<R*,×>是代數系統, R*為非零實數的集合，×為普通乘法，下面函數中是V 的自同態的是_。A、f(x)=2x B、f(x)= -x C、 f(x)=1/x D、f(x)=x+17、

3、設V=<Z,+>是代數系統, Z為整數的集合，+為普通加法在，則 (-2)-3= _。A、-8 B、8 C、-6 D、68、給定下列各序列，可以構成無向簡單圖的度數序列為_。A、1,1,2,2,3 B、1,1,2,3,3 C、0,1,1,3,3 D、1,3,4,4,59、具有6 個頂點，12條邊的連通簡單平面圖中，次數為3的面有_個。A、5 B、 6C、 7D、 810、在下面所示的4個圖中，_不是單向連通圖。A、B、C、D、得分二、填空題（本大題共 15 空，每空 2 分，共 30 分）1、pq 的主合取范式是_。2、表達式中謂詞的個體域是，將其中的量詞消去，寫成與之等價的命題公

4、式為_。3、若明天是星期一或星期三，我就有課。若有課，今天必備課。我今天下午備課。 所以，明天不是星期一和星期三。 將命題中的4個簡單命題依次符號化為，p：明天是星期一，q：明天是星期三，r：我有課，s：我備課。則推理的形式結構為：前提：_；結論：_。4、的前束范式為：_。5、設R，S是集合上的兩個關系，其中，,則_。6、設偏序集的哈斯圖如右所示，若A的子集，則B的最大下界為_。7、在整數集上定義二元運算，有，則關于運算 的幺元是_。8、設a是12階群的生成元，則a3是 階元素9、若連通平面圖G有4個結點，3個面，則G有 條邊。10、在右邊的PERT圖中，關鍵路徑為_。11、一顆帶權

5、為2,3,5,7,8,9的最優2元樹，其權為_。12、1400 的不同的正因子個數為_。13、滿足等式的非負整數解的個數有_。14、n階無向樹至少有_片樹葉。（n>=2）得分1.5CM三、計算題：（6+4+6+6，共 22 分）1、設A=1, 2, 3, 4，R=<x，y>|xÎA，yÎA且x+y<5（1）寫出R的集合表達式和關系矩陣，畫出R的關系圖。（2）畫出關系R的自反閉包r(R)、對稱閉包s(R)和傳遞閉包t(R)的關系圖。2、分別畫出下面無向圖A的關聯矩陣和有向圖B的鄰接矩陣。v1v2v3v4圖Be1e2e3e5e4v1v2V4V3圖Ae2e

6、1e3e4e53、求下面帶權圖中v1到其它頂點的最短路徑及對應的權。v1v4v2v3v5v631064322244、設有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個城市的且造價最低的鐵路網。四、證明題：（本大題共 4 個小題，每題 6 分，共 24 分）1、用等值演算法證明下面的等值式2、設 A為整數

7、集合，在 A´A上定義二元關系R：<<x,y>,<u,v>>ÎR Û x+y = u+v，證明：R是A´A上的等價關系。3、符號化下列各命題，并說明結論是否有效（用推理規則）。甲乙丙丁四人參加拳擊比賽，如果甲獲勝，則乙失敗；如果丙獲勝，則乙也獲勝，如果甲不獲勝，則丁不失敗。所以，如果丙獲勝，則丁不失敗。4、設<G, *>是群，給定aG，令H=y| y*a=a*y, yG，證明：<H, *>是G的子群。五、應用題（共4分）若有n個人，每個人都恰有三個朋友，則n必為偶數。華南農業大學期末考試參考答案

8、（A卷）得分一、選擇題（本大題共 10 小題，每小題 2 分，共 20 分）1B2D3C4C5B6C7D8B9D10C得分二、填空題（本大題共 15 空，每空 2 分，共 30 分）1、 ¬pq ； 2、； 3、 (pq)r, rs, s ； ¬p ¬q ；4、；5、； 6、 2 ；7、 2 ； 8、 4 ； 9、 5 ； 10、v1v3v7v8； 11、 83 ； 12、 24 ； 13、 165（或，或） 14、 2 得分1.5CM三、計算題：（6+4+6+6，共 22 分）1、 R的集合表達式： R的關系矩陣: R的關系圖： R的自反閉包r(R)關系圖： 對

9、稱閉包s(R)關系圖： 傳遞閉包t(R)關系圖： 2、圖A的關聯矩陣： 圖B的鄰接矩陣： 3、解：用標號法解題如下：r viv1v2v3v4v5v60034¥¥¥13/ v1413¥¥24/ v176¥376/ v31047/ v3959/ v4w034769v1到v2的最短路徑: v1 v2 ，對應的權為3v1到v3的最短路徑: v1 v3 ，對應的權為4v1到v4的最短路徑: v1 v3 v4 ，對應的權為7v1到v5的最短路徑: v1 v3 v5 ，對應的權為6v1到v6的最短路徑: v1 v3 v4 v6 ，對應的權為94、

10、解：將本題用帶權圖來描述，如下圖(a)，于是求解此題便成為求帶權圖的最小生成樹問題。按Kruskal算法，下圖中(b)-(e) 就是求解最小生成樹的過程。總造價=3+4+7+10=24萬元得分四、證明題：（本大題共 4 個小題，每題 5 分，共 20 分）1、 證明：從左邊開始演算: 2、證明：(1)自反性：對于任意的(2)對稱性：對于任意的(3)傳遞性：對于任意的 3、證明：1. 解：設p: 甲獲勝； q：乙獲勝；r：丙獲勝；s：丁不敗（或丁獲勝）。前提為：； 結論為：（1）（2）（3）（4）（5）（6）（7）4、證明： 對于任一aG，e*a=a*e，群G的幺元 e H, 所以H是 G 的非空子集。 任取 a, bH，下面證明 a*b-1與 G 中所有的元素都可交換. "xG，有 (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 =