試卷十四試題及答案

1、-. z.試卷十四試題與答案填空 10% 每題 2分設是由有限布爾格誘導的代數(shù)系統(tǒng)，S是布爾格，中所有原子的集合，則。集合S=，上的二元運算*為*則，代數(shù)系統(tǒng)中的幺元是 , 的逆元是。設I是整數(shù)集合，Z3是由模3的同余類組成的同余類集，在Z3上定義+3如下：，則+3的運算表為；是否構成群。設G是n階完全圖，則G的邊數(shù)m=。如果有一臺計算機，它有一條加法指令，可計算四數(shù)的和?，F(xiàn)有28個數(shù)需要計算和，它至少要執(zhí)行次這個加法指令。選擇 20% 每題 2分在有理數(shù)集Q上定義的二元運算*，有，則Q中滿足。所有元素都有逆元； B、只有唯一逆元；C、時有逆元； D、所有元素都無逆元。設S=0，1，*為普通乘

2、法，則是。半群，但不是獨異點； B、只是獨異點，但不是群；C、群； D、環(huán)，但不是群。3、圖給出一個格L，則L是。A、分配格； B、有補格； C、布爾格； D、 A,B,C都不對。有向圖D= ，則長度為2的通路有條。A、0； B、1； C、2； D、3 。在Peterson圖中，至少填加條邊才能構成Euler圖。A、1； B、2； C、4； D、5 。判斷 10% 每題 2分在代數(shù)系統(tǒng)中如果元素的左逆元存在，則它一定唯一且。設是群的子群，則中幺元e是中幺元。設， +,為普通加法和乘法，則代數(shù)系統(tǒng)是域。設G=是平面圖，|V|=v, |E|=e，r為其面數(shù)，則v-e + r=2。如果一個有向圖D是

3、歐拉圖，則D是強連通圖。四、證明 46%設，是半群，e是左幺元且，使得，則是群。10分循環(huán)群的任何非平凡子群也是循環(huán)群。10分設aH和bH是子群H在群G中的兩個左陪集，證明：要末，要末。8分設，是一個含幺環(huán)，|A|3，且對任意，都有，則不可能是整環(huán)這時稱是布爾環(huán)。8分假設圖G不連通，則G的補圖是連通的。10分五、布爾表達式 8%設是布爾代數(shù)上的一個布爾表達式，試寫出其的析取*式和合取*式。六、圖的應用 16%構造一個結點v與邊數(shù)e奇偶性相反的歐拉圖。6分假設英文字母，a，e，h，n，p，r，w，y出現(xiàn)的頻率分別為12%，8%，15%，7%，6%，10%，5%，10%，求傳輸它們的最正確前綴碼，

4、并給出happy new year的編碼信息。10分答案填空 10%每題2分+30120012112022011、；2、，；3、是；4、；5、9選擇 10%每題 2分題目12345答案CBDBD判斷 10%每題2分題目12345答案NYYNY證明 46%1、10分證明：1(2) e 是之幺元。事實上：由于e是左幺元，現(xiàn)證e是右幺元。3由2，3知：為群。2、10分證明：設是循環(huán)群,G=(a)，設是的子群。且，則存在最小正整數(shù)m，使得：，對任意，必有，故：即：所以但m是使的最小正整數(shù)，且，所以r=0即：這說明S中任意元素是的乘冪。所以是以為生成元的循環(huán)群。3、8分證明：對集合，只有以下兩種情況：1

5、；2對于，則至少存在，使得，即有，這時任意，有，故有同理可證：所以4、8分證明：反證法：如果，是整環(huán)，且有三個以上元素，則存在即有：這與整環(huán)中無零因子條件矛盾。因此不可能是整環(huán)。5、10分證明：因為G=不連通，設其連通分支是，則有兩種情況：u , v，分別屬于兩個不同結點子集Vi，Vj，由于G(Vi) , G(Vj)是兩連通分支，故(u , v)在不G中，故u , v 在中連通。u ,v ，屬于同一個結點子集Vi，可在另一結點子集Vj中任取一點w，故(u , w),(w , v )均在中，故鄰接邊( u ,w ) ( w , v ) 組成的路連接結點u和v，即u , v在中也是連通的。五、布爾表達式 8%函數(shù)表為：00000011010001111000101111011111析取*式：合取*式：樹的應用 16%1、6分解：2、10分解：根據(jù)權數(shù)構造最優(yōu)二叉樹：傳輸它們的最正確前綴碼如上圖所示，h