《离散数学》习题2A

2A第5页共8页一、单选题（20小题，每小题2分，共40分）得分1．设A为图G的邻接矩阵，的主对角线元素之和为600，则G上有（）个三角形。A．100；B．200；C．300；D．6002．设，则有（）。A．{{1,2}}；B．{1,2}；C．{1}；D．{2}3．下列关系中能构成函数的是（）。A．；B．；C．；D．4．52张扑克牌分配给4个桥牌比赛者进行比赛，那么扑克牌集合A到桥牌比赛者集合B的函数是（）。A.入射B.满射C.双射D.映射5．下列符号串是合式公式的是（）A、；B、；C、；D、。6．关系R所具有的关系矩阵，则关系R所具有的性质是（）A．自反的，对称的，可传递的B．自反的，反对称的，可传递的C．自反的，对称的D．都不是7．下列等价式不成立的是（）．A．B．C． D．．8．设，以下哪一个关系是从到的满射()。A．B．C．D．9．下列各图不是欧拉图的是（）．10．设图G有5个结点，若各结点的度数分别为：3,4,6,2,3,则G有（）条边。A．10；B．20；C．9；D．18．11．下列句子是命题的是()．A．再过5000年，地球上就没水了．B．．C．水开了吗?D．我正在说谎．12．下列等价公式正确的是（）．A．；B．；C．；D．．13．给定公式：(x)(A（x）B），与之等价的公式是（）A．(x)A（x）B B．(x)A（x）BC．B(x)A（x） D．B(x)A（x）14．下面哪个图是强连通的（）．15．下图中是哈密尔顿图的是（）。16．命题公式中极小项的个数为（ ）A．0 B．1 C．2 D．317．下列等价式不成立的是（）.A．;B．C．D．18．设，下列二元关系为到的函数的是()A．B．C．D．19．下面哪一种图不一定是树（）．A．无圈的连通图；B．有ｎ个结点ｎ－１条边的连通图；C．每对结点间都有路的图；D．连通但删去一条边就不连通的图．20．设为无向图，=7，=23，则G一定是（）。A．完全图；B．树；C．简单图；D．多重图二、填空题（20小题，每空1分，共20分）得分1．设命题公式的真值表为00001111001100110101010100101100则命题公式的主析取范式为。2．设表示“是马”，表示“是动物”．则命题“马是动物，动物不一定是马”符号化为．3．设A为任一集合，则．4．设是到的函数，如果，则称为5．设集合Ａ＝｛ａ，ｂ，ｃ｝上的关系Ｒ＝｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝，ｔ（Ｒ）＝6．完全图K5的连通分支数是。7．设图G=〈V，E〉，V＝｛,,,｝的邻接矩阵A(G)=，则的出度为。8．对谓词公式（（x）P（x）（y）Q（y））（x）R（x）中约束变元应用变换规则所得到的前束范式是9．设的函数，且，则。10．设表示“天下雨”，表示“我骑自行车上班”，则命题“除非下雨，否则我骑自行车上班”符号化为。11．写出下表中所定义的命题联结词00011011011112．命题公式（PQ）（QP）的主析取范式为。13．设是集合上的二元关系，则=。14．命题公式的逆反式是。15．在偏序集中，其中={2,3,6,12,24,36}，≤是中的整除关系，则集合={2,3,6}的极大元是16．设是集合上的具有自反性、对称性、反对称性和传递性的二元关系，则的关系矩阵是。17．设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为。18．设R是实数集合，，，且，则19．在任何有向图中，=。20．在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的极小元是三、简答题（4小题，每小题6分，共24分）得分1．以给定权2，4，5，8，13，15，18，25构造一棵最优二叉树．2．今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示．要求设计一个最经济的煤气管道路线，并求所需的总费用．AABCDEFGHIJKS2222223.554526345313.对有向图求解下列问题：1）写出邻接矩阵；2）中由到长度为2和4的路有几条？3）求出的可达性矩阵。vv1v4v2v34．设={1,2,3,4,5,6}，集合上的关系={〈1,3〉,〈1,5〉,〈2,5〉,〈4,4〉,〈4,