离散数学复习题.docVIP

一、填空题 1、集合的表示方法有两种： 法和 法。请把“奇整数集合”表示出来{ }。 2、无向连通图G含有欧拉回路的充分必要条件是. 2*、连通有向图D含有欧拉回路的充分必要条件是 3、设R是集合A上的等价关系，则R所具有的关系的三个特性是 、 4、有限图G是树的一个等价定义是： 5、设N(x)：x是自然数，Z(y)；y是整数，则命题“自然数都是整数，而有的整数不是自然数”符号化为 6、在有向图的邻接矩阵中，第i行元素之和,第j列元素之和分别为 、 7、设A，B为任意命题公式，C为重言式，若，那么命题是 重言式的真值是 8、命题公式的主析取范式为 ． 设图G＝V，E和G(＝V(,E(,若 ，则G(是G的真子图，若 ，则G(是G的生成子图 10、在平面图中,则＝ 其中ri(i=1,2,…,r)是G的面． 11、设，则从A到B的所有映射是 11、(1={（a，1），（b，1）}；(2={（a，2），（b，2）}；(3={（a，1），（b，2）}；(4={（a，2），（b，1）} 12、表达式(x(yL（x，y）中谓词的定义域是{a，b，c}，将其中的量词消除，写成与之等价的命题公式为 12*、设个体域D＝{a,b},公式消去量词化为 13、含有三个命题变项P，Q，R的命题公式P(Q的主析取范式是 14、设R，S都是集合A上的等价关系，则对称闭包s(R(S)= 15、设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v,e和r满足的关系式是 16、设G是n个结点的简单图，若G中每对结点的度数之和 ，则G一定是哈密顿图. 17、一个有向树T称为根树，若 ，其中 ，称为树根， 称为树叶. 18、图的通路中边的数目称为 . 结点不重复的通路是 通路. 边不重复的通路是 通路. 19、设A和B为有限集，|A|=m，|B|=n，则有 个从A到B的关系，有 个从A到B的函数，其中当m(n时有 个入射，当m=n时，有 个双射。 1、列举；描述； 2、不含有奇数度结点. 2*、D中每个结点的入度＝出度 3、自反性、对称性、传递性 4、连通无回路（或任一等价定义） 5、(x(N(x)(Z(x))((x(Z(x)((N(x)) 6、结点vi的出度和结点vj的入度 7、1 8、P((Q 9、 V(=V,E((E 10、2(E(, 11、11、(1={（a，1），（b，1）}；(2={（a，2），（b，2）}；(3={（a，1），（b，2）}；(4={（a，2），（b，1）} 12、（L（a，a）(L（a，b）(L（a，c））(（L（b，a）(L（b，b）(L（b，c））(（L（c，a）(L（c，b）(L（c，c）） 13、(G(a)((H(a,a)(H(a,b)))( (G(b)((H(b,a)(H(b,b))) 14、R(S 15、 16、≥n 17、若有向图T恰有一个结点的入度为0，其余结点入度为1；入度为0的结点；出度为0的结点. 18、通路长度；初级；简单. 二、单项选择题（选择一个正确答案的代号，填入括号中） 1、设命题公式G= (（P(Q），H=P(（Q( (P），则G与H的关系是（ ）。 A．G(H B．H(G C．G=H D．以上都不是 2、下列命题公式等值的是( ) 3、设V＝{a,b,c,d},与V能构成强连通图的边集E＝( ) (A) {a,b,a,c,d,a,b,d,c,d} (B) {a,d,b,a,b,c,b,d,d,c} (C) {a,c,b,a,b,