2022年《离散数学》模拟题.docx

《2022年《离散数学》模拟题.docx》由会员分享，可在线阅读，更多相关《2022年《离散数学》模拟题.docx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -优秀学习资料欢迎下载v 的入度,记为）； 第 1 页,共 20 页 - - - - - - - - - 北 航10 秋 学 期 离 散 数 学 模 拟 题 一一、单项挑选题（本大题共15 小题,每道题2 分,共 30 分）1.中全部有限长度的串形成的集合记为* ,简单证得*上的连接运算不满意交换律,但满意（A ）A结合律B安排律C幂等律D吸取律2.Klein 群中元素 a,b,c的阶为（B ）；A 1 B2 C3 D4 3.群 G 的元素 x 的全部幂的集合为G 的子群 ,称由 x 生成的子群；记为（A ）

2、. A Bx C x Dx 4.交换环是指乘法满意（A ）；A交换律B结合律C安排律D吸取律5.至少有（B ）元素的含单位元、无零因子环称为除环；A一B二C三D四6.,满意 C 的格称为安排格A交换律B结合律C安排律D幂等律7.如 L 为有限布尔代数,就（B ）正整数 n,L 与含有 n 个元素的集合A 的幂集同构；A不存在B存在C有可能存在8.有向图 D 的顶点 v 作为边的始点的次数之和称为v 的出度,记为d+v, v 作为边的终点的次数之和称为d-v, v 的度数 dv= A ；A d +v+d-v B d+v Cd-v Dd+v*d-v 9.如通路 =v0e1v 1e2 e1v1中全部

3、顶点互不相同全部边自然互不相同时称为（B ）A初级回路B路径C复杂通路D迹10.在 n 阶图中,如一顶点存在到自身的回路,就必存在从该顶点到自身的长度不超过 B 的回路；A n-1 B n Cn+1 D 2n 11.“ 人总是要死的” 谓词公式表示为（C ）；（论域为全总个体域）Mx ：x 是人； Mortalx ： x 是要死的；AMxMortalx；BMx MortalxCxMxMortalx；DxMxMortalx12.公式AxP xQx的说明 I 为：个体域 D=2 , Px： x3, Qx ： x=4 就 A 的真值为（A A 1；B 0；C可满意式；D无法判定；13.以下等价关系正

4、确选项（B ）；AxPx QxxPxxQx；细心整理归纳 精选学习资料 - - - - - - - - - - - - - - -名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -14.BxPxQxC ,优秀学习资料欢迎下载）；xPxxQx；CxPxQ xPxQ；DxPxQxPx Q；以下偏序集（）能构成格；15.设s,11,2 ,13 ,1,4 , *为一般乘法,就S, * 是（D 234A代数系统；B半群；C群；D都不是；参考答案：1-5 ABAAB 6-10 CBABB 11-15 CABCD 二、填空题（本大题共 4 题, 16 题 2 分,其它每空

5、 3 分,共 20 分）16、设格中表达式 E = a b cd,就 E 的对偶表达式 E*=_ ；考核学问点：格的对偶表达式,参见教材 P144 参考答案：（a b）（ c d）17、设集合A = a, b, c, d, e , A 上半序关系R 的哈斯图如下图所示,就A 的极大元为 _,微小元为 _；考核学问点：半序关系的极值,参见教材P93 参考答案：a c,d 18、由集合运算的基本定律：（ 1） A A = A ,满意 _律；（ 2） A E = E,满意 _律；（ 3） A E = A,满意 _律；（ 4） A A = ,满意 _律；考核学问点：集合的运算律,参见教材 P65-67

6、 参考答案：等幂律零一律同一律R的真值互补律 第 2 页,共 20 页 三、问答题（本大题共3 小题,每道题10 分,共 30 分）19求命题公式QRPPQRP细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -考核学问点：命题公式的真值表P优秀学习资料欢迎下载,参见教材 P5 参考答案：QR PQRPRQRPPQR PRPRQQPR120、设集合 A 0 , 1,2,3,4, 5,6 上的偏序关系 R如下：R , I A做偏序集 的哈斯

7、图,并求 B=0,2,3 的极大元、微小元、最大元和最小元；考核学问点：偏序关系的极值,参见教材 P93 参考答案： A 0,1,2,3,4,5,6, B=0 ,2, 3 ,哈斯图如右图B 的极大元： 2, 3, B 的微小元： 0 B 的最大元：无 B 的最小元： 0 21、说明 N 如下：个体域 D N 为全体自然数的集合DN中特定元素a=0 xy,gx,yxyDN上函数fx,yD 上谓词Fx ,y为xy在说明 N 下,判定公式的真假：（ 1）个体域为自然数集合D N；y,gx ,yxy；（2）DN 上特定函数fx ,yx考核学问点：前束范式,参见教材 P48 参考答案：（1）在说明N 下

8、,gx ,ax00 ,Fgx ,a,x0x ,y,xyS所以,RS 有反对称公式xFgx ,a,x成为详细命题：“任自然数等于0”；明显为假命题；2在说明N 下,xyzFfx ,y,z成为xyzxyz,即 “ 任二自然数的和仍为自然数” ；明显为真命题；四、证明题（此题共2 小题,每道题10 分,共计 20 分）22证明假如非空集合A 上的二元关系R 和 S 是偏序关系,就RS也是 A上的偏序关系；考核学问点：偏序关系的判定,参见教材P91 参考答案： xA ,x ,xR ,x,xSx ,xRS,所以RS有自反性；x,yA,由于 R, S 是反对称的,x,yRSy,xRSx,yRx ,yS y

9、,xRx,yRy,xRx,ySy,xS xyyxx性x ,y,zA,由于 R,S 是传递的, 第 3 页,共 20 页 x,yRSy,zRS细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -x,ySRx,ySy,zR优秀学习资料欢迎下载y,zSx,yRy,zRx,ySy,zSx ,zRx,zSx,zRS所以,R有传递性；总之, R 是偏序关系；23设 A, B,C为三个集合,证明如 C A就 A B C A B C 考核学问点：集合的运

10、算 参见 P 65 参考答案：x A B C x A B x C x A x B x C x A x C x B x C x A x B C x A B C 即 A B C A B C 北 航 10 秋 学 期 离 散 数 学 模 拟 题 二一、单项挑选题（本大题共 15 小题,每道题 2 分,共 30 分）1. 设集合 A 1 ,2, 3 , A 上的关系 R 1 , 1, 2,2 ,就 R 不具有关系的（A ）性质；A.自反性 B.对称性 C.传递性 D.反对称性2. 设集合 A a, b, c ,A 上关系 R 的关系图如下图所示,就 R 具有（B ）；A.自反性、对称性、传递性B.自反

11、性、传递性C.对称性、反对称性D.对称性、反对称性、传递性3.设命题公式G（ PQ）, HP（ QP）,就 G 与 H 的关系是（A ）；）公式不成立；4.A.GHB.HGC. GH D.以上都不是下面给出的一阶规律等价式中,（ B ）是错的；5.A. x（ Ax Bx ）x Ax x Bx B. x（ Ax Bx ）xAx xBx C. xAx x（Ax ）D. AxBx x（ ABx ）如下图所示,半序集中哪个不是格？（B ）6.设（ B, , 0, 1）是布尔代数, a, b 是 B 中元素, a b,就下面（C 细心整理归纳 精选学习资料 - - - - - - - - - - - -

12、 - - - 第 4 页,共 20 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -7.A. ab= 0 B.平面图B. 优秀学习资料欢迎下载a b = 1 C. ab= 1 D. ab=a下图是（C ）；C.哈密顿图D.欧拉图A.完全图8.00100R 产 生的SS上一个划分000111000001001已知图 G 的相邻矩阵为01010,就 G 的边数与分枝数为（B ）9.A. 5, 3 B. 4,2 C. 5, 1 D. 6, 4 如干能等值地表示出全部合式 公式 真值函数 的规律联结词集合称为（A ）10.A

13、 全功能集B功能集C全功能联结词集合D特别联结词集合以下不是微小全功能集的是（D ）11.A , B , C , D , 设S,1 ,12 ,就2S有（D ）个元素；12.A 3；B6；C7；D 8 ；设S,12 ,3,定义SS上的等价关系Ra,b,c,d|a,bSS ,c,dSS,adbc 就由13.共有（B ）个分块；D ）性质；A 4；B 5；C6；D 9 ；设S,12 ,3, S 上关系 R 的关系图为,就 R 具有（A自反性、对称性、传递性；B反自反性、反对称性；,a,bZ 第 5 页,共 20 页 C反自反性、反对称性、传递性；D自反性；14.设,为一般加法和乘法,就（A ）S ,

14、是域；ASx|xab3,a ,bQBSx|x2nCSx|x2n1,nZDSx|xZx0 = N ；细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -15.下面偏序集（B ）能构成格；优秀学习资料欢迎下载参考答案：1-5 ABABB 6-10 CCBAD 11-15 DBDAB,值域为 _；_二、填空题（此题共5 小题,每题4 分,共 20 分）16、已知A=,a,那么 2A=_；考核学问点：幂集参见 P 65 参考答案： , , a,a

15、17、设（ 0,0）、（ 0,2）,（ 2,0）,（ 3,2） 就的定义域为考核学问点：函数的域参见 P 93 参考答案：D 0 2 3 R 0, 218、已知 # A n , # B m（nm）问存在 _个不同的 A 到 B 上的内射；考核学问点：映射 参见 P 97 参考答案：A m nm m 1. m n 119、整数集上的四就运算中不能保证封闭性的是 _；考核学问点：整数集合运算的封闭性 参见 P 66 参考答案： 减法和除法20、写出群中生成元的定义_；1,问度数为3 的结点有几个？考核学问点：群的生成元参见 P 131 参考答案： g 为生成元 , 就任给群中的一元素a , 那么存

16、在整数K, 使得agK三、问答题（此题共3 小题,每道题10 分,共计 30 分）21、一棵树有1 个结点度数为5, 2 个结点度数为4,5 个结点度数为2,14 个结点度数为考核学问点：树的结点,参见P 177 参考答案： 设 T 是n,m 图, 度为 3 的结点数为 x , 就 n=1+2+5+14+ x =22+ xndeg i1 5245 214 13x 第 6 页,共 20 页 由握手定理 2m=i13x373x581014222x1373xx42375细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳

17、总结 精品学习资料 - - - - - - - - - - - - - - -优秀学习资料 欢迎下载答：有 5 个度数为 3 的结点；22设 , 是实数集合 R 上的三个映射,其中, x x / 5, x2x+3, x x2+1 对 x R,试求复合映射 , , 和 ,并指出这些映射中哪些是双射？考核学问点：映射,参见 P 97 参考答案： （x）（ 2 x 3）/5； （x） 2 x /53； （x） 4 x9； （ x） 2 x 2 5； （ x）（ 4 x 212 x10）/5 其中 , , 是双射；23、 F= Q. . PQ P 是什么类型的公式？说明理由；考核学问点：重言式 参见

18、P 8 参考答案：Q P Q P Q P P Q P Q Q P Q Q P 1 P 1所以为重言式；24设（ L,）是一个安排格,x, y 是格中任意元素,假如对格中某个元素a,有a xa y, ax ay,就 x y；考核学问点：安排格,参见 P 148参考答案：.x = x （ x a）=（ x x） （ xa）=x （ ay）=（ x a）（ x y）=（ a y）（ x y）=（ ax） y =（ ay） y = y 北航 10 春学期离散数学考试模拟题一一、单项挑选题（本大题共 15 小题,每道题 2 分,共 30 分）1、设 G是有 6 个结点的无向完全图,从 G中删去 C 条边

19、,就得到树；A 6 B 9 C 10 D 15 2、设 G是连通平面图,有 v 个结点, e 条边, r 个面,就 r= A A ev2 B ve2 C ev2 D ev2 3、以下各图中存在哈密顿回路的图是 C DA4、以下命题真值为B1 的是 D CA无向完全图都是欧拉图B有 n 个结点 n1 条边的无向图都是树细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页,共 20 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -优秀学习资料 欢迎下载 C无向完全图都是平面图

20、 D树的每条边都是割边 5、以下数组中,不能构成无向图的度数列的数组是 B A 1,1,1,2,3 B 1,2,3,4,5 C 2,2,2,2,2 D 1,3,3,3 6、 B 是布尔代数；A有余有界格 B有余安排格 C有界安排格 D有余代数格7、以下偏序集中是格的为 B CDAB8、在自然数集N上定义的二元运算*,满意结合律的是 C A . ababa ,b B. aba2 bC. abmaxD. abab9、设 AQ Q,其中 Q是有理数集, D 定义 A 上的二元运算 *为 :a,b,x ,yA,a ,b x,yax ,ayb, 就1,2*3,4= A 3,10 B -5,1 C 6,8

21、 D 3,6 10、全体小项合取式为（ C ）；A可满意式 B冲突式 C永真式 D A, B,C 都有可能11、设 A=1 ,2 ,3 ,就 A上有（ D ）个二元关系；A 23 B 32 C 22 D 2312、设S, 1, ,12,就有（ A ）；SA 1,2 B 1,2 C 1 D 213、设 S=1 ,2,3 ,R为 S 上的关系,其关系图如右图所示,就 R 具有（D ）的性质A自反、对称、传递 B什么性质也没有 C反自反、反对称、传递 D自反、对称、反对称、传递14、下面函数（ B ）是单射而非满射； 第 8 页,共 20 页 细心整理归纳 精选学习资料 - - - - - - -

22、- - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -Af:RR ,fx 优秀学习资料欢迎下载x22x1B:ffZR ,xlnxff:RZ,x x ,x 表示不大于 x 的最大整数CDf:RR ,fx 2x1其中 R 为实数集, Z 为整数集, R+,Z+分别表示正实数与正整数集；15、以下代数系统中,只是半群的为 B ；A Z , ,其中 Z 是整数集,a,b Z,a b=a+b 2 B Z , ,其中 Z 是整数集,a,b Z,a b=b C Z , ,其中 Z 是整数集,a,b Z,a b

23、=a+b ab D R0 , ,其中 R是实数集,a,b R,a b=ab 16、设格中表达式 E = ab c d,就 E 的对偶表达式 E*= （a b）（ c d）；考核学问点：格的对偶表达式,参见教材 P144 17、设集合 A = a, b, c, d, e ,A 上半序关系 R 的哈斯图如下图所示,就 A 的极大元为 _a_,微小元为 _ c, d _；考核学问点：半序关系的极值,参见教材 P93 18、由集合运算的基本定律：（ 1） A A = A ,满意 _等幂律；（ 2） A E = E,满意 _零一律 _；（ 3） A E = A,满意 _同一律 _；（ 4） A A =

24、,满意 _互补律 _；考核学问点：集合的运算律,参见教材 P65-67 QP三、问答题（本大题共3 小题,每道题10 分,共 30 分）19、作命题公式PQPQP的真值表,并判定该公式的类型；考核学问点：命题公式的真值表,参见教材P5命题公式PQPQP的真值表P Q PQ PQPQPPQP0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 原式为可满意式；20、设集合 A 0 , 1,2,3,4, 5,6 上的偏序关系 R如下：R, I A做偏序集 的哈斯图,并求 B=0,2,3 的极大元、微小元、最大元和最小元；考核学问点：偏序关系的极值,参见教材

25、 P93 A 0,1,2,3,4,5,6, B=0 ,2, 3 ,哈斯图如右图B 的极大元： 2, 3, B 的微小元： 0 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 9 页,共 20 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -B 的最大元：无B 的最小元： 0 优秀学习资料欢迎下载654 321 021、说明 N 如下：个体域 D N 为全体自然数的集合DN中特定元素a=0 xy,gx,yxyDN上函数fx,yD 上谓词Fx ,y为xy在说明 N 下,判定公式

26、的真假：（ 1）个体域为自然数集合D N；得分评卷人S偏序关系；（2）DN 上特定函数fx ,yxy,gx ,yxy；考核学问点：前束范式,参见教材 P48 （1）在说明N 下,gx ,ax00 ,Fgx ,a,x0x ,公式xFgx ,a,x成为详细命题：“任自然数等于0”；明显为假命题；2在说明N 下,xyzFfx ,y,z成为xyzxyz,即 “ 任二自然数的和仍为自然数” ；明显为真命题；四、证明题（此题共2 小题,每道题10 分,共计 20 分）22、证明假如非空集合A 上的二元关系R 和 S 是偏序关系,就RS也是 A上的考核学问点：偏序关系的判定,参见教材P91 xRy,x所以,

27、RS 有反对称xA ,x ,xR ,x ,xSx ,xRS,所以RS有自反性；x,yA,由于 R, S 是反对称的,x,yRSy,xRSx,yRx ,yS y,x,yRy,xRx,ySy,xS xyyxxy性x ,y,zRA,由于 R,S 是传递的,RSy,zS 第 10 页,共 20 页 x,yRSy,zRSx,yx,ySy,zx,yRy,zRx,ySy,zSx ,zRx,zSx,zR细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -

28、所以,RS有传递性；优秀学习资料欢迎下载总之, R 是偏序关系；23、证明PQQR RPS S；密考核学问点：命题公式的等价,参见教材P8 .Q RPPRQ,析取三段论PQPP,拒取式PSPS,析取三段论北航 10 春学期离散数学考试模拟题二一、单项挑选题（本大题共15 小题,每道题2 分,共 30 分）1、A 封2、 B 线3、 D 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 11 页,共 20 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -优秀学习资料 欢迎下载4

29、、 A 5、 D 6、 C 7、 B 8、 B 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 12 页,共 20 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -优秀学习资料 欢迎下载9、 C 10、 D 11、 A 12、 C细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 13 页,共 20 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -优秀学习资

30、料 欢迎下载13、 D 14、 C 15、 A 二、填空题（此题共5 小题,每题4 分,共 20 分）16、已知A=,a,那么 2A=_, , a,a_； 第 14 页,共 20 页 考核学问点：幂集参见 P 65细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -优秀学习资料 欢迎下载17、设 （ 0,0）、（ 0,2）,（ 2,0）,（ 3,2） 就 的定义域为 D 0 2 3,值域为 _ R 0, 2 _；_ _考核学问点：函数的域 参见 P 93n18、已知 # A n , # B m（nm）问存在 _ A m m m 1. m n 1 _个不同的 A 到 B 上的内射；考核学问点：映射 参见 P 9719、整数集上的四就运算中不能保证封闭性的是 _减法和除法 _；考核学问点：整数集合运算的封闭性 参见 P 6620、写出群中生成元的定义 _ g 为