天津大学研究生考试离散数学试卷及答案解析
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
天津理工大学 2007 年硕士研究生入学复试试题 考试科目：离散数学 共 ３ 页 第 １ 页 一、填空题（每空1分，共25分） 1．无向图G具有一条欧拉回路，当且仅当G是 ，并且所有结点的度数都是 。 ２．设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统<Z,*>的幺元是 ，零元是 。 3．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是 ，其关系矩阵是 。 4．一个格称为布尔代数，如果它是______格和______格.设〈B,∧,∨,′，0，1〉是布尔代数，对任意的a∈B,有a∨a′=____, a∧a′=______。 5．谓词公式(x)( y)（P(x,y)∨R(y)）→Q(y)，则其约束变元是________，自由变元是________。 6．设G是n个结点m条边的连通平面图，则当n≥3时必有 成立。 7．设命题公式A的真值表为 P 0 0 0 0 1 1 1 1 Q 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 A 0 0 1 0 1 1 0 0 则命题公式A的主析取范式（编码形式）为 。 8．一棵有6个叶结点的完全二叉树，有____个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 9．在一棵根树中，有且只有一个结点的入度为_____，其余所有结点的入度均为_____。 10．设图G1=V1,E1,G2V2,E2,且E2E1，如果 ，则称G2是G1的子图，如果 ，则称G2是G1的生成子图。 01111011．设图G的邻接矩阵为M=，则G的可达性矩阵为____ __. 10012．在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，则集合D={2,3,4,6}的极大元是 ，极小元是 ，上确界是 ，下确界是 。 二、单项选择题（每小题2分，共20分） 1．设N为自然数集(含0)，函数F：N→N×N,F(n)=是( )。 (1)．满射，不是入射； (2)．入射，不是满射； (3)．双射； (4)．不是入射，不是满射． ２．设R1和R2是集合Ａ上的任意两个关系，则下列命题为真的是（ ）． (1)．若R1和R2是自反的，则R1R2也是自反的； (2)．若R1和R2是非自反的，则R1R2也是非自反的； 1 天津理工大学 2007 年硕士研究生入学复试试题 考试科目：离散数学 共 ３ 页 第 ２ 页 (3)．若R1和R2是对称的，则R1R2也是对称的； (4)．若R1和R2是传递的，则R1R2也是传递的． ３．下面哪个偏序集构成有界格（ ）． (1)．N,； (2)．2,3,4,6,12,／，其中／为整除关系； (3)．Z,； (4)．，(A)为Ａ的幂集． (A),；其中Ａ＝｛ａ，ｂ，ｃ｝４．设个体域是正整数集，则下列公式中真值为真的公式是( )． (1)．(x)(y)(x·y=0) (2)． (x)(y)(x·y=1) (3)．( x)(y)(x·y=2) (4)．(x)(y)(z)(x-y=z)． ５．设P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）． (1)．P→┐Q； (2)．P∨┐Q； (3)．P∧Q； (4)．P∧┐Q． ６．设<A,*,>是环，则下列正确的是（ ）． (1)．<A,>是交换群； (2)．<A,*>是加法群； (3)．对*是可分配的； (4)．*对是可分配的 ７．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）． (1)．2个面； (2)．4个面； (3)．3个面； (4)．5个面． ８．下面哪个哈斯图构成分配格（ ）． ９．设完全二叉树Ｔ有ｔ片叶子。ｅ条边，则有（ ）． (1)．ｅ>2(t-1)； (2)．e<2(t-1)； (3)．e=2(t-1)； (4)．e=2(t+1)． 10．下列各图是平面图的是( )． 三、简答题（每小题6分，共30分） 1．设A={a,b,c }，P（A）是A的幂集，是集合对称差运算。已知<P(A),>是群。在群>中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}x={b}。 ２．设有6个城市V1，V2，…，V6，它们之间有输油管连通，其布置如下图,Si(数字)中Si为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏， 在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?
2
本文来源：https://www.wddqw.com/doc/9f783c91541810a6f524ccbff121dd36a32dc4a3.html