去日本留学费用-上海计算机等级考试

复习题

一、填空题（请将每空的正确答案写在答题纸相应位置 处，答在试卷上不得分。每小题
2分，共16分。）
1．谓词公式
xy(P(x ,y)Q(y,z))xR(x,y)
中
x
的辖域是 。
2．命题公式
　(　pq)
的成真赋值为 。
3．在1和1000之间（包括1和1000在内）不能被4和5整除的数有 个。
4．设
R
是定义在集合
A{1,2,3,4}
上的二元关系
R{1,1,1,2,2,3,1,4}
，
则
R
的对称 闭包
s(R)
。
5．
A{1,2,3,4}< br>,
xymin{x,y}
,则代数系统
A,
中的零元是 。
6．具有10个结点的无向完全图的边数= 。
7．一次同余方程
3x1(mod5)
的最小正整数解是 。
8．84与198的最大公约数是 。
二、单项选择题（从下列各题四个备 选答案中选出一个正确答案，并将其代号写在答题
纸相应位置处。答案错选或未选者，该题不得分。每小 题2分，共16分。）
1. 设
F(x)
:
x
是有理数，
G(x)
：
x
能表示成分数。在一阶逻辑中，命题“没有不能表
示成分数的 有理数”可符号化为( )。
A.
x(F(x)G(x))
B.
x(F(x)G(x))

C.
x(F(x)G(x))
D.
x(F(x)G(x))

2. 设个体域是整数集，则下列命题的真值为真的是( )。
A．
yx(xy1)
B．
xy(xy0)

C．
xy(xyy
2
)
D．
yx(xyx
2
)

3. 集合
A{1,2 ,,10}
上的关系
R{x,y|xy10,x,yA}
，则
R
的性质为( )。
A、自反的 B、传递的、对称的
C、对称的 D、反自反的、传递的
4．对自然数集合
N
，下列定义的运算中( )是不可结合的。
A.
abab3
B.
aba2b

C.
abab(mod 3)
D.
abmin{a,b}

5．下列各图中既是欧拉图，又是汉密尔顿图的是( )。

A． B． C． D．

6．对于下列度数序列，可画成简单无向图的是( )。
A．(1，1，1，2，3) B．(1，2，2，3，4，5)
C．(1，2，3，4，5，5) D．(2，3，3，4，5，6)
7. 含有5个结点、3条边的不同构的简单图有( )个。
A. 2 B. 3 C. 4 D. 5
【第 1 页 共 2 页】

8．5的模6逆等于( )。
A．1 B．3 C．4 D．5
三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）
1．求命题公式
(pq)(pr)
的主析取范式和主合取范式。
2． 设
A,R
为偏序集，其中
A{1,2,3,4,6,9,24,54}
，
R
是
A
上的整除关系。（1）画
出
A,R
的 哈斯图；（2）求
A
中的极大元；（3）令
B{4,6,9}
，求
B
的上确界和下确界。
3．求下图1中带权无向图的最小生成树，并求出该最小生成树的权值。
4．求解递推方程：
a
n
7a
n1
12a
n2
0,a
0
4,a
1
6
。
5．有向图D如图2所示，求：（1）D 中
v
1
到
v
3
长度为3的通路有几条？（2）D中
v
1
到
v
1
长度为3的回路有几条？（3）D是哪类连通图？

1
2
1
2
4
5
3
6
3
4
4
v
1
v
4


3

图1 图2
v
2
v
3

6．在通讯中要传输字母
a,b,c,d,e,f,g
，它们出现的频率为：
a:30%,b:20%,c:15%,d:10%,e:10%,f:9%,g:6%
，设计传输上 述字母的最佳二
元前缀码，画出最优树，并求传输100个按上述频率出现的字母所需二进制字个数。
四、证明题（每小题8分，共16分。）
1．设
R
为自然数集
N< br>上的关系，定义
N
上的关系R如下：
x,yRxy
是偶数。
（1）证明
R
为等价关系；
（2）求商集
NR
。
x,yZ,xyxy2
，
Z,
2．设
Z
为整数集合 ，在
Z
上定义二元运算如下：证明：
是群。
五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）
若小张喜欢数学， 则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张
确实喜欢数学，可小李不喜欢物理。 所以，小赵喜欢数学。
【第 2 页 共 2 页】

参考答案

一、填空题 （请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题
2分，共16分。）
1．
P(x,y)Q(y,z)
2．10，11，00 3．600
4．
{1,1,1,2,2,3,1,4,2,1,3,2,4, 1}
5．1
6．45 7．3 8．6
二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题
纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）
1．C 2．C 3．C 4．B 5．C 6．A 7．C 8．D
三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）
1．解：主合取范式为： （5分）
(pq)(pr)
(pq) (pr)
((pq)(rr))((pr)(qq))
(pqr)(pqr)(pqr)(pqr)
(pq r)(pqr)(pqr)
M
4
M
5
M< br>6
主析取范式为： （2分）
(pq)(pr)
m
0
m
1
m
2
m
3
m
7
(pqr)(pqr)(pqr)(pqr)(pq r)
2．解：（1）
A,R
的哈斯图如下图所示。 （3分）
24
54

4
2
6
3
2
9

1

（2）
A
中的极大元是：24，54； ( 2分)
（3）
B
的上确界：无；
B
的下确界：1。 ( 2分)
3．解：所求该图的最小生成树如下图所示。 （5分）
1
2
1
2
3
4

【第 1 页 共 3 页】

该最小生成树的权值之和
W（t）=2+1+1+2+3+4=13 （2分）
4．解：其特 征方程为：
x
2
7x120
，其特征根是：
x
13,x
2
4
（2分）
通解为：
a
nc
1
3
n
c
2
4
n
（2分）
代入初值得到：
c
1
c
2
4,3c
1
4c
2
6

解得：
c
1
10,c
2
6
（2分）
所以，原方程的解为：
a
n
103
n
64
n
。 （1分）
5．解：先求图D的邻接矩阵
A
及
A
2
、
A
3
。

1

1
A

< br>0


1
1
0
0
0
1
1< br>0
0
0


2

2
1
< br>2

，（1分）
A


1
1



0


1
1
1
0
1
2
1
0
1
2


5

4
1

3

,（2分）
A


1
0



0


2
2
2
1
1
3
3
1
2
3

2


（2分）
0


2

(1) D中
v
1
到
v
3
长度为3的通路有3条。 （1分）
(2) D中
v
1
到
v
1
长度为3的回路有5条。 （1分）
(3) D是强连通图。 （1分）
6． 解：按字母顺序，令
p
i
为传输第
i
个字母的频率，
i1 ,2,,7
，则传输100个字母，
各字母出现的频数为
w
i
10 0p
i
，得
w
1
30,w
2
20,w
3
15,w
4
10,w
5
10,w
6
9 ,w
7
6
。将它们按照从小到大
顺序排列，得
691010152030
。 （2分）
以
w
i
为权求最优2叉树如下图所示。
100
60
30
15
15
001
9
0001
30
01
10
100
20
40
20
11
10
101
6

0000

（4分）
传输的前缀码分别为：
a01,b11,c001,d100,e101,f00 01,g0000
。
传100个所需二进制数字个数为：
W(t)=15+30+60+100+40+20=265。 （2分）
四、证明题（每小题8分，共16分。）
1．（1）证明：
xN,
因为
xx2x
，
2xN
且是偶数，于是
x,x R,

因此
R
在
N
上是自反的； （1分）
【第 2 页 共 3 页】

x,yN,
若x,yR,
则
xy
是偶数，即
yx
是偶数，于是y,xR,

因此
R
在
N
上是对称的； （1分）
x,y,zN,
若
x,yR
且
y,zR ,
则
xy2k
1
yz2k
2
,k
1,k
2
Z
，
于是
xz(xy)(yz)2y 2(k
1
k
2
y)
，进而
x,zR,

因此
R
在
N
上是传递的； （2分）
综上所述，
R
是
N
上的等价关系。 （1分）
（2）
N
关于等价关系
R
的所有等价类为
[0]
R
{0,2,4,6,}
和
[1]
R
{1,3, 5,7,}
，
则
NR{[0]
R
,[1]
R
}
。 （3分）

2．证明：显然，
Z
关于是封闭的。 （1分）
对于任意
x,y,zZ
，由于
(xy)z(xy2)z(xy2)z2xyz4
， 而
x(yz)x(yz2)x(yz2)2xyz4
，于是
(xy)zx(yz)
，即满足结合律。 （2分）
xZ
，因为
x2x22x2x
，因此2是
Z
关于的单位元。（2分）
xZ
，由于
4xZ
且
x(4x)x(4x)22(4x)x
，于是
x
关于存在逆元
4x
。 （2分）
所以，
Z,
是群。 （1分）

五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）
解：设简单命题
p：小张喜欢数学。 q：小李喜欢数学。
r：小赵喜欢数学。 s：小李喜欢物理。 （2分）
前提：
p(qr),qs,p,s

结论：
r

（或写为：推理形式为
p(qr),qs,p,sr
） （1分）
证明：
(1)qs
前提引入
(2)s
前提引入
(3)q
（1）（2）拒取式 （2分）
(4)p(qr)
前提引入
(5)p
前提引入
(6)qr
（4）（5）假言推理 （2分）
(7)r
（3）（6）析取三段论 （1分）

【第 3页 共 3 页】