离散结构(2010-1-B)《期末考试试卷》.doc

装订线华南农业大学期末考试试卷（B卷）2010-2011学年第一学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间：120 分钟学号 姓名 年级专业 题号一二三四五六总分得分评阅人得分一、判断题（本大题共10小题，每小题1分，共10分）1、命题公式是一个矛盾式2、任何循环群必定是阿贝尔群，反之亦真。 3、根树中最长路径的端点都是叶子。4、若集合A上的关系R是对称的，则也是对称的。5、数集合上的不等关系（）可确定A的一个划分。6、设集合A、B、C为任意集合，若AB = AC，则B = C。7、函数的复合运算“。”满足结合律。8、若G是欧拉图，则其边数合结点数的奇偶性不能相反。9、图G为（n , m）图，G的生成树必有n个结点。10、使命题公式的真值为F的真值指派的P、Q、R值分别是T、F、F。 1.5CM得分二、选择题（本大题共18小题，每小题2分，共36分）1命题公式是（ ）。A、 矛盾式； B、可满足式； C、重言式； D、等价式。2下列各式中哪个不成立（ ）。 A、 ；B、；C、；D、。3谓词公式中的 x是（ ）。A、自由变元； B、约束变元；C、既是自由变元又是约束变元； D、既不是自由变元又不是约束变元。 4设 A ， 是偏序集，下面结论正确的是（ ）。 A、的极大元且唯一； B、的极大元且不唯一；C、的上界且不唯一； D、的上确界且唯一。5在自然数集N上，下列（ ）运算是可结合的。（对任意） A、 ； B、 ；C、 ； D、。6Q为有理数集N，Q上定义运算*为a*b = a + b ab ,则的幺元为（ ）。 A、a； B、b； C、1； D、0。7给定下列序列，（ ）可以构成无向简单图的结点次数序列。 A、（1，1，2，2，3）； B、（1，1，2，2，2）；C、（0，1，3，3，3）； D、（1，3，4，4，5）。8设G是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。A、点与边； B、边与点； C、点与点； D、边与边。9一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。A、5； B、7； C、9； D、8。10下图描述的偏序集中，子集的上界为 （ ）。A、 ； B、 ； C、 ； D、。11下面集合（ ）关于减法运算是封闭的。A、N ； B、 ； C、 ； D、。12具有如下定义的代数系统，（ ）不构成群。A、，*是模11乘 ； B、，*是模11乘 ；C、（有理数集），*是普通加法 ； D、（有理数集），*是普通乘法。13设，则有向图是（ ）。A、强连通的 ； B、单侧连通的 ； C、弱连通的 ； D、不连通的。14下面那一个图可一笔画出（ ）。15在任何图中必定有偶数个（ ）。A、度数为偶数的结点 ； B、入度为奇数的结点 ；C、度数为奇数的结点 ； D、出度为奇数的结点 。16含有3个命题变元的具有不同真值的命题公式的个数为（ ）。A、 ； B、 ； C、 ； D、 。17下列集合中哪个是最小联结词集（ ）。A、 ； B、 ； C、 ； D、 。18n个结点的无向完全图的边数为（ ）。A、 ； B、 ； C、 ； D、。1.5CM得分三、填空题（本大题共10空，每小题1.5分，共15分）1设图G = 中有7个结点，各结点的次数分别为2，4，4，6，5，5，2，则G中有 条边，根据 。2设个体域为自然数集，命题“不存在最大自然数”符号化为 。3设S为非空有限集，代数系统中幺元为 ，零元为 。4设图G = ，的邻接矩阵，则的入度 = ，的出度= ，从到的长度为2的路有 条。5命题公式的主合取范式为 ，其编码表示为 。1.5CM得分四、计算题（本大题共2小题，第1小题4分，第2小题5分，共9分）1、将公式划为只含有联结词的等价公式。2、有向图D如图4-1所示，试求：(1) 写出有向图D邻接矩阵A；(2) 判断有向图D的连通性。v1v2v3v4图4-11.5CM得分五、应用题（本大题共2小题，每小题6分，共12分）1图给出的赋权图表示五个城市及对应两城镇间公路的长度。试给出一个最优化的设计方案使得各城市间能够有公路连通。2、设集合，X上的关系R如图5-1所示，试求：abcde图5-1（1）写出关系R的关系矩阵；（2）画出关系R的自反闭包r(R)的关系图；（3）画出关系R的对称闭包s(R)的关系图；（4）画出关系R的传递闭包t(R)的关系图。1.5CM得分六、证明题（本大题共3小题，每小题6分，共18分）1试证明若是群，且任意的，对每一个，有，则是的子群。2符号化下列各命