2008-2离散结构(a).doc

离散结构期末考试试卷 2008学年第二学期华南农业大学期末考试试卷（A卷）2008学年第 二 学期 考试科目： 离散结构考试类型：（闭卷） 考试时间：120分钟学号 姓名 年级专业 注意事项：1考试时间120分钟，闭卷考试2试卷共五大题，满分100分3全部答案写在答题纸上，试卷纸上答题无效一、填空（每空2分，共30分）1、的真值= (1) 。2、如果有一台计算机，它有一条加法指令，可计算四个数字的和，现求15个数的和，它至少要执行 (2) 次这个加法指令。3、命题“对于任意给定的正实数，都存在比它大的实数”令：为实数，则命题的逻辑谓词公式为 (3) 。4、若解释I的个体域D仅包含一个元素，则公式 在I下真值为 (4) 。5、若关系R具有自反性，当且仅当在关系矩阵中，主对角上元素 (5) 。6、前缀表达式 + * 2 / 8 4 5 的值是 (6) 。7、树高为5的二元正则树T的顶点数为49，则树叶为 (7) 。8、10个顶点的无向完全图的边数为 (8) 。9、以数1，4，5，8，11，15构造一棵最优二元树，其权值为 (9) 。10、谓词的前束范式为 (10) 。11、完全二部图K r, s中，度数和为 (11) 。12、设G为群，且，则x的阶为 (12) 。*a b cabca b cb b cc c b13、设代数系统，其中A=a，b，c,运算表如下：则单位元是 (13) ， 是否满足幂等律 (14) (填是/否)，是否满足交换律 (15) (填是/否)。二、单选题（请找出最符合题意的答案，每题2分，共30分）1、下列语句是命题的有_。A、明年中秋节的晚上是晴天 B、 C、下午有会吗D、我正在说谎2、设A=1，2，3，则A上的二元关系有_个。 A、 23 B、 32 C、 D、 3、设则下列关系中，具有自反性的是_。A、当且仅当不等于B、当且仅当或为素数C、当且仅当D、当且仅当4、设R和S是P上的关系，P是所有人的集合， 则表示关系 _。A、 B、 空关系 C、 D、。5、命题公式 中成真赋值的个数为_。A、0 B、1 C、2 D、3 6、下列等值公式成立的是_。A、 B、 C、 D、7、以下整数序列，能成为一个简单图的顶点度数序列的是_。A、1，2，2，3，4，5B、2，3，3，4，4，5C、1，1，1，2，3D、1，3，3，4，5，68、设A=，1，1，3，1，2，3则A上包含关系“”的哈斯图为_。9、设，定义上的等价关系 则由 R产 生的上一个划分共有_个分块。A、4 B、5 C、6 D、9 10、设，S上关系R的关系图如下，则R具有_性质。A、自反性、对称性、传递性 B、反自反性、反对称性 C、反自反性、反对称性、传递性 D、自反性 。11、p表示王荣努力学习，q表示取得好成绩，则“除非王荣努力学习，否则她不能取得好成绩”的正确表示_。A、 B、 C、 D、 12、在下列关于图论的命题中，正确的是_。A、哈密顿图一定是欧拉图B、无向完全图都是欧拉图C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出D、哈密顿图是平面图13、下图中既不是欧拉图，也不是哈密尔顿图的是_。14、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有_个4度结点。A、1 B、2 C、3 D、415、设R是实数集合，“”为普通乘法，则代数系统 是_。A、群 B、阿贝尔群 C、半群 D、含幺半群。三、计算题（每题6分，共18分）1、在巡回联赛里，老虎队击败蓝松鸦队，老虎队击败红衣主教队，老虎队击败金莺队，蓝松鸦队击败红衣主教队，蓝松鸦队击败金莺队，红衣主教队击败金莺队。请用有向图（记为G）标示这四个队的比赛结果，以下问题基于所画出的有向图G作答：（1）画出有向图（2）有向图G的连通分支数p为多少？（3）请写出有向图G的邻接矩阵,并求出有向图G中通路长度小于或等于6的条数（不包括回路）（注：画有向图时，赢的队作为有向边的起点，输的队作为有向边的终点）2、画出6阶所有非同构的无向树。3、设集合，A上的关于等价关系R的商集=，试求：（1）写出关系矩阵（2）画出关系图（3）写出R的传递闭包四、证明题（每题6分，共18分）1、若无向图G中只有两个奇数度结点，则这两个结点一定连通。2、设T=是n阶非平凡的无向树，证明：T至少有两片树叶。3、证明：若是自反的、循环的，则一定是传递的。（注：