2023年7月19日发(作者：)

一、单项选择题

1．设A = {a, {a }}，P(A)表示集合A的幂集，下列哪一个是错的？（ ）

A．{a}P(A) B．{a}P(A) C．{{a}}P(A) D．{{a}}P(A)

2．设A={1 , 2 , 3 }上的二元关系R = {<1 , 1>, <1 , 2> , <1 , 3> , <3 ,

3> } , 则R具备性质（ ）

A．反对称的，传递的 B．反对称的

C．反对称的, 自反的 D．传递的

3．集合A = {x, y, z }, B = {1, 2, 3}，下列A到B的二元关系中，哪一个能构成函数？（ ）

A．{, , , } B．{, }

C．{, , } D．{, , }

4．下列命题中（ ）是正确的。

A．欧拉图的子图一定是欧拉图。

B．哈密顿图的子图一定是哈密顿图 。

C．平面图的子图一定是平面图 。

D．树的子图一定是树。

5．设有向图D的邻接矩阵为

10A00110010，则D中长度为3的通路总数有( ) 条。

001010 A．9 B．10 C．11 D．12

二、填空题

1．公式(PQ)(QR)的主析取范式为 。

2．某班共有学生60人，其中有25人订杂志甲，26人订杂志乙，26人订杂志丙，11人订杂志甲和乙，9人订杂志甲和丙，8人订杂志乙和丙，还有8人未订任何杂志，则三种杂志都订的学生有 人。

3．设A = {2，4，5，10，12，20}，R为A上的整除关系，则A的子集B = {4，10，12}的极大元为 ，极小元为 ，上界为 ，下界为 。

4．设f:NNN,f(n)n,n1 ，则函数f是 （单射，满射还是双射）。

5．设集合A={ a , b , c , d , e}上的的划分S ={{a，d}，{{b}，{c，e}}，则由划分S所确定的A上的等价关系R = 。

6．用kruskal算法求得下图G的一棵最小生成树为 。

v1

2

v5

12

11

v6

9

8

v2

10

图G

4

1

v4

3

v8

5

6

v7

7

v3

7．设连通平面图G有4个面，9条边，则G有 个结点。

三、解答题 ( 4×8 = 32分 )

1．将下列语句翻译成命题逻辑公式或谓词逻辑公式。

(1)（4分）只有天下大雨，小明才乘公共汽车上学。

(2)（4分）不是所有整数都是奇数。

2．设A = {1, 2, 3 }上的二元关系R = {<1, 1>, <1, 3>, <2, 1>}，求R的关系矩阵，关系图。

3．设f是A到 A 的满射，且fff，证明

fIA 。这里

IA 表示A 上的恒等映射。

4．画图:(1)一个既没有欧拉回路，又没有哈密尔顿回路的图；

（2）一个具有欧拉回路和哈密尔顿回路的图，并具体指出这两个回路。

5.用哈夫曼算法求带权为2,3,6，8,10,11的最优二元树并计算此最优树的权。

6. 设一棵树T有7片树叶，3个度数为3的结点，其余结点的度数均为4，求T的结点总数。

7.用二元有序完全树表示算术表达式

((ab)c-d)(ef)g(hij)

并分别用波兰符号法和逆波兰符号法表示上述算术表达式。

四、证明题

1．用演绎法证明下述论断的正确性。

PQ,PR,ST,SR,TQ.

2. 设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得

a,bTa,bR且b,aR，证明 T是A上的等价关系。

3.试证明：树是一个偶图。

4．用演绎法证明

x(M(x)F(x)),x(F(x)G(x)),xG(x)xM(x)。

5．P335 27，28 这类题

一．

1 2 3 4 5

B A C

二、

1．(PQR)(PQR)(PQR)(PQR)

2． 3

3． 10，12； 4，10； 没有； 2

4． 单射

5．a,d,d,a,c,e,e,cIA

6．

C B v1v5v8v4v6v7v2v3

7． 7

三、

1．解：（1）设P：天下大雨 Q：小明乘公共汽车上学，则有（2）设Z（x）：x 是整数，E(x)：X是奇数

x(Z(x)E(x))

1012．解：MR100

000123

S(R)1,1,1,2,,1,3,2,1,3,1

3．略

4．略

5．解：

QP

41018

权

W(T)(23)463(81011)296

（

定义10.3.7

）

注：哈夫曼算法见书本（P292）算法10.3.6以及例10.3.9

6．解：设T有x个4度结点，则T的结点总数

n73x10x，边数mn19x

由握手定理d(vi)2m

得

71334x2(9x)

i1n解得

x1

所以结点总数

n73111

7．

（1）＋

÷

－

×

d

c

×

+

f

e

g

－

+

h

÷

a b i

j

（2）算式的波兰符号表示式为

abcdefghij

（书上P295：先根次序遍历算法…

省去括号

） （3）算式的逆波兰符号表示式为

abcdefghij

（同上，用后根遍历，省去括号，规定…

即为…

）

四、

1．证明：

(1)T(2)ST(3)S(4)SR(5)R(6)PR(7)P(8)PQ(9)QP

P

T,(1)(2)

P

T,(3)(4)

P

T,(5)(6)

P

T,(7)(8)

2．证明：

（1）对任意的xA，由R是自反的，得x,xRx,xR，

所以x,xT，即T是自反的。

（2）对任意的x,yA，若x,yT，则

x,yRy,xR

，即有

y,xRx,yR

从而y,xT，即T是对称的。

（3）对任意的x,y,zA，若x,yT,y,zT，则

x,yR,y,xR

且,y,zRz,yR

即x,yR,y,z

且,z,yRy,xR

又因为R是传递的

，

所以

x,zR,z,xR

从而

x,zT，所以T是传递的。

由（1）、（2）、（3）知T是等价关系。

3．试证明：树是一个偶图。（P334:18）

证：设 G= 是一棵树。任选

v0V, 定义 V 的两个子集如下：

V1{v|d(v,v0)为偶数}，

V2V-V1. 现证明V1

中任二结点之间无边存在。若存在一条边 （u,v）E, u,vV1 , 由于树中任意两个结点之间仅存在唯一一条基本通路，故这条基本通路就是他们之间的短程线，设v0到u 的短程线为

v0,v1,v2,...,vk,u，则其长度为k+1,是偶数，因为（u,v）E，所以

v0,v1,v2,...,vk,u，v 是

v0 到 v 的一条通路，且该通路的长度k+2 为奇数，从而它不是基本通路， 故v必与某个vi(i0,1,2,...k)相同，从而

v,vi1,vi2,...,vk,u,v 是G中的一条基本通路，这与G 是树矛盾。

4．用演绎法证明

x(M(x)F(x)),x(F(x)G(x)),xG(x)xM(x)。

证明：

(1)

x(G(x)) P

（2）G(c) ES，(1)

（3）x(F(x)G(x)) P

（4）F(c)G(c) US，（3）

（5）G(c)F(c) T，（4） （6）F(c) T，（5）（2）

（7）x(M(x)F(x)) P

（8）M(c)F(c) US，（7） （6分）

（9）M(c) T，（8）（6） （7分）

（10）x(M(x)) EG，（9）

5．在简单平面图G中，至少有一个度数小于等于5的结点。（P335:27）

或

5‘ 证明小于30条边的简单平面图G中至少有一个度数小于等于4的结点。（P335: 28 ）