一、選擇題（每題220）1．Q是整數(shù)集，<Q，﹡>（其中﹡為普通乘法）不能構(gòu)成。（）A．群 B．獨異點 C．半群 D．交換半2．在代數(shù)系統(tǒng)中，整環(huán)和域的關(guān)系為（。A．整環(huán)一定是域 B．域不一定是整環(huán)C．域一定是整環(huán) D．域一定不是整環(huán)3．﹡運算如下表所示，哪個能使<{a,b}，﹡>成為獨異點？（）aabB. aaaC. aaaD. aabbabbbbbaabbaaababababA.4．Z<Z，+>（）A．fx2xB．C．fxxD．fx1000xfx05．設(shè)<A,>是一個有界格，它也是有補格，只要滿足()。A．每個元素都有一個補元 B．每個元素都自少有一個補元C．每個元素都無補元素 D．每個元素都有多個補元素設(shè)G是由5個頂點組成的完全圖，則從圖G中刪去幾條邊可以得到樹。（ ）A．6 B．5 C．8 D．4在有n個結(jié)點的連通圖中，其邊數(shù) （ 。A．最多有n-1條 B．至少有n-1條 C．最多有n條 D．至少有n條8．7個頂點非同構(gòu)的無向樹有幾棵。 （ A．8 B．6 C．11 D．5GGA．有些邊不是割邊C．無割邊集（。B．每條邊都是割邊D．每條邊都不是割邊浙江工業(yè)大學(xué)考試命題紙一個無向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中 （ 。A．有奇數(shù)長度的回路 B．有偶數(shù)長度的回路C．無偶數(shù)長度的回路 D．無奇數(shù)長度的回路二、判斷題（每題110）1．具有兩個或多個元素的格中不存在以自身為補元的元素。（）2．若半群有左單位元，則左單位元唯一。（）3．設(shè)G是循環(huán)群，G同構(gòu)于H，則H也是循環(huán)群。（）4．彼得森圖是平面圖。（）5．任何一個阿貝爾群不一定是循環(huán)群。（）6．若有向圖D是歐拉圖，則D必為強連通圖。（）7．設(shè)圖G是有n個結(jié)點，n-1條邊的無向圖，則G為一棵樹。（）8．完全圖Kn（n≥1）都是哈密頓圖。（）9．n（n≥3）階無向樹既是簡單圖又是二部圖。（）10．完全二部圖Kn,m（n≥1，n≥1）都是哈密頓圖。（）三、填空題（每空218）1．設(shè)是一個群，若運算*在G上滿足 律，則稱<G，*>為Abel群。設(shè)是格其中為整除關(guān)系則3的補元是 ，8的補元是 ，6的補元是 。一個連通平面圖G有10條邊，G中度為1的結(jié)點有2個，其余是度為6的結(jié)點，則G共有 個面。一棵樹有2個4度結(jié)點，3個3度結(jié)點，其余結(jié)點是樹葉，樹葉的個數(shù)為 。設(shè)圖G的鄰接矩陣為M=0 1 1 ，則G的可達性矩陣為 。110 110 1

0 0在一棵根樹中，有且只有一個結(jié)點的入度為 。舉一個既是完美匹配又是極大匹配的例子 。對于具有個連通分支的森林，恰好加 條新邊能使所得圖為無向樹。9．算式的表達式為((((a+(b*c))*d)-e)÷(f+g))，則此式的波蘭符號表示法為 ，逆波蘭符號法表示法為 四、證明題（每題5分，共10分）<S,﹡>S，使得對于Sxy，都有xy=xay，證明：二元運算是可結(jié)合的。選做一題：(1)n(n+1)/2(2)證明K3,3是不是平面圖。第2頁浙江工業(yè)大學(xué)考試命題紙五、計算題：（每題742）A2,3，AabAab為abmod4。計算出運算的運算表。判斷A是否是一個半群，獨異點，群。2.設(shè)B0,1是布爾代數(shù)，（1）a,bB,公式為baa'(bb')))B中化簡f。（2）在B中等式(ab')(a'b)0 成立的條件是什么?第3頁浙江工業(yè)大學(xué)考試命題紙3．A={1,2,3,4,5,60}，x,y∈A,xyx|y（其中|是整除關(guān)系）畫出哈斯圖。它是否為格？是否為有補格？是否為分配格？是否為布爾格？寫出右圖所示的鄰接矩陣和關(guān)聯(lián)矩陣從v 到v 長度為2的路的數(shù)目是多少？2 5v1veeevv1 2eeevv72 3eeev3 4 5eeevev4 5ev61，2，3，3，4，5，8T，W(T)以及權(quán)對應(yīng)的前綴碼。選做一題：1PERTv6關(guān)鍵路徑。橋1大鐘醫(yī)院橋4橋3 橋2教科大樓圖1 圖224教科大樓