离散数学期末试卷及答案.docxVIP

离散数学期末试卷及答案

1.选择题

1.1下列哪个不是无向图G的表示方法？

A.邻接矩阵

B.关联矩阵

C.有向图

D.简单图

1.2设G=(V,E)是一个无向图，其中V={a,b,c,d}，E={{a,b},{a,c},{b,c},{b,d}}，则图G的度数序列是？

A.{1,2,2,2}

B.{1,2,2,3}

C.{1,2,2,4}

D.{2,2,2,2}

1.3对于集合A={1,2,3,4,5}，则A的幂集的元素个数为？

A.16

B.32

C.64

D.128

2.简答题

2.1什么是图的连通性？无向图和有向图的连通性有何区别？

2.2什么是图的路径？路径的长度是如何定义的？

2.3什么是集合的笛卡尔积？如何用笛卡尔积来定义关系？

3.计算题

3.1有向图G的邻接矩阵为：

011

100

110

请计算图G的度数序列。

3.2设A={1,2,3}，B={a,b}，则A和B的笛卡尔积是？

3.3用组合数学的方法计算排列A(5,3)的值。

4.证明题

4.1证明集合的幂集的元素个数为2^n，其中n为集合的基数。

4.2证明图的关系矩阵是对称矩阵当且仅当图是无向图。

4.3证明排列A(n,1)=n。

答案：

1.选择题

1.1选C。有向图是另一种图的表示方法，不是无向图的表示方法。

1.2选A。图G的度数序列是{1,2,2,2}。

1.3选D。集合A的幂集的元素个数为2^5=32。

2.简答题

2.1图的连通性是指图中任意两个顶点之间存在路径。无向图的连通性指的是任意两个顶点之间有无向路径，有向图的连通性指的是任意两个顶点之间有有向路径。

2.2图的路径是图中顶点的一个序列，使得任意相邻的两个顶点间都有边相连。路径的长度是指路径中的边的数量。

2.3集合的笛卡尔积是指两个集合中的元素的所有可能的有序对的集合。关系可以用笛卡尔积来定义，即关系是集合的笛卡尔积的子集。

3.计算题

3.1图G的度数序列为{2,1,2}。

3.2A和B的笛卡尔积是{(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}。

3.3排列A(5,3)=60。

4.证明题

4.1证明略。

4.2证明略。

4.3证明略。