離散數(shù)學(xué)練習(xí)題

TTAstandardizationoffice【TTA5AB-TTAK08-TTA2C】TTAstandardizationoffice【TTA5AB-TTAK08-TTA2C】離散數(shù)學(xué)練習(xí)題一、填空題（10分，每空1分，請將本題答案填在原題橫線上?。?、設(shè)集合X={0，1，2}，R是X上的二元關(guān)系，R={<0，0>，<0，2>，<1，2>，<2，0>，<2，1>}，則R的關(guān)系矩陣MR=。2、為模6整數(shù)加群，則由2生成的子群<2>=，右陪集<2>⊕65=。3、設(shè)A和B為有限集，|A|=m，|B|=n，則有個從A到B的關(guān)系，有個從A到B的函數(shù)。4、無向圖G如下圖所示，G的點連通度κ為，邊連通度λ為。5、在上面無向圖中，已給出了一棵生成樹T（粗邊所示），則樹枝d對應(yīng)的基本割集是，弦b對應(yīng)的基本回路是。6、令F(x)：x是整數(shù)，G(x)：x是奇數(shù)，則“不存在不是奇數(shù)的整數(shù)”符號化為。7、含有三個命題變項P，Q，R的命題公式PQ的主析取范式是（用mi形式表示最小項）。二、單選題（20分，每題1分，請將本題答案寫在下方表格中?。?2345678910111213141516171819201、下面給出的符號串集合中，（）不是前綴碼。A、B、C、D、2、下列()組賦值不是命題公式的成真賦值。A、010B、011C、110D、1013、設(shè)A={a，b，c，d}，A上的等價關(guān)系R={<a，b>，<b，d>，<d，a>}∪R-1∪IA，則對應(yīng)于R的A的劃分是（）。A、{{a，b}，{c，d}}B、{{a，b，d}，{c}}C、{{a}，，{c}，1ajxmog}D、{{a}，{b，c}，pu7x1qi}4、二部圖是()。A、歐拉圖B、哈密頓圖C、非連通圖D、完全圖5、令p:我將去上網(wǎng)，q:我有時間，則“我將去上網(wǎng)，僅當我有時間”可符號化為()。(A)(B)(C)(D)6、下面（）圖不一定是樹。A、每對結(jié)點間都有路的圖B、無回路的連通圖C、連通但刪去一條邊則不連通的圖D、有n個頂點n—1條邊的連通圖7、集合A={1,2,…,10}上的關(guān)系R={<x,y>|x+y=10,x,y∈A},則R的性質(zhì)是()。(A)自反的 (B)傳遞的、對稱的(C)對稱的 (D)反自反的、傳遞的8、設(shè)G如右圖，那么G不是()。 (A)哈密頓圖 (B)完全圖(C)歐拉圖 (D)樹9、設(shè)圖D的鄰接矩陣為，則D的頂點數(shù)與邊數(shù)分別為()。A、4，5B、5，16C、4，10D、5，810、下列式子中正確的是（）。A、＝1B、C、｛｝D、＝{}11、由2個命題變元p和q組成的不等值的命題公式的個數(shù)有()。(A)2(B)4(C)16(D)812、給定下列非負整數(shù)序列，可構(gòu)成簡單無向圖的節(jié)點度數(shù)序列的為()。(A)(1，3，4，4，5)(B)(1，1，2，2，2)(C)(0，1，3，3，5)(D)(1，1，2，2，3)13、4階完全無向圖中含3條邊的不同構(gòu)的生成子圖有()。(A)5(B)4(C)3(D)214、任意12階群的子群的階一定不為()。(A)3(B)6(C)8(D)415、在公式F(x，y)→yG(x，y)中變元x是()。(A)既是自由變元，又是約束變元 (B)既不是自由變元，又不是約束變元(C)自由變元 (D)約束變元16、設(shè)圖G=<V，E>為無向圖，|V|=5，|E|=20，則G一定是()。A、完全圖B、正則圖C、多重圖D、簡單圖17、給定公式，當D={a,b}時，解釋()使該公式真值為0。(a)=0、P(b)=0 (a)=0、P(b)=1 (a)=1、P(b)=118、設(shè)A={1,2,3}，則A上有（）個二元關(guān)系。A、23B、32C、D、19、設(shè)Z是整數(shù)集合，“+”是數(shù)的加法運算，則<Z，+>的單位元是()A、1B、-1C、沒有單位元D、020、設(shè)R和S是集合A={1，2，3，4}上的二元關(guān)系，則S是R的（）閉包。R={1，1，1，2，2，2，2，3，4，4}S={1，1，1，2，2，2，2，3，3，3，4，4}A、對稱B、自反C、傳遞D、以上都不對三、求解題（40分，每題8分，請將本題答案寫在后面答題紙上?。?、在自然推理系統(tǒng)中構(gòu)造證明：已知張三或李四的彩票中獎了。如果張三的彩票中獎了，那么你會知道張三的彩票中獎了。如果李四的彩票中獎了，那么王五的彩票也中獎了。你不知道張三的彩票中獎了。所以，李四和王五的彩票都中獎了。2、設(shè)A={a,b,c,d,e}，A上的偏序關(guān)系R＝{<c,a>，<c,b>，<d,a>，<d,b>，<e,a>，<e,b>，<e,c>，<e,d>}IA，求：(1)畫出偏序集<A，R>的哈斯圖；(2)求子集B={c,d,e}的極大元，極小元，最大元，最小元。3、求一階邏輯公式的前束范式：(xF(x,y)→yG(y))→xH(x,y,z)。4、設(shè)7個字母在通信中出現(xiàn)的頻率如下：a:35%，b:20%，c:15%，d:10%，e:10%，f:5%，g:5%，用Huffman算法求傳輸它們的最佳前綴碼。要求畫出最優(yōu)二叉樹，并指出傳輸100個按上述頻率出現(xiàn)的字母，需要多少個二進制數(shù)字。5、四、證明題（30分，每題7、7、8、8分，請將本題答案寫在后面答題紙上?。?、例如，f和g都是群<G1，。>到群<G2，*>的同態(tài)映射，C={x|x∈G1∧f(x)=g(x)}。證明：<C，。>是<G1，。>的一個子群。2、要在七天安排七場考試，同一個老師監(jiān)的任何兩場考試不能安排在接連的兩天內(nèi)進行。假如每個教師最多監(jiān)