3. 一棵树有 2 个 4 度结点,3 个 3 度结点, 其余为树叶, 则该树中树叶个数是 () A. 7 B. 8 C. 9 D. 10 答案 :C 解析 : 根据无向树的定义,2 个 4 度结点可以组成艹树状,3 个 3 度节点可以通过艹 6 个结点中选择任意 3 个结点上分别悬挂 2 片

Size: px

Start display at page:

Download "3. 一棵树有 2 个 4 度结点,3 个 3 度结点, 其余为树叶, 则该树中树叶个数是 () A. 7 B. 8 C. 9 D. 10 答案 :C 解析 : 根据无向树的定义,2 个 4 度结点可以组成艹树状,3 个 3 度节点可以通过艹 6 个结点中选择任意 3 个结点上分别悬挂 2 片"

之莫
5 years ago
Views:

1 离散数学 2017 年 10 月真题及答案解析单项选择题 : 本大题共 10 小题, 每小题 3 分, 共 30 分 1. 令 P: 他怕困难,q: 他战胜困难, 命题他战胜困难是因为他不怕困难的符号化形式为 () A. B. C. D. 答案 :A 解析 : 他不怕困难是他怕困难的否定式, 命题他战胜困难是因为他不怕困难化成基本结构为因为他不怕困难, 所以他战胜困难, 典型的蕴涵式因此, 符号化形式为, 选 A 2. 令 F(x):x 为苹果,H(x,y):x 与 y 完全相同,L(x,y):x=y, 则命题没有完全相同的苹果的符号化形式为 () A. B. C. D. 答案 :B 解析 : 本题命题没有完全相同的苹果中, 没有指明个体域, 因而采用全总个体域其中相同的苹果需要任意两个苹果进行比较, 即是两个苹果同时非同一个苹果且完全相同, 符号化为果符号化为, 因此选 B ; 没有为否定词 ; 则没有完全相同的苹 1

2 3. 一棵树有 2 个 4 度结点,3 个 3 度结点, 其余为树叶, 则该树中树叶个数是 () A. 7 B. 8 C. 9 D. 10 答案 :C 解析 : 根据无向树的定义,2 个 4 度结点可以组成艹树状,3 个 3 度节点可以通过艹 6 个结点中选择任意 3 个结点上分别悬挂 2 片树叶即可这样树叶总个数为 9 故选 C 4. 设集合 A={a,b,c,d}, 现有 A 上的二元关系 R={<a,b>,<b,c>,<c,b>,<b,a>,}, 则 A 是 () A. 自反的 B. 对称的 C. 反对称的 D. 传递的答案 :B 解析 : 二元关系 R 中典型满足系的定义故选 B 即满足对称的关 5. 下图中为欧拉图的是 () A. A. B. B. C. C. 2

3 D. D. 答案 :C 解析 : 根据欧拉图的定义, 具有欧拉回路的图为欧拉图, 其充分必要条件是连通的且不含有奇度顶点而 ABD 三个选项中均有奇度顶点, 故选 C 6. 下列谓词公式中, 不是前束范式的为 () A. B. C. D. 答案 :D 解析 : 根据一阶逻辑前束范式的定义, 所有约束量词只能在公式最前面, 后面公式不能出现量词, 排除选项 ABC, 故选 D 7. 表示集合之间关系的图是 () A. 文氏图 B. 哈斯图 C. 欧拉图 D. 树答案 :A 解析 : 根据集合代数理论, 表示集合之间关系与运算的图为文氏图, 故选 A 8. 无向完全图的边的条数为 () A. 10 B. 15 C. 20 3

4 D. 30 答案 :B 解析 : 根据无向完全图的定义, 可以 6 结点中每一个都与其余 5 个相邻接, 其边数计算公式为 n(n-1)/2, 带入 n=6, 则为 15, 故选 B 9. 设 T 是 n 阶树 (n 2), 则 T 不具有的性质是 () A. 连通图 B. 哈密顿图 C. 有 n-1 条边 D. 至少有两片树叶答案 :B 解析 : 根据树的定义及等价命题,n 阶树一定是连通的, 且有 n-1 条边, 至少有两片树叶, 但不会有回路, 因此不是哈密顿图 ( 具有哈密顿回路的图 ), 故选 B 10. 设 R S 均为集合 A 上的二元关系, 下面命题正确的是 () A. 若 R 与 S 是自反的, 则也是自反的 B. 若 R 与 S 是反自反的, 则也是反自反的 C. 若 R 与 S 是对称的, 则也是对称的 D. 若 R 与 S 是传递的, 则也是传递的答案 :A 解析 : 根据二元关系的运算规律, 两个二元关系的右复合只有自反性保持不变, 故选 A 11. 以下关于图的矩阵的描述, 正确的是 () A. 邻接矩阵即关系矩阵 B. 可达矩阵是针对无向图的 C. 无向图有邻接矩阵 D. 可达矩阵是针对有向图的答案 :C 4

5 解析 : 根据图的矩阵的描述理论, 邻接矩阵与关系矩阵是不同的, 无向图与有向图都有关系矩阵, 邻接矩阵仅应用于有向图, 故选 C 12. 一个 6 阶连通图的边数至少为 () A. 4 B. 5 C. 6 D. 7 答案 :B 解析 : 根据连通图的概念, 必须存在 6 个顶点至少经过一次的通路, 最简单的通路就是 6 个点用 5 条线连接而没有圈的情况, 故选 B 13. 下列关于反函数的命题, 正确的是 () A. 单射函数有反函数 B. 任意函数均有反函数 C. 满射函数有反函数 D. 双射函数有反函数答案 :D 解析 : 根据反函数的定义, 双射函数有反函数, 双射函数的反函数也是双射函数, 故选 D 14. 一个 6 阶图, 其各结点度数之和不可能为 () A. 10 B. 12 C. 15 D. 20 答案 :C 解析 : 根据欧拉握手定理, 无向图的各结点度数之和等于边数的 2 倍, 因此总度数不会是奇数, 故选 C 15. 在整数集合 Z 上定义 * 运算如下 :a b Z,a*b=a+b-10, 则代数系统 <Z,*> 是 () A. 格 5

6 B. 环 C. 域 D. 群答案 :D 解析 : 根据运算规律 a*b=a+b-10, 可以看到具有单位元 : 由 a*e=a 推出 e=10, 同时具有逆元 : 由 a*a-1=e 推出 a-1=20-a, 既有单位元又有逆元, 恰为群的定义, 故选 D 填空题 : 本大题共 10 小题, 每小题 2 分, 共 20 分 16. 设 Σ={a,b} 是字母表,Σ* 表示由 Σ 上的字符构成的有限长度的串的集合 ( 包含长度为 0 的串, 即空串在内 ),A={a,b,aa,bb,aaa,bbb},B={ω ω Σ* ω 2},C={ω ω Σ* ω 2}, 则 A -(B C) = 答案 :{A,B,AAA,BBB} 解析 : 根据题意,B C ={ 所有长度为 2 的字符串 }={aa,bb,ab,ba}, 则 A-(B C)= {a,b,aaa,bbb} 17. 在整数域中, 命题公式的真值为, 命题公式的真值为答案 :T,F 解析 : 根据命题公式的意义, 第一个公式表示对任意一个 x 存在一个 y 与之相乘为 0, 显然在整数域中只要取 y=0 即可满足, 因此是正确的 ; 第二个公式表示存在一个 x 与任意一个 y 相乘为 1, 显然在整数域是不可能实现的, 因此是错误的 18. 设 A 为非空有限集合,P(A) 为 A 的幂集, 为集合的并运算, 群 <P(A), > 中, 单位元是, 零元是答案 :,A 解析 : 根据单位元定义, 设任意集合集合即 A 为零元则由即为单位元 ; 根据零元的定义, 设任意 19. 一个手镯等距离地镶嵌着 5 颗彩珠, 每颗彩珠可以从红白蓝绿黄 5 种颜色中挑选如果要求手镯上的彩珠颜色都不相同, 则可以构成种不同颜色彩珠分布的手镯答案 :120 解析 : 颜色集合由红白蓝绿黄 5 种颜色组成, 根据排列组合知识可得 5!= 某连通平面图有 6 个顶点, 其平面表示中共有 8 个面, 则其边有条 6

7 答案 :12 解析 : 根据连通平面图的欧拉定理 : 顶点数 - 边数 + 面数 =2, 可得边数 =6+8-2= 设有集合 A={a,b,c,d} 上的二元关系 R={<a,b>,<b,a>,<c,c>,<d,d>}, 则 R2=,R3= 答案 :{<A,A>,<B,B>,<C,C>,<D,D>},{<A,B>,<B,A>,<C,C>,<D,D>} 解析 : R2={<a,a>,<b,b>,<c,c>,<d,d>},R3={<a,b>,<b,a>,<c,c>,<d,d>} 于是 22. 为了从无向完全图 K6 中得到其生成树, 至少需要删除条边答案 :10 解析 : 无向完全图 K6 共有边数为 n(n-1)/2=15 条, 而有 n 个顶点的树有 n-1 条边, 即有 6-1=5 条边, 所以至少要删除 15-5=10 条边 23. 设有集合 A={a,b,c} 上的二元关系则 R1 的自反闭包 r(r1)=,r1 的对称闭包 s(r1)= 答案 :{<A,B>,<A,C>,<C,B>,<A,A>,<B,B>,<C,C>},{<A,B>,<A,C>,<C,B>,<B,A>,<C,A>,<B,C>} 7

8 解析 : 于是 r(r1)={<a,b>,<a,c>,<c,b>,<a,a>,<b,b>,<c,c>},s(r1)= {<a,b>,<a,c>,<c,b>,<b,a>,<c,a>,<b,c>} 24. 一个无向图有 21 条边, 有 3 个 4 度结点, 其余结点均为 3 度, 则其结点共有个答案 :13 解析 : 根据欧拉握手定理, 无向图的各结点度数之和等于边数的 2 倍, 设共有 x 个节点,3*4+ (x-3)*3=21*2, 则 x= 设集合 A={1,2,3}, 集合 B={a,b,c,d,e}, 则 A B =, 而 P(A) B = 答案 :15,40 解析 : A =3, B =5, 所以 A B =3 5=15 P(A) =2 A =23=8, B =5, 所以 P(A) B =8 5=40 计算题 : 本大题共 5 小题, 每小题 6 分, 共 30 分 26. 用列真值表的方法说明下列逻辑等价式成立答案 : 解 : 分别列出两个命题公式的真值表如下 : 解析 : 逻辑等价式必须具有相同的真值表, 这是等价式的充分必要条件 27. 用等值演算法推导命题公式的主析取范式答案 : 解析 : 利用等值式的运算规律与置换原则转换成主析取范式 28. 设解释 Ⅰ 为 : 个体域 D={a,b},F(x) 与 G(x) 为 2 个一元谓词, 且 F(a)=0,F(b)=1,G(a)=1, G(b)=0 在 Ⅰ 下, 求命题公式的真值 8

9 答案 : 解 : 在解释 I 下设集合 S={1,2,3}, 题 29 图为 S 上的二元关系 R 的关系图 (1) 写出 R 的集合表达式 ;(2) 写出 R 的关系矩阵答案 :(1) 由题 29 图二元关系 R 的关系图可得,R={ 1,1, 2,2, 3,3, 1, 2, 2,1, 2,3, 3,1 }(2)R 的关系矩阵为解析 : 根据二元关系 R 的关系图的集合表达式方法与关系矩阵构造方法即得 30. 求下述集合等式成立的充要条件, 并证明结论答案 :(1) 成立的充要条件是 (2) 现在证明以上结论. 证明 : 解析 : 根据集合的运算规律证明即可证明题 : 本大题共 3 小题, 每小题 7 分, 共 21 分 31. 设 n 阶无向简单图 G=<V,E>, 其中边数满足 : E >(n-1)(n-2)/2, 证明 G 是连通图答案 : 证明 : 假设 G 不是连通图, 不妨设 G 有两个连通分支 G1<V1,E1> 和 G2<V2,E2>, 且 V1 =N1, V2 =N2, 易见 N1+N2=N, 由于 N1 1,N2 1, 所以 N1*N2-( N1+N2)+1 0 (*) 而 E1 N1(N1-1)/2, E2 N2(N2-1)/2, 从而 E = E1 + E2 N1(N1-1)/2+ N2(N2-1)/2 由式 (*) 可得,N1(N1-1)/2+ N2(N2-1)/2 [(N1+N2)2-3(N1+N2)+2]/2=(N-1)(N-2)/2, 即 E (N-1)(N-2)/2 这与题设条件 E >(N-1)(N-2)/2 矛盾, 故 G 是连通图解析 : 根据连通图的定义及边数计算公式即可证明 32. 证明下列谓词公式为永真式 : 答案 : 证明 : 利用谓词等值式, 可得易见, 这是一个永真式所以, 为永真式解析 : 利用谓词等值式即可转换为易于判断的永真式 33. 设 a b c 均为奇数, 证明一元二次方程 ax2+bx+c=0 无有理数根 9

10 答案 : 证明 : 设 AX2+BX+C=0 有有理数根, 不失一般性, 设根为 P/Q, 这里 P,Q 均为整数, 且 Q 0, 并且 P,Q 不能同时为偶数, 于是 A(P/Q)2+B(P/Q)+C=0 AP2+BPQ+CQ2=0P,Q 的奇偶性有四种情况, 而 A B C 均为奇数, 于是可得下表 : 由此可见,AP2+BPQ+CQ2 均为奇数, AP2+BPQ+CQ2=0 不成立所以, 一元二次方程 AX2+BX+C=0 无有理数根解析 : 利用命题公式真值表的结构来证明综合应用题 : 本大题共 2 小题, 每小题 7 题, 共 14 分 34. 无向树 T 有 8 片树叶,2 个 3 度分支点, 其余的分支点都是 4 度, 求 T 的阶数, 并画出全部非同构的这种树答案 : 解 : 设 4 度结点有 X 个, 由握手定理可得 2(8+2+X-1)=5*1+3*2+4X 解方程得 X=2, 即 T 为 12 阶, 全部的非同构树共有 6 棵, 如下所示 : 解析 : 先利用握手定理求出树的阶数, 再按照要求画出非同构树 35. 设 <A, > 为偏序关系, 其中为整除关系, 即 ab 当且仅当 a 整除 b 已知 A={1,2,3,5,6,15,30}, 画出这个偏序关系的哈斯图, 并判断其是否为格答案 : 解 : 根据各元素的关系, 可以画出哈斯图如下 : 从图上可见, 任意两个元素都有上确界和下确界存在, 故为格解析 : 根据偏序关系的定义, 画出哈斯图, 再根据格的定义确定是否为格 10

第一章三角函数 1.3 三角函数的诱导公式 A 组 ( ) 一选择题 : 共 6 小题 1 ( 易诱导公式 ) 若 A B C 分别为 ABC 的内角, 则下列关系中正确的是 A. sin( A B) sin C C. tan( A B) tan C 2 ( 中诱导公式 ) ( ) B. cos(

第一章三角函数 1.3 三角函数的诱导公式 A 组 ( ) 一选择题 : 共 6 小题 1 ( 易诱导公式 ) 若 A B C 分别为 ABC 的内角, 则下列关系中正确的是 A. sin( A B) sin C C. tan( A B) tan C 2 ( 中诱导公式 ) ( ) B. cos( 第一章三角函数 1. 三角函数的诱导公式 A 组一选择题 : 共 6 小题 1 ( 易诱导公式 ) 若 A B C 分别为 ABC 的内角则下列关系中正确的是 A. sin( A B) sin C C. tan( A B) tan C ( 中诱导公式 ) B. cos( B C) cos A D. sin( B C) sin A sin60 cos( ) sin( 0 )cos( 70 ) 的值等于