1/8专科《离散数学模拟》试题（一）姓名______________学号______________成绩______________一、填空（每小题5分，共25分）1．设}41,,3|{KNkkxxA，则用列举法表示A=_____________________.2．设}2,{A，则A的幂集A2________________________.3．设)}1,2(),2,4(),3,1{(是A到B的关系，则的逆关系~_______________.4．下图G的邻接矩阵A=__________________________5．设}},3,2{,3,2{A，则}}3,2{{A____________________________.二、选择题（将正确答案的编号填入相应题目后面的括号中，每小题5分，共20分）1．设集合}3,2,1{A，A上的关系)}1,1(),1,2(),1,3(),3,2{(，则是（）.A．自反的B．反对称的C．可传递的2．设有函数ZZZf:（Z表示非负整数集），定义为yxyxf),(，则f是（）.A．满射B．内射C．双射3．设}4,3,2,1{A，则A的分划有（）.A．}}3{},4,2{),1{(B．}}4{},3,2{{C．}}4{},3,2,1{{4．设简单图G所有结点的度之和为12，则G一定有（）.A．3条边B．4条边C．6条边4v3v2v1v2/8三、问答题（每小题6分，共42分）1．下图G是否二部图？若是，找出它的互补结点子集.2．设有命题公式)(QPPF，问F是否求真公式？为什么？3．判断下图是否欧拉图，若是，找出一个欧拉回路.4．设1和2是集合A上的偏序关系，问1－2是A上的偏序关系吗？为什么？5．判断下述命题公式的等值关系是否成立PQPQPQ)((6．将下一命题符号化.分析到个体词、谓词和量词，使用全总个体域.“有些大学生不钦佩任何运动员”4v3v2v1v5v4v3v2v1v5v0v3/87．设有函数RRf:和RRg:（R表示实数集），其中,14)(xxf32)(2xxg.试求?)2(gf四、证明题（共13分）1．设简单无向图G有n个结点，n+1条边，证明G中至少有一上结点的度≥3.（7分）2．用“形式证明”的方法证明)(SRP、Q、SRPQ（6分）专科《离散数学模拟》试题（二）姓名______________学号______________成绩______________一、填空（每小题5分，共25分）1．设aaA,{是小于15的正奇数}，则A的元素是________________________.2．设}7,6,2,1{},7,5,3,1{},7,6,5,4,3,2,1{BAV则AB__________________.3．设}},2{,1{A，则A的幂集有元素_____________个.4．设},,,{dcbaA，A上的关系)},(),,(),,(),,{(cddbbaaa，则2_________.5．设有函数BAf:和函数Abg:，且fg是A上的恒等函数，则f是____射，g是______射.二、选择题（将正确答案的编号填入相应题目后面的括号中）（每小题5分，共20分）1．设有函数RRgRRf:,:（R表示实数集），且2)(,12)(xxgxxf，则复合数函数fg是（）A．满射B．内射C．双射2．图G1是（）A．欧拉图B．哈米尔顿图C．二部图D．树3．定义正整数集N上的关系为：当且仅当“yx”时，yx，则是（）.4v3v2v1v8v7v6v5v图G14/8A．自反的B．对称的C．反对称的D．可传递的4．设T是一棵具有n个结点m条边)2(n的树，则T（）.A．连通B．包含有环C．1nmD．至少有两个度为1的结点.三、问答题（）1．以下图G2是否平面图，若是平面图，将图重画，使其边没有交叉.2．以下两个谓词公式等值关系成立吗？)()())()((xxBxxAxBxAx3．设P、Q是命题变元，以下两命题公式等值关系成立吗？QPQPQ))((4v3v2v1v图G25/84．设}2,1{A，在A上可以定义多少个不同的偏序关系？5．将下一命题符号化，分析到个体词，谓词和量词，使用全总个体域“在北京工作的人未必都是北京人”6．图),(3EVG如下所示，试问G有多少个分图？4v3v2v1v8v7v6v5v图G36/87．设用G是由5棵树构成的一个树林，G有20个结点，问G有多少条边？四、证明题（共13分）1．设是集合A上的等价关系，试证明~（7分）2．设T是一棵完全二元树，0n表示树叶结点数，试证明边数)1(20nm（6分）专科《离散数学模拟》试题（三）姓名______________学号______________成绩______________一、填空（每小题5分，共25分）1．设A和B是两个有限集，若#A<#B，则存在由A到B的______射.若#A>#B，则存在由A到B的______射.2．设G是具有n个结点，m条边的连通图，则G的生成树T有_____个结点，____条边.3．设有函数AAf:，且AIf2，则可以判定f是_____射.4．设T是一棵完全二元树，有15个结点，其中8个树叶结点，则T分枝结点数是______________，T的所有结点度数之和是________________.5．设}3,2,...
