2008-2离散结构(a)

《2008-2离散结构(a)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《离散结构》期末考试试卷2008学年第二学期华南农业大学期末考试试卷（　A　卷）2008　学年第二学期　考试科目：　离散结构　　考试类型：（闭卷）　　　考试时间：　120　分钟学号姓名年级专业注意事项：1．考试时间120分钟，闭卷考试2．试卷共五大题，满分100分3．全部答案写在答题纸上，试卷纸上答题无效一、填空（每空2分，共30分）1、的真值=(1)。2、如果有一台计算机，它有一条加法指令，可计算四个数字的和，现求15个数的和，它至少要执行(2)次这个加法指令。3、命题“对于任意给定的正实数，都存在比它大的实数”令：为实数，则命题的逻辑谓词公式为(3)。

2、4、若解释I的个体域D仅包含一个元素，则公式在I下真值为(4)。5、若关系R具有自反性，当且仅当在关系矩阵中，主对角上元素(5)。6、前缀表达式+*2/845的值是(6)。7、树高为5的二元正则树T的顶点数为49，则树叶为(7)。8、10个顶点的无向完全图的边数为(8)。9、以数1，4，5，8，11，15构造一棵最优二元树，其权值为(9)。10、谓词的前束范式为(10)。11、完全二部图Kr,s中，度数和为(11)。12、设G为群，且，则x的阶为(12)。*abcabcabcbbcccb13、设代数系统，其中A={a，b，c},运算表如下：则单位

3、元是(13)，是否满足幂等律(14)(填是/否)，是否满足交换律(15)(填是/否)。-4-《离散结构》期末考试试卷2008学年第二学期二、单选题（请找出最符合题意的答案，每题2分，共30分）1、下列语句是命题的有_______。A、明年中秋节的晚上是晴天B、C、下午有会吗D、我正在说谎2、设A={1，2，3}，则A上的二元关系有_______个。A、23B、32C、D、3、设则下列关系中，具有自反性的是_______。A、当且仅当不等于B、当且仅当或为素数C、当且仅当D、当且仅当4、设R和S是P上的关系，P是所有人的集合，，，则表示关系_______。A

4、、B、空关系C、D、。5、命题公式中成真赋值的个数为_______。A、0B、1C、2D、36、下列等值公式成立的是_______。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上包含关系“”的哈斯图为_______。-4-《离散结构》期末考试试卷2008学年第二学期9、设，定义上的等价关系则由R产生的上一个划分共有_______个分块。A、4B、5C、6D、910、设，

5、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

6、度结点则该树有_______个4度结点。A、1B、2C、3D、4-4-《离散结构》期末考试试卷2008学年第二学期15、设R是实数集合，“”为普通乘法，则代数系统是_______。A、群B、阿贝尔群C、半群D、含幺半群。三、计算题（每题6分，共18分）1、在巡回联赛里，老虎队击败蓝松鸦队，老虎队击败红衣主教队，老虎队击败金莺队，蓝松鸦队击败红衣主教队，蓝松鸦队击败金莺队，红衣主教队击败金莺队。请用有向图（记为G）标示这四个队的比赛结果，以下问题基于所画出的有向图G作答：（1）画出有向图（2）有向图G的连通分支数p为多少？（3）请写出有向图G的邻接

7、矩阵,并求出有向图G中通路长度小于或等于6的条数（不包括回路）（注：画有向图时，赢的队作为有向边的起点，输的队作为有向边的终点）2、画出6阶所有非同构的无向树。3、设集合，A上的关于等价关系R的商集=，试求：（1）写出关系矩阵（2）画出关系图（3）写出R的传递闭包四、证明题（每题6分，共18分）1、若无向图G中只有两个奇数度结点，则这两个结点一定连通。2、设T=是n阶非平凡的无向树，证明：T至少有两片树叶。3、证明：若是自反的、循环的，则一定是传递的。（注：如果对若，则称关系是循环的）五、应用题（共4分）假定有重量相同的七枚硬币和重量较轻的一枚伪

8、币。为了用一架天平秤确定这八枚硬币中哪个是伪币，至少需要多少次称重