离散结构试卷答案

1离散结构2007A一、填空（每空2分，共30分）1、设P224，Q3是奇数将命题“224，当且仅当3是奇数”符号化_1_，其真值为_2_。2、在公式中，自由出现的变元为_3_。,YXF3、若关系R具有自反性，当且仅当在关系矩阵中，主对角上元素_4_，若关系R具有对称性，当且仅当关系矩阵是_5_。4、若关系，则关系一定具有_6_性。15、有向图的连通性可分为弱连通、强连通、_7_。6、前缀表达式2/843的值是_8_。7、设G是完全二元树，G有15个顶点，其中有8个叶子，则G有_9_条边，G的总度数是_10_。8、十进制3位数的数字中恰好有一个8和一个9，共有_11_个这样的3位数。9、设集合，上的运算定义为,EDCBASSABCDEAABCDEBBDACDCCABABDDACDCEEDACE则代数系统中单位元是_12_，的左逆元是_13_，无左逆元的元素是_14_。,SB10、设是由元素生成的循环群，且的阶为4，则集合_15_。SASS二、选择题（每题2分，共30分）1、下列语句中，_是命题。A、地球上的人真多B、把门关上2C、下午有会吗D、65X2、一个公式在等价意义下，下面哪个写法是唯一的_。A、析取范式B、合取范式C、主析取范式D、以上都不唯一3、设命题公式，则G是_。QPGA、永真式B、矛盾式C、可满足式D、以上都不是4、设I是如下一个解释，其中，为真，为假，则在,BAD,AP,B,BAP,解释I下取真值的公式是_A、B、C、D、,YXP,YX,X,YX5、下列哪个表达式错误_。A、QPB、XXQXPC、D、6、设R，S是集合上的两个关系，其中，4,321A4,3,2,1,R，则S是R的_闭包。4,1A、自反B、反对称C、对称D、传递7、设R和S是非空集合A上的等价关系，下列各式是A上等价关系的是_。A、B、C、D、的对称闭包SRSRSR8、设偏序集（）关系R的哈斯图如右所示，若A的子集，则元素6为B的,5,432B_。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，610、设图G是有6个顶点的连通图，总度数为20，则从G中至少删去_条边后使之成为树。A、10B、5C、3D、2311、在下列关于图论的命题中，正确的是_。A、哈密顿图一定是欧拉图B、无向完全图都是欧拉图3NKC、度数为奇数的顶点个数为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、1B、2C、3D、414、由0、1、2、3这四个数字能构成_个3位数A、64B、48C、24D、1815、在下列选项中，不是群的是_。A、，为有理数，为加法运算,QB、，为非零实数集，为乘法运算RC、全体实对称矩阵集合，对于矩阵的加法运算D、，为有理数，为乘法运算,三、计算题（5分5分8分，共18分）1、设有5个城市，任意两城市之间的铁路造价如下54321,V，,2VW716,4W10,5V13,2VW，84,523354试求出连接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的商集，试求5,431A/5,432,1（1）等价关系R4（2）写出关系矩阵RM（3）画出关系图（4）写出R的传递闭包四、证明题（5分5分6分，共16分）1、设R是A上的等价关系，S是B上的等价关系，且A和B非空，关系T满足且，证明T是上的等价关系。TBYAX,RYX,SBA,BA2、设G为N阶无向简单图，证明若G为自补图（若一个图的补图为本身则称为自补图），则或，其中K为正整数。K413、若是群，定义G中的运算“”为，对,UBUA1GA,证明为群。G五、应用题（6分）的意义如下P张群是大学生，Q张群心情愉快，R张群唱歌RQP,试用日常语言说明下列复合命题12RQP32007B一、填空（每空2分，共30分）1、表达式中谓词的个体域是，将其中的量词消去，写成与之等价的命题XGXFC,BA公式为_1_。2、设R是集合A上的二元关系，如果关系R同时具有_2_、_3_和传递，则称R是A上的偏序关系。3、已知集合上的二元关系，5,43212,4,32,1，则_4_，_5_。,1,4SS4、若有限集关系具有自反性，则其对应的关系矩阵主对角元素全为_6_。AR55、若某个简单图不是欧拉图但具有欧拉通路，则图中顶点度数为奇数的顶点个数一定为_7_。6、设是图，如果G是_8_并且_9_则G是树。EVG,7、一个无向图的欧拉回路要求经过图中_10_一次且仅一次，哈密顿回路要求经过图中_11_一次且仅一次。8、树是平面图，它有_12_个面。9、在群、半群、独异点中，_13_满足消去律。10、设Q为有理数集，笛卡尔积，是S上的二元运算，有QSSYXBA,，则运算的单位元为_14_，（），则BYAXBA,0的逆元为_15_。二、选择题（每题2分，共30分）1、下列语句中_是命题。A、把门关上B、地球外的星球上也有人C、65XD、下午有会吗2、已知命题，则所有使G取真值的解释是_。RQPGA、000，001，100B、100，101，110C、010，101，001D、001，101，1113、命题公式A和B是等价的是指A、A和B由相同的原子变元B、A和B都是可满足的C、当A的真值为真时，B的真值也为真D、A和B有相同的真值4、对、而言，下列是极小项的是_。PQRA、B、QPC、D、R5、设集合，R、S、T都是A上的关系，3,213,1,2,，则T_。,S312,A、B、C、D、RS66、若T为树，以下叙述不正确的是_。A、T是连通的且不含回路B、T的每对顶点之间有唯一的一条路径C、T是连通的且每条边都是割边D、T是连通的且每个点都是割点7、设集合为，下列关系R中不是等价关系的是_。3,21AA、,RB、3,2,C、12,11D、3,2,3,8、设集合，A上的关系，则R不具备322R_。A、自反性B、传递性C、对称性D、反对称性9、设T是由N个顶点的完全二元树，则T的叶子数为_。A、B、C、D、112N2/1N3/2N10、设无向图G有12条边，已知G中3度顶点有6个，其余顶点度数均小于3，则G中顶点数最多有_。A、6B、8C、9D、1211、设I是如下一个解释，其中，为真，为假，则,BAD,AP,B,BAP,在解释I下取真值的公式是_。A、B、C、D、,YXP,YX,X,YXP12、设R和S是非空集合A上的等价关系，下列各式是A上等价关系的是_。A、B、C、D、的对称闭包SRSRSR13、下面编码_不是前缀码。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、64B、48C、24D、18715、在下列选项中，不是群的是_。A、，为有理数，为加法运算,QB、，为非零实数集，为乘法运算RC、全体实对称矩阵集合，对于矩阵的加法运算D、，为有理数，为乘法运算,三、计算题（5分5分8分，共18分）1、已知有向图，E，EV,5,43213,24,12,，求有向图D的邻接矩阵和可达矩阵。15,3,42、求叶的权值分别为2，4，6，8，10，12，14的最优二元树及其权值。3、试画出集合，在偏序关系整除下的哈斯图，并分别求出,53,1A1集合的最大元，最小元，极大元，极小元；2集合的上界，下界，最小上界，最小下界。6,2B四、证明题（5分5分6分，共16分）1、证明利用命题演绎法证明RSQPSRQP2、设R和S是A上的二元关系，证明11S3、证明设是一个代数系统，是上的二元运算，则,R,RBABA0是单位元，且是含幺半群。（为实数集合）。五、应用题（共6分）的意义如下P张群是大学生，Q张群心情愉快，R张群唱歌RQP,试用日常语言说明下列复合命题（1）（2）RQP8（3）RQP2008AV11一、填空（每空2分，共30分）1、设P112，Q2是偶数，将命题“112，仅当2是偶数”符号化1_，其真值为2_。2、在公式中，约束出现的变元为3_。,YXGZFX3、给定集合上的3个关系如下,21A，1,1R1,3,1,23,2,2R，,2,3,3,23则其中满足对称性的关系是4_；满足自反性的关系是5_。4、非空集合A上的自反、6_和传递的关系称为A上的偏序关系。5、后缀表达式35274/的值是7_。6、设无向图G有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、设集合，上的运算定义为,EDCBASSABCDEAABCDEBBDACDCCABABDDACDCEEDBCE则代数系统中单位元是12_，的右逆元是13_，无右逆元的元素是14,S_。910、设运算的运算表如下所示，则运算满足交换律、幂等律、结合律中的15_。ABCACABBABCCBCA二、选择题（每题2分，共30分）1、下面语句是真命题的为_。A、我正在说谎。B、如果112，则太阳从西边升起来。C、如果113，则太阳从西边升起来。D、吃饭了吗2、命题公式PQP为_。A、重言式B、可满足式C、矛盾式D、等值式3、下面联结词不具有交换律的是_。A、B、C、D、4、设I是如下一个解释，其中，为真，为假，则在,BAD,AP,B,BAP,解释I下取真值的公式是_A、B、C、D、,YXP,YX,X,YX5、下列哪个表达式错误_。A、QPB、XXQXPC、D、6、设集合上的两个关系，则R具有_。4,321A4,3,23,1,RA、自反性B、传递性C、对称性D、反自反性7、下述结论错误的是_。A、存在这样的关系，它可以既满足对称性，又满足反对称性。B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。10C、存在这样的关系，它可以既满足自反性，又满足反自反性。D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。8、设偏序集（）关系R的哈斯图如右所示，若A的子集，则元素6为B的,A5,432B_。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、10B、5C、3D、211、在下列关于图论的命题中，正确的是_。A、哈密顿图一定是欧拉图B、无向完全图都是欧拉图3NKC、度数为奇数的顶点个数为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、5B、6C、7D、814、实数集R关于下列二元运算满足结合律和交换律的是_。A、B、C、D、BA2BAABA2|BA15、在下列选项中，不是群的是_。A、，为有理数，为加法运算,QB、，为非零实数集，为乘法运算R11C、，为实数集，为加法运算,RD、，为有理数，为乘法运算Q三、计算题（5分6分8分，共19分）1、求下图中的最小生成树，并计算它的权。V1V2V6V3V5V41352467892、设有7个字母在通信中出现的频率如下A35B20,C15,D10,E10,F5,G51以频率或乘100为权，求最优2元树2利用所求最优2元树找出每个字母的前缀码3求传输10000个按上述比例出现的字母需要多少个二进制数字若用等长的长为3的码字传输需要多少个二进制数字节约多少个二进制位3、设集合，X上的关系R如图所示，试求,DCBAABCD（1）写出关系R的关系矩阵RM（2）求关系R的自反闭包RR的关系矩阵,RRXIR0（3）求关系R的对称闭包SR的关系矩阵,S1（4）求关系R的传递闭包TR的关系矩阵,RT432四、证明题（5分5分5分，共15分）1、设,在A上定义二元关系R如下Z，证明R是A上的等价关系。ZVUYXXVVUYX,其中122、设N阶M条边的无向图G中，MN1，证明G中存在顶点VDV3。3、设G为群，令，证明H是G的子群。A|ZKA五、应用题（共6分）1如果王小红努力学习，她一定取得好成绩。若王小红贪玩或不按时完成作业，她就不能取得好成绩。所以，如果王小红努力学习，她就能按时完成作业。1将命题中的4个简单命题依次符号化为P,Q,R,S；2将命题符号化，即将命题的前提和结论符号化；3在自然推理系统P中构造命题的推理证明。20082A一、填空（每空2分，共30分）1、设P张晓拿一个苹果，Q张晓拿一个梨，将命题“张晓只能拿一个苹果或拿一个梨”符号化1_。2、设PXX是偶数，QXX是奇数，在实数R个体域中将命题“存在偶数，也存在奇数”符号化2_，其真值为3_。3、非空集合A上的自反、对称和4_的关系称为A上的等价关系。4、给定集合上的3个关系如下,21，1,1R3,2,1,2R，23323则其中满足自反性的关系是5_；满足对称性的关系是6_；满足传递性的关系是7_。5、关系，3,2,4,12,R，则RS3S8_。6、波兰符号表达式45/821的值是9_。7、设无向图G有11条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点即1度顶点，则G中13有10_个悬挂顶点。8、设G为连通的平面图，有5个面，总度数为16，则G有11_条边，有12_个顶点。9、已知一棵无向树T中有4度、3度和2度分支点各1个，其余顶点均为树叶，则T有13_个树叶。10、设是无向图，如果G是14_并且15_则G是树。EV,二、选择题（每题2分，共30分）1、下面语句是命题的为_。A、我正在说谎。B、把门关上。C、地球外的星球上也存在生命。D、吃饭了吗2、命题公式PQPQP为_。A、重言式B、非重言式的可满足式C、矛盾式D、等值式3、下列集合不是连接词完备集的为_。A、,B、,C、,D、4、下列谓词公式不是命题公式PQ的代换实例的是_A、B、C、D、YGXF,YXGYXFXGFX5、下列哪个表达式错误_。A、XPXB、QXPC、QD、XX6、下列哪个表达式错误_。A、BAXB、XC、D、X147、设集合上的两个关系，则R具有_。4,321A3,2,4,1,RA、对称性B、传递性C、自反性D、反自反性8、下述结论错误的是_。A、存在这样的关系，它可以既满足对称性，又满足反对称性。B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。C、存在这样的关系，它可以既满足自反性，又满足反自反性。D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。9、下面关于对称关系的描述错误的是_。A、对称关系与其逆关系相等B、对称关系的矩阵与其逆矩阵相等C、对称关系的矩阵与其转置矩阵相等D、对称关系的关系图中任何两个顶点之间如果有边必是一对方向相反的边10、以下无向图中，不是二部图的是_。A、B、C、D、11、在下列关于图论的命题中，正确的是_。A、哈密顿图一定是欧拉图B、无向完全图都是欧拉图3NKC、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出D、哈密顿图是平面图12、以下无向图中，不是平面图的是_。A、B、C、D、1513、下面编码_不是前缀码。A、11，00，10，01B、01，11，001，1001C、101，11，001，011，010D、010，11，011，1011，1001，1110114、5阶非同构的无向树有_棵。A、3B、4C、5D、615、在下列选项中，关于N阶树N1的性质描述不正确的是_。A、在连通N阶图中，N阶树的边的数量最少B、在N阶无回路图中，N阶树的边的数量最多C、N阶树不一定是平面图D、N阶树N1至少有两片树叶三、计算题（5分8分，共13分）1、如下图所示的赋权图表示某七个城市，及预先算出它们之间直接通信线路造价，试给721,V出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算出最小造价。V1V2V3V4V5V6135246789V7102、设集合，X上的关系R如图所示，试求,DCBAABCD（1）写出关系R的关系矩阵；RM（2）画出关系R的自反闭包RR的关系图；（3）画出关系R的对称闭包SR的关系图；16（4）画出关系R的传递闭包TR的关系图。四、证明题（6分，共6分）1、设T是N阶非平凡的无向树，证明T至少有两片树叶。五、应用题（9分6分6分，共21分）1、给出集合，分别求出6,5432,1A1画出集合的整除偏序关系的哈斯图；2集合的最大元，最小元，极大元，极小元；3集合的上界，下界，最小上界，最小下界。,B2、某研究机构要从A,B,C三人中选派若干人出国考察,由于工作需要必须满足下述条件若A去，则C必须去；若B去，则C不能去；若C不去，则A或B可以去。请按以下三个步骤筛选可能的选派方案1符号化命题；2求命题的主析取范式；3列出可行的选派方案。3、请在自然推理系统P中构造下面的证明如果数A是实数，则它不是有理数就是无理数；若A不能表示成分数，则它不是有理数；A是实数且它不能表示成分数，因此A是无理数。1将命题中的4个简单命题依次符号化为P,Q,R,S；2将命题符号化，即将命题的前提与结论符号化；3在自然推理系统P中构造命题的推理证明。20082B一、填空（每空2分，共30分）1、设P112，Q2是偶数，将命题“112，仅当2是偶数”符号化1_，其真值为2_。172、在公式中，约束出现的变元为3_。,YXGZFX3、给定集合上的3个关系如下,21A，1,1R1,3,1,23,2,2R，,2,3,3,23则其中满足对称性的关系是4_；满足自反性的关系是5_。4、非空集合A上的自反、6_和传递的关系称为A上的偏序关系。5、后缀表达式35274/的值是7_。6、设无向图G有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、设集合，上的运算定义为,EDCBASSABCDEAABCDEBBDACDCCABABDDACDCEEDBCE则代数系统中单位元是12_，的右逆元是13_，无右逆元的元素是14,S_。10、设运算的运算表如下所示，则运算满足交换律、幂等律、结合律中的15_。ABCACABBABCCBCA18二、选择题（每题2分，共30分）1、下面语句是真命题的为_。A、我正在说谎。B、如果112，则太阳从西边升起来。C、如果113，则太阳从西边升起来。D、吃饭了吗2、命题公式PQP为_。A、重言式B、可满足式C、矛盾式D、等值式3、下面联结词不具有交换律的是_。A、B、C、D、4、设I是如下一个解释，其中，为真，为假，则在,BAD,AP,B,BAP,解释I下取真值的公式是_A、B、C、D、,YXP,YX,X,YX5、下列哪个表达式错误_。A、QPB、XXQXPC、D、6、设集合上的两个关系，则R具有_。4,321A4,3,23,1,RA、自反性B、传递性C、对称性D、反自反性7、下述结论错误的是_。A、存在这样的关系，它可以既满足对称性，又满足反对称性。B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。C、存在这样的关系，它可以既满足自反性，又满足反自反性。D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。8、设偏序集（）关系R的哈斯图如右所示，若A的子集，则元素6为B的,A5,432B_。19A、下界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、10B、5C、3D、211、在下列关于图论的命题中，正确的是_。A、哈密顿图一定是欧拉图B、无向完全图都是欧拉图3NKC、度数为奇数的顶点个数为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、5B、6C、7D、814、实数集R关于下列二元运算满足结合律和交换律的是_。A、B、C、D、BA2BAABA2|BA15、在下列选项中，不是群的是_。A、，为有理数，为加法运算,QB、，为非零实数集，为乘法运算RC、，为实数集，为加法运算,D、，为有理数，为乘法运算三、计算题（5分6分8分，共19分）1、求下图中的最小生成树，并计算它的权。20V1V2V6V3V5V41352467892、设有7个字母在通信中出现的频率如下A35B20,C15,D10,E10,F5,G51以频率或乘100为权，求最优2元树2利用所求最优2元树找出每个字母的前缀码3求传输10000个按上述比例出现的字母需要多少个二进制数字若用等长的长为3的码字传输需要多少个二进制数字节约多少个二进制位3、设集合，X上的关系R如图所示，试求,DCBAABCD（1）写出关系R的关系矩阵RM（2）求关系R的自反闭包RR的关系矩阵,RRXIR0（3）求关系R的对称闭包SR的关系矩阵,S1（4）求关系R的传递闭包TR的关系矩阵,RT432四、证明题（5分5分5分，共15分）1、设,在A上定义二元关系R如下Z，证明R是A上的等价关系。ZVUYXXVVUYX,其中2、设N阶M条边的无向图G中，MN1，证明G中存在顶点VDV3。3、设G为群，令，证明H是G的子群。A|ZKA21五、应用题（共6分）1如果王小红努力学习，她一定取得好成绩。若王小红贪玩或不按时完成作业，她就不能取得好成绩。所以，如果王小红努力学习，她就能按时完成作业。1将命题中的4个简单命题依次符号化为P,Q,R,S；2将命题符号化，即将命题的前提和结论符号化；3在自然推理系统P中构造命题的推理证明。20092A一、判断题（本大题共10小题，每小题1分，共10分）1、“如果天气好，那么我去散步”是命题。2、“我正在说谎话”是命题。3、既是合取范式也是析取范式。QP4、是前束范式。XGXF5、A，B，C都是集合，如果ABAC，则BC。6、和是集合A上的具有自反性的关系，则也一定具有自反性。1R221R7、顶点数目相同，边数也相同的两个无向图一定同构。8、每个顶点的度数都是偶数的无向图一定是欧拉图。9、五阶完全图既是欧拉图，也是哈密顿图。5K10、设无向图T是树，则T中一定没有简单回路。二、选择题（本大题共15小题，每小题2分，共30分）1、下面语句是简单命题的为_。A、3不是偶数。B、李平既聪明又用功。C、李平学过英语或日语。D、李平和张三是同学。2、下列命题公式中是矛盾式的有_。得分15CM22A、B、PPPQC、D、QR3、下列集合不是连接词极小全功能集的为_。A、,B、,C、D、4、下列谓词公式不是命题公式PQ的代换实例的是_A、B、YGXF,YXGYXFC、D、X5、设个体域为整数集，下列公式中其值为1的是_。A、0YXB、0YXC、D、6、下列哪个表达式错误_。A、BXAXB、C、D、XX7、设集合A1,2,3,4,5,6,7,8，则下列各式为真的是_。A、1AB、4,5AC、1,2,3AD、A8、设集合，集合，则_。12,0864,18,529,63BA、B、C、D、5328,5049,69、设集合上的两个关系，则R具有_。4,14,3,23,1,RA、对称性B、传递性C、自反性D、反自反性10、下述结论错误的是_。A、存在这样的关系，它可以既满足对称性，又满足反对称性。B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。C、存在这样的关系，它可以既满足自反性，又满足反自反性。23D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。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，3，513、设无向图G的关联矩阵为，则G的顶点数与边数分别为_。021A4,5B4,10C5,4D5,1014、以下无向图中，不是二部图的是_。A、B、C、D、15、设G是由5个顶点组成的无向完全图，则从G中删去_条边可以得到树。A、4B、5C、6D、10三、填空题（本大题共10小题，每小题2分，共20分）1、设P天冷，Q小王穿羽绒服，将命题“除非天冷，小王才穿羽绒服”符号化1_。2、命题公式的对偶式是2_。RQP得分15CM243、PQ的主合取范式是3_。4、设GXX爱美，FXX为人，在全总个体域中将命题“人都爱美”符号化4_。5、设FXX是兔子，GYY是乌龟，HX,YX比Y跑得快，在全总个体域中将命题“有的兔子比所有的乌龟跑得快”符号化5_。6、设集合，集合，则6_。12,086A12,963BAB7、设集合，则7_。AAP8、设集合A1,2,3,4，R,和S,是集合A上关系，则RS8_。9、设无向图G有12条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点即1度顶点，则G中有9_个悬挂顶点。10、写出波兰符号表达式ABCDEFG对应的算术表达式10_。四、计算题（本大题共2小题，每小题6分，共12分）1、求1到1000之间的整数（包含1和1000在内）既不能被6和7整除，也不能被8整除的数有多少个2、有向图D如图41所示，试求1写出有向图D邻接矩阵A；2判断有向图D的连通性。V1V2V3V4图41得分15CM25五、应用题（本大题共2小题，每小题8分，共16分）1、给出集合，分别求出12,09,8765,4321A1画出集合的整除偏序关系的哈斯图；2集合的最大元，最小元，极大元，极小元；3集合的上界，下界，最小上界，最大下界。,B2、设集合，X上的关系R如图51所示，试求,EDCBAXABCDE图51（1）写出关系R的关系矩阵；RM（2）画出关系R的自反闭包RR的关系图；（3）画出关系R的对称闭包SR的关系图；（4）画出关系R的传递闭包TR的关系图。六、证明题（本大题共2小题，每小题6分，共12分）1、公安人员审查一件盗窃案，已知的事实如下甲或乙盗窃了录音机；若甲盗窃了录音机，则作案时间不能发生在午夜前；若乙的证词正确，则午夜时屋里灯光未灭；若乙的证词不正确，则作案时间发生在午夜之前；午夜时屋里灯光灭了。试问谁盗窃了录音机将命题符号化，即将命题的前提符号化；然后在自然推理系统中构造命题的推理证明过程。2、求下列谓词公式的前束范式，要求使用自由变项换名规则，请写出推理过程,ZYXHZYXGFX得分得分15CM15CM2620092B一、判断题（本大题共10小题，每小题1分，共10分）1、奇数阶完全图一定是欧拉图。012NK2、二阶以上连通没有回路的无向图是二部图。3、“如果天气好，那么我去散步”是命题。4、“我正在说谎话”是命题。5、既是合取范式也是析取范式。QP6、是前束范式。XGXF7、A，B，C都是集合，如果ABAC，则BC。8、和是集合A上的具有自反性的关系，则也一定具有自反性。1R221R9、顶点数目相同，边数也相同的两个无向图一定同构。10、每个顶点的度数都是偶数的无向图一定是欧拉图。二、选择题（本大题共15小题，每小题2分，共30分）1、下面语句是真命题的为_。A、我正在说谎。B、如果112，则太阳从西边升起来。C、如果113，则太阳从西边升起来。D、吃饭了吗2、命题公式PQP为_。A、重言式B、可满足式C、矛盾式D、等值式3、下面联结词不具有交换律的是_。A、B、C、D、4、设I是如下一个解释，其中，为真，为假，则在,BAD,AP,B,BAP,解释I下取真值的公式是_得分15CM27A、B、C、D、,YXP,YXP,XP,YXP5、下列哪个表达式错误_。A、QPB、XXQXPC、D、6、设集合上的两个关系，则R具有_。4,321A4,3,23,1,RA、自反性B、传递性C、对称性D、反自反性7、下述结论错误的是_。A、存在这样的关系，它可以既满足对称性，又满足反对称性。B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。C、存在这样的关系，它可以既满足自反性，又满足反自反性。D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。8、设偏序集（）关系R的哈斯图如右所示，若A的子集，则元素6为B的,A5,432B_。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、10B、5C、3D、211、在下列关于图论的命题中，正确的是_。A、哈密顿图一定是欧拉图B、无向完全图都是欧拉图3NKC、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出D、哈密顿图是平面图12、下面编码_不是前缀码。28A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010113、6阶非同构的无向树有_棵。A、5B、6C、7D、814、实数集R关于下列二元运算满足结合律和交换律的是_。A、B、C、D、BA2BAABA2|BA15、在下列选项中，不是群的是_。A、，为有理数，为加法运算,QB、，为非零实数集，为乘法运算RC、，为实数集，为加法运算,D、，为有理数，为乘法运算三、填空题（本大题共10小题，每小题2分，共20分）1、设P112，Q2是偶数，将命题“112，仅当2是偶数”符号化1_。2、在公式中，约束出现的变元为2_。,YXGZFX3、给定集合上的3个关系如下,1A，1,22,1R1,3,1,23,2,2R，,3则其中满足对称性的关系是3_；4、非空集合A上的自反、4_和传递的关系称为A上的偏序关系。5、后缀表达式35274/的值是5_。6、设无向图G有11条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点即1度顶点，则G中有6_个悬挂顶点。7、设G为连通的平面图，有5个面，总度数为14，则G有7_个顶点。15CM298、已知一棵无向树T中有4度、3度和2度分支点各1个，其余顶点均为树叶，则T有8_个树叶。9、设集合，上的运算定义为,EDCBASSABCDEAABCDEBBDACDCCABABDDACDCEEDBCE则代数系统中单位元是9_。,S10、设运算的运算表如下所示，则运算满足交换律、幂等律、结合律中的10_。ABCACABBABCCBCA四、计算题（本大题共2小题，每小题6分，共12分）1、求下图中的最小生成树，并计算它的权。V1V2V6V3V5V41352467892、设有7个字母在通信中出现的频率如下A35B20,C15,D10,E10,F5,G51以频率或乘100为权，求最优2元树2利用所求最优2元树找出每个字母的前缀码3求传输10000个按上述比例出现的字母需要多少个二进制数字若用等长的长为3的码字传输需要多少个二进制数字节约多少个二进制位15CM30五、应用题（本大题共2小题，每小题8分，共16分）1、设集合，X上的关系R如图所示，试求,DCBAABCD（1）写出关系R的关系矩阵RM（2）求关系R的自反闭包RR的关系矩阵,RRXIR0（3）求关系R的对称闭包SR的关系矩阵,S1（4）求关系R的传递闭包TR的关系矩阵,RT4322、如果王小红努力学习，她一定取得好成绩。若王小红贪玩或不按时完成作业，她就不能取得好成绩。所以，如果王小红努力学习，她就能按时完成作业。1将命题中的4个简单命题依次符号化为P,Q,R,S；2将命题符号化，即将命题的前提和结论符号化；3在自然推理系统P中构造命题的推理证明。六、证明题（本大题共2小题，每小题6分，共12分）1、设,在A上定义二元关系R如下Z，证明R是A上的等价关系。ZVUYXXVVUYX,其中2、设N阶M条边的无向图G中，MN1，证明G中存在顶点VDV3。2010一、选择题（本大题共15小题，每小题2分，共30分）1、给定语句如下，则_是复合命题。A、15是素数B、2X23得分15CM15CM31C、小王和小李是好朋友。D、小王和小李成绩都好。2、给定下列语句中，是真命题的是_。A、这个男孩真勇敢呀。B、明年5月1日是晴天。C、如果226，则3是奇数。D、2X233、下列哪个表达式错误_。A、XQPXB、QXPC、XXD、QPX4、斯科特先生、他的妹妹、儿子、女儿都是网球选手，关于这四个人，有如的情况最佳选手的孪生同胞与最差选手性别不同；最佳选手与最差选手年龄相同。则_是最佳选手。A、斯科特B、斯科特妹妹C、斯科特儿子D、斯科特女儿5、是人，活百岁以上；则“有人能活百岁以上”可表示为_。XMXFA、B、XXC、MFD、XX6、给定解释如下个体域为整数集合；中特定元素；特定函数IIDI1,0AID；上特定谓词为。给定下面各公式YXGYXF,IYXF32A、,11AXGFFB、,YFYXC、,XGFD、,0YXGFFAYF则公式_真值为假。7、若，则上可以定义_个二元关系。3|AA、9B、27C、81D、5128、下列关于关系的等式不成立的是_。A、HGFB、11C、D、HGFG9、若关系的关系矩阵为对称矩阵，则关系一定具有_。RRA、自反性B、对称性C、反对称D、传递性10、若T为树，以下叙述不正确的是_。A、T是连通的且每个点都是割点B、T的每对顶点之间有唯一的一条路径C、T是连通的且每条边都是割边D、T是连通的且不含回路11、在下列选项中，不是群的是_。A、，为有理数，为乘法运算,QB、，为非零实数集，为乘法运算,R33C、全体实对称矩阵集合，对于矩阵的加法运算D、，为有理数，为加法运算,Q12、给定下列各序列，可以构成无向简单图的度数序列为_。A、1,1,2,2,3B、1,1,2,2,2C、0,1,3,3,3D、1,3,4,4,513、5个顶点非同构的根树有_个。A、7B、8C、9D、1014、下面编码_不是前缀码。A、11，00，10，01B、01，11，011，1001C、101，11，001，011，010D、010，11，011，1011，1001，1010115、无向完全带权图中，按权计算最多有_条不同的哈密顿回路。NK2A、B、C、D、12/1N2/N二、填空题（本大题共15空，每空2分，共30分）1、若有限集合上的等价关系有三个等价类，则其关系图的连通分支数为_。AR2、设个体域为整数集合，命题的真值为_。0YX3、的前束范式为_。,YXGYXF4、设R是集合A上的二元关系，如果关系R同时具有自反性、_和传递性，则称R是A上的偏序关系。5、设，定义S上的关系，则R具有_性10,2S10,|YXSYXR质。6、在有理数集上定义二元运算，有，则关于运算的幺元是QQ,_。7、在群、半群、独异点中，_满足消去律。得分348、35条边，每个顶点的度数至少为3的图最多有_个顶点。9、设阶图中有条边，每个顶点的度数不是就是，若中有_个度顶点（用关于NGMK1GKM、N、K的表达式表示）。10、若10阶平面图中有5个面，则图中有_条边。G11、一颗带权为1，2，3，4，5，6的最优三元树，其权为_。12、群中（为模6加法运算），则5的阶为_。,Z13、若某个简单图不是欧拉图但具有欧拉通路，则图中奇度数的顶点个数一定为_。14、N个顶点的无向树是平面图，它的无穷面的次数为_。15、求满足不等式的正整数解的个数有_6321X三、计算题（本大题共4个小题，每题5分，共20分）1、画出下列集合关于整除关系的哈斯图，并指出它的极小元、最小元、极大元、最大元。2,158,63,22、已知有向图，E，EVD,4,3213,24,12,，求有向图D的邻接矩阵和可达矩阵。134,33、带有N个顶点的2元完全正则树有多少树叶4、设有A、B、C、D、E、F、G七个人，他们分别会讲的语言如下A英，B汉、英，C英、西班牙、俄，D日、汉，E德、西班牙，F法、日、俄，G法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈四、证明题（本大题共4个小题，每题5分，共20分）15CM351、RPQRP2、设和是集合上的等价关系，且，证明1R2A121R是集合上的对称关系。3、设G为N阶无向简单图，证明若G为自补图（若一个图的补图为本身则称为自补图），则或，其中K为正整数。K414、证明设是一个代数系统，是上的二元运算，,RR,RBAAB则0是