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

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

3、則中幺元e是中幺元。（ ）3、 設(shè)， +,為普通加法和乘法，則代數(shù)系統(tǒng)是域。（ ）4、 設(shè)G=是平面圖，|V|=v, |E|=e，r為其面數(shù)，則v-e + r=2。（ ）5、 如果一個(gè)有向圖D是歐拉圖，則D是強(qiáng)連通圖。（ ）四、證明 46%1、 設(shè)，是半群，e是左幺元且，使得，則是群。（10分）2、 循環(huán)群的任何非平凡子群也是循環(huán)群。（10分）3、 設(shè)aH和bH是子群H在群G中的兩個(gè)左陪集，證明：要末，要末 。（8分）4、 設(shè)，是一個(gè)含幺環(huán)，|A|3，且對(duì)任意，都有，則不可能是整環(huán)（這時(shí)稱(chēng)是布爾環(huán)）。（8分）5、 若圖G不連通，則G的補(bǔ)圖是連通的。（10分）五、布爾表達(dá)式 8%設(shè)是布爾代數(shù)上的

4、一個(gè)布爾表達(dá)式，試寫(xiě)出其的析取范式和合取范式。六、圖的應(yīng)用 16%1、 構(gòu)造一個(gè)結(jié)點(diǎn)v與邊數(shù)e奇偶性相反的歐拉圖。（6分）2、 假設(shè)英文字母，a，e，h，n，p，r，w，y出現(xiàn)的頻率分別為12%，8%，15%，7%，6%，10%，5%，10%，求傳輸它們的最佳前綴碼，并給出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

5、) e 是之幺元。事實(shí)上：由于e是左幺元，現(xiàn)證e是右幺元。（3）由（2），（3）知：為群。2、（10分）證明：設(shè)是循環(huán)群,G=(a)，設(shè)是的子群。且，則存在最小正整數(shù)m，使得：，對(duì)任意，必有，故： 即：所以但m是使的最小正整數(shù)，且，所以r=0即：這說(shuō)明S中任意元素是的乘冪。 所以是以為生成元的循環(huán)群。3、（8分）證明：對(duì)集合，只有下列兩種情況：（1）； （2）對(duì)于，則至少存在，使得，即有，這時(shí)任意，有，故有同理可證：所以 4、（8分）證明：反證法：如果，是整環(huán)，且有三個(gè)以上元素，則存在即有：這與整環(huán)中無(wú)零因子條件矛盾。因此不可能是整環(huán)。5、（10分）證明：因?yàn)镚=不連通，設(shè)其連通分支是，則有兩種情況：（1） u , v，分別屬于兩個(gè)不同結(jié)點(diǎn)子集Vi，Vj，由于G(Vi) , G(Vj)是兩連通分支，故(u , v)在不G中，故u , v 在中連通。（2） 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析取范式：合取范式：六、 樹(shù)的應(yīng)用 16%1、（6分）解：2、（10分）解：根據(jù)權(quán)數(shù)構(gòu)造最優(yōu)二叉樹(shù)：傳輸它們的最佳