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

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

3、歐拉圖，則D是強(qiáng)連通圖。四、證明 46%設(shè)，是半群，e是左幺元且，使得，則是群。10分循環(huán)群的任何非平凡子群也是循環(huán)群。10分設(shè)aH和bH是子群H在群G中的兩個(gè)左陪集，證明：要末，要末。8分設(shè)，是一個(gè)含幺環(huán)，|A|3，且對(duì)任意，都有，則不可能是整環(huán)這時(shí)稱是布爾環(huán)。8分假設(shè)圖G不連通，則G的補(bǔ)圖是連通的。10分五、布爾表達(dá)式 8%設(shè)是布爾代數(shù)上的一個(gè)布爾表達(dá)式，試寫出其的析取*式和合取*式。六、圖的應(yīng)用 16%構(gòu)造一個(gè)結(jié)點(diǎn)v與邊數(shù)e奇偶性相反的歐拉圖。6分假設(shè)英文字母，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 是之幺元。事實(shí)上：由于e是左幺元，現(xiàn)證e是右幺元。3由2，3知：為群。2、10分證明：設(shè)是循環(huán)群,G=(a)，設(shè)是的子群。且，則存在最小正整數(shù)m，使得：，對(duì)任意，必有，故：即：所以但m是使的最小正整數(shù)，且，所以r=0即：這說明S中任意元素是的乘冪。所以是以為生成元的循環(huán)群。3、8分證明：對(duì)集合，只有以下兩種情況：1

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