离散数学2010--A卷.doc

第 1 页福建工程学院2009–2010 学年第二学期期末考试 共 4 页 课程名称：《 离散数学 》课程考试试题 ( A 卷 ) 题号 一 二 三 四 五 六 七 八 九 十 总分 考生注意事项：1、本试卷共10页，请查看试卷中是否有缺页。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 判断题(每个选项1分，共10分，对的打√，错的打×) 得分 评卷人 （ ）1.在命题题逻辑中，任何命题公式的主合取范式都是存在的，并且是惟一的。 ( )2. 011是公式的成真赋值 ( )3.三种重要的二元关系是等价关系、偏序关系和函数关系，它们的共同特点是都具有自反性 。 ( )4. 设F,R都是二元关系,则(FR)-1=F-1R-1。　　　　　　 ( )5.无向完全图（n2）一定是哈密顿图 ( )6.阶数至少是2 树的每一条边都是桥,因而它的边连通度是1. ( )7.封闭的公式在任何解释下都变成命题。 ( )8. 设A,B,C是三集合，已知AB＝AC，则一定有B＝C. ( )9.有向图是强连通的，则它一定是单向连通的，也弱连通的。 ( )10.二部图是欧拉图也是哈密顿图。 填空题(每小题1分，共10分) 1.若集合A的元素个数=8，则其幂集的元素个数是是 7. 已知n阶无向简单图G有m条边，则G的补图有条边。 评卷人 1．设集合A={ab，c，d，e}，关系R的哈斯图图所示，则元素的 ） A． B． C． D．A． B． C． D． A.双射 B. 满射 C. 单射 D. 不是单射也不是满射 4．设A,B,C是三个非空集合,则( )是正确的. A. B. C. D. 5．下图中,（ ）是欧拉图。 A B C D 6.关于无向树的描述,不正确的是( ). 无向树是连通图、没有回路,每个边都是桥； 无向树是连通图、边数比顶点数少１,任意两个顶点的路径是惟一的； 无向树是连通图、没有回路,每个顶点都是割点； 无向树是连通图、没有回路，每条边都是割边。 7.关于含有n片树叶的最优二叉树描述,不正确的是( ). 　A. 含有n片树叶的最优二叉树每个分支点都有两个孩子； B. 含有n片树叶的最优二叉树分支点的个数是n-1； C.　W(T)等于个分支点的权重（构造最优二叉树时产生）之和； D. 在权重一定的前提下，含有n片树叶的最优二叉树是惟一的。 8. 令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（???? ） A. p∧┐q B．p∨┐q C.p∧q D．p→┐q 9.下图所示的二叉树序遍历的结果是（ ） A．abcde B．edcba C．bdeca D．badce 设R是集合A上的偏序关系，则R不一定是() A.自反的 ??B. 对称的 ?C. 反对称的D. 传递的 四、解答题（每小题10分，共40分） 得分 评卷人 1.求(P((Q∨R))∧((P∨(Q(R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。 2．某班有学生60人，其中有38人学习PASCAL语言，有16人学习C语言，有21人学习java语言；有3个人这三种语言都学习，有2个人这三种语言都不学习，问仅学习两门语言的学生数是多少？ 3．x,y| x,y(N∧y=x2}，S={x,y| x,y(N∧y=x+1}。求R-1、RS、SR、R{1,2}、S[{1,2}] 4．求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。 五、证明题（共20分） 得分 评卷人 ??? 1. 设T= 2. 设G为连通的简单平面图