离散结构试卷+答案讲解学习.doc

《离散结构试卷+答案讲解学习.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、离散结构试卷+答案精品文档离散结构2007-a一、填空（每空2分，共30分）1、设P：2+2=4，Q：3是奇数将命题“2+2=4，当且仅当3是奇数”符号化__(1)___，其真值为__(2)___。2、在公式中，自由出现的变元为___(3)____。3、若关系R具有自反性，当且仅当在关系矩阵中，主对角上元素__(4)___，若关系R具有对称性，当且仅当关系矩阵是__(5)___。4、若关系，则关系一定具有__(6)___性。5、有向图的连通性可分为弱连通、强连通、__(7)___。6、前缀表达式+*2/843的值是__(8)___。7、设G是完全二元树，G有15个顶点，其中有8个

2、叶子，则G有__(9)___条边，G的总度数是__(10)___。8、十进制3位数的数字中恰好有一个8和一个9，共有__(11)___个这样的3位数。9、设集合，上的运算定义为：则代数系统中单位元是__(12)___，的左逆元是__(13)___，无左逆元的元素是__(14)___。10、设是由元素生成的循环群，且的阶为4，则集合=__(15)___。二、选择题（每题2分，共30分）1、下列语句中，_____是命题。A、地球上的人真多B、把门关上C、下午有会吗？收集于网络，如有侵权请联系管理员删除精品文档D、2、一个公式在等价意义下，下面哪个写法是唯一的_____。A、析取范式B

3、、合取范式C、主析取范式D、以上都不唯一3、设命题公式，则G是_____。A、永真式B、矛盾式C、可满足式D、以上都不是4、设I是如下一个解释，，其中，为真，，为假，则在解释I下取真值的公式是______A、B、C、D、5、下列哪个表达式错误_____。。A、B、C、D、6、设R，S是集合上的两个关系，其中，，则S是R的____闭包。A、自反B、反对称C、对称D、传递7、设R和S是非空集合A上的等价关系，下列各式是A上等价关系的是_____。A、B、C、D、的对称闭包8、设偏序集（）关系R的哈斯图如右所示，若A的子集，则元素6为B的_____。A、下界B、上界C、最小上界D、以上

4、都不对9、以下整数序列，能成为一个简单图的顶点度数序列的是_____。A、1，2，2，3，4，5B、2，3，3，4，4，5C、1，1，1，2，3D、2，3，3，4，5，610、设图G是有6个顶点的连通图，总度数为20，则从G中至少删去_____条边后使之成为树。A、10B、5C、3D、211、在下列关于图论的命题中，正确的是_____。收集于网络，如有侵权请联系管理员删除精品文档A、哈密顿图一定是欧拉图B、无向完全图都是欧拉图C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出D、哈密顿图是平面图12、下面编码_____不是前缀码。A、11，00，10，01B、01，11，

5、011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010113、5阶非同构的无向树有_____棵。A、1B、2C、3D、414、由0、1、2、3这四个数字能构成_____个3位数A、64B、48C、24D、1815、在下列选项中，不是群的是_____。A、，为有理数，+为加法运算B、，为非零实数集，为乘法运算C、全体实对称矩阵集合，对于矩阵的加法运算D、，为有理数，*为乘法运算三、计算题（5分+5分+8分，共18分）1、设有5个城市，任意两城市之间的铁路造价如下：，，，，，，，，，试求出连接5个城市的且造价最低的铁路网2、构造

6、前序遍历为a，b，f，c，g，h，i，d，e，j，k，p的有序树，其中a有4个子结点，c有3个子结点，j有2个子结点，b和e都有一个子结点，所有其它结点都是树叶。34、设集合，A上的关于等价关系R的商集=，试求：（1）等价关系R收集于网络，如有侵权请联系管理员删除精品文档（2）写出关系矩阵（3）画出关系图（4）写出R的传递闭包四、证明题（5分+5分+6分，共16分）1、设R是A上的等价关系，S是B上的等价关系，且A和B非空，关系T满足：且，证明T是上的等价关系。2、设G为n阶无向简单图，证明：若G为自补图（若一个图的补图为本身则称为自补图），则或，其中k为正整数。3、若是群，，定

7、义G中的运算“”为：，对证明为群。五、应用题（6分）的意义如下：p：张群是大学生，q：张群心情愉快，r：张群唱歌试用日常语言说明下列复合命题：(1)(2)(3)2007-b一、填空（每空2分，共30分）1、表达式中谓词的个体域是{}，将其中的量词消去，写成与之等价的命题公式为__(1)__。2、设R是集合A上的二元关系，如果关系R同时具有__(2)__、__(3)__和传递，则称R是A上的偏序关系。3、已知集合上的二元关系，，则=__(4)__，=__(5)__。4、若有限集关系