离散数学...董亚茹

《离散数学...董亚茹》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、忻州师范学院计算机科学与技术系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才能被2整除3．设A={1,2,3}，则A上有（）个二元关系。【A】23【B】32【C】【D】4．在下述公式中不是重言式为（）【A】【B】【C】【D】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】

3、可满足式【B】矛盾式【C】永真式【D】A，B，C都有可能10．任何图中必定有偶数个（）。【A】度数为偶数的结点【B】入度为偶数的结点【C】度数为奇数的结点【D】出度为奇数的结点11．设，S上关系R的关系图如下，则R具有（）性质。【A】自反性、对称性、传递性【B】反自反性、反对称性【C】反自反性、反对称性、传递性【D】自反性12．下列图形中为欧拉图的是（）。13．已知图G的邻接矩阵为，则G有（）。【A】5点，8边【B】6点，7边【C】5点，7边【D】6点，8边14．设图G是有6个顶点的连通图，总度数为20，则从G中删去（）边后使之变成树。【A】10【B】5【C】

4、3【D】215．在如下的有向图中，从V1到V4长度为3的道路有（）条。【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中度

5、数为3的顶点数是。6．中的辖域是。7．的前束范式是。8．设A={a,b}，则=。9．设A={1,2,3,4}，R={

6、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={1，2，3，4，6，9，12，24},R是A上的整除关系。（1）

7、画R出的哈斯图；（2）求A的极大元和极小元；（3）求B={4,6}的上确界和下确界。4、设集合A={a,b,c,d}上关系R={,,,}要求1、写出R的关系矩阵和关系图。2、用矩阵运算求出R的传递闭包。5.求下图的最小生成树。 6.设7个字母在通信中出现的频率如下：a：35%b:20%c:15:d:10%e:10%f:5%g:5%用huffman算法求传输它们的前缀码，要求画出最优二叉树，指出每个字母对应的编码。二．证明题（共13分)将下列自然语言符号化，并构造推理。没有白色的乌鸦，北京鸭都是白色的。因此，北京鸭都不是乌

8、鸦。