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

《离散结构(2010-1-b)《期末考试试卷》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、装订线华南农业大学期末考试试卷（B卷）2010-2011学年第一学期　考试科目：　离散结构　　考试类型：（闭卷）考试　　　考试时间：　120分钟学号姓名年级专业题号一二三四五六总分得分评阅人得分一、判断题（本大题共10小题，每小题1分，共10分）1、命题公式是一个矛盾式2、任何循环群必定是阿贝尔群，反之亦真。3、根树中最长路径的端点都是叶子。4、若集合A上的关系R是对称的，则也是对称的。5、数集合上的不等关系（≠）可确定A的一个划分。6、设集合A、B、C为任意集合，若A×B=A×C，则B=C。7、函数的复合运算

2、“。”满足结合律。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、；5装订线C、；D、。3．谓词公式中的x是（）。A、自由变元；B、约束变元；C、既是自由变元又是约束变元；D、既不是自由变元又不是约束变元。4．设

3、>是偏序集，，下面结论正确的是（）。A、的极大元且唯一；B、的极大元且不唯一；C、的上界且不唯一；D、的上确界且唯一。5．在自然数集N上，下列（）运算是可结合的。（对任意）A、；B、；C、；D、。6．Q为有理数集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

4、)刻划下列（）关系。A、点与边；B、边与点；C、点与点；D、边与边。9．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（）。A、5；B、7；C、9；D、8。10．下图描述的偏序集中，子集的上界为（）。A、；B、；C、；D、。5装订线11．下面集合（）关于减法运算是封闭的。A、N；B、；C、；D、。12．具有如下定义的代数系统，（）不构成群。A、，*是模11乘；B、，*是模11乘；C、（有理数集），*是普通加法；D、（有理数集），*是普通乘法。13．设，，则有向图是（）。A、强连通的；B、单侧连

5、通的；C、弱连通的；D、不连通的。14．下面那一个图可一笔画出（）。15．在任何图中必定有偶数个（）。A、度数为偶数的结点；B、入度为奇数的结点；C、度数为奇数的结点；D、出度为奇数的结点。16．含有3个命题变元的具有不同真值的命题公式的个数为（）。A、；B、；C、；D、。17．下列集合中哪个是最小联结词集（）。A、；B、；C、；D、。18．n个结点的无向完全图的边数为（）。A、；B、；C、；D、。1.5CM5装订线得分三、填空题（本大题共10空，每小题1.5分，共15分）1．设图G=中有7个结点，各

6、结点的次数分别为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的连通性。v1v2v3v

7、4图4-15装订线1.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．试证明若是群，，且任意的，对每一

8、个，有，则是的子群。2符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。3若有n个人，每个人都恰有三个朋友，则n必为偶数。5