中央電大歷年試題答案—計算題

1、四、計算題解：14求謂詞公式的前束范式15已知圖的結(jié)點集Va,b,c,d以及圖G和圖D的邊集合分別為： E(G)(a,a), (a,b), (b,c), (a,c) E(G)，試作圖G和圖D，寫出各結(jié)點的度數(shù)，回答圖G、圖D是簡單圖還是多重圖?圖D是簡單圖16設(shè)集合Al，2，3，P(A)是A的冪集合，是集合的對稱差運算，求運算在 P(A)上的單位元x P (A)，求x關(guān)于運算的逆元并解方程1，2y117化簡布爾代數(shù)式(ab)V(abc)V(bc)V(aVc)理由14列命題公式(PQ)R的真值表，并給出該公式的成假賦值做真值表公式為假的賦值是(0，l，0)，(1，0，0)，(1，1，0)16設(shè)圖

2、G(如圖2所示)是6個結(jié)點a,b.c,d,e,f的圖，試求圖G的最小生成樹，并計算它的權(quán)16構(gòu)造連通無圈的圖，即最小生成樹，用克魯斯克爾算法：第一步：取db=;第二步：取af=4第三步：取fe=3；第四步：取ad=9第五步：取bc23如附圖1權(quán)為1+4+3+9+23=4017設(shè)T是有5片樹葉的二元正則樹，那末T有多少條邊解：設(shè)T有n個頂點，則有n-1條邊，T中有5個1度頂點，1個根為2度頂點，其余n-5-1個3度頂點由握手定理 5+2+3(n-5-1)=2(n-1)解得n=9;于是T有8條邊五計算題（每小題12分，本題共36分） 15求（PQ）R的析取范式與合取范式（PQ）R15（PQ）R （

3、4分）Q)R （析取范式）P ( （8分）QR) （合取范式） PR)( ( （12分） 16設(shè)A=0，1，2，3，R=A且x+yA，y|x0，S=2，試求R，S，RS，SA且x+yA，y|x -1，r(R),16R= S=, （3分）， RS= （6分）S -1= S， （9分）r(R)=IA=, （12分）17畫一棵帶權(quán)為1, 2, 2, 3, 4的最優(yōu)二叉樹,計算它們的權(quán)17最優(yōu)二叉樹如圖三所示 （10分） 圖三2=27 2+42+33+23+2權(quán)為1 （12分）16試求出(PQ)R的析取范式，合取范式，主合取范式.16(PQ)R(PQ)R(PQ)R析取范式 (3分)(PR)(QR) 合

4、取范式 (6分)(PR)(QQ)(QR)(PP)(PRQ)(PRQ)(QRP)(QRP)(PQR)(PQR)(PQR) 主合取范式 (12分)17. 設(shè)A=a, b, 1, 2，B=a, b, 1, 1，試計算 （1）（AB）; （2）（AB）; （3）( AB)(AB).17（1）(AB)=a, b, 2 (4分)（2）(AB)=a, b, 1, 2,a, b, 1 (8分)（3）(AB)(AB)=a, b, 2,a, b, 1 (12分)18. 圖G=，其中V=a，b，c，d，e，E= (a,b)，(a,c)，(a,e)，(b,d)，(b,e)，(c,e)，(c,d) ,(d,e)，對應(yīng)邊的權(quán)值依次為2 , 1 , 2 , 3 , 6 , 1 , 4 及5 ， 試 ( 1 ) 畫出G的圖形; ( 2 ) 寫出G的鄰接矩陣; ( 3 ) 求出G權(quán)最小的