离散数学题库简答题

编号

题目

答案

题型

分值

大纲

难度

1 1

设集合A={a，b，c，d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。

答:

，

t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > }

简答题

8

4.3

3

2

如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。　　

答: 用Kruskal算法求产生的最优树。算法略。结果如图：

树权C(T)=23+1+4+9+3+17=57即为总造价。

简答题

8

7.2

3

3

设6,+6>是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求出6,+6>的所有子群。

答: 子群有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6>

简答题

8

8.3

3

4

权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。

答:

简答题

8

7.2

3

5

集合X={<1,2>, <3,4>, <5,6>,

… }，R={<1,y1>,2,y2>>|x1+y2 = x2+y1} 。

1） 说明R是X上的等价关系。 （6分）

2） 求出X关于R的商集。（2分）

答: 1）、

1、 自反性：

2、 对称性：

3、 传递性：

即

由（1）（2）（3）知：R是X上的先等价关系。

2）、X/R=

简答题

8

4.4

3

6

设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >}

要求 1）、写出R的关系矩阵和关系图。（4分） 2）、用矩阵运算求出R的传递闭包。（4分）

答:

1、； 关系图

2、

t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > }。

简答题

8

4.1;4.3

4

7

利用主析取范式，判断公式的类型。

答:

它无成真赋值，所以为矛盾式。

简答题

8

2.3

3

8

在二叉树中:1)求带权为2，3，5，7，8的最优二叉树T。（4分）2)求T对应的二元前缀码。（4分）

答: （1）由Huffman方法,得最佳二叉树为：

（2）最佳前缀码为：000，001，01，10，11

简答题

8

7.2

3

9

下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。

答: 图中奇数点为E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF复制道路EG、GF，得图G‘，则G‘是欧拉图。

由D开始找一条欧拉回路：DEGFGEBACBDCFD。

道路长度为：

35+8+20+20+8+40+30+50+19+6+12+10+23=281。

简答题

8

7.2

5

10

设S={1 , 2 , 3 , 4, 6 , 8 , 12 , 24}，“”为S上整除关系，问：（1）偏序集的Hass图如何？（2）偏序集的极小元、最小元、极大元、最大元是什么?

答: (1)≤={<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4>,<2,6>,<2,8>，<2,12>,<2,24>,<3,6>,<3,12>,<3,24>,<4,8>,<4,12>,<4,24>,<6,12>,<6,24>,<8,24>,<12,24>}

covS={<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,8>,<4,12>,<6,12> ,<8,24>,<12,24>}

Hass图为

（2）极小元、最小元是1，极大元、最大元是 24。

简答题

8

4.4

4

11

设解释R如下：DR是实数集，DR中特定元素a=0，DR中特定函数，特定谓词，问公式的涵义如何？真值如何？

答: 公式A涵义为：对任意的实数x,y,z，如果x则 (x-z) < (y-z)

A的真值为： 真（T）。

简答题

8

3.2

3

12

给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。 求复合命题：的真值。

答: P，Q是真命题，R是假命题。

简答题

8

2.2

3

13

给定解释I：D={2，3}，L（x,y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式的真值。

答:

简答题

8

3.1;3.2

3

14

将化为与其等价的前束范式。

答:

简答题

8

3.2

3

15

简述关系的性质有哪些？

自反性，对称性，传递性，反自反性，反对称性

简答题

8

4.3

1

16

假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year的编码信息。

答:解：传输它们的最佳前缀码如上图所示，happy new year的编码信息为：

10 011 0101 0101 001 110 111 0100 001 111 011 000

附：最优二叉树求解过程如下：

简答题

8

7.2

3

17

用washall方法求图的可达矩阵，并判断图的连通性。

答:

1：A[2，1]=1，； 2： A[4，2]=1，

3： A[1，3]=A[2，3]=A[4，3]=1，

4： A[k，4]=1，k=1，2，3，4，

p中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。

简答题

8

6.3

3

18

设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？

答:

用a,b,c,d,e,f,g 7个结点表示7个人，若两人能交谈可用一条无向边连结，所得无向图为

此图中的Hamilton回路即是圆桌安排座位的顺序。

Hamilton回路为a b d f g e c a。

简答题

8

6.4

3

19

用 Huffman算法求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。若传递a ，b， c， d ，e， f 的频率分别为2%， 3% ，5 %， 7% ，8% ，9%求传输它的最佳前缀码。（

答:

（1） 用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e

传输它们的最优前缀码为{0000，0001，001，01，10，11} 。

简答题

8

7.2

3

20

构造一个结点v与边数e奇偶性相反的欧拉图。

答:

简答题

8

6.4

5

21

设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A的一个分划，求由S导出的等价关系。

答: R={< 1 , 1 > , < 2 , 2> , < 2, 3 > , < 3 , 2 > , < 3 , 3 > < 4 , 4 > }

简答题

8

4.4

3

22

设，偏序集的Hass图为

求 A中最小元与最大元； 的上界和上确界，下界和下确界。

答: A中最大元为，最小元不存在；

上界，上确界；下界无，下确界无。

简答题

8

4.4

3

23

用Warshall算法，对集合A={1，2，3，4，5}上二元关系R={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}求t（R）。

答:

1时， [1,1]=1, A =

2时，M[1,2]=M[4,2]=1

A=

3时，A的第三列全为0，故A不变

4时，M[1,4]=M[2,4]=M[4,4]=1

A= 5时，M[3,5]=1 ，这时

A=

所以t (R)={<1,1>, <1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>} 。

简答题

8

4.1;4.3

4

24

将谓词公式

化为前束析取范式与前束合取范式。

答:

简答题

8

2.1;3.1;3.2

3

25

１)、画一个有一条欧拉回路和一条汉密尔顿回路的图。

２)、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。

３)、画一个有一条欧拉回路，但有一条汉密尔顿回路的图。

答:

简答题

8

6.4

3

26

求的主合取范式。

答:

简答题

8

2.3

3

27

在下面关系中:

判定关系的性质。

答: R自反

任意实数x，x-x+2>0 ， x-x-2<0 , 所以直线y=x上的点在区域内，即 , 故R自反；

R对称

若有 得 即

所以 R对称；

因R自反且结点集非空，故R非反自反；

因R对称且结点集非空，并非全是孤立点，故R不是反对称；

由 得 所以而

所以R4不是传递的。

简答题

8

4.3

4

28

求图的邻接矩阵和可达矩阵。

答:

， ，

，。

所以可达矩阵

简答题

8

6.3

3

29

已知某有向图的邻接矩阵如下：

试求：到的长度为4的有向路径的条数。

答:

， ， ，

，由到长度为4的有向路径的条数为3条。

简答题

8

6.3

3

30

已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点）。

答: 设该树有t 片树叶，总结点数为

总边数为

所以 ， 29+t=2·(8+t) 即 t=13 。 该树有13片树叶。

简答题

8

7.1;7.2

3

31

设和是A上的任意二元关系，如果和是自反的，是否也是自反的，为什么？如果和是对称的，是对称的吗？

答: 若是自反的，则也是自反的。因为

自反，，从而，即也是自反的。

若是对称的，但不一定是对称的。

如：A = {a , b , c}，，，则是对称的，但不是对称的。

简答题

8

4.3

4

32

如图给出的赋权图表示六个城市及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。

答: 要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得：

其最小生成树为：

其树权即最小造价为：1+2+3+5+7=18。

简答题

8

7.1;7.2

3

33

设S = R - {-1}（R为实数集），。

说明是否构成群；

答: 1），即运算*是封闭的。

2）

而

，即*可结合。

3）设S关于*有幺元e，则。

而。

4）设有逆元。则，

即，，即 S中任意元都有逆元，综上得出，构成群。

简答题

8

8.3

5

34

将公式

划为只含有联结词的等价公式。

答: 原式

。

简答题

8

2.1;2.2

3

35

设和都是群的子群，问和是否是的子群并说明理由。

答:是的子群，不一定是的子群。

都是的子群，

的子群。如：G = {1，5，7，11}，：模12乘，则为群。且H = {1，5}，K = {1，7}，皆为的子群，但， 不是的子群。因为，即运算不封闭。

简答题

8

8.3

5

36

设，，从A到B的关系

，试给出R的关系图和关系矩阵，并说明此关系是否为函数？为什么？

答:则R的关系图为：

R的关系矩阵为

关系R不是A到B的函数，因为

元素2，4的象不唯一（或元素9无象）。

简答题

8

5.2;4.2

4

37

设是半群，是左零元，对任是否是左零元？为什么？

答:仍是左零元。因为，由于是左零元，所以，，又

为半群，所以*可结合。

所以，，所以，仍是左零元。

简答题

8

8.1

3

38

某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）

答: 可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图

，20人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅一次得回路。由题已知， ，，由判定定理，G中存在一条汉密尔顿回路。即所谈情况可能。

简答题

8

6.4

3

39

通过主合取范式，求出使公式的值为F的真值指派。

答:

∴使公式的值为F的真值指派为：

； ； 。

简答题

8

2.2;2.3

3

40

设，A上的关系，

求出。

答:，

，

，

，

。

简答题

8

4.1;4.3

3

41

已知，为模7乘法。试说明是否构成群？是否为循环群？若是，生成元是什么？

答:既构成群，又构成循环群，其生成元为3，5。因为：的运算表为：

1）由运算表知，封闭；

2）可结合（可自证明）

3）1为幺元；

4），，，，，，

综上所述，构成群。

由，，，，，。所以，3为其生成元，3的逆元5也为其生成元。

故为循环群。

简答题

8

8.1;8.3

5

42

用等值演算法求下面公式的主析取范式，并求其成真赋值。

答: 原式

∴ 使其成真赋值为：

， ， ， ， ，

简答题

8

2.1;2.3

3

43

集合上的关系，写出关系矩阵，画出关系图并讨论R的性质。

答:

R的关系图为

R是自反、对称的。

简答题

8

4.1;4.3

3

44

一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。（1）T中有几个结点；（2）画出具有上述度数的所有非同构的无向图。

答: （1）设该树树叶数为t，则树T的结点数为，又边数 = 结点数 － 1，

，∴

即，∵，∴ T中7个结点。

（2）具有3个两度结点，一个3度结点，3片树叶的树（非同构的）共有以下三种：

简答题

8

7.1;7.2

3

45

设A={1,2,…,10}。下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？

（1）B={{1,3,6},{2,8,10},

{4,5,7}};

（2）C={{1,5,7},{2,4,8,9},

{3,5,6,10}};

（3）D={{1,2,7},{3,5,10},

{4,6,8},{9}}

答: （1）和（2）都不是A的划分。

（3）是A的划分。其诱导的等价关系是

I{<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,10>,

<10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>}。

简答题

8

4.4

3

46

设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路

的总数和回路总数。

答: M=

M2=

G中长度为2的路总数为18，长度为2的回路总数为6。

简答题

8

6.3

4

47

设A={1,2,3,4,5},A上偏序关系

R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA;

(1)作出偏序关系R的哈斯图

(2)令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。

答: 偏序关系R的哈斯图为

(2)B的最大元：无，最小元：无； 极大元：2，5，极小元：1，3

下界：4， 下确界4； 上界：无，上确界：无

(2)B的最大元：无，最小元：无； 极大元：2，5，极小元：1，3

下界：4， 下确界4； 上界：无，上确界：无

简答题

8

4.4

4

48

求┐(P→Q) (P→┐Q)的主合取范式并给出所有使命题为真的赋值。

答: 原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))

((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))

(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))

(┐(P∧┐Q)∨(P∧┐Q))

(P∧Q)∨(P∧┐Q)

P∧(Q∨┐Q)

P∨(Q∧┐Q)

(P∨Q)∧(P∨┐Q)

命题为真的赋值是P=1,Q=0和P=1,Q=1

简答题

8

2.1;2.2;2.3

3

49

求公式┐((x)F(x,y)→(y)G(x,y))∨(x)H(x)的前束范式。

答: 原式┐(x1F(x1,y)→y1G(x,y1))∨x2H(x2) (换名)

┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2)

x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2)

x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2)

简答题

8

3.2

3

50

设A={a,b,c }，P（A）是A的幂集，是集合对称差运算。已知<P(A), >是群。在群 >中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}x={b}。

答:e=Ф; 任一元素x的逆元x-1;

x={a}-1{b}={a}{b}={a,b}。

简答题

8

8.1;8.3

3