广东海洋大学2008-2009学年第二学期《离散数学》课程试题A卷..docxVIP

广东海洋大学2008-2009学年第二学期 《离散数学》课程试题 A卷一、填空题（每空1分，共20分）1、数理逻辑中公式的三种类型是 、 和 。2、设：我说谎；：太阳从西边出来；则表示 ； 。3、，则= ；而 。4、若则 ， 。5、，则 ， 。6、若非空集合上的关系是 、 和 的，则称为偏序关系。7、中 ， 。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、；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、每个顶点的度数均为偶数。三、判断题（每题1分，共15分）1、语句“豆沙包是由面粉和红小豆做成的”是命题逻辑中的复合命题（ ）2、任何命题公式都存在唯一与之等值的主析取范式，相应的主合取范式则不唯一（ ）3、所谓的“自然推理系统”是指，从任意给定的前提出发，应用系统中的推理规则进行推理演算，最后得到的命题公式是推理的结论，这个结论肯定是有效的结论。（ ）4、在一阶逻辑（谓词逻辑）中，同一个公式在不同的解释下，其真假值可能不同（ ）5、在一阶逻辑公式中，换名规则是对量词辖域中的自由变元而言的（ ）6、数字60的欧拉函数值是16（ ）7、笛卡尔积运算对于并和交运算满足分配律（ ）8、一个关系只能是对称的或者反对称的；不能即是对称的，又是反对称的（ ）9、在等价关系中，商集和划分是等值的，即：商集就是一个划分，不同的商集对应不同的划分（ ）10、如果一个代数系统存在零元，则一定存在单位元（ ）11、n阶竞赛图可能是有向简单图，也可能是有向复杂图（ ）12、在有向图的关联矩阵中，每一列的元素之和必为零（ ）13、n(n≥2)阶有向完全图都是欧拉图（ ）14、Huffman算法所构造的最优二叉树是唯一的（ ）15、在构造最小生成树的过程中，Kruskal算法是通过按照大小顺序添加边的形式实现的，根据其思想，也可以通过添加点的形式，实现构造最小生成树算法（ ）四、计算题（10+10+5+10=35分）1、求的主合取范式；2、已知无向图G=V,E如下所示，求该图的全部点割集、割点、边割集、割边（桥），并分别求出其连通度和边连通度。3、为整数集，定义，求的幺元（单位元）和逆元。4、设表达式为1）求表达式树；（6分）2）前序遍历该表达式树；（2分）3）后序遍历该表达式树；（2分）五、证明题（每题10分，共20分）1、前提：结论：2、设为群,，有 证明 广东海洋大学2008——2009学年第二学期 《离散数学》评分细则填空题（每空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四、计算题（10+10+5+10=35分）1、 4分2分2分2分2、点割集：｛v2,v4｝, ｛v3｝, ｛v5｝ （2分）割点：v3 和v5(2分)边割集：｛e5｝、｛e6｝、｛e2 ,e