離散數(shù)學題庫簡答題

1、編號題目答案題型分值大綱難度1 1設(shè)集合A=a，b，c，d上的關(guān)系R= , , , 用矩陣運算求出R的傳遞閉包t (R)。 答: ， t (R)= , , , , , , , , 簡答題84.332如下圖所示的賦權(quán)圖表示某七個城市及預先算出它們之間的一些直接通信線路造價，試給出一個設(shè)計方案，使得各城市之間能夠通信而且總造價最小。答: 用Kruskal算法求產(chǎn)生的最優(yōu)樹。算法略。結(jié)果如圖：樹權(quán)C(T)=23+1+4+9+3+17=57即為總造價。簡答題87.233設(shè)是一個群，這里+6是模6加法，Z6=0 ，1，2，3，4，5，試求出的所有子群。答: 子群有；簡答題88.334權(quán)數(shù)1，4，9，16

2、，25，36，49，64，81，100構(gòu)造一棵最優(yōu)二叉樹。答: 簡答題87.235集合X=, , , ，R=,|x1+y2 = x2+y1 。1） 說明R是X上的等價關(guān)系。 （6分）2） 求出X關(guān)于R的商集。（2分）答: 1）、1、 自反性： 2、 對稱性： 3、 傳遞性：即由（1）（2）（3）知：R是X上的先等價關(guān)系。2）、X/R=簡答題84.436設(shè)集合A= a ,b , c , d 上關(guān)系R= , , , 要求 1）、寫出R的關(guān)系矩陣和關(guān)系圖。（4分） 2）、用矩陣運算求出R的傳遞閉包。（4分）答: 1、； 關(guān)系圖2、 t (R)= , , , , , , , , 。簡答題84.1;4.

3、347利用主析取范式，判斷公式的類型。答: 它無成真賦值，所以為矛盾式。簡答題82.338在二叉樹中:1)求帶權(quán)為2，3，5，7，8的最優(yōu)二叉樹T。（4分）2)求T對應的二元前綴碼。（4分）答: （1）由Huffman方法,得最佳二叉樹為：（2）最佳前綴碼為：000，001，01，10，11簡答題87.239下圖所示帶權(quán)圖中最優(yōu)投遞路線并求出投遞路線長度（郵局在D點）。答: 圖中奇數(shù)點為E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF復制道路EG、GF，得圖G，則G是歐拉圖。由D開始找一條歐拉回路：DEGFGEBACBDCFD。道路長度為：35+8+20+20+8+40+3

4、0+50+19+6+12+10+23=281。簡答題87.2510設(shè)S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24，“”為S上整除關(guān)系，問：（1）偏序集的Hass圖如何？（2）偏序集的極小元、最小元、極大元、最大元是什么?答: (1)=,，,covS=, ,Hass圖為 （2）極小元、最小元是1，極大元、最大元是 24。簡答題84.4411設(shè)解釋R如下：DR是實數(shù)集，DR中特定元素a=0，DR中特定函數(shù)，特定謂詞，問公式的涵義如何？真值如何？答: 公式A涵義為：對任意的實數(shù)x,y,z，如果xy 則 (x-z) (y-z) A的真值為： 真（T）。簡答題83.2312給定3個命

5、題：P：北京比天津人口多；Q：2大于1；R：15是素數(shù)。 求復合命題：的真值。答: P，Q是真命題，R是假命題。簡答題82.2313給定解釋I：D=2，3，L（x,y）為L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求謂詞合式公式的真值。答: 簡答題83.1;3.2314將化為與其等價的前束范式。答: 簡答題83.2315簡述關(guān)系的性質(zhì)有哪些？自反性，對稱性，傳遞性，反自反性，反對稱性簡答題84.3116假設(shè)英文字母，a，e，h，n，p，r，w，y出現(xiàn)的頻率分別為12%，8%，15%，7%，6%，10%，5%，10%，求傳

6、輸它們的最佳前綴碼，并給出happy new year的編碼信息。答:解：傳輸它們的最佳前綴碼如上圖所示，happy new year的編碼信息為：10 011 0101 0101 001 110 111 0100 001 111 011 000 附：最優(yōu)二叉樹求解過程如下：簡答題87.2317用washall方法求圖的可達矩陣，并判斷圖的連通性。答: 1：A2，1=1，； 2： A4，2=1，3： A1，3=A2，3=A4，3=1，4： Ak，4=1，k=1，2，3，4，p中的各元素全為1，所以G是強連通圖，當然是單向連通和弱連通。簡答題86.3318設(shè)有a、b、c、d、e、f、g七個人，他

7、們分別會講的語言如下：a：英，b：漢、英，c：英、西班牙、俄，d：日、漢，e：德、西班牙，f：法、日、俄，g：法、德，能否將這七個人的座位安排在圓桌旁，使得每個人均能與他旁邊的人交談？答:用a,b,c,d,e,f,g 7個結(jié)點表示7個人，若兩人能交談可用一條無向邊連結(jié)，所得無向圖為此圖中的Hamilton回路即是圓桌安排座位的順序。Hamilton回路為a b d f g e c a。簡答題86.4319用 Huffman算法求出帶權(quán)為2，3，5，7，8，9的最優(yōu)二叉樹T，并求W（T）。若傳遞a ，b， c， d ，e， f 的頻率分別為2%， 3% ，5 %， 7% ，8% ，9%求傳輸它的

8、最佳前綴碼。（答: （1） 用0000傳輸a、0001傳輸b、001傳輸c、01傳輸f、10傳輸d、11傳輸e傳輸它們的最優(yōu)前綴碼為0000，0001，001，01，10，11 。簡答題87.2320構(gòu)造一個結(jié)點v與邊數(shù)e奇偶性相反的歐拉圖。答: 簡答題86.4521設(shè)A=1，2，3，4，S=1，2，3，4，為A的一個分劃，求由S導出的等價關(guān)系。答: R= , , , , 簡答題84.4322設(shè)，偏序集的Hass圖為求 A中最小元與最大元； 的上界和上確界，下界和下確界。答: A中最大元為 ，最小元不存在； 上界 ，上確界；下界無，下確界無。簡答題84.4323用Warshall算法，對集合A

9、=1，2，3，4，5上二元關(guān)系R=,求t（R）。答: 1時，1,1=1, A =2時，M1,2=M4,2=1A=3時，A的第三列全為0，故A不變4時，M1,4=M2,4=M4,4=1A= 5時，M3,5=1 ，這時A=所以t (R)=, , 。簡答題84.1;4.3424將謂詞公式化為前束析取范式與前束合取范式。答: 簡答題82.1;3.1;3.2325)、畫一個有一條歐拉回路和一條漢密爾頓回路的圖。)、畫一個有一條歐拉回路，但沒有一條漢密爾頓回路的圖。)、畫一個有一條歐拉回路，但有一條漢密爾頓回路的圖。答:簡答題86.4326求的主合取范式。答: 簡答題82.3327在下面關(guān)系中:判定關(guān)系的

10、性質(zhì)。答: R自反任意實數(shù)x，x-x+20 ， x-x-20 , 所以直線y=x上的點在區(qū)域內(nèi)，即 , 故R自反； R對稱若 有 得 即 所以 R對稱；因R自反且結(jié)點集非空，故R非反自反；因R對稱且結(jié)點集非空，并非全是孤立點，故R不是反對稱；由 得 所以 而 所以R4不是傳遞的。簡答題84.3428求圖的鄰接矩陣和可達矩陣。答: ， ， ，。所以可達矩陣簡答題86.3329已知某有向圖的鄰接矩陣如下： 試求：到的長度為4的有向路徑的條數(shù)。答: ， ， ， ，由到長度為4的有向路徑的條數(shù)為3條。簡答題86.3330已知某樹有2個2度結(jié)點、3個3度結(jié)點、4個4度結(jié)點，問有幾個葉子點（無其它度數(shù)點）

11、。答: 設(shè)該樹有t 片樹葉，總結(jié)點數(shù)為 總邊數(shù)為 所以 ， 29+t=2(8+t) 即 t=13 。 該樹有13片樹葉。簡答題87.1;7.2331設(shè)和是A上的任意二元關(guān)系，如果和是自反的，是否也是自反的，為什么？如果和是對稱的，是對稱的嗎？答: 若是自反的，則也是自反的。因為 自反，從而 ，即也是自反的。 若是對稱的，但不一定是對稱的。 如：A = a , b , c，則是對稱的，但不是對稱的。簡答題84.3432如圖給出的賦權(quán)圖表示六個城市及架起城市間直接通訊線路的預測造價。試給出一個設(shè)計方案使得各城市間能夠通訊且總造價最小，并計算出最小總造價。答: 要設(shè)計一個方案使各城市間能夠通訊且總造

12、價最小，即要求該圖連通、無回路、邊權(quán)之和最小的子圖即最小生成樹，由避圈法或破圈法可得：其最小生成樹為：其樹權(quán)即最小造價為：1+2+3+5+7=18。簡答題87.1;7.2333設(shè)S = R - -1（R為實數(shù)集），。 說明是否構(gòu)成群； 答: 1），即運算*是封閉的。 2） 而，即*可結(jié)合。 3）設(shè)S關(guān)于*有幺元e，則。而 。4） 設(shè)有逆元 。則，即 ，即 S中任意元都有逆元，綜上得出，構(gòu)成群。簡答題88.3534將公式劃為只含有聯(lián)結(jié)詞的等價公式。答: 原式 。簡答題82.1;2.2335設(shè)和都是群的子群，問和是否是的子群并說明理由。答: 是 的子群，不一定是的子群。 都是的子群， 的子群。如：

13、G = 1，5，7，11，：模12乘，則為群。且H = 1，5，K = 1，7，皆為的子群，但， 不是的子群。因為 ，即運算不封閉。簡答題88.3536設(shè)，從A到B的關(guān)系，試給出R的關(guān)系圖和關(guān)系矩陣，并說明此關(guān)系是否為函數(shù)？為什么？A2349B2471012答: 則R的關(guān)系圖為：R的關(guān)系矩陣為 關(guān)系R不是A到B的函數(shù)，因為元素2，4的象不唯一（或元素9無象）。簡答題85.2;4.2437設(shè)是半群，是左零元，對任是否是左零元？為什么？答: 仍是左零元。因為，由于是左零元，所以，又 為半群，所以*可結(jié)合。 所以，所以，仍是左零元。簡答題88.1338某次會議有20人參加，其中每人至少有10個朋友，

14、這20人擬圍一桌入席，用圖論知識說明是否可能每人鄰做的都是朋友？（理由）答: 可能。將人用結(jié)點表示，當兩人是朋友時相應結(jié)點間連一條邊，則得一個無向圖，20人圍一桌，使每人鄰做都是朋友，即要找一個過每個點一次且僅一次得回路。由題已知， ，由判定定理，G中存在一條漢密爾頓回路。即所談情況可能。簡答題86.4339通過主合取范式，求出使公式的值為F的真值指派。答: 使公式的值為F的真值指派為： ； ； 。簡答題82.2;2.3340設(shè)，A上的關(guān)系 ，求出。答: ， ， ，。簡答題84.1;4.3341已知，為模7乘法。試說明是否構(gòu)成群？是否為循環(huán)群？若是，生成元是什么？答: 既構(gòu)成群，又構(gòu)成循環(huán)群，

15、其生成元為3，5。因為：的運算表為： 1）由運算表知，封閉；2）可結(jié)合（可自證明）3）1為幺元；4），綜上所述，構(gòu)成群。 由，。所以，3為其生成元，3的逆元5也為其生成元。故為循環(huán)群。簡答題88.1;8.3542用等值演算法求下面公式的主析取范式，并求其成真賦值。答: 原式 使其成真賦值為： ， ， ， ， ，簡答題82.1;2.3343集合上的關(guān)系，寫出關(guān)系矩陣，畫出關(guān)系圖并討論R的性質(zhì)。答: R的關(guān)系圖為 R是自反、對稱的。簡答題84.1;4.3344一棵樹T中，有3個2度結(jié)點，一個3度結(jié)點，其余結(jié)點都是樹葉。（1）T中有幾個結(jié)點；（2）畫出具有上述度數(shù)的所有非同構(gòu)的無向圖。答: （1）設(shè)

16、該樹樹葉數(shù)為t，則樹T的結(jié)點數(shù)為，又邊數(shù) = 結(jié)點數(shù) 1， ， 即 ， ， T中7個結(jié)點。（2）具有3個兩度結(jié)點，一個3度結(jié)點，3片樹葉的樹（非同構(gòu)的）共有以下三種：簡答題87.1;7.2345設(shè)A=1,2,10。下列哪個是A的劃分？若是劃分，則它們誘導的等價關(guān)系是什么？（1）B=1,3,6,2,8,10,4,5,7;（2）C=1,5,7,2,4,8,9,3,5,6,10;（3）D=1,2,7,3,5,10,4,6,8,9答: （1）和（2）都不是A的劃分。（3）是A的劃分。其誘導的等價關(guān)系是I,。簡答題84.4346設(shè)有向圖G=(V,E)如下圖所示，試用鄰接矩陣方法求長度為2的路的總數(shù)和回路

17、總數(shù)。答: M= M2= G中長度為2的路總數(shù)為18，長度為2的回路總數(shù)為6。簡答題86.3447設(shè)A=1,2,3,4,5,A上偏序關(guān)系R=1，2，3，2，4，1，4，2，4，3，3，5，4，5IA;(1)作出偏序關(guān)系R的哈斯圖(2)令B=1,2,3,5，求B的最大，最小元，極大、極小元，上界，下確界，下界，下確界。答: 偏序關(guān)系R的哈斯圖為 (2)B的最大元：無，最小元：無； 極大元：2，5，極小元：1，3 下界：4， 下確界4； 上界：無，上確界：無 (2)B的最大元：無，最小元：無； 極大元：2，5，極小元：1，3 下界：4， 下確界4； 上界：無，上確界：無簡答題84.4448求(PQ)(PQ)的主合取范式并給出所有使命題為真的賦值。答: 原式(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ) (PQPQ)(PQ)(PQ) (PQ)(PQ) (PQ)(PQ) P(QQ) P(QQ) (PQ)(PQ) 命題為真的賦值是P=1,Q=0和P=1,Q=1簡答題82.1;2.2;2.33