2008-2009《离散数学》期末试题A

忻州师范学院计算机科学与技术系2008-2009学年第二学期《离散数学》期末考试试题(A卷)（考试班级：2008级本0801、0802班考试时间：110分钟）一、单项选择题：（每小题2分，共30分）下列各题【A】\【B】\【C】\【D】四个选项中,只有一个选项是正确的,请将正确选项写在答卷纸的相应位置上。1．下列语句是命题的有（）。【A】明年中秋节的晚上是晴天【B】【C】当且仅当x和y都大于0【D】我正在说谎2．下列命题真值为真者（）。【A】若3+3=6则雪是黑的【B】是无理数当且仅当印度位于非洲【C】“2或4是素数，这是不对的”是不对的【D】只有2能被4整除，2才能被2整除3．设A={1,2,3}，则A上有（【A】23【B】32【C】）个二元关系。【D】4．在下述公式中不是重言式为（）【A】【B】【D】【C】5．命题公式中成真赋值的个数为（）。【A】0【B】1【C】2【D】36．下列等价关系正确的是（）。【A】【B】【C】【D】；；；。7．令是火车，是汽车，比跑得快，则公式：的含义是（）。【A】并不是所有的火车都比汽车跑得快【B】有的火车比所有的汽车跑得快【C】不存在跑得一样快的火车与汽车【D】火车比汽车跑得快8．公式中既呈约束出现又呈自由出现的变元是（）。【A】【B】【C】【D】9．全体小项合取式为（）。【A】可满足式【C】永真式【B】矛盾式【D】A，B，C都有可能10．任何图中必定有偶数个（）。【A】度数为偶数的结点【B】入度为偶数的结点【C】度数为奇数的结点【D】出度为奇数的结点，S上关系R的关系图如下，则R具有（）性质。11．设【A】自反性、对称性、传递性【B】反自反性、反对称性【C】反自反性、反对称性、传递性【D】自反性12．下列图形中为欧拉图的是（）。13．已知图G的邻接矩阵为，则G有（）。【A】5点，8边14．设图G是有6个顶点的连通图，总度数为20，则从G中删去（）边后使之变成树。【A】10【B】5【C】3【D】215．在如下的有向图中，从V1到V4长度为3的道路有（）条。【B】6点，7边【C】5点，7边【D】6点，8边【A】1【B】2【C】3【D】4二．填空题(每空1分，共15分)1．P：你努力，Q：你失败。“除非你努力，否则你将失败”符号化为败了”符号化为。；“虽然你努力了，但还是失2．数列（2，4，3，3，5）是否可图化。3．含3个命题变项的命题公式的主合取范式为,则它的主析取范式为。4．命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数，，则命题的逻辑谓词公式为。5．设G是完全二叉树，G有15个点，其中8个叶结点，则G有条边；它的总度数为_____，分枝结点数为______，G中度数为3的顶点数是。6．中的辖域是。7．的前束范式是。8．设A={a,b}，则=。9．设A={1,2,3,4}，R={<x,y>|x是y的倍数，x,y∈A}，则=；=。10．对下图二叉树的点先序遍历的结果是三．简答题(每小题7分，共42分)，中序遍历的结果是。1、已知命题公式2、R1={<1,2>,<1,3>,<2,3>},R2={<2,2>,<2,3>,<3,4>},求：(３)求，求主析取范式(要求通过等值演算推出)。(1)（２）3、设<A,R>为一个偏序集，其中，A={1，2，3，4，6，9，12，24},R是A上的整除关系。（1）画R出的哈斯图；（2）求A的极大元和极小元；（3）求B={4,6}的上确界和下确界。4、设集合A={a,b,c,d}上关系R={<a,b>,<b,a>,<b,c>,<c,d>}要求1、写出R的关系矩阵和关系图。2、用矩阵运算求出R的传递闭包。5.求下图的最小生成树。6.设7个字母在通信中出现的频率如下：a：35%b:20%c:15:d:10%e:10%f:5%g:5%用huffm