(完整word版)離散數學試卷及答案(14)

1、離散數學試卷（十四） 89 填空10% （每小題2分） 1、 設 A, 是由有限布爾格 A, 誘導的代數系統(tǒng)，S 是布爾格 A,，中 所有原子的集合，貝 y A , _ 。 2、 集合 S= a,3,Y, 上的二元運算*為 * a 3 Y a s a 3 Y 3 a 3 Y S Y 3 Y Y Y a Y S 那么，代數系統(tǒng) 中的幺元是 _ , a的逆元是 _ 。 3、設 I是整數集合，Z3是由模 3 的同余類組成的同余類集，在 Z3上定義+3如下: i 3 j （i j）mod 3，則 +3 的運算表為 _ ； 是否構成群 _ 。 4、 設 G 是 n階完全圖，貝 U G 的邊數 m= _

2、。 5、 如果有一臺計算機，它有一條加法指令，可計算四數的和?，F(xiàn)有 28 個數需要計算和，它 至少要執(zhí)行 _ 次這個加法指令。 選擇20% （每小題2分） 1、在有理數集 Q 上定義的二元運算*, x, y Q有x*y x y xy , 則 Q 中滿足（ ）。 A、所有元素都有逆元； B、只有唯一逆元； 離散數學試卷（十四） 90 C、 x Q,x 1時有逆元x 1 ; D、所有元素都無逆元。離散數學試卷（十四） 91 判斷10% （每小題2分） 1 1、 在代數系統(tǒng)A,*中如果元素a A的左逆元ae存在， 則它一定唯一且a 1 ae1。（ ） 2、 設S,*是群G,*的子群，則G,*中幺元

3、e 是S,*中幺元。（ ） 設 S=0，1，*為普通乘法，則 S , * 是（ 半群，但不是獨異點; B、只是獨異點，但不是群; D、環(huán)，給出一個格 L ,則 L 是（ 有補格；C、布爾格；D、 A,B,C 都不對。 ，則Vi到 V4長度為 2 的通路有（ ）條。 ）條邊才能構成 Euler 圖。 A、 A、分配格; 離散數學試卷（十四） 92 3、 設A x|x a b-3, a,b 均為有理數 , +, 為普通加法和乘法，則代數系統(tǒng)A , +, 是域。（ ） 4、 設 G=V ,E 是平面圖，|V|=v, |E|=e , r 為其面數，則 v-e + r=2。（ ）離散數學試卷（十四） 9

4、3 5、如果一個有向圖 D 是歐拉圖，則 D 是強連通圖。（ ） 四、證明46% 1、 設A,*，是半群，e 是左幺元且 x A,燈 A，使得?*x e, 則A , *是群。（10 分） 2、 循環(huán)群的任何非平凡子群也是循環(huán)群。 （10 分） 3、 設 aH 和 bH 是子群 H 在群 G 中的兩個左陪集，證明： 要末 aH bH ，要末 aH bH。（ 8 分） 4、 設A，+ , ，是一個含幺環(huán)，|A|3，且對任意 a A, 都有a a a，則 不可能是整環(huán)（這時稱 A , + , 是布爾環(huán)）。（8 分） 5、 若圖 G 不連通，貝 U G 的補圖G是連通的。（10 分） 五、布爾表達式

5、8% 布爾表達式，試寫出其的析取范式和合取范式。 六、圖的應用 16% 1、 構造一個結點 v 與邊數 e 奇偶性相反的歐拉圖。（6 分） 2、 假設英文字母，a, e, h, n, p, r，w，y 出現(xiàn)的頻率分別為 12%，8%，15%，7%，6%，10%， 5%， 10%，求傳輸它們的最佳前綴碼，并給出 happy new year 的編碼信息。（10 分） 填空10% （每小題2分） 設 E（XI，X2，X3） （XI X2） （X2 X3） （X2 X3）是布爾代數 0,1, 上的一個 離散數學試卷（十四） 94 選擇 10% （每小題 2 分） 題目 1 2 3 4 5 答案 C

6、B D B D 三、判斷 10% （每小題 2 分） 題目 1 2 3 4 5 答案 N Y Y N Y 四、證明 46% 1、 ( 10 分)證明： (1) a,b,c A ,若 a * b a* c 貝 V b c 事實上：a* b a* c c?使?* (a* b) ?* (a* c) (a?* a) * b (O?*a)*c, e* b e* c 即:b c e 是A, *之幺元。 事實上：由于 e 是左幺元，現(xiàn)證 e 是右幺元。 x A ,x* e A, X使)?* (x* e) (5?*x)*e e* e e )?* x 由(1)即x* e x, e為右幺元 (3) x A,則 x

7、 1 A 事實上：x A (x* x) * x x* (X* x) x* e x e* x x* X e故有5?* x x* X e x有逆元X 由(2), ( 3)知：A,* 為群。 2、 (10 分)證明： 設G,*是循環(huán)群,G=(a)，設S,*是G,*的子群。且S e, S G，則存在最小正整數 m,使 得: am S，對任意a S，必有丨tm r, 0 r m, t 0, 1、; 2、B, Y； 3、 1) ; 5、9 是; 離散數學試卷（十四） 95 故: ar C1 tm C1 * a tm a1 * (am) t S 即: a1 a * (a ) S 所以 ar S但 m 是使a

8、m S的最小正整數，且 0 r m，所以 r=0 即: a1 (am)t 離散數學試卷(十四) 96 這說明 S 中任意元素是am的乘幕。 所以G,*是以am為生成元的循環(huán)群。 3、 ( 8 分)證明： 對集合aH禾口 bH，只有下列兩種情況： (1)aH bH ； ( 2)aH bH 1 對于aH bH ，則至少存在 h, h2 H，使得ah1 bh2，即有a bh2 h.j ，這時任意 1 ah aH，有 ah bh2 h1 h bH，故有 aH bH 同理可證：bH aH所以aH bH 4、 ( 8 分)證明： 反證法：如果A, +, ，是整環(huán)，且有三個以上元素，則存在 a 代 a ,

9、a 1 且 a a a 即有：a , a 1 但 a (a 1) a a a a a 這與整環(huán)中無零因子條件矛盾。因 此A, +, 不可能是整環(huán)。 5、 (10 分)證明： 因為 G= V , E不連通，設其連通分支是 G(V1), ,G(Vk) (k 2), u,v V，則有兩種情 況： (1) u , v,分別屬于兩個不同結點子集 Vi, Vj，由于 G(Vi) , G(Vj)是兩連通分支，故(u , v)在不 G 中，故 u , v 在G中連通。 (2) u ,v ,屬于同一個結點子集 Vi，可在另一結點子集 Vj中任取一點 w，故(u , w),(w , v )均 在G中，故鄰接邊(u

10、 ,w ) ( w , v )組成的路連接結點 u和 v,即 u , v 在G中也是連通的。 五、布爾表達式 8% 函數表為: X1 X2 X3 E(X1,X2,X3) 0 0 0 0 0 0 1 1 0 1 0 0 離散數學試卷（十四） 97 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 析取范式： E(X1,X2,X3) (X1 X2 (X1 X3) (X1 X2 X3) (X1 X2 X3) X2 X3) (X1 X2 X3) 合取范式： E(X1,X2,X3) (X1 X 2 X3) (X1 X2 X3) (X1 X2 X3) 六、樹的應用 16% 1、（6 分）解： 10 011 0101 0101 001 110 111 0100 001 111 011 000結點數乩邊歎 L毎個 結點度數均為偶數，所 以它是歐樁圖。 2、（10 分）解： 根據權數構造最優(yōu)二叉樹： 結點數邊數每個 結點度傳