《离散数学复习资料12月》由会员分享，可在线阅读，更多相关《离散数学复习资料12月（11页珍藏版）》请在金锄头文库上搜索。
1、离散数学复习资料年月一、单项选择题（每小题分，本题共分）若集合，则下列表述正确的是 （）. ，且三，且三 .：_,且匕.二，且设有向图（）、（）、（）与（）如图一所示，则下列结论成立的是（）.（）是强连通的.（）是强连通的.设图的邻接矩阵为图一()是强连通的()是强连通的01100_100111000001001L01011则的边数为（）.C.无向简单图是棵树，当且仅当（.连通且边数比结点数少.的边数比结点数少）.连通且结点数比边数少.中没有回路.F列公式（）为重言式.（）（一（）(一 ) -(一 ( )（一（）一.设, , , ,是到的一兀关系，且, , , , , , ,则（ ）不是从到的
2、函数.和.和.设, , , , , , , ，是上的整除关系，, , ，则集合的最大元、最小元、上界、下界依次 为（）.、.无、无、.若集合的元素个数为，则其幕集的元素个数为（）.10 C.设完全图n有个结点（ ），条边，当（）时，n中存在欧拉回路.为奇数.为奇数1.为偶数工.为偶数.已知图的邻接矩阵为# / 8r010II1I000I0 0 0 11I010I11110,则有().点，边.点，边.点，边.点，边.无向完全图的不同构的生成子图的个数为()() ()() ()阶无向完全图中的边数为()n(n -1)n(n 1)() ()2 2.在图= 中，结点总度数与边数的关系是() ()()(
3、)()()Z deg(v) = 2 E v召送 d egv() = Ev申、填空题(每小题分，本题共分).命题公式P (Q P)的真值是若 , - , - , ，则的自反闭包为,.已知一棵无向树中有个结点，度，度，度的分支点各一个，的树叶数为(一)()()V (,)中的自由变元为(,)中的.设集合= , ，那么集合的幕集是 _ ,.如果和是上的自反关系，则u,n，中自反关系有个.设图是有个结点的连通图，结点的总度数为，则可从中删去 条边后使之变成树.无向图存在欧拉回路，当且仅当所有结点的度数全为偶数且连通.设连通平面图的结点数为，边数为，则面数为 .设个体域=, ，则谓词公式(-)()A()(
4、)消去量词后的等值式为 ()人()M () V ()三、逻辑公式翻译(每小题分，本题共分).将语句“雪是黑色的.”翻译成命题公式. 设：雪是黑色的，则命题公式为：.将语句“他不去学校.”翻译成命题公式.(分)解：设：他去学校，则命题公式为：-将语句 小王是个学生，小李是个职员，而小张是个军人. 设：小王是个学生，：小李是个职员，：小张是个军人. 则命题公式为：将语句“如果所有人今天都去参加活动，则明天的会议取消. 解：设：所有人今天都去参加活动，:明天的会议取消，则命题公式为： 将语句“他去旅游，仅当他有时间.”翻译成命题公式.”翻译成命题公式.(分)”翻译成命题公式.解：设：他去旅游，：他有
5、时间,则命题公式为：将语句“次列车下午五点开或者六点开.”翻译成命题公式.解：设：次列车下午五点开，：次列车下午六点开，（分）命题公式为：(A )V (-人)将语句“小张学习努力，小王取得好成绩.”翻译成命题设：小张学习努力，：小王取得好成绩,（分）则命题公式为：将语句“有人去上课.”翻译成谓词公式解：设()：是人，()()()（）:（分）将语句“所有的人都学习努力.”翻译成命题公式 解：设()：是人，()：学习努力，-)()()四、判断说明题(每小题分，本题共分)判断下列各题正误，并说明理由设集合, , , , , , , ,判断下列关系是否构成函数：At B，并说明理由.(), , , ；
6、 (), , ；(), , , 答：()不构成函数因为3 A，但f 3没有定义，所以不构成函数()不构成函数 因为4，A，但f 4没有定义，所以不构成函数()满足。因为任意A，都有f x B且结果唯一。若集合, 上的二元关系 , , ，则()是自反的关系；()是对称的关系.答：()错误因为3,3； R，所以不是自反的()错误因为1,2? R，但是R，所以不是对称的如果和是上的自反关系，判断结论:“、u、门是自反的” 是否成立？并说明理由.答：成立 因为任意aw A，有(a,a产R,(a,a严 &所以a,a)wR二，(a,a)RUR2, a,a)ER,P|& 、u、门是自反的若偏序集 的哈斯图如
7、图一所示， 则集合的最大元为，最小元不存在.答：错误，集合没有最大元，也没有最小元/其中是极大元/e若偏序集 的哈斯图如图一所示，则集合的最大元为，最小元不存在.图一解：正确对于集合的任意元素，均有 三(或)，所以是集合中的最大元.按照最小元的定义，在集 合中不存在最小元.如果图是无向图，且其结点度数均为偶数，则图存在一条欧拉回路.答：错误 如果图是无向图，且图是连通的，同时结点度数都是偶数.设是一个连通平面图，且有个结点条边，则有个面.答案：正确定理，连通平面图的结点数为，边数是，面数为，则欧拉公式成立所以则存在一条欧拉回路.设是一个有个结点条边的连通图，则为平面图.解：错误，不满足“设是一
8、个有个结点条边的连通简单平面图，若，则W.” .命题公式(厂)为永真式.解：正确因为，由真值表-1-1T-1可知，该命题公式为永真式.五.计算题(每小题分，本题共分).设集合, , , , ，试计算()(H)；()(-)；()( n) X.解()(n) ；()(-);()(门), 设, w, 且 , w，迂且 0,试求，(). 解：/,)()图,其中, , , , , (, ), (, ), (, ), (, ), (, ), (, ), (, ), (, ) ,对应边的权值依次为及,试()画出的图形；()写出的邻接矩阵；()求出权最小的生成树及其权值. 解：()的图形表示为：(分)()邻接矩
9、阵：0 110 110 0 11(分)10 0 110 110 11111 0 一()粗线表示最小的生成树，L”权为：设图， (, )，(, )，(, )，(, )，(, )，(, )，(, ) ，试(1) 画出的图形表示；(2) 求出每个结点的度数；()画出图的补图的图形.解：()关系图()() () ()() ()()补图设集合, , 因为 , 均属于,即的每个元素构成的有序对均在中, 上不是传递的。,试计算()()因有 与 属于，但 不属于,设集合, , , ()解：()3* , ,()()()(), ;,、求出如图一所示赋权图中的最小生成树(要求写出求解步骤)故在上是自反的。(分)(分
10、),并求此最小生成树的权.解用算法求产生的最小生成树步骤为:W(Vi, V7)=1W(V3, V4) =3w(V2, V7) =4w(V3,V7)=9wM, V5) =18w(w, V6)=22选 二 V1V7选 e2 = v3v4选 Q =V2V7选 e4 -V3V7选 eV4V5选 e6 = v1v6(分)最小生成树如图四所示:图四(分)(分)最小生成树的权为：().试画一棵带权为，的最优二叉树，并计算该最优二叉树的权. 解：最优二叉树 如图二所示.权为(分)设谓词公式 x(A(x,y)-zB(x,y,z) -yC(y,z)，试()写出量词的辖域；()指出该公式的自由变元和约束变元.()量
11、词的辖域为(A(x, y) -zB(x, y,z),(分)-量词的辖域为B(x, y, z),(分)-量词的辖域为C(y,z).(分)()自由变元为(A(x,y)-zB(x, y, z)中的，以及C(y, z)中的 (分)约束变元为(A(x, y) -zB(x, y,z)中的与B(x, y,z)中的，以及C( y, z)中的.设谓词公式(x)P(x, y) (-z)Q(x, y, z)，试()写出量词的辖域；()指出该公式的自由变元和约束变元.() 量词的辖域为P(x, y),(分)-量词的辖域为Q(x, y,z),(分)()自由变元为公式中的与 Q(x, y,z)中的,(分)约束变元为P(x, y)的与Q(x, y,z).VV(如(S极小项极大项-aa-1-AAA-1AA.求命题公式()一；()的主析取范式、主合取范式. 解：主析取范式(极小项析取)() ( ：.) (、.：.：)()(八 J )()主合取范式(极大项合取).求(V)t( V)的析取范式，合取范式 解：(V)T(V)(分)二
