中央电大历年试题答案—计算题

1、四、计算题解：14求谓词公式的前束范式15已知图的结点集Va,b,c,d以及图G和图D的边集合分别为： E(G)(a,a), (a,b), (b,c), (a,c) E(G)，试作图G和图D，写出各结点的度数，回答图G、图D是简单图还是多重图?图D是简单图16设集合Al，2，3，P(A)是A的幂集合，是集合的对称差运算，求运算在 P(A)上的单位元x P (A)，求x关于运算的逆元并解方程1，2y117化简布尔代数式(ab)V(abc)V(bc)V(aVc)理由14列命题公式(PQ)R的真值表，并给出该公式的成假赋值做真值表公式为假的赋值是(0，l，0)，(1，0，0)，(1，1，0)16设图

2、G(如图2所示)是6个结点a,b.c,d,e,f的图，试求图G的最小生成树，并计算它的权16构造连通无圈的图，即最小生成树，用克鲁斯克尔算法：第一步：取db=;第二步：取af=4第三步：取fe=3；第四步：取ad=9第五步：取bc23如附图1权为1+4+3+9+23=4017设T是有5片树叶的二元正则树，那末T有多少条边解：设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设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画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权17最优二叉树如图三所示 （10分） 图三2=27 2+42+33+23+2权为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. 设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)，对应边的权值依次为2 , 1 , 2 , 3 , 6 , 1 , 4 及5 ， 试 ( 1 ) 画出G的图形; ( 2 ) 写出G的邻接矩阵; ( 3 ) 求出G权最小的