离散数学(本)7月试题（知识点复习考点归纳总结参考） .doc

计算机科学与技术专业 级第二学期离散数学试题一、单项选择题（每小题3分，本题共15分）1若集合a=1，2，1，2，则下列表述正确的是( ) a2a b1ac1a d2 a2已知一棵无向树t中有8个顶点，4度、3度、2度的分支点各一个，t的树叶数为( )a6 b4 c3 d53设无向图g的邻接矩阵为,则g的边数为( )a1 b7 c6 d144设集合a=a，则a的幂集为( )aa ba，ac，a d，a5下列公式中 ( )为永真式aab ab bab (ab) cab ab dab (ab)二、填空题（每小题3分，本题共15分）6命题公式的真值是 7若无向树t有5个结点，则t的边数为 8设正则m叉树的树叶数为t，分支数为i，则(m-1)i= 9设集合a=1，2上的关系r,，则在r中仅需加一个元素 ，就可使新得到的关系为对称的10(x)(a(x)b(x，z)c(y)中的自由变元有 三、逻辑公式翻译（每小题6分，本题共12分） 11将语句“今天上课”翻译成命题公式12将语句“他去操场锻炼，仅当他有时间”翻译成命题公式 四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由13设集合a=1，2，b=3，4，从a到b的关系为f=，则f是a到b的函数14设g是一个有4个结点10条边的连通图，则g为平面图 五计算题（每小题12分，本题共36分） 15试求出（pq）（rq）的析取范式16设a=1, 1, 2，b= 1, 2，试计算（1）ab （2）ab （3）a -（ab）17图g=，其中v= a, b, c, d ，e= (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)，对应边的权值依次为1、2、3、1、4及5，试（1）画出g的图形； （2）写出g的邻接矩阵；（3）求出g权最小的生成树及其权值六、证明题（本题共8分）18试证明：若r与s是集合a上的自反关系，则rs也是集合a上的自反关系离散数学（本）试题解答一、单项选择题（每小题3分，本题共15分）1a 2c 3c 4d 5b二、填空题（每小题3分，本题共15分）6真（或t，或1）7e+18g是连通的且结点度数都是偶数910x三、逻辑公式翻译（每小题6分，本题共12分）11设p：雪是黑色的， （2分）则命题公式为：p （6分）12设 p：如果明天下雨， q：我们在室内上体育课， （2分）则命题公式为：p q （6分）四、判断说明题（每小题7分，本题共14分）13错误 （3分）因为a中元素1有b中两个不同的元素与之对应，故f不是a到b的函数 （7分）14正确 （3分）因g是一个连通平面图，满足欧拉定理，有v-e+r=2，所以r=2-（v-e）=2-（5-9）=6 （7分）五计算题（每小题12分，本题共36分）15p（rq）p（rq） （6分） (pr) （pq）（合取范式） （12分） 16（1）（ab）=1 （4分） （2）（ab）=1, 2, 1, 2, 1, 2 （8分） （3）（ab）-a = （12分）ooooooooo23345510717 17最优二叉树如图二所示 （10分） 图二 权为23+33+32+42+52=39 （12分） 六、证明题（本题共8分） 18证明：设x，ya，因为r对称，