大学离散数学复习题

PAGEPAGE9《离散数学》试题A系别班级学号（最后两位）姓名题号一二三四总分得分一、单项选择题（每小题2分，共16分）1.下列命题为假命题的是（）

A.如果4是偶数，那么一个公式的合取范式惟一

B.如果4是偶数，那么一个公式的合取范式不惟一

C.如果4是奇数，那么一个公式的合取范式惟一

D.如果4是奇数，那么一个公式的合取范式不惟一2．下列是真命题的是（）A．； B．；C．{a}∪{b}={a,b,c}；D．。3.设集合A={1，2，3}，R是A上的二元关系，下列关系R中不是等价关系的是（）

A.R={<1,1>,<2,2>,<3,3>}

B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}

C.R={<1,1>,<2,2>,<3,3>,<1,2>}

D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3><3,2>}

4。设A={1，2，3}，则A上所有的二元关系共有（）个。A．23；B．32；C．；D．。5．设R，S是集合A上的关系，则下列说法正确的是（）A．若R，S是自反的，则是自反的；B．若R，S是反自反的，则是反自反的；C．若R，S是对称的，则是对称的；D．若R，S是传递的，则是传递的。6．设是整数集合，函数定义为：，则是()的．A．双射 B．满射 C．单射 D．非单射也非满射7．设为有向图，其中，，则该有向图是（）.A．强连通图 B．单向连通但非强连通图C．弱连通图但非单向连通图 D．不连通图8．设G是有5个顶点的无向完全图，则G是()A．没有哈密尔顿通路 B．没有欧拉回路C．是欧拉图 D．是平面图二、填空题（每空2分，共24分）1．设:是人，：喜欢读书，则命题“不是所有的人都喜欢读书”可符号化为_______________________。2.设A={1,2，3}，那么可以定义________个不同的上的等价关系,________个偏序关系。3．集合A={a,b,c},A×A=________________________。4．公式q∧(p∨r)→┐q的主合取范式为。5．若解释I的论域D仅包含一个元素，则在I下真值为。6．设A={1，2，3，4}，A上关系图为R2=。7．设A={a，b，c，d}，其上偏序关系R的哈斯图如下则R=。8.设集合，上的关系，则的对称闭包是__________________________，自反闭包是________________________．9.已知无向简单图G中,有10条边,4个3度结点,其余结点的度均小于或等于2,则G中至少有________个结点．10.一棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,则它有________个度数为1的结点．三、解下列各题（每小题9分，共45分）1．求命题公式的主析取范式，成真赋值，成假赋值．2．画一棵带权为1，3，4，5，5，7，9，9的最优二元树T，并计算它的权W（T）。3．设集合，是上的二元关系.(1)画出的关系图，写出的关系矩阵；(2)说明是否是自反、反自反、对称、反对称、传递的．4．若集合Ｘ＝｛（1，2），（3，4），（5，6），(7,8)……｝（1）证明R是X上的等价关系。（2）求出X关于R的商集。5．有向图D如右所示，（1）写出D的邻接矩阵；（2）求D中从到的长度为3的通路的条数，并具体写出各条通路。四、应用题（15分）1.构造下面推理的证明:前提:p→﹁q,q∨﹁r,r∧﹁s结论:﹁p（10分）2.如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（5分）《离散数学》试题B系别班级学号（最后两位）姓名题号一二三四总分得分一、填空题（每空2分，共18分）1．令：河北的省会是保定，：2是偶数，则命题“河北的省会是保定，当且仅当2是偶数”的真值是___________________。2．设A={1,2}，那么可以定义________个不同的上的等价关系,________个偏序关系。3．设:是人，：可以活到百岁以上，则命题“不是所有的人都可以活到百岁以上”可符号化为_______________________。4.公式┐(p∧q)的类型是____________________________。5.谓词公式中的辖域为________________________。6．设，上的二元关系，则_______________________t(R)=_______________________7．一棵树有2个4度顶点，3个3度顶点，其余都是树叶，则该树有____片树叶。二、单选题（每小题2分，共10分）1．“王兰和王英是姐妹”是（）A复合命题B简单命题C不是命题D不能确定2．设，，下列选项错误的是（）A． B．C． D．3．是整数集合，函数定义为：则是（）A．单射 B．满射C．双射 D．非单射也非满射4．下述偏序集中，（）是全序集。5．设G是有5个顶点的无向完全图，则G是()A．无哈密顿通路 B．无欧拉回路C．是欧拉图 D．是平面图三、综合题（每小题10分，共60分）1.用等值演算法求命题公式的主析取范式，并说明公式的类型。2.已知有向图，，的邻接矩阵（1）求，，；（2）已知，求到长度为3的通路数，和过长度为3的回路数；（3）问图D属于哪一种连通。3.设集合A={a，b，c，d}上的关系R={<a,b>,<b,a>,<b,c>,<c,d>}用矩阵运算求出R的传递闭包t(R)。（9分）4.设集合，是集合的幂集，试画出的哈斯图，并指出子集的极大元、极小元、上确界、下确界。5..求带权为2，3，5，7，8的最优二元树，并求对应的二元前缀码。6.设集合，上的二元关系。求出的集合表达式，并画出的关系图。四、应用题（每小题6分，共12分）