广东海洋大学离散数学08-09年考试试卷a

《广东海洋大学离散数学08-09年考试试卷a》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、GDOU-B-11-302班级：姓名：学号：试题共4页加白纸3张密封线广东海洋大学2008——2009学年第二学期《离散数学》课程试题课程号：1920015-0考试A卷闭卷□考查□B卷□开卷题号一二三四五总分阅卷教师各题分数2010153520100实得分数注：第一、第二和第三大题的答案直接写在试卷上指定空格内。只有计算题和证明题的答案写在答题纸上。一、填空题（每空1分，共20分）1、数理逻辑中公式的三种类型是、和。2、设：我说谎；：太阳从西边出来；则表示；。3、，则=；而。4、若则，。5、，则，。6、若非空集合上的关系是、和的，则称为偏序关

2、系。7、中，。第5页共13页8、，则的生成树中有条边，个顶点。9、除顶点外，的图称为平面图，平面图中的欧拉公式为。二、单项选择题（每题1分，共10分）1、下列语句中，真命题是；A、是有理数；B、全体起立！；C、2是素数三角形有三条边；D、4是2的倍数或是3的倍数吗？2、：张三可做此事；：李四可做此事；“张三可做此事或李四不可做此事”符号化为；A、；B、；C、；D、3、，则；A、；B、；C、；D、；4、上的关系，则的性质为；A、自反；B、对称；C、传递、对称；D、反自反，传递；5、对任意非空集合，的幺元（单位元）是；A、；B、；C、；D、；第5

3、页共13页6、下列矩阵，能够作为无向图关联矩阵的是；A、B、C、D、7、群必须满足；A、存在幺元；B、每个元素均有逆元；C、结合律和交换律；D、以上全是；8、图有6个顶点，各顶点度数分别为1，4，4，3，5，5则边数为；A、11；B、12；C、22；D、23；9、个顶点的图是强连通图当且仅当；A、中至少有一条通路；B、中有通过每个顶点至少一次的通路；C、中至少有一条回路；D、中有通过每个顶点至少一次的回路；10、无向图是欧拉图，当且仅当中（）；A、每个顶点的度数相同；B、每个顶点的入度等于出度；C、每个顶点的度数均为奇数；D、每个顶点的度数均

4、为偶数。三、判断题（每题1分，共15分）1、语句“豆沙包是由面粉和红小豆做成的”是命题逻辑中的复合命题（）2、任何命题公式都存在唯一与之等值的主析取范式，相应的主合取范式则不唯一（）3、所谓的“自然推理系统”是指，从任意给定的前提出发，应用系统中的推理规则进行推理演算，最后得到的命题公式是推理的结论，这个结论肯定是有效的结论。（）第5页共13页4、在一阶逻辑（谓词逻辑）中，同一个公式在不同的解释下，其真假值可能不同（）5、在一阶逻辑公式中，换名规则是对量词辖域中的自由变元而言的（）6、数字60的欧拉函数值是16（）7、笛卡尔积运算对于并和交运

5、算满足分配律（）8、一个关系只能是对称的或者反对称的；不能即是对称的，又是反对称的（）9、在等价关系中，商集和划分是等值的，即：商集就是一个划分，不同的商集对应不同的划分（）10、如果一个代数系统存在零元，则一定存在单位元（）11、n阶竞赛图可能是有向简单图，也可能是有向复杂图（）12、在有向图的关联矩阵中，每一列的元素之和必为零（）13、n(n≥2)阶有向完全图都是欧拉图（）14、Huffman算法所构造的最优二叉树是唯一的（）15、在构造最小生成树的过程中，Kruskal算法是通过按照大小顺序添加边的形式实现的，根据其思想，也可以通过添加

6、点的形式，实现构造最小生成树算法（）四、计算题（10+10+5+10=35分）1、求的主合取范式；2、已知无向图G=如下所示，求该图的全部点割集、割点、边割集、割边（桥），并分别求出其连通度和边连通度。第5页共13页3、为整数集，定义，求的幺元（单位元）和逆元。4、设表达式为1）求表达式树；（6分）2）前序遍历该表达式树；（2分）3）后序遍历该表达式树；（2分）五、证明题（每题10分，共20分）1、前提：结论：2、设为群,，有证明第5页共13页GDOU-B-11-302广东海洋大学2008——2009学年第二学期《离散数学》评分细则

7、课程号：1920015-0考试A卷闭卷□考查□B卷□开卷一、填空题（每空1分，共20分）1、永真式、永假式和可满足式；2、若我不说谎则太阳从西边出来；1；3、，；4、3，-2；5、；6、自反，反对称，传递；7、0，2；8、，；9、无边相交，。二、单项选择题（每题1分，共10分）1～5、C/ABDBB；6～10：ADADD。三、判断题：（每题1分，共15分）对的有：3、4、6、7、9、12、13、15错的有：1、2、5、8、10、11、14第13页共13页四、计算题（10+10+5+10=35分）1、4分2分2分2分2、点割集：｛v2,v4｝,

8、｛v3｝,｛v5｝（2分）割点：v3和v5(2分)边割集：｛e5｝、｛e6｝、｛e2,e3｝、｛e1,e2｝、｛e3,e4｝、｛e1,e4｝、｛e1,e3｝｛e2,