离散数学题库简答题..doc

编号 题目 答案 题型 分值 大纲 难度 1 设集合A={a，b，c，d}上的关系R={a , b , b , a , b, c , c , d }用矩阵运算求出R的传递闭包t (R)。 答: ， t (R)={a , a , a , b , a , c , a , d , b , a , b ,b , b , c . , b , d , c , d } 简答题 8 4.3 3 如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。　　 答: 用Kruskal算法求产生的最优树。算法略。结果如图： 树权C(T)=23+1+4+9+3+17=57即为总造价。 简答题 8 7.2 3 设Z6,+6是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求出Z6,+6的所有子群。 答: 子群有{[0]},+6；{[0],[3]},+6；{[0],[2],[4]},+6；{Z6},+6 简答题 8 8.3 3 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。 答: 简答题 8 7.2 3 集合X={1,2, 3,4, 5,6, … }，R={x1,y1,x2,y2|x1+y2 = x2+y1} 。 说明R是X上的等价关系。 （6分） 求出X关于R的商集。（2分） 答: 1）、 自反性： 对称性： 传递性： 即 由（1）（2）（3）知：R是X上的先等价关系。 2）、X/R= 简答题 8 4.4 3 设集合A={ a ,b , c , d }上关系R={ a, b , b , a , b , c , c , d } 要求 1）、写出R的关系矩阵和关系图。（4分） 2）、用矩阵运算求出R的传递闭包。（4分） 答: 1、； 关系图 2、 t (R)={a , a , a , b , a , c , a , d , b , a , b ,b , b , c . , b , d , c , d }。 简答题 8 4.1;4.3 4 利用主析取范式，判断公式的类型。 答: 它无成真赋值，所以为矛盾式。 简答题 8 2.3 3 在二叉树中:1)求带权为2，3，5，7，8的最优二叉树T。（4分）2)求T对应的二元前缀码。（4分） 答: （1）由Huffman方法,得最佳二叉树为： （2）最佳前缀码为：000，001，01，10，11 简答题 8 7.2 3 下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。 答: 图中奇数点为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+30+50+19+6+12+10+23=281。 简答题 8 7.2 5 设S={1 , 2 , 3 , 4, 6 , 8 , 12 , 24}，“”为S上整除关系，问：（1）偏序集的Hass图如何？（2）偏序集的极小元、最小元、极大元、最大元是什么? 答: (1)≤={1,2,1,3,1,4,1,6,1,8,1,12,1,24,2,4,2,6,2,8，2,12,2,24,3,6,3,12,3,24,4,8,4,12,4,24,6,12,6,24,8,24,12,24} covS={1,2,1,3,2,4,2,6,3,6,4,8,4,12,6,12 ,8,24,12,24} Hass图为 （2）极小元、最小元是1，极大元、最大元是 24。 简答题 8 4.4 4 设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数，特定谓词，问公式的涵义如何？真值如何？ 答: 公式A涵义为：对任意的实数x,y,z，如果xy 则 (x-z) (y-z) A的真值为： 真（T）。 简答题 8 3.2 3 给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。 求复合命题：的真值。 答: P，Q是真命题，R是假命题。 简答题 8 2.2 3 给定解释I：D={2，3}，L（x,y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式的真值。 答: 简答题 8 3.1;3.2 3 将化为与其等价的前束范式。