资源描述：
《大学离散数学复习题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、《离散数学》试题A系别班级学号（最后两位）姓名题号—•二三四总分得分-V单项选择题（每小题2分，共16分》1.下列命题为假命题的是（）A.如果4是偶数，那么一个公式的合取范式惟一B.如果4是偶数，那么一个公式的合取范式不惟一C.如果4是奇数，那么一个公式的合取范式惟一D.如果4是奇数，那么一个公式的合取范式不惟一2.下列是真命题的是（）A.⑷［{{“}}:B.{{O}}e沖，沖}};C.{a}U{b}={a,b,c}；D.{0>}g{{O}}o3.设集合人={1,2,3}，R是A上的二元关系，下列关系R屮不是等价关系
2、的是（）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。设八={1,2,3},则A上所有的二元关系共有（）个。A.23；B.32；C.23x3；D.3么2。5.设R,S是集合A上的关系，则下列说法正确的是（）A.若R，S是自反的，则是自反的；A.若R,S是反自反的，则是反自反
3、的；B.若R,S是对称的，则是对称的；C.若R，S是传递的，则/?。5是传递的。6.设Z是整数集合，函数/定义为：Z^Z,/（x）=
4、x
5、-2%,则/是（）的.A.双射B.满射C.单射D.非单射也非满射7.设Z）=〈V,£〉为有向图，其中V=｛a，b，c，d，e，f｝，E=｛〈a，6〉，〈Z?，c〉，〈a，6/〉，〈t/，e〉，〈/＞〉｝，则该有向图是（）.八.强连通图B.单向连通但非强连通图C.弱连通图但非单向连通图D.不连通图8.设G是有5个顶点的无向完全图，则0是（）A.没有哈密尔顿通路B.没有欧拉回路C.是欧
6、拉图D.是平面图二、填空题（每空2分，共24分》1.设G（x）:x是人，F（x）:x喜欢读书，则命题“不是所有的人都喜欢读书”可符号化为。1.设A=｛1,2,3｝，那么可以定义个不同的4上的等价关系，个偏序关系。2.集合A=｛a，b，c｝，AXA=。3.公式q八(pVr)q的主合取范式为O4.若解释I的论域D仅包含一个元素，则3xP(x)fxP(x)在I下真值为o5.设八={1,2,3,4}，A上关系图为R2=O6.设人={3,b,c,d}，其上偏序关系R的哈斯图如下则R=o8•设集合4={1，2,3},A上的关系
7、/?={〈1，1〉，〈1，2〉，〈2，1〉，〈2,3〉},贝ij/?的对称闭包是,自反闭包是5.已知无向简单图G中，有10条边，4个3度结点,其余结点的度均小于或等于2,则G中至少有个结点.6.—棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,则它有个度数为1的结点.三、解下列各题(每小题9分，共45分》1.求命题公式PA(P40的主析取范式，成真赋值，成假赋值.2.画一棵带权为1，3，4，5,5，7,9，9的最优二元树T,并计算它的权W(T)。3.设集合A={1,2,3},/?={〈1，1〉，〈3，1〉
8、，〈1，3〉，〈3,3＞，〈3,2〉，〈2,3〉}是4上的二元关系.(1)画出/?的关系图，写出/?的关系矩阵：(2)说明是否是自反、反自反、对称、反对称、传递的.4.若集合X={(1,2),(3,4)，(5,6),(7,8)……}R={«A，凡〉，＜义2,＞’2〉〉l+)’2=X2+%}(1)证明R是X上的等价关系。(2)求出X关于R的商集。5.有向图D如右所示，(1)写出D的邻接矩阵；(2)求D中从到v3的长度为3的通路的条数，并具体写出各条通路。四、应用题(15分)1.构造下面推理的证明：前提：P一一'q,qV
9、—'r,rA—-s结论：—(10分)2.如下图所示的赋权图表示某七个城市v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。(5分)《离散数学》试题B系别班级学号(最后两位)姓名题号—•二三四总分得分一、填空题(每空2分，共18分》1.令河北的省会是保定，心•2是偶数，则命题“河北的省会是保定，当且仅当2是偶数”的真值是2.设人=｛1，2｝，那么可以定义个不同的A上的等价关系，个偏序关系。3.设G(x):x是人，F(x)：%可以活到百岁以上，则命题“不是所有的人都可
10、以活到百岁以上”可符号化为04.公式］(pAq)的类型是。5.谓词公式Vx(F(x)3yH(x，y))中Vx的辖域为O6.设A=｛“，/?，＜?｝，A上的二元关系/?=｛〈“，/?〉,〈/?，＜?〉｝，贝ijs(R)=t(R)=7.一棵树有2个4度顶点，3个3度顶点，其余都是树叶，则该树有片树叶。二、单选题(每小题2分，共10分〉1.“王兰和王
