离散结构试卷+答案.doc

《离散结构试卷+答案.doc》由会员分享，可在线阅读，更多相关《离散结构试卷+答案.doc（46页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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 / 8 4 3 的值是_(8)_。7、设G是完全二元树，G有15个顶点，其中有8个叶子，则G有_(9)_条

2、边，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、合取范式 C、主析取范式 D、以上都不唯一3、设命题公式，则G是_。A、永真式 B、矛盾式 C、可满足式 D、以上都不是4、设I是如下一

3、个解释，其中，为真，为假，则在解释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、以上都不对 9、以下整数序列，能成为一个简单图的顶点度数序列的是_。A、1，2，2，3，4，5B、2，3，3，4，4，5C、1，1，1，2，3D、2，3，3，4，5，61

4、0、设图G是有6个顶点的连通图，总度数为20，则从G中至少删去_条边后使之成为树。A、10 B、5 C、3 D、211、在下列关于图论的命题中，正确的是_。A、哈密顿图一定是欧拉图B、无向完全图都是欧拉图C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出D、哈密顿图是平面图12、下面编码_不是前缀码。A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010113、5阶非同构的无向树有_棵。A、1 B、2 C、3 D、4 14、由0、1、2、3这四个数字能构成_个3位数A、64 B、48 C、

5、24 D、1815、在下列选项中，不是群的是_。A、，为有理数，+为加法运算B、，为非零实数集，为乘法运算C、全体实对称矩阵集合，对于矩阵的加法运算D、，为有理数，*为乘法运算三、计算题（5分+5分+8分，共18分）1、设有5个城市，任意两城市之间的铁路造价如下：试求出连接5个城市的且造价最低的铁路网2、 构造前序遍历为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的传递闭包四、

6、证明题（5分+5分+6分，共16分）1、设R是A上的等价关系，S是B上的等价关系，且A和B非空，关系T满足：且，证明T是上的等价关系。2、 设G为n阶无向简单图，证明：若G为自补图（若一个图的补图为本身则称为自补图），则或，其中k为正整数。3、若是群，定义G中的运算“”为：，对证明为群。五、应用题（6分）的意义如下：p：张群是大学生，q：张群心情愉快，r：张群唱歌试用日常语言说明下列复合命题：(1) (2) (3) 2007-b一、填空（每空2分，共30分）1、表达式中谓词的个体域是，将其中的量词消去，写成与之等价的命题公式为_(1)_。2、设R是集合A上的二元关系，如果关系R同时具有_(2)

7、_、_(3)_和传递，则称R是A上的偏序关系。3、已知集合上的二元关系，则=_(4)_，=_(5)_。4、若有限集关系具有自反性，则其对应的关系矩阵主对角元素全为_(6)_。5、若某个简单图不是欧拉图但具有欧拉通路，则图中顶点度数为奇数的顶点个数一定为_(7)_。6、设是图，如果G是_(8)_并且_(9)_则G是树。7、一个无向图的欧拉回路要求经过图中_(10)_一次且仅一次，哈密顿回路要求经过图中_(11)_一次且仅一次。8、树是平面图，它有_(12)_个面。9、在群、半群、独异点中，_(13)_满足消去律。10、设Q为有理数集，笛卡尔积，是S上的二元运算，有，则运算的单位元为_(14)_，

8、（），则的逆元为_(15)_。二、选择题（每题2分，共30分）1、下列语句中_是命题。A、把门关上 B、地球外的星球上也有人C、D、下午有会吗2、已知命题，则所有使G取真值的解释是_。A、000，001，100 B、100，101，110C、010，101，001 D、001，101，1113、命题公式A和B是等价的是指A、A和B由相同的原子变元B、A和B都是可满足的C、当A的真值为真时，B的真值也为真D、A和B有相同的真值4、对、而言，下列是极小项的是_。A、 B、 C、 D、5、设集合，R、S、T都是A上的关系，则T=_。A、 B、 C、 D、6、若T为树，以下叙述不正确的是_。A、T是连

9、通的且不含回路B、T的每对顶点之间有唯一的一条路径C、T是连通的且每条边都是割边D、T是连通的且每个点都是割点7、设集合为，下列关系R中不是等价关系的是_。A、B、C、D、8、设集合，A上的关系，则R不具备_。A、自反性 B、传递性 C、对称性 D、反对称性9、设T是由n个顶点的完全二元树，则T的叶子数为_。A、 B、 C、 D、10、设无向图G有12条边，已知G中3度顶点有6个，其余顶点度数均小于3，则G中顶点数最多有_。A、6 B、8 C、9 D、1211、设I是如下一个解释，其中，为真，为假，则在解释I下取真值的公式是_。A、 B、 C、 D、12、设R和S是非空集合A上的等价关系，下列

10、各式是A上等价关系的是_。A、 B、 C、 D、的对称闭包13、下面编码_不是前缀码。A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010114、由0、1、2、3这四个数字能构成_个3位数A、64 B、48 C、24 D、1815、在下列选项中，不是群的是_。A、，为有理数，+为加法运算B、，为非零实数集，为乘法运算C、全体实对称矩阵集合，对于矩阵的加法运算D、，为有理数，*为乘法运算三、计算题（5分+5分+8分，共18分）1、已知：有向图，E=，求有向图D的邻接矩阵和可达矩阵。2、求叶的权值分

11、别为2，4，6，8，10，12，14的最优二元树及其权值。3、试画出集合，在偏序关系整除下的哈斯图，并分别求出： (1)集合的最大元，最小元，极大元，极小元； (2)集合的上界，下界，最小上界，最小下界。四、证明题（5分+5分+6分，共16分）1、证明：利用命题演绎法证明2、 设R和S是A上的二元关系，证明：3、 证明：设是一个代数系统，*是上的二元运算，则0是单位元，且是含幺半群。（为实数集合）。五、应用题（共6分）的意义如下：p：张群是大学生，q：张群心情愉快，r：张群唱歌试用日常语言说明下列复合命题：（1）（2）（3）2008a v1.1一、填空（每空2分，共30分）1、设P：1+1=2

12、，Q：2是偶数，将命题“1+1=2，仅当2是偶数”符号化 (1)_，其真值为 (2)_。2、在公式中，约束出现的变元为 (3)_。 3、给定集合上的3个关系如下：则其中满足对称性的关系是 (4)_；满足自反性的关系是 (5)_。4、非空集合A上的自反、 (6)_和传递的关系称为A上的偏序关系。5、后缀表达式 3 5 2 * 7 + 4 / 的值是 (7)_。6、设无向图G有11条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中有 (8)_个悬挂顶点。7、设G为连通的平面图，有5个面，总度数为14，则G有 (9)_条边，有 (10)_个顶点。8、已知一棵无向树T中有

13、4度、3度和2度分支点各1个，其余顶点均为树叶，则T有 (11)_个树叶。9、设集合，上的运算定义为：则代数系统中单位元是 (12)_，的右逆元是 (13)_，无右逆元的元素是 (14)_。10、设运算的运算表如下所示，则运算满足交换律、幂等律、结合律中的 (15)_。*abcacabbabccbca二、选择题（每题2分，共30分）1、下面语句是真命题的为_。A、我正在说谎。B、如果112，则太阳从西边升起来。C、如果113，则太阳从西边升起来。D、吃饭了吗？2、命题公式P(QP)为_。A、重言式 B、可满足式 C、矛盾式 D、等值式3、下面联结词不具有交换律的是_。A、 B、 C、 D、4、

14、设I是如下一个解释，其中，为真，为假，则在解释I下取真值的公式是_A、 B、 C、 D、5、下列哪个表达式错误_。A、 B、 C、 D、 6、设集合上的两个关系，则R具有_。A、自反性 B、传递性 C、对称性 D、反自反性7、下述结论错误的是_。A、存在这样的关系，它可以既满足对称性，又满足反对称性。B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。C、存在这样的关系，它可以既满足自反性，又满足反自反性。D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。8、设偏序集（）关系R的哈斯图如右所示，若A的子集，则元素6为B的_。A、下界 B、上界 C、最小上界 D、以上都不对 9

15、、以下整数序列，能成为一个简单图的顶点度数序列的是_。A、1，2，2，3，4，5B、2，3，3，4，4，5C、2，2，3，4，5，6D、1，2，2，3，3，510、设图G是有6个顶点的连通图，总度数为16，则从G中删去_条边后可以使之成为树。A、10 B、5 C、3 D、211、在下列关于图论的命题中，正确的是_。A、哈密顿图一定是欧拉图B、无向完全图都是欧拉图C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出D、哈密顿图是平面图12、下面编码_不是前缀码。A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，101

16、1，1001，1010113、6阶非同构的无向树有_棵。A、5 B、6 C、7 D、8 14、实数集R关于下列二元运算满足结合律和交换律的是_。 A、 B、 C、 D、15、在下列选项中，不是群的是_。A、，为有理数，+为加法运算B、，为非零实数集，为乘法运算C、，为实数集，+为加法运算D、，为有理数，*为乘法运算三、计算题（5分+6分+8分，共19分）1、求下图中的最小生成树，并计算它的权。V1V2V6V3V5V41352467892、设有7个字母在通信中出现的频率(%)如下： a: 35% b: 20%, c: 15%, d: 10%, e: 10%, f: 5%, g: 5%(1)以频率

17、(或乘100)为权，求最优2元树(2)利用所求最优2元树找出每个字母的前缀码(3)求传输10000个按上述比例出现的字母需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字?节约多少个二进制位？3、设集合，X上的关系R如图所示，试求：abcd（1）写出关系R的关系矩阵（2）求关系R的自反闭包r(R)的关系矩阵, ()（3）求关系R的对称闭包s(R)的关系矩阵, ()（4）求关系R的传递闭包t(R)的关系矩阵, ()四、证明题（5分+5分+5分，共15分）1、设,在A上定义二元关系R如下：，证明：R是A上的等价关系。2、 设n阶m条边的无向图G中，m=n+1，证明G中存在

18、顶点v：d(v)3。3、 设G为群，令，证明：H是G的子群。五、应用题（共6分）1. 如果王小红努力学习，她一定取得好成绩。若王小红贪玩或不按时完成作业，她就不能取得好成绩。所以，如果王小红努力学习，她就能按时完成作业。(1) 将命题中的4个简单命题依次符号化为p,q,r,s；(2) 将命题符号化，即将命题的前提和结论符号化；(3) 在自然推理系统P中构造命题的推理证明。2008-2-A一、填空（每空2分，共30分）1、 设P：张晓拿一个苹果，Q：张晓拿一个梨，将命题“张晓只能拿一个苹果或拿一个梨”符号化 (1)_。2、 设P(x)：x是偶数，Q(x)：x是奇数，在实数R个体域中将命题“存在偶

19、数，也存在奇数”符号化 (2)_，其真值为 (3)_。3、非空集合A上的自反、对称和 (4)_的关系称为A上的等价关系。4、给定集合上的3个关系如下：则其中满足自反性的关系是 (5)_；满足对称性的关系是 (6)_；满足传递性的关系是 (7)_。5、关系，则RS= (8)_。6、波兰符号表达式 * + 4 5 - / 8 2 1的值是 (9)_。7、设无向图G有11条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中有 (10)_个悬挂顶点。8、设G为连通的平面图，有5个面，总度数为16，则G有 (11)_条边，有 (12)_个顶点。9、已知一棵无向树T中有4度、3

20、度和2度分支点各1个，其余顶点均为树叶，则T有 (13)_个树叶。10、设是无向图，如果G是 (14)_并且 (15)_则G是树。二、选择题（每题2分，共30分）1、下面语句是命题的为_。A、我正在说谎。B、把门关上。C、地球外的星球上也存在生命。D、吃饭了吗？2、命题公式(PQ)(PQ) P为_。A、重言式 B、非重言式的可满足式 C、矛盾式 D、等值式3、下列集合不是连接词完备集的为_。A、, B、, C、, D、4、下列谓词公式不是命题公式PQ的代换实例的是_A、 B、 C、 D、5、下列哪个表达式错误_。A、 B、 C、 D、 6、下列哪个表达式错误_。A、 B、 C、 D、 7、设集

21、合上的两个关系，则R具有_。A、对称性 B、传递性 C、自反性 D、反自反性8、下述结论错误的是_。A、存在这样的关系，它可以既满足对称性，又满足反对称性。B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。C、存在这样的关系，它可以既满足自反性，又满足反自反性。D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。9、下面关于对称关系的描述错误的是_。A、对称关系与其逆关系相等 B、对称关系的矩阵与其逆矩阵相等 C、对称关系的矩阵与其转置矩阵相等 D、对称关系的关系图中任何两个顶点之间如果有边必是一对方向相反的边 10、以下无向图中，不是二部图的是_。A、 B、C、D、11、在

22、下列关于图论的命题中，正确的是_。A、哈密顿图一定是欧拉图B、无向完全图都是欧拉图C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出D、哈密顿图是平面图12、以下无向图中，不是平面图的是_。A、 B、C、D、13、下面编码_不是前缀码。A、11，00，10，01B、01，11，001，1001C、101，11，001，011，010D、010，11，011，1011，1001，1110114、5阶非同构的无向树有_棵。A、3 B、4 C、5 D、6 15、在下列选项中，关于n阶树(n1)的性质描述不正确的是_。A、在连通n阶图中，n阶树的边的数量最少B、在n阶无回路图中，n阶树的边的数

23、量最多C、n阶树不一定是平面图D、n阶树(n1)至少有两片树叶三、计算题（5分+8分，共13分）1、如下图所示的赋权图表示某七个城市 ，及预先算出它们之间直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算出最小造价。V1V2V3V4V5V6135246789V7102、设集合，X上的关系R如图所示，试求：abcd（1）写出关系R的关系矩阵；（2）画出关系R的自反闭包r(R)的关系图；（3）画出关系R的对称闭包s(R)的关系图；（4）画出关系R的传递闭包t(R)的关系图。四、证明题（6分，共6分）1、设T=是n阶非平凡的无向树，证明：T至少有两片树叶。五、应用题（

24、9分+6分+6分，共21分）1、给出集合，分别求出： (1)画出集合的整除偏序关系的哈斯图；(2)集合的最大元，最小元，极大元，极小元； (3)集合的上界，下界，最小上界，最小下界。2、某研究机构要从A,B,C三人中选派若干人出国考察, 由于工作需要必须满足下述条件: 若A去，则C必须去；若B去，则C不能去；若C不去，则A或B可以去。请按以下三个步骤筛选可能的选派方案：(1)符号化命题；(2)求命题的主析取范式；(3)列出可行的选派方案。3、请在自然推理系统P中构造下面的证明：如果数a是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不是有理数；a是实数且它不能表示成分数，因此a是无理

25、数。(1) 将命题中的4个简单命题依次符号化为p,q,r,s；(2) 将命题符号化，即将命题的前提与结论符号化；(3) 在自然推理系统P中构造命题的推理证明。2008-2-B一、填空（每空2分，共30分）1、设P：1+1=2，Q：2是偶数，将命题“1+1=2，仅当2是偶数”符号化 (1)_，其真值为 (2)_。2、在公式中，约束出现的变元为 (3)_。 3、给定集合上的3个关系如下：则其中满足对称性的关系是 (4)_；满足自反性的关系是 (5)_。4、非空集合A上的自反、 (6)_和传递的关系称为A上的偏序关系。5、后缀表达式 3 5 2 * 7 + 4 / 的值是 (7)_。6、设无向图G有

26、11条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中有 (8)_个悬挂顶点。7、设G为连通的平面图，有5个面，总度数为14，则G有 (9)_条边，有 (10)_个顶点。8、已知一棵无向树T中有4度、3度和2度分支点各1个，其余顶点均为树叶，则T有 (11)_个树叶。9、设集合，上的运算定义为：则代数系统中单位元是 (12)_，的右逆元是 (13)_，无右逆元的元素是 (14)_。10、设运算的运算表如下所示，则运算满足交换律、幂等律、结合律中的 (15)_。*abcacabbabccbca二、选择题（每题2分，共30分）1、下面语句是真命题的为_。A、我正在说谎

27、。B、如果112，则太阳从西边升起来。C、如果113，则太阳从西边升起来。D、吃饭了吗？2、命题公式P(QP)为_。A、重言式 B、可满足式 C、矛盾式 D、等值式3、下面联结词不具有交换律的是_。A、 B、 C、 D、4、设I是如下一个解释，其中，为真，为假，则在解释I下取真值的公式是_A、 B、 C、 D、5、下列哪个表达式错误_。A、 B、 C、 D、 6、设集合上的两个关系，则R具有_。A、自反性 B、传递性 C、对称性 D、反自反性7、下述结论错误的是_。A、存在这样的关系，它可以既满足对称性，又满足反对称性。B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。C、存在这样的

28、关系，它可以既满足自反性，又满足反自反性。D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。8、设偏序集（）关系R的哈斯图如右所示，若A的子集，则元素6为B的_。A、下界 B、上界 C、最小上界 D、以上都不对 9、以下整数序列，能成为一个简单图的顶点度数序列的是_。A、1，2，2，3，4，5B、2，3，3，4，4，5C、2，2，3，4，5，6D、1，2，2，3，3，510、设图G是有6个顶点的连通图，总度数为16，则从G中删去_条边后可以使之成为树。A、10 B、5 C、3 D、211、在下列关于图论的命题中，正确的是_。A、哈密顿图一定是欧拉图B、无向完全图都是欧拉图C、度数为奇

29、数的顶点个数为0个或2个的连通无向图可一笔画出D、哈密顿图是平面图12、下面编码_不是前缀码。A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010113、6阶非同构的无向树有_棵。A、5 B、6 C、7 D、8 14、实数集R关于下列二元运算满足结合律和交换律的是_。 A、 B、 C、 D、15、在下列选项中，不是群的是_。A、，为有理数，+为加法运算B、，为非零实数集，为乘法运算C、，为实数集，+为加法运算D、，为有理数，*为乘法运算三、计算题（5分+6分+8分，共19分）1、求下图中的最小生

30、成树，并计算它的权。V1V2V6V3V5V41352467892、设有7个字母在通信中出现的频率(%)如下： a: 35% b: 20%, c: 15%, d: 10%, e: 10%, f: 5%, g: 5%(1)以频率(或乘100)为权，求最优2元树(2)利用所求最优2元树找出每个字母的前缀码(3)求传输10000个按上述比例出现的字母需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字?节约多少个二进制位？3、设集合，X上的关系R如图所示，试求：abcd（1）写出关系R的关系矩阵（2）求关系R的自反闭包r(R)的关系矩阵, ()（3）求关系R的对称闭包s(R)的

31、关系矩阵, ()（4）求关系R的传递闭包t(R)的关系矩阵, ()四、证明题（5分+5分+5分，共15分）1、设,在A上定义二元关系R如下：，证明：R是A上的等价关系。2、 设n阶m条边的无向图G中，m=n+1，证明G中存在顶点v：d(v)3。3、 设G为群，令，证明：H是G的子群。五、应用题（共6分）1. 如果王小红努力学习，她一定取得好成绩。若王小红贪玩或不按时完成作业，她就不能取得好成绩。所以，如果王小红努力学习，她就能按时完成作业。(1) 将命题中的4个简单命题依次符号化为p,q,r,s；(2) 将命题符号化，即将命题的前提和结论符号化；(3) 在自然推理系统P中构造命题的推理证明。2

32、009-2-A一、判断题（本大题共10小题，每小题1分，共10分）1、“如果天气好，那么我去散步”是命题。2、“我正在说谎话”是命题。 3、既是合取范式也是析取范式。4、是前束范式。5、A，B，C都是集合，如果AB=AC，则B=C。6、和是集合A上的具有自反性的关系，则也一定具有自反性。7、顶点数目相同，边数也相同的两个无向图一定同构。8、每个顶点的度数都是偶数的无向图一定是欧拉图。9、五阶完全图既是欧拉图，也是哈密顿图。10、设无向图T是树，则T中一定没有简单回路。 1.5CM得分二、选择题（本大题共15小题，每小题2分，共30分）1、下面语句是简单命题的为_。A、3不是偶数。B、李平既聪明

33、又用功。C、李平学过英语或日语。D、李平和张三是同学。2、下列命题公式中是矛盾式的有_。A、 B、C、 D、3、下列集合不是连接词极小全功能集的为_。A、, B、, C、 D、4、下列谓词公式不是命题公式PQ的代换实例的是_A、 B、 C、 D、5、设个体域为整数集，下列公式中其值为1的是_。A、 B、C、 D、6、下列哪个表达式错误_。A、 B、 C、 D、 7、设集合A1,2,3,4,5,6,7,8，则下列各式为真的是_。A、1A B、4,5A C、1,2,3A D、A8、设集合，集合，则 _。A、 B、 C、 D、9、设集合上的两个关系，则R具有_。A、对称性 B、传递性 C、自反性 D

34、、反自反性10、下述结论错误的是_。A、存在这样的关系，它可以既满足对称性，又满足反对称性。B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。C、存在这样的关系，它可以既满足自反性，又满足反自反性。D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。11、集合A上的关系R为一个等价关系，当且仅当R具有_。A、自反性、对称性和传递性 B、自反性、反对称性和传递性 C、反自反性、对称性和传递性 D、反自反性、反对称性和传递性 12、以下整数序列，能成为一个简单图的顶点度数序列的是_。A、1，2，2，3，4，5B、2，3，3，4，4，5C、2，2，3，4，5，6D、1，2，2，3，

35、3，513、设无向图G的关联矩阵为，则G的顶点数与边数分别为_。(A)4, 5 (B)4, 10 (C)5, 4 (D)5, 1014、以下无向图中，不是二部图的是_。A、 B、C、D、15、设G 是由 5 个顶点组成的无向完全图，则从 G 中删去_条边可以得到树。A、4B、5C、6D、101.5CM得分三、填空题（本大题共10小题，每小题2分，共20分）1、设 p:天冷，q:小王穿羽绒服，将命题“除非天冷，小王才穿羽绒服”符号化 (1)_。2、命题公式的对偶式是 (2)_。3、pq 的主合取范式是 (3)_。4、设G(x)：x爱美，F(x)：x为人，在全总个体域中将命题“人都爱美”符号化 (

36、4)_。5、设F(x)：x是兔子， G(y)：y是乌龟，H(x,y)：x比y跑得快，在全总个体域中将命题“有的兔子比所有的乌龟跑得快”符号化 (5)_。6、设集合，集合，则 (6)_。7、设集合，则 (7)_。8、设集合A=1, 2, 3, 4，R=, , , , 和S=, , , 是集合A上关系，则RS= (8)_。9、设无向图G有12条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中有 (9)_个悬挂顶点。10、写出波兰符号表达式 abcdefg对应的算术表达式 (10)_。1.5CM得分四、计算题（本大题共2小题，每小题6分，共12分）1、求1到1000之间

37、的整数（包含1和1000在内）既不能被 6 和7 整除，也不能被 8 整除的数有多少个？2、有向图D如图4-1所示，试求：(1) 写出有向图D邻接矩阵A；(2) 判断有向图D的连通性。v1v2v3v4图4-11.5CM得分五、应用题（本大题共2小题，每小题8分，共16分）1、给出集合，分别求出： (1)画出集合的整除偏序关系的哈斯图；(2)集合的最大元，最小元，极大元，极小元； (3)集合的上界，下界，最小上界，最大下界。2、设集合，X上的关系R如图5-1所示，试求：abcde图5-1（1）写出关系R的关系矩阵；（2）画出关系R的自反闭包r(R)的关系图；（3）画出关系R的对称闭包s(R)的关系图；（4）画出关系R的传递闭包t(R)的关系图。1.5CM得分六、证明题（本大题共2小题，每小题6分，共12分）1、公安人员审查一件盗窃案，已知的事实如下： 甲或乙盗窃了录音机； 若甲盗窃了录音机，则作案时间不能发生在午夜前； 若乙的证词正确，则午夜时屋里灯光未灭； 若乙的证词不正确，则作案时间发生在午夜之前； 午夜时屋里灯光灭了。试问谁盗窃了录音机？将命题符号化，即将命题的前提符号化；然后在自然