大三期末离散数学试卷

大三期末离散数学试卷一、选择题

1.在集合论中，下列哪个选项不是等价关系的性质？

A.自反性

B.对称性

C.传递性

D.关联性

2.设集合A={1,2,3}，B={2,4,6}，则集合A与B的笛卡尔积C的元素个数是多少？

A.1

B.3

C.6

D.9

3.在图论中，下列哪个图是连通图？

A.无向图

B.有向图

C.无向图且连通

D.有向图且连通

4.设函数f(x)=2x+1，则下列哪个选项是函数f(x)的反函数？

A.f^(-1)(x)=x/2-1/2

B.f^(-1)(x)=x/2+1/2

C.f^(-1)(x)=2x+1

D.f^(-1)(x)=2x-1

5.在计算机科学中，下列哪个算法是用于求解最大子序列和问题？

A.快速排序算法

B.冒泡排序算法

C.分治算法

D.动态规划算法

6.在逻辑代数中，下列哪个公式是恒等式？

A.A+AB=B

B.A+AB=A

C.A+AB=A+B

D.A+AB=1

7.设集合A={1,2,3}，B={2,3,4}，则集合A与B的交集C的元素个数是多少？

A.1

B.2

C.3

D.4

8.在树形结构中，下列哪个选项是树的定义？

A.每个节点有且仅有一个父节点

B.每个节点可以有多个子节点

C.每个节点有且仅有一个子节点

D.每个节点可以有零个或多个子节点

9.在计算机网络中，下列哪个协议是用于传输文件的？

A.HTTP

B.FTP

C.DNS

D.SMTP

10.在组合数学中，下列哪个公式是组合数公式？

A.C(n,k)=n!/(k!(n-k)!)

B.C(n,k)=k!(n-k)!

C.C(n,k)=n!/(k!(n-k)!)^2

D.C(n,k)=k!/(n-k!)

二、判断题

1.在图论中，一个无向图中的每个顶点度数之和等于边数的两倍。（）

2.在逻辑代数中，德摩根定律表明，一个逻辑表达式与其非表达式的非是等价的。（）

3.在集合论中，空集是任何集合的子集，但不是任何集合的真子集。（）

4.在离散数学中，一个有向图是无环的，当且仅当它是一个有向树。（）

5.在组合数学中，二项式定理可以用来计算一个多项式的展开式中的系数。（）

三、填空题

1.在集合论中，表示集合A包含于集合B的符号是_______。

2.在图论中，如果图中任意两个顶点之间都有路径相连，则称该图为_______。

3.在逻辑代数中，表示逻辑与的运算符是_______。

4.在离散数学中，一个排列是指从n个不同元素中取出r个元素的所有不同排列方式的集合，其排列数公式为_______。

5.在组合数学中，一个事件在概率论中被称为_______事件，如果该事件在任何试验中都有可能发生。

四、简答题

1.简述图论中图的遍历算法的基本概念及其主要类型，并举例说明。

2.解释逻辑代数中的吸收律和分配律，并给出一个应用这两个律的例子。

3.说明离散数学中递归函数的定义，并举例说明如何使用递归函数来计算阶乘。

4.简要介绍组合数学中的二项式系数的概念，并解释为什么在二项式定理中会出现组合数的性质。

5.解释计算机网络中数据包交换和电路交换的基本区别，并讨论它们各自适用的场景。

五、计算题

1.计算集合A={1,2,3,4,5}与集合B={2,4,6,8}的笛卡尔积。

2.设有向图G的顶点集合V={A,B,C,D,E}，边集合E={<A,B>,<B,C>,<C,D>,<D,E>,<E,A>},计算图G的邻接矩阵。

3.给定逻辑表达式F=(A+B')'(C+D)，化简该表达式。

4.设有5个不同的元素，从中任取3个元素进行排列，计算排列的总数。

5.设有一组数据：2,3,5,7,11,13，计算该数据的众数和平均数。

六、案例分析题

1.案例背景：

某公司在进行新产品研发时，需要从5个候选方案中选择最优方案。每个候选方案都有其成本、预期收益和市场风险三个方面的评估指标。公司决定使用决策树方法来辅助决策。

案例分析：

（1）请设计一个决策树模型，包括决策节点、机会节点和结果节点，并标明每个节点的决策变量和概率。

（2）根据给定的评估指标，计算每个候选方案的期望值，并确定最优方案。

2.案例背景：

某城市正在规划新的交通网络，现有三个不同的路线设计方案：方案A、方案B和方案C。每个方案都有其建设成本、预期交通流量和环境影响三个方面的评估指标。市政府希望采用多标准决策方法来选择最佳方案。

案例分析：

（1）请列出评估这三个方案的多标准决策指标体系，并简要说明每个指标的重要性。

（2）根据给定的评估数据，采用层次分析法（AHP）对三个方案进行权重分配，并计算出每个方案的综合得分。

（3）基于综合得分，提出一个推荐方案，并简要说明推荐理由。

七、应用题

1.应用题：

假设有一个无向图，顶点集合为V={A,B,C,D,E}，边集合为E={<A,B>,<B,C>,<C,D>,<D,E>,<E,A>,<A,C>,<B,E>}。请设计一个算法来判断该图是否为连通图，并给出判断结果。

2.应用题：

一个在线教育平台提供了多门课程，每门课程都有一定的学分。学生需要从这些课程中选择一定数量的课程来满足毕业要求。课程集合为C={C1,C2,C3,C4,C5}，学分要求为R=12。请设计一个算法，根据学生的选择偏好（每门课程有一个偏好分数），推荐给学生一个满足学分要求的课程组合。

3.应用题：

在密码学中，散列函数是一种将任意长度的数据映射到固定长度数据的函数。给定一个散列函数h(x)=x^2mod256，请设计一个算法来破解一个散列值为123的明文消息。

4.应用题：

在一个社交网络中，每个用户都有一个好友列表。设计一个算法，能够计算两个用户之间的共同好友数量，并给出一个示例，说明如何使用该算法来计算用户A和用户B的共同好友数量。

本专业课理论基础试卷答案及知识点总结如下：

一、选择题

1.D

2.C

3.C

4.A

5.D

6.B

7.B

8.A

9.B

10.A

二、判断题

1.×

2.√

3.×

4.×

5.√

三、填空题

1.⊆

2.连通图

3.·

4.nPr=n!/(n-r)!

5.随机

四、简答题

1.图的遍历算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。DFS是从一个起始顶点开始，按照一定的顺序访问图中的顶点，直到所有顶点都被访问过。BFS是从一个起始顶点开始，按照层次遍历图中的顶点，先访问起始顶点的邻接顶点，然后依次访问下一层的邻接顶点。

2.吸收律表明，在逻辑代数中，A+AB=A。分配律表明，A(B+C)=AB+AC。

3.递归函数是一种通过递归调用来计算自身值的函数。例如，计算阶乘的递归函数可以定义为：fact(n)=n*fact(n-1)，其中fact(0)=1。

4.二项式系数是从n个不同元素中取出r个元素的所有不同排列方式的数量，表示为C(n,r)=n!/(r!(n-r)!).

5.数据包交换和电路交换的主要区别在于连接建立和带宽分配。数据包交换在发送数据前不需要建立固定的连接，而是将数据分割成多个数据包，独立地传输。电路交换在发送数据前需要建立一条固定的连接，整个传输过程中数据包都通过这条连接传输。

五、计算题

1.集合A与B的笛卡尔积C={(1,2),(1,4),(1,6),(2,2),(2,4),(2,6),(3,2),(3,4),(3,6),(4,2),(4,4),(4,6),(5,2),(5,4),(5,6)}。

2.邻接矩阵如下：

|ABCDE|

|01011|

|10101|

|01010|

|10101|

|11010|

3.化简后的表达式为F=(A+B')'(C+D)=AC'D+A'B'C+A'B'D。

4.排列总数为5P3=5!/(5-3)!=60。

5.众数是数据中出现次数最多的数值，这里众数是13。平均数是所有数值的总和除以数值的个数，平均数=(2+3+5+7+11+13)/6=7。

六、案例分析题

1.（1）决策树模型如下：

-决策节点：选择候选方案

-机会节点：成本、预期收益、市场风险

-结果节点：期望值

-决策变量：成本、预期收益、市场风险

-概率：根据历史数据或专家意见确定

（2）根据评估指标和概率，计算每个候选方案的期望值，选择期望值最大的方案为最优方案。

2.（1）多标准决策指标体系：建设成本、预期交通流量、环境影响

（2）使用层次分析法（AHP）进行权重分配和计算综合得分，根据综合得分最高的方案进行推荐。

（3）推荐方案为综合得分最高的方案，并简要说明推荐理由。

知识点总结：

1.集合论：集合、子集、笛卡尔积、交集、