02324离散数学2021年10月答案

02324离散数学200604及答案

2006年4月高等教育自学考试全国统一命题考试

离散数学试题

课程代码：2324

一、单项选择题（本大题共15小题，每小题1分，共15分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．下列命题公式为重言式的是（）

A．p→(p∨q) B．(p∨┐p)→q

C．q∧┐q D．p→┐q

2．下列语句中不是

．．命题的只有（）

A．这个语句是假的。B．1+1=1.0

C．飞碟来自地球外的星球。D．凡石头都可练成金。

3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是

（）A．┐p∧q B．┐p→q

C．┐p→┐q D．p→┐q

4．下列等价式正确的是（）

A．┐)

x?

A

?

?┐A

(

)

(x

B．A

(?

?

)(

?

)

?

?

x)

A

x

y

y

)(

(

C．┐)

?

?┐A

x?

A

)

(x

(

D．)

B

x

x

x

x

A

x

A

?

∧

?

∨

x?

?

))

)

(

(

)

(

)

(

)(

(x

(

)

(

B

5．在公式)

Q

y

z

P

y

x

P

∧

?

→

x?

y

?中变元y是（）

(z

(

))

)

(

y

(

,

)(

)

)(

(

,

A．自由变元

B．约束变元

C．既是自由变元，又是约束变元

D．既不是自由变元，又不是约束变元

6．设A={1，2，3}，A上二元关系S={<1

02324离散数学200604及答案

2006年4月高等教育自学考试全国统一命题考试

离散数学试题

课程代码：2324

一、单项选择题（本大题共15小题，每小题1分，共15分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．下列命题公式为重言式的是（）

A．p→(p∨q) B．(p∨┐p)→q

C．q∧┐q D．p→┐q

2．下列语句中不是

．．命题的只有（）

A．这个语句是假的。B．1+1=1.0

C．飞碟来自地球外的星球。D．凡石头都可练成金。

3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是

（）A．┐p∧q B．┐p→q

C．┐p→┐q D．p→┐q

4．下列等价式正确的是（）

A．┐)

x?

A

?

?┐A

(

)

(x

B．A

(?

?

)(

?

)

?

?

x)

A

x

y

y

)(

(

C．┐)

?

?┐A

x?

A

)

(x

(

D．)

B

x

x

x

x

A

x

A

?

∧

?

∨

x?

?

))

)

(

(

)

(

)

(

)(

(x

(

)

(

B

5．在公式)

Q

y

z

P

y

x

P

∧

?

→

x?

y

?中变元y是（）

(z

(

))

)

(

y

(

,

)(

)

)(

(

,

A．自由变元

B．约束变元

C．既是自由变元，又是约束变元

D．既不是自由变元，又不是约束变元

6．设A={1，2，3}，A上二元关系S={<1

1/6 第10章

第十章 树

10.1画出所有不同构的，有5个顶点的树。

解

图10.1 习题1图

10.2 证明：一棵树的顶点度数之和为2(|V| ?1)，其中V是顶点集。

证明

一棵树的所有顶点的度数之和

?deg(v)?2|E|，因为树的|E|?|V|?1，所以

ii?1n?deg(v)?2|E|?2(|V|?1)。

ii?1n故一棵树的顶点度数之和为2(|V| ?1)。

10.3 一棵树有3个2度顶点，5个3度顶点，8个4度顶点，问有几个一度顶点？

解

设树T有n个一度顶点，则

?deg(v)=3?2?5?3?8?4?1?n?2(3?5?8?n?1)，

从而有n?23。

即该棵树有23个一度顶点。

10.4 一棵树n2个顶点的度数为2，n3个顶点的度数为3，…，nk个顶点度数为k，问有几个顶点度数为1个顶点。

解

设有n1个度数为

1

的顶点。顶点数v?n1?n2?..?.nk，边数

e?v?1?(n1?n2?..?.nk)?1。由握手定理知：

2e?2(v?1)??deg(vi)，故2(n1?n2?...?nk)?2?n1?1?n2?2?...?nk?k，

i?1n因此，n1?n3?2n4?...?(k?2)nk?2

10.5 证明：一棵树若有

离散数学（本）2016年10月份试题

一、单项选择题（每小题3分，本题共15分）

1．若集合A＝{1,2,3,4}，则下列表述不正确的是 ( )． A．1?A B．{1,2,3}?A

C．{1,2,3}?A D．? ?A

2．设A＝｛1, 2, 3｝，B={1, 2, 3, 4}，A到B的关系R＝｛〈x, y〉|x=y｝，则R为 ( ) ． A. {<1, 2>, <2, 3>} B. {<1, 1>, <1, 2>, <1, 3>, <1, 4>, <1, 5>} C. {<1, 1>, <2, 1>} D. {<1, 1>, <2, 2>, <3, 3 >} 3．无向图G的边数是10，则图G的结点度数之和为（ ）． A. 10 B. 20 C. 30 D. 5

4．设连通平面图G有v个结点，e条边，r个面，则（ ）． A．r + v - e =2 B．v + e - r=4 C．v + e – r = – 4 D．v + e - r=2

5．设个体

离散数学（本）2016年10月份试题

一、单项选择题（每小题3分，本题共15分）

1．若集合A＝{1,2,3,4}，则下列表述不正确的是 ( )． A．1?A B．{1,2,3}?A

C．{1,2,3}?A D．? ?A

2．设A＝｛1, 2, 3｝，B={1, 2, 3, 4}，A到B的关系R＝｛〈x, y〉|x=y｝，则R为 ( ) ． A. {<1, 2>, <2, 3>} B. {<1, 1>, <1, 2>, <1, 3>, <1, 4>, <1, 5>} C. {<1, 1>, <2, 1>} D. {<1, 1>, <2, 2>, <3, 3 >} 3．无向图G的边数是10，则图G的结点度数之和为（ ）． A. 10 B. 20 C. 30 D. 5

4．设连通平面图G有v个结点，e条边，r个面，则（ ）． A．r + v - e =2 B．v + e - r=4 C．v + e – r = – 4 D．v + e - r=2

5．设个体

离散数学

离散数学第10 章 网 络 模 型

H LP-DM

离散数学

国外计算机科学教材序列

离散数学(第6版)Richard Johnsonbaugh 石纯一 等译电子工业出版社

H LP-DM

离散数学

主题网络模型 通过一个网络的最大流量问题 系统优化，资源分配和人员分配

H LP-DM

离散数学

10.1 网络模型b 3 码头a 码头 5 d 2 e b 2 4 2 c 4 炼油厂z 炼油厂

求出从码头到炼油厂的最大流量H LP-DM

离散数学

定义 10.1.1一个传输网络是一个满足下列条件的简 单加权有向图 一个源 一个汇 有向边(i,j)的权 Cij 是非负数，称为容 量

H LP-DM

离散数学

例10.1.2 网络模型b 3 源a 5 d 2 e b 2 4 2 c 4 汇z

一个网络的流量是对每边赋流量值，该值不超过 一个网络的流量是对每边赋流量值， 所在边的容量。 所在边的容量。H LP-DM

离散数学

定义10.1.3 定义G是一个传输网络， Cij是 (i,j)的容量 G的一个流量F 赋予 (i,j) 值Fij 满足 Fij ≤Cij

∑ Fij =∑ Fj Ii i

流入=流出 流量守恒

H LP-DM

离散数学

10.1.4b3,2

2,2 b 2,1

c 4,3

第10章 图

第10章习题答案

1.解 (1)设G有m条边，由握手定理得2m＝?d(v)＝2＋2＋3＋3＋4＝14，所以G的边数7条。

v?V(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得?d(v)＝2m＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有，

v?V其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G中至多有9个结点。

2.证明 设v1、v2、?、vn表示任给的n个人，以v1、v2、?、vn为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G。由握手定理知

?d(v)＝3n必为偶数，从而n必为偶数。

kk?1n3. 解 由于非负整数列d＝(d1，d2，…，dn)是可图化的当且仅当?di≡0(mod 2)，所以(1)、(2)、

i?1n(3)、(5)能构成无向图的度数列。

(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。

(5)是不可简单图化的。若不然，存在无向图G以为1，3，3，3度数列，不妨设G中结点为v1、v2、

v3、v4，且d(v1)＝1，d(v2)＝d(v3)＝d

离散数学

离散数学第10 章 网 络 模 型

H LP-DM

离散数学

国外计算机科学教材序列

离散数学(第6版)Richard Johnsonbaugh 石纯一 等译电子工业出版社

H LP-DM

离散数学

主题网络模型 通过一个网络的最大流量问题 系统优化，资源分配和人员分配

H LP-DM

离散数学

10.1 网络模型b 3 码头a 码头 5 d 2 e b 2 4 2 c 4 炼油厂z 炼油厂

求出从码头到炼油厂的最大流量H LP-DM

离散数学

定义 10.1.1一个传输网络是一个满足下列条件的简 单加权有向图 一个源 一个汇 有向边(i,j)的权 Cij 是非负数，称为容 量

H LP-DM

离散数学

例10.1.2 网络模型b 3 源a 5 d 2 e b 2 4 2 c 4 汇z

一个网络的流量是对每边赋流量值，该值不超过 一个网络的流量是对每边赋流量值， 所在边的容量。 所在边的容量。H LP-DM

离散数学

定义10.1.3 定义G是一个传输网络， Cij是 (i,j)的容量 G的一个流量F 赋予 (i,j) 值Fij 满足 Fij ≤Cij

∑ Fij =∑ Fj Ii i

流入=流出 流量守恒

H LP-DM

离散数学

10.1.4b3,2

2,2 b 2,1

c 4,3

全国2008年7月自考试题离散数学（附答案）

课程代码：02324

一、单项选择题（本大题共15小题，每小题1分，共15分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（A．? P∧Q B．P∧? Q C．P→? Q D．P∨? Q

2．下面联结词运算不可交换的是（ ） A．∧ B．→ C．∨ D．

3．下列命题公式不是重言式的是（ ） A．Q→（P∨Q）

B．（P∧Q）→P

C．?（P∧? Q）∧（? P∨Q） D．（P→Q）（? P∨Q） 4．下列等价式不正确的是（ ） A．?x(P(x)?Q(x))??xP(x)??xQ(x) B．?x(P(x)?Q(x))??xP(x)??xQ(x) C．?x(P(x)?Q(x))??xP(x)??xQ(x) D．?x(P(x)?Q)??xP(x)?Q

5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（A．?x(A(x)?B(x)) B．??x(A(x)?? B（x）） C．??x(A(x)?B(x)) D．??x(A(x)

2006年下半年《离散数学》（闭卷）70学时

离散数学（A卷）

闭卷、70学时

一、 填空选择题 (每空1分，共26分)

1、给定命题公式如下：p?(q??r)。该公式的成真赋值为A,成假赋值为B,公式的类型为C。

供选择的答案

A：①无；②全体赋值；

③010，100，101，111；④010，100，101，110，111。

B：①无；②全体赋值；③000，001，011；④000，010，110。 C：①重言式；②矛盾式；③可满足式。

（?x)(P(y)?Q(x,y))?(?y)R(x,y)中，?x的辖域是 P(z)→Q(x,z) ， 2、在公式

?y的辖域是 R(x,z) 。

3、设Z+={x∣x∈Z∧X>0},π1, π2,π3是Z+的3个划分。

π1={{x}∣x∈Z+},π2={S1,S2},S1为素数集,S2=Z+-S1.π3＝{Z+}, (1)3个划分块中最多的是A,最少的是B. +++

(2)划分π1对应的是Z上的C,π2对应的是Z上的D,π3对应的是Z上的E. 供选择的答案

A:( ①),B:( ③ ) ①π1, ②π2,③π3. C:( ⑧)