浙师大离散数学试卷2011.doc

《浙师大离散数学试卷2011.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浙江师范大学《离散数学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．运算

2、满足消去律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为权

3、的最优二元树的权为。5、设，则的奇偶性为。6、集合A,.则在A上可建立个二元关系。7、设,将公式中量词消去后的公式是8、G是一个群，则的阶是。三、计算题。（共6题，每题8分共48分）1、在集合上随机产生二个关系，，要求，。求；。2、求公式的主析取范式。3、计算机系有120名学生，其中有100名学生每人至少学习三门外语（英语，法语，德语）中的一门外语。设65名学习英语，45名学习法语，42名学习德语，20名学习英语和法语，25名学习英语和德语，15名学习法语和法语，求三门外语都学的学生数。4、设，在Ａ上构造一个二元关系，它同时不满足自反性，反自反性，对

4、称性，反对称性，传递性。5、各找一个只有六个元素的交换群和非交换群。再在找到的二个群中各找一个3阶子群。6、任意画一个具有4个顶点、10条边的连通的有向图，并求该图长度为2的通路的总条数，问该图是否为强连通图？四、证明和讨论题。（共3题，每题6分，共18分）1、证明集合恒等式。2、设H，K是G的二个子群，在G上定义一个二元关系R如下：证明R为G上的等价关系。3、构造证明：前提：，，。结论：。五、讨论题。（共1题，每题8分，共8分）讨论A上具有传递关系性质的关系和关系复合运算之间的联系。（不能只给结论，要有具体的说明过程。）