本科：1009离散数学

本科：1009 离散数学 第 1 页 共 12 页 一、单项选择题 1．设P：a 是偶数，Q：b 是偶数。R：a + b 是偶数，则命题“若 a 是偶数，b 是偶数，则a + b 也是偶数”符号化为（D． P Q→R）。 2．表达式 x（P（x，y）  Q（z））  y（Q（x，y）→ zQ（z））中 x 的辖域是（P（x，y） Q（z））。 3．设)(} ),({} ,{,4321PSPSSS则命题为假的是（42SS ）。 4．设G 是有 n 个结点的无向完全图，则G 的边数（ 1/2 n（n-1））。 5．设G 是连通平面图，有 v 个结点，e 条边，r 个面，则r=（ e-v+2）。 6．若集合 A={1，{2} ，{1，2} } ，则下列表述正确的是( {1} A )． 7．已知一棵无向树 T 中有 8 个顶点，4 度、3 度、2 度的分支点各一个，T 的树叶数为( 5 )． 8．设无向图 G 的邻接矩阵为0101110011000011100111110则G 的边数为( 7 )． 9．设集合 A={a} ，则A 的幂集为({，{a} } )． 10．下列公式中 (AB  (AB) )为永真式． 11．若 G 是一个汉密尔顿图，则G 一定是( 连通图 )． 12．集合 A={1, 2, 3, 4} 上的关系 R={|x=y 且 x, yA} ，则R 的性质为（传递的 ）． 13．设集合 A={1，2，3，4，5} ，偏序关系是A 上的整除关系，则偏序集上的元素 5 是集合 A 的（极大元 ）． 14．图 G 如图一所示，以下说法正确的是 ( {(a, d) ,(b, d)} 是边割集 ) ．图一 15．设A（x）：x 是人，B（x）：x 是工人，则命题“有人是工人”可符号化为（( x)(A(x)∧B(x)) ）． 16．若集合 A={1，2} ，B={1，2，{1，2} } ，则下列表述正确的是(AB，且 AB )． 17．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( （d）是强连通的 )． 18．设图 G 的邻接矩阵为0101010010000011100100110则G 的边数为( 5 )． 19．无向简单图 G 是棵树，当且仅当(G 连通且边数比结点数少 1 )． 20．下列公式 ((P(QP))(P(PQ)) )为重言式． 21．若集合 A＝{ a，{a} ，{1，2} } ，则下列表述正确的是({a} A)． 22．设图 G＝，vV，则下列结论成立的是 (EvVv2)deg( ) ． 本 科 ： 1009 离 散 数 学 第 2 页 共 12 ...