离散数学填空题及问题详解

1、实用文档标准文案编号题目答案题型分值大纲难度1谓词公式x(p(x)yr(y)q(x) 中量词x 的辖域是（） 。答： p(x)yr(y) 填空题2 3.1 3 2令 r(x):x是实数， q(x):x是有理数。 则命题 “并非每个实数都是有理数”的符号化表示为（） 。答：x(r(x)q(x) 填空题2 3.1 3 3一棵无向树的顶点数n 与边数 m关系是 ( )。答： m=n-1 填空题2 7.1 3 4一个图的欧拉回路是一条通过图中( )的回路。答：所有边一次且恰好一次填空题2 6.4 3 5有 n 个结点的树，其结点度数之和是( ) 。答： 2n-2 填空题2 6.4 3 6设 t是一棵树

2、，则t是一个连通且 ( )图。答：简单无回路填空题2 6.2 3 7任一有向图中，度数为奇数的结点有( ) 个。答：偶数填空题2 6.1 3 8设7|),5()(|xexxbxnxxa且且（n： 自然数集，e+正偶数）则ba（） 。答： 0 ，1，2， 3，4，6 填空题2 1 2 9设 p，q 的真值为 0，r，s的真值为1，则答： 1 填2 2.1 3 实用文档标准文案)()(srprqp的真值 = （） 。空题10公式prsrp)()(的主合取范式为（） 。答：)()(rsprsp填空题2 2.3 4 11设 a=1， 2， 3， 4 ，a 上关系为 ,则 r2 = ( )。答： , ,

3、 , 填空题2 4.1；4.2 3 12设 a=a，b，c， d ，其上偏序关系r的哈斯图为则 r= （） 。答： , ia填空题2 4.4 4 13树是不包含树是不包含（）的（）图的。答：环 ; 无向填空题2 8.1 3 14设 a=1，2，3 ，则 a上既不是对称的又不是反对称的关系r= ( )。答： r=, 填空题2 4.3 3 15设 f ， g 是自然数集n 上的函数xxgxxfnx2)(,1)(,，则)(xgf（） 。答： 2(x+1) 填空题2 5.2 3 16设 a=a，b，c ，a上二元关系r= , , , 则 s（r）= （） 。答：a,c,a,b,c,c,c,a,b,a,

4、a,a填空题2 4.4 5 实用文档标准文案17p，q真值为 0 ； r， s真值为 1。则)()()(srqpsrpwff的真值为（） 。答： 1 填空题2 2.2 3 18rrqpwff)(的主合取范式为（） 。答：)()()(rqprqprqp填空题2 2.3 4 19设 p（x） ：x 是素数， e(x) ：x 是偶数， o(x) ：x 是奇数 n (x,y)：x 可以整数y 。 则 谓 词),()()(xynyoyxpxwff的 自 然 语 言 是（） 。答：)()()(rqprqprqp填空题2 3.1 3 20谓 词),(),(),(uyxuqzypzxpzyxwff的 前 束

5、范 式 为（） 。答：),(),(),(uyxqzypzxpuzyx填空题2 3.2 4 21若 p，q，为二命题，qp真值为 0 当且仅当（） 。答： p真值为 1，q的真值为0 填空题2 2.1 3 22将量词辖域中出现的（） 和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。答：约束变元填空题2 3.1 3 23设 g为 9 阶无向图， 每个结点度数不是5 就是 6， 则 g中至少有 （） 个5 度结点。答： 6 填空题2 6.1 3 实用文档标准文案24有向图中从v1到v2长度为2 的通路有（） 条。答： 2 填空题2 6.3 3 25设,l是 代 数 系 统 ，

6、 则,l满 足 幂 等 律 ， 即 对la有（） 。答：aaaaaa且填空题2 8.2 4 26任何 (n,m) 图 g = (v,e) , 边与顶点数的关系是（） 。答：vvmvd2)(填空题2 6.4 3 27当 n 为（）时, 非平凡无向完全图kn是欧拉图。答：奇数填空题2 6.2 3 28已知一棵无向树t有三个 3 顶点 , 一个 2 度顶点 , 其余的都是1 度顶点 , 则 t 中有（）个 1 度顶点。答： 5 填空题2 7.1 3 29集合 a=, 的幂集 p(a) = （） 。答： , ,填空题2 1 3 30设|a|=3 ，则 a上有（）个二元关系。答： 29填空题2 4.1

7、3 实用文档标准文案31q：我将去上海，r：我有时间，公式)()(qrrq的自然语言为（） 。答：我将去上海当且仅当我有空填空题2 2.1 3 32公式)()(qppq的主合取范式是（） 。答：)()()()(qpqpqpqp填空题2 2.3 3 33若,21mssss是集合 a的一个分划， 则它应满足 （） 。答：asjissimiji1)2()()1 (填空题2 4.4 3 34代数系统 中，|a|1 ， 如果和e分别为 的幺元和零元， 则和e的关系为（） 。答：e填空题2 8.1 3 35设,2|nnxxan，定义 a上的二元运算为普通乘法、除法和加法，则代数系统 中运算 * 关于（）运

8、算具有封闭性。答：乘法填空题2 8.1 3 36设 是由元素ga生成的循环群，且|g|=n ，则 g = ( )。答：,12eaaaagnn，填空题2 8.3 4 37一个图是平面图的充要条件是 ( )。答：它不包含与k3, 3或 k5在 2 度结点内同构的子图填空题2 6.4 3 38某 人 有 三 个 儿 子 ， 组 成 集 合a=s1,s2,s3 ， 在a 上 的 兄 弟 关 系 具 有（）性质。答：反自反性、对称性、传递性填空题2 4.1 3 39若baf :是函数，则当f 是ba的（） ，abfc:是 f答：双射填空题2 5.2 3 实用文档标准文案的逆函数。40设 p：它占据空间，

9、 q：它有质量， r：它不断运动， s ：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为（） 。答：rqps填空题2 2.1 3 41设 a，b是两命题公式，ba当且仅当（） 。答：tba填空题2 2.1；2.2 3 42对 谓 词 公 式),(),(),(yxxrzxzqyxyp的 自 由 变 元 代 入 得( )。答：),(),(),(wxxrzuzqyuyp填空题2 3.1；3.2 3 43对集合 x和 y，设 |x|=m ，|y|=n ，则从 x到 y的函数有 ( )个。答： nm填空题2 5.1 3 44若关系 r是等价关系 , 则 r满足 ( )性质。答：

10、自反性、对称性、传递性填空题2 4.4 3 45关系 r的传递闭包t (r) = ( ) 。答：rrii1填空题2 4.3 4 46代数系统,a是群，则它满足( )。答：运算 *在 a 上封闭， * 在 a 上可结合， *在 a上存在幺元，a中每个元素都有逆元；填空题2 8.2；8.3 3 47设,ba和是两代数系统，f是,ba到的同态映射，则f具有答：)()()(,)()()(,bfafbafbfafbafaba填空题2 8.2；8.3 3 实用文档标准文案( )性质。48若连通平面图evg,共有r 个面，其中eevv,，则它满足的euler 公式为 ( )。答：2rev填空题2 6.4 3

11、 49树 t的边数 e 与点数 v 有关系 ( )。答：1ve填空题2 7.1；7.2 3 50n 个命题变元有( )个互不等价的极小项。答：n2填空题2 2.2；2.3 3 51按 de-morgan 定理，ininaaaa121 =( )。答：)(1inia填空题2 2.2；2.3 3 52公式)(rqp的主析取范式为( )。答：7,5,4, 3,2,1,0)()()()()()()(rqprqprqprqprqprqprqp填空题2 2.3 4 53设 p(x) ：x 是大象， q(x) ：x 是老鼠， r(x,y)：x 比 y 重，则命题“大象比老鼠重”的符号化为( )。答：),()(

12、)(yxryqxpyx填空题2 3.1 3 54设,cbax，x上的关系r的关系矩阵是111011101rm，则rrm( )。答：111111111填空题2 6.3 4 55在 具 有n个 结 点 的 有 向 图 中 ， 任 何 基 本 通 路 的 长 度 都 不 超 过答： n-1 填空2 6.1 3 实用文档标准文案( ) 。题56任 何 图 的 点 连 通 度)(g， 边 连 通 度)(g， 最 小 点 度)(g的 关 系 为( )。答：)()()(ggg填空题2 6.1；6.2 3 57结点数n（3n）的简单连通平面图的边数为m ，则m 与 n 的关系为( )。答：63nm填空题2 6

13、.4 4 58群 g的非空子集h是 g的子群当且仅当若x , yh 则( )。答：hyx1填空题2 8.3 4 59代数系统,a是环，若对运算“”还满足( )则,a是整环。答：含幺元，可交换，无零因子填空题2 8.2；8.3 5 60给定命题公式a、b，若（） ，则称 a和 b是逻辑相等的。答：对于 a，b中原子变元nppp,21任意一组真值指派， a和 b的真值相同。填空题2 2.1 3 61设,cbaa考虑下列子集,1cbbas，,2cabaas，,3cbas，,4cbas,5cbas，,6caas则 a的覆盖有（） ，a的划分有（） 。答：54354321,ssssssss，；填空题2

14、4.4 4 实用文档标准文案62若evg,为哈密顿图，则对于结点集v的每个非空子集s，均有p(g-s) （）s成立，答：填空题2 6.4 4 63某班有学生 50人 , 有 26人在第一次考试中得优, 有 21人在第二次考试中得优,有17人 两 次 考 试 都 没 有 得 优 , 那 么 两 次 考 试 都 得 优 的 学 生 人 数 是（） 。答： 14 填空题2 1 3 64给命题变元p、s 和 r 指派真值1,q 指派真值0, 公式 p( (s r) q) s)的真值为（） 。答： 1 填空题2 2.1；2.2 3 65设 p：我生病， q：我去上课，命题“我虽然生病但我还是去上课”符号

15、化为：（） 。答：qp填空题2 2.1；2.2 3 66公式xa(x) xb(x) 的前束范式为（） 。答：)()()()(xbxaxxbxax或填空题2 3.2 4 67若1,2,3,4上的二元关系r=,则 r 的自反闭包r(r )=（） 。答： r(r)=, 填空题2 4.1；4.2 4 68有向图 d如下，则d的邻接矩阵a(d) = （） 。答：0010100011001010填空题2 6.3 3 实用文档标准文案695 阶的群有（）个不同的子群。答： 2 填空题2 8.3 4 70一棵高度为5 的二元树结点数最多为（） 。答： 63 填空题2 7.1；7.2 3 71一个连通平面图g有

16、 10 条边， g中度为 1 的顶点有2 个，其余是度为6 的顶点，则 g中共有（）个顶点，（）个面。答： 5， 7 填空题2 6.1；6.2 3 72集合x=0,1,2,3，r是x上的二元关系，r=,，则 r 的关系矩阵mr是（） 。答：0010100110100110填空题2 6.2；6.3 3 73无向图 g中有 n 个结点 m条边，且g中每个结点的度数不是k 就是 k+1, 则 g中度数为k 的结点的个数是（） 。答： (k+1)n-2m 填空题2 6.1；6.2 3 74设 z+=x xzx0 ，* 表示求两个数的最小公倍数的运算，则* 运算的幺元是（） 。答： 1 填空题2 8.1

17、；8.2 3 75群总共有（）个不同的子群。答： 2 填空题2 8.1；8.2 4 实用文档标准文案76在个体域d=a,b 中，与公式xa(x) 等价又不含量词的公式是（） 。答： a(a) a(b) 填空题2 3.1；3.2 3 77具有 4 个结点的有向完全图的边数为（）条。答： 24 填空题2 6.1 3 78若 p：他聪明； q：他用功； 则“他虽聪明， 但不用功”，可符号化为 （） 。 答： p q 填空题2 2.1 3 79若集合 a=1, 2, 3上的二元关系r1和 r2的关系图如下所示，则 r1or2 =（） 。答： r(r)=,填空题2 4.1；4.2 3 80树是平面图，它

18、有（）个面。答： 1 填空题2 6.1；7.1 3 81哈密尔顿回路要求经过图中（）一次且仅一次。答：每个顶点填空题2 6.4 3 82有向图 d如下： d的邻接矩阵a=(aij)33, 则 a11= （） ,a32= （） 。 答： 1， 0 填空题2 6.3 3 83在一棵根树中，仅有一个结点的入度为（） ，称为树根，其余结点的入度均为（） 。答： 0， 1 填空题2 7.2 3 实用文档标准文案84合式公式q (p(pq) 与 q p的关系是 _的。 （等价或蕴含选一）答：等价填空题2 2.2；2.3 3 85设 r为非空集合a上的二元关系，如果r满足（） ，则称 r 为 a上的一个偏序

19、关系。答：自反、反对称、传递填空题2 4.3 3 86设 r为 a 上的关系，则r的自反闭包r(r)= （） ，对称闭包s(r)= （） 。答： rix, rrc填空题2 4.3 4 87一棵高度为3 的二叉树结点数最多为（） 。答： 7 填空题2 7.1；7.2 3 88设 z是整数集，在z 上定义二元运算*为 a*b=a+b+a? b，其中 +和 ? 是数的加法和乘法，则代数系统 的幺元是 （） ，零元是（） 。答： a , 0 填空题2 8.1；8.2 3 89设 t是有 n 个结点的完全二叉树，则t 叶子数为（） 。答： (n+1)/2 填空题2 7.1；7.2 3 90设 a=a,b,c,则 aa中的元素有 ( )。答： 9 填空题2 1；4.1 3 91图 g与其对偶图g*的结点数目（）相等。答：不一定填空题2 6.4 4 92设3,2, 1s，定义ss上的等价关系,|,cbdassdcssbadc