浙师大离散数学试卷.docVIP

浙江师范大学《离散数学A》考试卷 （2010----2011 学年第1学期） 考试形式　　　闭卷笔试　　　　　　　　　使用学生　 计本10非师范　　　　　　　　　　　　 考试时间　　120　　　分钟　　　　　　 　出卷时间　2011　年　12　月　29　日　 　说明：考生应将全部答案都写在答题纸上，否则作无效处理。　 一、选择题。（每题2分，共10分） 1、设公式为重言式，则公式的类型为（） A．重言式 B．可满足式 C．矛盾式 D．不能确定 2、以下结论不正确的是（） A． B． C． D．1、2、2、4、2、3为某图的度数列 3、G是阶小于6的一个群，则以下结论不正确的是（） A．运算满足消去律 B．运算满足交换律 C．运算满足结合律 D．运算满足分配律 4、设R和S为集合A上的两个等价关系，则具有等价关系（） A．一定有 B．不一定有 C．一定没有 D．可能有 5、下列哪一个图不一定是树（） A．无回路的连通图 B．有n个顶点，n-1条边的连通图 C．每对顶点间都有通路的图 D．连通但删去一条边则是不连通图 二、填空题。（每空2分，共16分） 1、无向连通图G有12条边，4个3度顶点，其余顶点的度数小于2，则G中至少有 个顶点。 2、在有n个顶点的连通图中，至少需要有 条边。 3、G为模12的乘法群，即，，则元素5的阶为 。 4、以数列1，1，2，4，8，12，25为权的最优二元树的权为 。 5、设，则的奇偶性为 。 6、集合A,. 则在A上可建立个 二元关系。 7、设,将公式中量词消去后的公式是 8、G是一个群，则的阶是 。 三、计算题。（共6题，每题8分共48分） 1、在集合上随机产生二个关系，，要求，。 求； 。 2、求公式的主析取范式。 3、计算机系有120名学生，其中有100名学生每人至少学习三门外语（英语，法语，德语）中的一门外语。设65名学习英语， 45名学习法语， 42名学习德语，20名学习英语和法语，25名学习英语和德语，15名学习法语和法语，求三门外语都学的学生数。 4、设，在Ａ上构造一个二元关系，它同时不满足自反性，反自反性，对称性，反对称性，传递性。 5、各找一个只有六个元素的交换群和非交换群。再在找到的二个群中各找一个3阶子群。 6、任意画一个具有4个顶点、10条边的连通的有向图，并求该图长度为2的通路的总条数，问该图是否为强连通图？ 四、证明和讨论题。（共3题，每题6分，共18分） 1、证明集合恒等式。 2、设H，K是G的二个子群，在G上定义一个二元关系R如下： 证明R为G上的等价关系。 3、构造证明： 前提：，，。 结论：。 五、讨论题。（共1题，每题8分，共8分） 讨论A上具有传递关系性质的关系和关系复合运算之间的联系。（不能只给结论，要有具体的说明过程。）