1、u 離 散 數 學 試、填空 20% （每小題2分)1 .設 A x|(xN)且(x 5), B x|x E 且x7 （ N :自然數集，E+正偶數）則2. A, B, C表示三個集合，文圖中陰影部分的集合表達式為3 .設P, Q的真值為0, R, S的真值為1,則(P (Q (R P) (R S)的真值=4 .公式（P R） （S R）P的主合取范式為5,若解釋I的論域D僅包含一個元素，則 xP（x） xP（x）在I下真值為6.設A=1 , 2, 3, 4, A上關系圖為貝ij R2 =設A=a , b, c, d,其上偏序關系 R的哈斯圖為7.O,A上二元運算如下:dc,*abcdaabc

2、dbbcdaccdabddabc,有逆元的元素為那么代數系統 <A ,*的幺元是,它們的逆元分別10.下圖所示的偏序集中，是格的為二、選擇 20% （每小題2分）1、下列是真命題的有（A. a可;B. , ；C. ，;D. 。2、下列集合中相等的有()A. 4, 3； B. , 3, 4; C. 4, 3, 3 ; D. 3,4。3、設A=1 , 2, 3,則A上的二元關系有()個。A.23 ； B,32 ； C,23 3; D.32 2 o4、設R, S是集合A上的關系，則下列說法正確的是()A.若R, S是自反的，則R S是自反的；B.若R, S是反自反的， 則R S是反自反的；C.

3、若R, S是對稱的，則R S是對稱的；D.若R, S是傳遞的，則R S是傳遞的。5、設A=1 , 2, 3, 4, P (A) (A的募集)上規定二元系如下R s，t |s，t P(A)(|s| |t|則 P (A) / R=()A. A; B. P(A) ;C. 1, 1 , 2 , 1 , 2, 3 ,1 , 2,3, 4;D. , 2 , 2, 3, 2 , 3, 4 , A06、設A=, 1 , 1 , 3, 1 , 2, 3則A上包含關系“”的哈斯圖為()7、下列函數是雙射的為()A. f : IE ,f (x) = 2x；B. f : NN N,f (n) = n , n+1；C.

4、 f : RI ,f (x) = x;D. f :IN, f (x)= | x |。(注：I一整數集，E偶數集，N 一自然數集，R實數集)8、圖中從V1到V3長度為3的通路有()條。A .0; B.1;C.2;D,3。9、下圖中既不是 Eular圖，也不是 Hamilton圖的圖是()10、在一棵樹中有 7片樹葉，3個3度結點，其余都是 4度結點則該樹有()個4度結點。A.1; B.2; C. 3; D.4。三、證明 26%1、R是集合X上的一個自反關系，求證：R是對稱和傳遞的，當且僅當 a, b 和a , c在 R 中有 .b , c在 R 中。(8 分)2、f和g者B是群G1 .到 G2,

5、 *的同態映射，證明 C , 是61, 的一個子群。其中C=x|x G1 且f(x)g(x) (8 分)k(v 2) e2-3、G=V, E (|V| = v,|E|二e )是每一個面至少由 k (k 3)條邊圍成的連通平面圖，則 k 2由此證明彼得森圖(Peterson)圖是非平面圖。(11分)四、邏輯推演 16%用CP規則證明下題(每小題8分)ABC D,D E F A F2、x(P(x) Q(x)xP(x)xQ(x)五、計算 18%1、設集合 A=a , b, c,d上的關系R=<a , b > ,< b , a > ,< b, c > , <

6、c , d > 用矩陣運算求出R的傳遞閉包t(R)。(9分)2、如下圖所示的賦權圖表示某七個城市v1,v2, ,v7及預先算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間能夠通信而且總造價最小。(9分)試卷一答案: 一、填空20% （每小題2分）1、0,1, 2, 3, 4, 6;2、(B C) A； 3、1；4、(P S R) ( P S R)； 5、1; 6、Ia ; 8、a , b , c ,d ； a , d , c , d ； 10、a,b, c X 若 < a, b >, < a,c >R 由 R 對稱T知 < b,a &g

7、t;, < Ga<1,1>, <1,.3>, <2,2>, <2,4> ； 7、<a.b>,<a,c>,<a,d>,<b,d>,<c,d>9、a ；二、選擇 20% （每小題 2分）題目12345678910答案C DB、CCADCADBA三、證明 26%1、證:得 < b,c >< a,b >若 < a,b>2、 證若 < a, b > RR < b,a >R < b, c >a,b Ca,c> R 有

8、所以R是對稱的則 <b,a>< b, c > Rb,cf(a)任意a,b X ,因<a,a> R 若< a,c > R即R是傳遞的。g(a), f(b) g(b)f(b 1)f 1(b),g(b1)g 1(b) f(b1)f 1(b)g 1(b) g(b 1)f(a”1-)f(a)*1f (b)1g(a)*g(b )g(ab 1)a* b 1< C , > 是< Gi , *>的子群。3、證:r2ed(Fi)設G有r個面，則 i 1rk，即2e re -即得 k 2 。（8分）k（v 2）e 彼得森圖為k 5，e 15，v

9、 10,這樣 k 2不成立,所以彼得森圖非平面圖。（3分）邏輯推演16%1、證明：AA B A B CDC DDD ED E FFA F2、證明P (附加前提)TIPTITITIPTICPQ(x) xP(x) P(c) x(P(x)P （附加前提）USP P(c) Q(c)USQTI xQ(x)UG xP(x) xQ(x) cp三、計算18%10 100 10 10 0 0 00 0 0 01、解：0 10 010 10MrM - M r M r0 0 0 1R0 0 0 00 10 1M R3 M R2 MRRR10 100 0 0 00 0 0 0M A M R3MRRR1 0 10 1

10、00 0 00 0 0010 M t(R)0M R M R2M R3 M R4111111110 0 0 10 0 0 0t (R尸<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c , d > 2、解：用庫斯克(Kruskal)算法求產生的最優樹。算法略。結果如圖：樹權 C(T)=23+1+4+9+3+17=57 即為總造價。試卷二試題與答案 一、填空

11、20% （每小題2分）1、P：你努力，Q：你失敗。“除非你努力，否則你將失敗”的翻y譯為; “雖然你努力了，但還是失敗了”的翻譯為2、論域D=1 , 2,指定謂詞PP (1,1)P (1,2)P (2,1)P (2,2)TTFF則公式 x yP（y,x）真值為 。2、設5=但1 , a2 ,，a8, Bi是S的子集，則由 B31所表達的子集是3、設A=2 , 3, 4, 5, 6上的二元關系R x, y | x y x是質數，則R= （列舉法）。R的關系矩陣M r=5、設A=1 , 2, 3,則 A上既不是對稱的又不是反對稱的關系R= ; A上既是對稱 的又是反對稱 的關系R= 0aabc6、

12、設代數系統<A, *>,其中A=a , b, c,則幺元是;是否有募等性；是否有對稱bbbc性。cccb7、4階群必是群或群。8、下面偏序格是分配格的是O9、n個結點的無向完全圖 Kn的邊數為,歐拉圖的充要條件是10、公式 （P （ p Q） （ p Q） R的根樹表示為、選擇20% （每小題2分）1、在下述公式中是重言式為（A. (PQ) (PQ) ; B.(PQ) (P Q)(QP).C. (PQ) Q；(P Q)2、命題公式P Q)P)中極小項的個數為（成真賦值的個數為（B. 1;C.2；3、設 S ,1,1,2,則2s）個元素。A. 3;B. 6; C.7；4、設S 1,

13、2,3,定義S S上的等價關系R a,bc,d | a,bS S,c, d S S, ac則由R產生的S S上一個劃分共有（）個分塊。B. 5; C.6；5、設 S 1,2, 3 , S上關系R的關系圖為則R具有（）性質。A.自反性、對稱性、傳遞性;B.反自反性、反對稱性;C.反自反性、反對稱性、傳遞性;D.自反性6、設為普通加法和乘法，則（S,是域。QB. Sx|2n , a,b ZC S x| x2n1, n Zx| xZ x 0= n7、下面偏序集（能構成格。8、在如下的有向圖中，從V1到V4長度為3的道路有（）條。B. 2;C. 3;9、在如下各圖中（）歐拉圖合,，為普通乘法，則代數系

14、統A.群;B .獨異點;C.半群CD）10、設R是實數集三、證明46%1、設R是A上一個二元關系,S a,b |（a,b A）（對于某一個 cA,有 a,cR且c,b R)試證明若R是A上一個等價關系，則 S也是A上的一個等價關系。9分）2、用邏輯推理證明:所有的舞蹈者都很有風度，王華是個學生且是個舞蹈者。因此有些學生很有風度。(11分)3、若f :A B是從 a 到 b 的函數，定義一個函數gA B 2對任的單射。(10g(b) x|(x A) (f(x)b)，證明：若f是A至ijB的滿射，則分)4、若無向圖G中只有兩個奇數度結點，則這兩個結點一定連通。(8分）1m (n 1)( n 2)

15、25、則G是Hamilton圖(8分)設G是具有n個結點的無向簡單圖，其邊數2四、計算14%1、設Z6, + 6是一個群，這里有子群及其相應左陪集。(+ 6是模6 加法,Z6=0 , 1 , 2 , 3,4, 5,試求出 <Z6,+6> 的所7分）2、權數 1, 4, 9, 16, 25,36, 49,64, 81, 100構造一棵最優二叉樹。7分）試卷二答案：一、填空20% (每小題2分)B31B00011111 a4 , a5, a6 , a7 ,a84R=<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,&

16、lt;3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,605、R=<1,2>,<1,3>,<2,1> ; R=<1,1>,<2,2>,<3,3>6、a ；否；有7、Klein四元群;循環群8、B9、1 n(n 1)2；圖中無奇度結點且連通10、選擇20% (每小題 2分)題目12345678910答案B、D

17、D; DDBDABBBB、C三、 證明46%1、( 9 分)(1) S自反的a A,由 R 自反， (a,a R) ( a,a(2) S對稱的(3) S傳遞的由(1)、(2)、(3)得；S是等價關系。2、11 分證明：設P(x): x是個舞蹈者；Q(x) : x很有風度;上述句子符號化為：前提：x(P(x) Q(x)、S(a) P(a)結論：R), a, a SS(x) : x是個學生；a：王華x(S(x) Q(x) S(a) P(a)P x(P(x) Q(x)P P(a) Q(a)usP(a)TIQ(a).TIS(a)TI S(a) Q(a)TI x(S(x) Q(x)eg 3、1 0 分證

18、明：b1,b2 B,(b1 b2) f 滿射a1,a2 A11分由h,b2任意Tt知，g為單射4、8分證明：設G中兩奇數度結點分別為 u和v,若 得u和v分別屬于Gi和G2,于是Gi和G2中各含有 一定連通。u, v不連通，則 G至少有兩個連通分支 Gi、G2 ,使1個奇數度結點，這與圖論基本定理矛盾，因而u, v5、8分反證法：若存在兩結點m點的簡單圖，它的邊數u, v不相鄰且d(u)12(n 1)(n 2) 2證明： 證G中任何兩結點之和不小于nd(v) n 1,令V1 u，v,則 G-Vi 是具有 n-2 個結1(n 1) m -(n 2)(n 3) 1，可得 2,這與Gi=G-V i為

19、n-2個結點為簡單圖的題設矛盾，因而 G中任何兩個相鄰的結點度數和不少于n所以G為Hamilton圖.四、 計算14%d1、7分解：子群有 <0,+ 6>； <0,3,+ 6>； <0,2,4,+6>； <Z6,+ 6>0的左陪集：0 , 1 ; 2 , 3 ; 4 , 50 , 3的左陪集：0 , 3 ; 1 , 4 ; 2 , 50 , 2 , 4的左陪集：0 , 2 , 4 ; 1 , 3 , 5Z6的左陪集：Z6。2、7分試卷三試題與答案填空20% （每空2分）1、設f, g是自然數集N上的函數 x N， f (x) x 1， g(x)

20、2x,則 f g(x) 。2、設 A=a , b, c , A 上二元關系 R=< a, a > , < a, b >,< a, c >, < c, c>,貝1J s ( R)=。3、A=1 , 2, 3, 4, 5, 6 , A上二元關系T x, y | x y是素數，則用列舉法T= ；T的關系圖為 ；T具有 性質。4、集合 A ,2,2的募集 2A= 。5、P, Q 真值為 0 ; R, S 真值為 1。則 wff (P (R S)(P Q) (R S)為 。6、wff (P Q) R)R的主合取范式為。則謂詞7、設P (x) : x是素數，

21、E(x) : x是偶數，O(x) : x是奇數 N (x,y) : x可以整數 y。wff x(P(x)y(O(y) N(y,x)的自然語言是 。8、謂tuwff x y( z(P(x,z) P(y,z) uQ(x,y,u)的前束范式為選擇20% （每小題2分）1、下述命題公式中，是重言式的為（）a、(P q)(P q)；b、(Pq) (pq) (qp) ；c、（p q） q； d、（p p） q。2、wff （p q） r的主析取范式中含極小項的個數為（）A、2;B、 3;C、5; D、0; E、 8。3、給定推理 x(F(x)G(x)USPES?F(y) G(y) xF(x) F(y)G（

22、 y）TI xG（x）UG 推理過程中錯在（）。A、-> ； B、-> ；C、-> ;D、-> ； E、-> 4、設 S仁1 , 2,，8, 9, S2=2, 4, 6, 8, S3=1 , 3, 5, 7, 9, 8=3 , 4, 5,S5=3 , 5,在條件X &且XS3下X與（）集合相等。A、X=S2或 S5； B、X=S4 或 S5；C、X=Si, S2或S4；D、X與Si,，S5中任何集合都不等。5、設R和S是P上的關系，P是所有人的集合，R X,y |X, y P x是y的父親,S x,y |x, y P x是y的母親則$1 R表示關系（）。A

23、x, y |x,yPx是y的丈夫;B、x, y | x,yPx是y的孫子或孫女;C、.D、x,y|x,y P x是y的祖父或祖母。6、 下面函數（）是單射而非滿射。A、 f : R R, f （x） x2 2x 1；B、 f :Z R, f（x） lnx；C、f:R乙f（x） x,x表示不大于x的最大整數；f : RR,f （x） 2x 1 。D、 。其中R為實數集，Z為整數集，R+, Z+分別表示正實數與正整數集。7、 設 S=1 ， 2， 3， R 為 S 上的關系，其關系圖為則 R 具有（）的性質。A 、 自 反、對稱、傳遞；B 、什么性質也沒有；C、反自反、反對稱、傳遞；D、自反、對稱

24、、反對稱、傳遞。8、 設 S ,1, 1, 2 ，則有（） S。A、 1,2； B、 1,2 ； C、 1 ； D、 2 。9、 、設 A=1 ,2 ,3 ，則 A 上有（）個二元關系。2332A、 23 ；B、 32 ；C、 2 ； D、 2 。10、全體小項合取式為（）。A、可滿足式；B、矛盾式； C、永真式； D、A, B, C都有可能用CP規則證明16% （每小題8分）1、AB CD, DE F A F2、x（P（x） Q（x）xP（x） xQ（x）四、（14%集合 X=<1,2>, <3,4>, <5,6>, R=<<x i,yi>

25、;,<x2,y2>>|xi+y2 = x2+yi1、證明R是X上的等價關系。（10分）2、求出X關于R的商集。（4分）五、（10%設集合 A= a ,b , c , d 上關系 R=< a, b > , < b , a > , < b , c > , < c , d >要求1、寫出R的關系矩陣和關系圖。（4分）2、用矩陣運算求出 R的傳遞閉包。（6分）六、（20%1、（ 10分）設f和g是函數，證明 f g也是函數。2、（10 分）設函數 g:S T f :T答案：五、填空20% （每空2分）S，證明 f : TS有一左逆函數當

26、且僅當 f是入射函數。2(x+1);2 a,a , a,b , a,c , c,c , b,a , c,a ；3 、 2,1 , 3,1 , 5,14、反對稱性、反自反性；6 （P Q R）6奇數且y整除x ； 8、,4,24、題目12345678910答案CCCCABDADC六、選擇20% （每小題 2分）七、證明16%（每小題8分）1、P （附加前提）TIDAB CDPC DTIDTID ETID E FPFTIA FCP2、(xP(x)P (附加前提) x( P(x)TE P(a)E電 x(P(x) Q(x)P P(a) Q(a)US Q(a)TI xQ(x)EGD(xP(x)xQ(x)

27、CP八、14%(1)證明：1、自反性：x，yX, 由于x y x y2、對稱性：x1, y1X ,x2 , y2 X3、傳遞性：x1, y1X ,x2,y2Xx3,y3 X即 x1y3 x3y1由(1) (2) ( 3)知：R是X上的先等價關系2、X/R= 1，2 r關系圖九、10%0 10 0Mr10 100 0 0 10 0 0 01、0M-MRMRR R R02、t (R尸<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b ,

28、c . > , < b , d > , < c , d > 六、20%1、 ( 1)x, y |x,y |x x,y |xx domfdomfdomfdomgx domg domg yy h(x)y f (x) y g(x) f(x) g(x)f(x) g(x)g也是函數2、證明:故g f是入射，所以f是入射即若f入射,必能構造函數g,使g為f左逆函數 試卷四試題與答案填空10% (每小題2分)1、若P, Q,為二命題，PQ真值為 0當且僅當 。2、命題“對于任意給定的正實數，都存在比它大的實數”令 F(x) : x為實數，L(x, y): x y則命題的邏 輯謂

29、詞公式為 。3、謂詞合式公式xP(x) xQ(x)的前束范式為 。4、將量詞轄域中出現的 和指導變元交換為另一變元符號，公式其余的部分不變，這種 方法稱為換名規則。5、設x是謂詞合式公式 A的一個客體變元， A的論域為D, A(x)關于y是自由的，則 被稱為存在量詞消去規則，記為ESo、 選擇25% (每小題2.5分)1、下列語句是命題的有()。A、明年中秋節的晚上是晴天；B、x y 0；C、xy 0當且僅當x和y都大于0; D、我正在說謊。2、下列各命題中真值為真的命題有()。A、2+2=4當且僅當 3是奇數；B、2+2=4當且僅當3不是奇數；C、2+2 w 4當且僅當3是奇數； D、2+2

30、 w 4當且僅當3不是奇數;3、 下列符號串是合式公式的有(A、Q； B、 PP Q； C、 ( P Q) (P Q)； D、(P Q)4、下列等價式成立的有()。A、P QQ P ； B 、 P (P R) R ；C、P (P Q) Q ；D、 P (Q R) (P Q) R5、若 A1, A2An 和 B 為 wff,且 A1A2AnB 則()。A、稱 A1A2An為B的前件；B、稱B為A1, A2 An的有效結論C、當且僅當A1A2An B F ； D 、當且僅當A1A2An6、 A， B 為二合式公式，且A B ，則(- . * *A、 AB為重百式；B、A B ；)。C、 A B ；

31、*D、 A B ；E 、 A B 為重言式。7、 “人總是要死的”謂詞公式表示為( )。M(x) ： x 是人； Mortal(x) ： x 是要死的。A、 M (x) Mortal (x)；B、 M (x) Mortal (x)C、x(M (x) Mortal (x) ； D、x(M (x) Mortal (x)8、 公式 A x(P(x) Q(x) 的解釋 I 為： 個體域 D=2 ， P(x)： x>3, Q(x) ： x=4 則 A 的真值為 (C、可滿足式A、 1； B、 0；9、 下列等價關系正確的是(A、 x(P(x) Q(x)A、B、 x(P(x)Q(x)C、 x(P(x

32、)Q)D、 x(P(x)Q)10、 、 下列推理步驟錯在( x(F(x) G(x) F (y) G(y) xF (x) F(y) G(y) xG(x)A、；B、；D 、無法判定。)。xP(x) xQ(x)；xP(x) xQ(x) ；xP(x) Q ；xP(x) Q。)。PUSPESTIEGC、；D、三、邏輯判斷30%1、用等值演算法和真值表法判斷公式A (P Q) (Q P) (P3的類型。(10分)2、下列問題，若成立請證明，若不成立請舉出反例：(10分)(I) 已知A C B C,問AB成立嗎？(2)已知 A B,問A B成立嗎？3、如果廠方拒絕增加工資，那么罷工就不會停止，除非罷工超過一

33、年并且工廠撤換了廠長。問：若廠方拒絕增加工資，面罷工剛開始，罷工是否能夠停止。(10分)四、計算10%1、設命題A1, A2的真值為1, A3, A4真值為0,求命題( Al (A2(A3A1) (A2A4)的真值。(5 分)2、利用主析取范式，求公式(P Q) Q R的類型。(5分)五、謂詞邏輯推理 15%符號化語句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證 其結論。六、證明：(10%)設論域 D=a , b , c，求證：xA(x) xB(x)x(A(x) B(x)答案：十、填空10% (每小題2分)1、P 真值為1,Q 的真值為 0;2、x(F(x)L(x，0)

34、y(F(y)L(y，x)；3、x(P(x)Q(x)；4、約束變元；5、 xA(x)A(y), y為D的某些元素。選擇25% (每小題2.5分)題目12345678910答案A,CA,DC,DA,DB,Ca,b,c,d,eCAB(4)十二、邏輯判斷 30%1、(1)等值演算法(2)真值表法P QA1 1111111 0010010 1100010 011111所以A為重言式2、(1)不成立。若取CT 則AT TBT T有AC但A與B不一定等價，可為任意不等價的公式。(2)成立證明:充要條件T ( A B) ( B 即： (B A) ( A B)A) (A B) (B A)(A B) (B A)

35、A BQ:罷工停止；R罷工超壺過一年；R:撤換廠長P, R結論：QPPTIPTIMeTI(1 1) (1 (10)111所以A B T故 A B3、解：設P：廠方拒絕增加工資；前提：P (RS)Q)，P ( (R S) Q)P(R S) QRR S(R S)Q罷工不會停止是有效結論。四、計算io%(1 (10 0)(1)解：(1 0) i i它無成真賦值，所以為矛盾式。五、謂詞邏輯推理 15%解：M(x):x是人；F(x):x是花;G(x): x是雜草；H (x, y): x喜歡y證明: x(M (x) y(F(y) H(x, y) M(a) y(F(y) H(a,y)ESM (a)T(2)I

36、2)1PUSTITEUS (4)US (8)T(9)(10) IUG (ID(4)y(F(y) H(a,y) x(M(x)y(G(y)H(x,y) M(a) y(G(y) H(a,y) y(G(y)H(a,y)(8)y(H(a,y) G(y) F(z) H(a,z)(io)H(a,z) G(z)(II) F (z) G(z) x(F(x) G(x)十三、 證明10%試卷五試題與答案1、設G為9階無向圖，每個結點度數不是5就是6,則G中至少有 個5度結點,條,+ , 為環。、填空15% (每空3分) 則稱R,5、設L, , 是代數系統，則L, , 滿足募等律，即對a L有、選擇15% (每小題3

37、分)1、下面四組數能構成無向簡單圖的度數列的有()A、(2, 2, 2, 2, 2) ;B、( 1,1,2,2,3);C、( 1, 1, 2, 2, 2) ;D、(0,1,3,3,3)。2、下圖中是哈密頓圖的為(3、如果一個有向圖 D是強連通圖，則 D是歐拉圖，這個命題的真值為（）A、真；B、假。4、下列偏序集（）能構成格。S5、設1,2,2,3i，3,4,4*為普通乘法，則S, *是（）A、代數系統； B、半群；C、群； D、都不是三、證明 48%1、（10%）在至少有2個人的人群中，至少有 2個人，他們有相同的朋友數。2、（8%）若圖G中恰有兩個奇數度頂點，則這兩個頂點是連通的。3、（8%

38、）證明在6個結點12條邊的連通平面簡單圖中，每個面的面數都是 3。4、（10%）證明循環群的同態像必是循環群。5、（12%）設B, , ,0,1是布爾代數，定義運算 "*b （a b） （a b）,求證B , *是阿貝爾群。四、計算22%1、在二叉樹中1）求帶權為2, 3, 5, 7, 8的最優二叉樹 To （5分）2）求T對應的二元前綴碼。（5分）2、下圖所示帶權圖中最優投遞路線并求出投遞路線長度（郵局在D點）。答案：一、填空（15%每空3分1、 6;2、n；3、2;4、+對分配且對+分配均成立；5> a a a且a a a。二、選擇（15%每小題3分題目12345答案A,B

39、B,DBCD三、證明（48%，Vn,設1、（10分）證明：用n個頂點vi,，vn表示n個人，構成頂點集V=v 1 ,E uv|u,v V,且 U,V是朋友（U V）,無向圖 G= （V, E）現證G中至少有兩個結點度數相同。事實上，(1)若G中孤立點個數大于等于2,結論成立。(2)若G中有一個孤立點， 則G中的至少有3個頂點，既不考慮孤立點。 設G中每個結點度數均大于等于 1 , 又因為G為簡單圖，所以每個頂點度數都小于等于n-1,由于G中n頂點其度數取值只能是 1, 2,，n-1,由鴿巢原理，必然至少有兩個結點度數是相同的。2、(8分)證：設 G中兩個奇數度結點分別為u, v。若u, v不連

40、通則至少有兩個連通分支Gi、G2,使得u,v分別屬于Gi和G2。于是Gi與G2中各含有一個奇數度結點，與握手定理矛盾。因而 u, v必連通。3 (8 分)證：n=6,m=12 歐拉公式 n-m+f=2 知 f=2-n+m=2-6-12=8由圖論基本定理知：deg(F) 2 m 24 ； wdeg(Fi) 3 所以必有 deg(Fi ) 3,即每個面用 3條邊 圍成。 n m4 (10分)證：設循環群A, 的生成元為a,同態映射為f,同態像為f (A) , *,于是 a ,a A都有 f(an am) f(an)* f(am)對n=1有f f-22n=2,有 f(a ) f(a a) f(a)*

41、 f (a) (f(a)k 1, k 1若 n=k-1 時 有 f(a ) (f(a)k _ k 1_ k 1k 1k對 n=k 時，f(a ) f(a a) f(a )* f(a) (f(a)* f(a) (f(a)這表明，f(A)中每一個元素均可表示為(f (a)n ,所以f(A),*為f(a)生成的循環群。5、證：(1)交換律：a,b B 有 a*b (a b) (a b) (b a) (b a) b* a(2) 結合律：a,b,c B有而：(3) 幺： a B有(4)逆：a b a* a (a a) (a a) 0 0 0 綜上所述：B, *是阿貝爾群。四、計算(22%1、(10 分)

42、(1) (5分)由Huffman方法，得最佳二叉樹為：(2) (5 分)最佳前綴碼為：000, 001, 01, 10, 112、(12 分)B . 1to F圖中奇數點為 E、F , d(E)=3,d(F)=3,d(E,F)=28 p=EGF由D開始找一條歐拉回路：DEGFGEBACBDCFD。道路長度為：35+8+20+20+8+40+30+50+19+6+12+10+23=281試卷六試題與答案填空15% （每小題3分）1、n階完全圖結點 v的度數 d（v） = 。2、設n階圖G中有m條邊，每個結點的度數不是k的是k+1 ,若G中有Nk個k度頂點，Nk+1個k+1度頂點，則N k = 。

43、3、算式（a （b*c）*d）仁*與的二叉樹表示為4、如圖給出格 L,則 e的補元是 。5、一組學生，用二二扳腕子比賽法來測定臂力的大小，則幺元是、選擇15% （每小題3分）1、設S=0,1,2,3,為小于等于關系，則 S, <是（）A、群；B、環；C、域；D、格。2、設a , b , c , *為代數系統，*運算如下:*abcaabcbbaccccc則零元為（）。A、a； B、b； C、c；D、沒有。）4度結點）時，A , +, 是整環3、如右圖相對于完全圖 K5的補圖為（）。4、一棵無向樹 T有7片樹葉，3個3度頂點，其余頂點均為 4度。則T有（A、1; B、2;C、3; D、4。5

44、、設A, +, 是代數系統，其中+, 為普通加法和乘法，則 A=（A、x|x 2n,n Z ；b、x|x 2n 1,n Z；C x|x 0,且x Z ；D、x|x a b4',5, a ,b R三、證明50%2nm -2),則G是連通圖。(10分)0,1,+, 的加法運算和乘法運算。如下:1、設G是(n,m)簡單二部圖，則 4。( 10分)m - (n 1)(n2、設G為具有n個結點的簡單圖，且 23、記“開”為1, “關”為0,反映電路規律的代數系統證明它是一個環,4、L,是一代數格，V 為自然偏序，則L,是偏序格。(16分)四、10%設E(x1,x2,x3) (x1 x2) (x2

45、 x3) (x2 x3)是布爾代數0,1,上的一個布爾表達式,試寫出E(x1,x2,x3)的析取范式和合取范式(10分)五、10%如下圖所示的賦權圖表示某七個城市Vi，V2， , v7及預先算出它們之間的一些直接通信成路造價(單位：萬元)，試給出一個設計方案，使得各城市之間既能夠通信又使總造價最小。答案：、填空15% (每小題3分)1、n-1； 2、n(k+1)-2m ； 3、如右圖；4、0 ； 5、臂力小者二、選擇 15% (每小題 3分)題目12345答案DCAAD三、證明(1)E50%證：設G=(V,)m n1對完全二部圖有n2n1(n n1)2n1/ n 2nn(n1-)2nn1當 2

46、時，完全二部圖(n ,m)的邊數m有最大值4m故對任意簡單二部圖（n ,m）有（2）證：反證法：若 G不連通，不妨設G可分成兩個連通分支G1、G2,假設和G2的頂點數分別為n1和n2,顯然n1n2 n與假設矛盾。所以 G連通。(3)(1) 0 , 1, +, 是環0 , 1, +是交換群乘：由“ +”運算表知其封閉性。由于運算表的對稱性知:+運算可交換。群： (0+0) +0=0+ (0+0) =0 ； (0+0) +1=0+ (0+1)=1 ；(0+1) +0=0+ (1+0) =1 ；(0+1) +1=0+ (1+1)(1+1 ) +1=1+ (1+1 ) =0結合律成立。幺：幺元為 0。

47、逆：0, 1逆元均為其本身。0 , 1, 是半群乘：由耍”運算表知封閉群： (0-0) 0=0 - (0-0) =0 ; (0-0) - 1=0 -(0 1) - 0=0 - ( 1 0) =0 ;. 1) =0；(1-1) 1=1 - ( 1 1) =0對+的分配律x, y0,10 - (x+y ) =0=0+0=(0x)+(0 - y);x=y (x+y)=0所以(x y)x,y,z同理可證：（x1)0,1均有zy) z (x(xz)y)(y(1 0)(1 1)(z x)z)(1(1(z0)(11)x) (1 y)y)所以對+是可分配的。由得，0,1,+, 是環。(2) 0 , 1, +, 是域因為0 , 1, +, 是有限環，故只需證明是整環即可。乘交環：由乘法運算表的對稱性知，乘法可交換。含幺環：乘法的幺元是1無零因子：1 1=1 /0因此0 , 1, +, 是整環，故它是域。4、證：(1)是偏序關系,a,b Laba反自反性：由代數格募等關系：a a a a a反對稱性:a,b L 若 a b ,b a 即.a b a, b則 a a b b a b b a傳遞性：a b,b c則:(2) x，y L 在L中存在x,y的下(上)確界設 X, y L 則：x y infx, y事實上：x (x y) (x x) y