浙师大离散数学试卷2011

浙江师范大学《离散数学A》考试卷（2010----2011学年第1学期）考试形式闭卷笔试使用学生计本10非师范考试时间120分钟出卷时间2011年12月29日说明：考生应将全部答案都写在答题纸上，否则作无效处理。一、选择题。（每题2分，共10分）1、设公式A为重言式，则公式A的类型为（）A．重言式B．可满足式C．矛盾式D．不能确定2、以下结论不正确的是（）A．ABABB．RSSRC．~ABABD．1、2、2、4、2、3为某图的度数列3、G是阶小于6的一个群，则以下结论不正确的是（）A．运算满足消去律B．运算满足交换律C．运算满足结合律D．运算满足分配律4、设R和S为集合A上的两个等价关系，则RS具有等价关系（）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的乘法群，即,xyG，*(mod12)xyxyr，则元素5的阶为。4、以数列1，1，2，4，8，12，25为权的最优二元树的权为。5、设123456164523，则2的奇偶性为。6、集合A,3A.则在A上可建立个二元关系。7、设1,2,3,4,A,将公式(()())xFxGx中量词消去后的公式是8、G是一个群12,,,2xGyxyxxey，则x的阶是。三、计算题。（共6题，每题8分共48分）1、在集合1,2,3,4A上随机产生二个关系1R，2R，要求15R，26R。求121RR；1()rR。2、求公式()()pqpr的主析取范式。3、计算机系有120名学生，其中有100名学生每人至少学习三门外语（英语，法语，德语）中的一门外语。设65名学习英语，45名学习法语，42名学习德语，20名学习英语和法语，25名学习英语和德语，15名学习法语和法语，求三门外语都学的学生数。4、设1,2,3A，在Ａ上构造一个二元关系，它同时不满足自反性，反自反性，对称性，反对称性，传递性。5、各找一个只有六个元素的交换群和非交换群。再在找到的二个群中各找一个3阶子群。6、任意画一个具有4个顶点、10条边的连通的有向图，并求该图长度为2的通路的总条数，问该图是否为强连通图？四、证明和讨论题。（共3题，每题6分，共18分）1、证明集合恒等式()()()ABCACBC。2、设H，K是G的二个子群，在G上定义一个二元关系R如下：{(,)|,,}RabhHkKbhak证明R为G上的等价关系。3、构造证明：前提：()pqr，ps，q。结论：sr。五、讨论题。（共1题，每题8分，共8分）讨论A上具有传递关系性质的关系和关系复合运算之间的联系。（不能只给结论，要有具体的说明过程。）