中央电大离散数学(本科)考试试题(可编辑).doc

《中央电大离散数学(本科)考试试题(可编辑).doc》由会员分享，可在线阅读，更多相关《中央电大离散数学(本科)考试试题(可编辑).doc（32页珍藏版）》请在三一办公上搜索。

1、 中央电大离散数学（本科）考试试题一、单项选择题（每小题3分，本题共15分）1若集合A 1，2 ，B 1，2， 1，2 ，则下列表述正确的是 a AAA B BA BCAA B DAA B2设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 d 图一A（a）是强连通的 B（b）是强连通的C（c）是强连通的 D（d）是强连通的G的邻接矩阵为则G的边数为 b ABCD c 为重言式A P Q P Q B Q P Q Q P Q C Q P P P Q D P P Q Q1若集合A a，b ，B a，b， a，b ，则（ a ）AA B，且A B BA B，但A BCA B，但A

2、B DA B，且A B2集合A 1, 2, 3, 4, 5, 6, 7, 8 上的关系R x，y |x+y 10且x, yA ，则R的性质为（ b ）A自反的 B对称的C传递且对称的 D反自反且传递的3如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有（ b ）个A0 B2 C1 D34如图一所示，以下说法正确的是 d A a, e 是割边 B a, e 是边割集C a, e , b, c 是边割集 D d, e 是边割集图一5设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（ c ）A x A x B x B x A x B x C x

3、 A x B x D x A x B x 1设A a, b ，B 1, 2 ，R1，R2，R3是A到B的二元关系，且R1 a，2 , b，2 ，R2 a，1 , a，2 , b，1 ，R3 a，1 , b，2 ，则（ b ）不是从A到B的函数AR1和R2 BR2 CR3 DR1和R32设A 1, 2, 3, 4, 5, 6, 7, 8 ，R是A上的整除关系，B 2, 4, 6 ，则集合B的最大元、最小元、上界、下界依次为 b A8、2、8、2 B无、2、无、2C6、2、6、2 D8、1、6、13若集合A的元素个数为10，则其幂集的元素个数为（ a ）A1024 B10 C100 D14设完全图

4、K有n个结点 n2 ，m条边，当（ c ）时，K中存在欧拉回路Am为奇数 Bn为偶数 Cn为奇数 Dm为偶数5已知图G的邻接矩阵为 ，则G有（ d ） A5点，8边 B6点，7边 C6点，8边 D5点，7边1若集合A a， a ， ，则下列表述正确的是 c A aa A B AC a A D A V，则下列结论成立的是 c Adeg v 2 E B deg v E C D3命题公式（PQ）R的析取范式是 d A （PQ）R B（PQ）R C（PQ）R D（ P Q）R4如图一所示，以下说法正确的是 a Ae是割点 B a, e 是点割集C b, e 是点割集 D d 是点割集5下列等价公式成立

5、的为 b A P Q P Q BP Q P P P Q C P Q Q P Q D P Q Q1若G是一个汉密尔顿图，则G一定是 d ABC D, 2, 3, 4 上的关系R x，y |x y且x, yA ，则R的性质为（ c ）A不是自反的 B不是对称的C传递的 D反自反3设集合A 1，2，3，4，5 ，偏序关系 是A上的整除关系，则偏序集 A， 上的元素5是集合A的（ b ）A最大元 B极大元 C最小元 D极小元4图G如图一所示，以下说法正确的是 c A a, d 是割边 B a, d 是边割集C a, d , b, d 是边割集 D b, d 是边割集 图一5设A（x）：x是人，B（x）

6、：x是工人，则命题“有人是工人”可符号化为（ a ）A x A x B x B x A x B x C x A x B x D x A x B x 1若集合A a， a ，则下列表述正确的是 a A a AB a AC aa A D APQ）的合取范式是 c A（PQ） B（PQ）（PQ） C（PQ） D （ P Q）3无向树T有8个结点，则T的边数为 b A 图一5下列公式成立的为 d A P Q PQ BP Q P QC P P D PQ1“小于5的非负整数集合”采用描述法表示为_a_A x xN, x 5 B x xR, x 5 C x xZ, x 5 D x xQ, x 5 2设R1，

7、R2是集合A a,b,c,d 上的两个关系，其中R1 a,a , b,b , b,c , d,d ，R2 a,a , b,b , b,c , c,b , d,d ，则R2是R1的_b_闭包A自反 B对称 C传递 D以上答案都不对3设函数f：RR，f a 2a+1；g：RR，g a a2，则_c_有反函数Afg Bgf Cf Dg 4已知图G的邻接矩阵为，则图G有_d_A5点，8边 B6点，7边 C6点，8边 D5点7边5无向完全图K4是_a_A汉密尔顿图 B欧拉图 C非平面图 D树6在5个结点的完全二叉树中，若有4条边，则有_b_片树叶A2 B3 C4 D57无向树T有7片树叶，3个3度结点，

8、其余的都是4度结点，则T有_c_个4度结点A3 B2 C1 D08与命题公式P （Q R）等值的公式是 P Q R B P Q R C P Q R DP Q R 9谓词公式中量词 x的辖域是 B CP x D10谓词公式的类型是蕴涵式永假式 永真式 非永真的可满足式 B C D2若集合A的元素个数为10，则其幂集的元素个数为_b_A1000 B1024C1 D103设集合A 1,2 ，B a,b ，C ，则_c_A 1,a, , 1,b, , 2,a, , 2,b, B 1, a, , 1, b, , 2, a, , 2, b, C 1,a , , 1,b , , 2,a , , 2,b ,

9、D 1,2 , a,b , 4设A 1, 2, 3, 4, 5, 6, 7, 8 ，R是A上的整除关系，B 2, 4, 6 ，则集合B的最大元、最小元、上界、下界依次为_d_A8、1、6、1 B 8、2、8、2C6、2、6、2 D无、2、无、25有5个结点的无向完全图K5的边数为_a_A10 B20 C5 D256设完全图K有n个结点 n2 ，m条边，当_b_时，K中存在欧拉回路An为偶数 Bn为奇数 Cm为偶数 Dm为奇数7一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，则T有_c_个顶点A3 B8C11 D138命题公式（PQ）R的析取范式是_b_A（ P Q）R B （

10、PQ）RC（PQ）R D（PQ）R9下列等价公式成立的是_b_A P Q P Q B P Q P P P Q C P P Q Q DQ P Q Q P Q 10谓词公式的类型是蕴涵式永假式 永真式 非永真的可满足式6命题公式的真值是 T （或1） 7若图G V, E 中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为 W |S| 8给定一个序列集合 000，001，01，10，0 ，若去掉其中的元素 0 ，则该序列集合构成前缀码9已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5

11、 10 x P x Q x R x，y中的变元R x，yA的元素个数为10，则其幂集的元素个数为 1024 7设A a，b，c ，B 1，2 ，作f：AB，则不同的函数个数为 8 8若A 1,2 ，R x, y |x A, y A, x+y 10 ，则R的自反闭包为 1,1 , 2,2 9结点数v与边数e满足 e v-1 关系的无向连通图就是树6设集合A a，b ，A的幂集是 , a,b , a , b 7如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有 2 个 8设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树9设连通平面图G的

12、结点数为5，边数为6，则面数为 3 10设个体域D a, b ，则谓词公式 x A x （ x）B（x）消去量词后的等值式为 A a A b B（a）B（b） 6设集合A 0, 1, 2, 3 ，B 2, 3, 4, 5 ，R是A到B的二元关系，则R的有序对集合为 2, 2 ， 2, 3 ， 3, 2 ， 3, 3 7设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r 2 8设G V, E 是有6个结点，8条边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成树9无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数10设个体域D 1

13、,2 ，则谓词公式消去量词后的等值式为A 1 A 2 6命题公式的真值是 T （或1） 7若图G V, E 中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为 W |S| 8给定一个序列集合 000，001，01，10，0 ，若去掉其中的元素 0 ，则该序列集合构成前缀码9已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 10 x P x Q x R x，y中的变元R x，yA的元素个数为10，则其幂集的元素个数为 1024 7设A a，b，c ，B 1，2 ，作f：AB，则不

14、同的函数个数为 8 8若A 1,2 ，R x, y |x A, y A, x+y 10 ，则R的自反闭包为 1,1 , 2,2 9结点数v与边数e满足 e v-1 关系的无向连通图就是树10设个体域D a, b, c ，则谓词公式 x A x 消去量词后的等值式为A a A b A（c）6若集合A 1，3，5，7 ，B 2，4，6，8 ，则AB 空集（或 ） 7设集合上的函数分别为：f 10设个体域D 1, 2, 3 ， P x 为“x小于2”，则谓词公式 x P x 的真值为假（或F，或0）则R的有序对集合为 2, 2 ， 2, 3 ， 2, 4 ， 3, 3 ， 3, 4 ， 4, 4 7

15、如果R是非空集合A上的等价关系，a A，b A，则可推知R中至少包含 a, a ， b, b 等元素8设G V, E 是有4个结点，8条边的无向连通图，则从G中删去 5 条边，可以确定图G的一棵生成树9设G是具有n个结点m条边k个面的连通平面图，则m等于n+k 210设个体域D 1, 2 ，A x 为“x大于1”，则谓词公式的真值为真（或T，或1）11设A 1,2,3 ，用列举法出A上的恒等关系IA，全关系EAIA _ IA 1,1 , 2,2 , 3,3 ；EA 1,1 , 1,2 , 1,3 , 2,1 , 2,2 , 2,3 , 3,1 , 3,2 , 3,3 12设集合A a，b ，A

16、的幂集是 , a , b , a,b 13设集合A 1,2,3 ，B a,b ，从A到B的两个二元关系R 1,a , 2,b , 3,a ，S 1,a , 2,a , 3,a ，则R-S _ R-S 2,b 14设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r 215无向连通图G是欧拉图的充分必要条件是结点度数均为偶数16设G V, E 是有6个结点，8条边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成树17设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有_14_条边，G的总度数是_28_，G的分支点数是_7_18设P，Q的

17、真值为1，R，S的真值为0，则命题公式的真值为_0_19命题公式的合取范式为析取范式为20设个体域为整数集，公式真值为设A 1,2,3,4 ，B 3,4,5,6 ，则：_ 3,4 _，_ 1,2,3,4,5,6 _12设集合A有n个元素，那么A的幂集合P A 的元素个数为 13设集合A ,b,c,d ，B x,y,z ，R a,x , a,z , b,y , c,z , d,y 则关系矩阵MR设集合A ,b,c,d,e ，A上的二元关系R a,b , c,d , b,b ，S d,b , b,e , c,a ，则R?SG的结点数为5，边数为6，则面数为 3 17设正则二叉树有n个分支点，且内部

18、通路长度总和为I，外部通路长度总和为E，则有E _ I+2n18设P，Q的真值为0，R，S的真值为1，则命题公式的真值为_1_19已知命题公式为G P Q R则命题公式G的析取范式是 P Q R x P x Q x R x，y中的约束变元1111将语句“他不去学校”翻译成命题公式设P：他去学校， （1分） P （4分）12将语句“他去旅游，仅当他有时间”翻译成命题公式设 P：他去旅游，Q：他有时间， （1分）P Q （4分）13将语句“所有的人都学习努力”翻译成命题公式设P x ：x是人，Q x ：x学习努力， （1分）（ x） P x Q x （3分）11将语句“尽管他接受了这个任务，但他没

19、有完成好”翻译成命题公式设P：他接受了这个任务，Q：他完成好了这个任务， （2分）P Q （6分）12将语句“今天没有下雨”翻译成命题公式设P：今天下雨， （2分） P （6分）11将语句“他是学生”翻译成命题公式设P：他是学生， （2分）则命题公式为： P （6分）12将语句“如果明天不下雨，我们就去郊游”翻译成命题公式设P：明天下雨，Q：我们就去郊游， （2分）则命题公式为： P Q （6分）11将语句“今天考试，明天放假”翻译成命题公式设P：今天考试，Q：明天放假 （2分）则命题公式为：PQ （6分）12将语句“我去旅游，仅当我有时间”翻译成命题公式设P：我去旅游，Q：我有时间， （2分

20、）则命题公式为：P Q （6分） 将语句“如果明天不下雨，我们就去春游”翻译成命题公式 将语句“有人去上课” 翻译成谓词公式设命题P表示“明天下雨”，命题Q表示“我们就去春游”.则原语句可以表示成命题公式 PQ. （5分）设P x ：x是人，Q x ：x去上课 则原语句可以表示成谓词公式 x P x Q x 四、判断说明题（每小题7分，本题共14分）14P（PQ）P为永真式正确 （3分）P（PQ）P是由P（PQ）与P组成的析取式，如果P的值为真，则P（PQ）P为真， （5分）如果P的值为假，则P与PQ为真，即P（PQ）为真，也即P（PQ）P为真，所以P（PQ）P是永真式 （7分）15若偏序集

21、A，R 的哈斯图如图一所示，则集合A的最大元为a，最小元不存在正确 （3分）对于集合A的任意元素x，均有 x, a R（或xRa），所以a是集合A中的最大元（5分）14如果R1和R2是A上的自反关系，则R1R2是自反的正确 （3分）R1和R2是自反的， x A， x, x R1， x, x R2， 则 x, x R1 R2， 所以R1R2是自反的 （7分）15如图二所示的图G存在一条欧拉回路正确 （3分）因为图G为连通的，且其中每个顶点的度数为偶数 （7分）14设N、R分别为自然数集与实数集，f：NR，f x x+6，则f是单射正确 （3分）设x1，x2为自然数且x1 x2，则有f x1 x1

22、+6 x2+6 f x2 ，故f为单射 （7分）15设G是一个有6个结点14条边的连通图，则G为平面图错误 （3分）不满足“设G是一个有v个结点e条边的连通简单平面图，若v3，则e3v-6” 13下面的推理是否正确，试予以说明 1 （ x）F（x）G（x） 前提引入 2 F（y）G（y） US（1）错误 （3分）（2）应为F（y）G（x），换名时，约束变元与自由变元不能混淆 （7分）14若偏序集 A，R 的哈斯图如图二所示，则集合A的最大元为a，最小元不存在错误 （3分）集合A的最大元不存在，a是极大元 （7分）13下面的推理是否正确，试予以说明 1 （ x）F（x）G（x） 前提引入 2 F

23、（y）G（y） US（1）错误 （3分）（2）应为F（y）G（x），换名时，约束变元与自由变元不能混淆 （7分）14如图二所示的图G存在一条欧拉回路错误 （3分）因为图G为中包含度数为奇数的结点 （7分）13如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图错误 （3分）当图G不连通时图G不为欧拉图 （7分）14若偏序集 A，R 的哈斯图如图二所示，则集合A的最大元为a，最小元是f 图二错误 （3分）集合A的最大元与最小元不存在，a是极大元，f是极小元， 五计算题（每小题12分，本题共36分）16设集合A 1，2，3，4 ，R x, y |x, y A；|x y| 1或x y 0 ，试（1

24、）写出R的有序对表示；（2）画出R的关系图；（3）说明R满足自反性，不满足传递性（1）R 1,1 , 2,2 , 3,3 , 4,4 , 1,2 , 2,1 , 2,3 , 3,2 , 3,4 , 4,3 （3分）（2）关系图为（6分）（3）因为 1,1 , 2,2 , 3,3 , 4,4 均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。 （9分）因有 2,3 与 3,4 属于R，但 2,4 不属于R，所以R在A上不是传递的。 17求P Q R的析取范式，合取范式、主析取范式，主合取范式P（RQ） P RQ PQR （析取、合取、主合取范式） （9分） PQR PQR PQR

25、 PQR PQR PQR PQR （主析取范式） （12分）18设图G V，E ，V v1，v2，v3，v4，v5 ，E v1, v2 ， v1, v3 ， v2, v3 ， v2, v4 ， v3, v4 ， v3, v5 ， v4, v5 ，试画出G的图形表示；写出其邻接矩阵； 3 求出每个结点的度数； 4 画出图G的补图的图形（1）关系图 （3分）（2）邻接矩阵 （6分）（3）deg v1 2deg v2 3deg v3 4deg v4 3deg v5 2 （9分）（4）补图16设谓词公式，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元（1） x量词的辖域为， （2分）

26、z量词的辖域为, （4分） y量词的辖域为 （6分）（2）自由变元为与中的y，以及中的z约束变元为x与中的z，以及中的y （12分）17设A 1 , 2 ,1,2 ，B 1,2, 1,2 ，试计算（1）（A B）； （2）（AB）； （3）AB（1）A B 1 , 2 （4分）（2）AB 1,2 （8分）（3）AB 1 ,1 ， 1 ,2 ， 1 , 1,2 ， 2 ,1 ， 2 ,2 ， 2 , 1,2 ， 1,1 ， 1,2 ， 1, 1,2 ， 2,1 ， 2,2 , 2, 1,2 18设G V，E ，V v1，v2，v3，v4，v5 ，E v1,v3 ， v2,v3 ， v2,v4 ，

27、 v3,v4 ， v3,v5 ， v4,v5 ，试（1）给出G的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形1）G的图形表示为： （3分）（2）邻接矩阵： （6分）（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2 （9分）（4）补图如下：16试求出（PQ）R的析取范式，合取范式，主合取范式（PQ）R PQ R PQ R（析取范式） （3分） PR QR （合取范式） （6分） PR QQ QR PP PRQ PRQ QRP QRP PQR PQR PQR （主合取范式） （12分）17设A a, b , 1, 2 ，B a, b, 1

28、 , 1 ，试计算（1）（A B） （2）（AB） （3）（AB） （AB）（1）（A B） a, b , 2 （4分）（2）（AB） a, b , 1, 2, a, b, 1 （8分）（3）（AB） （AB） a, b , 2, a, b, 1 （12分）18图G V, E ，其中V a, b, c, d, e ，E a, b , a, c , a, e , b, d , b, e , c, e , c, d , d, e ，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形； （2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值（1）G的图形表示为： （3分）（2）邻接矩阵：（3）粗线表示最小的生成树， （10分）权为7： （12分）15求（PQ）（RQ）的合取范式（PQ）（RQ） （PQ）（RQ） （4分） P Q （RQ） PRQ QRQ PRQ R 合取范式 （12分）16设A 0，1，2，3，4 ，R x，y |x A，y A且x+y 0 ，S x，y |x A，y A且x+y 3 ，试求R，S，R S，R，S，r R R ,